Журнал Пушыстого

Сегодня осознал удивительное и новое для меня: добавление нового параметра для предсказания в линейную модель - может поменять смысл старых параметров на _противоположный_.


Например, хотим для красных и зеленых объектов предсказать их цвет, если известны только их координаты x, y. Если известен только x, то работает логика "чем больше x, тем скорее всего объект красный". Если же известны и x, и y, то смысл параметра x меняется наоборот: "чем больше x, тем скорее всего объект НЕ красный". НУ КАК ТАК

Осознал, что союз 'и' может означать как 'и', так и 'или':

А) Холодное и огнестрельное оружие, охотник на птиц и зверей
Б) Длинная и сухая палка, любитель молодых и красивых

В каких-то контекстах - понять значение невозможно: "Запрещено красное и большое".

В каком-то французском фильме обыгрывалась эта неоднозначность:
Полицейский (негр) и его помощник (араб) входят в клуб, и натыкаются на охранника-вышибалу.
Вышибала: Неграм и арабам вход воспрещен!
Полицейский-негр: А я не араб!
Полицейский-араб: А я не негр!
Затем парой ударов отправляют его в нокаут и проходят мимо него.

Восьмерята и Десятибристы.

Негабрь, нуллабрь, унябрь (солябрь), дуабрь, трябрь, квадрабрь, квинтябрь (пентабрь), сексабрь, сентябрь, октябрь, ноябрь, декабрь.

Как следует разобрался в алгоритме сортировки суффиксов. Написал более-менее читабельную и не сильно тормозящую функцию (легко переписывается на C). https://gist.github.com/dobrokot/ed1ae766ee6d90e50540

суффиксов
а суффиксов
в
вка суффиксов
иксов
ировка суффиксов
ка суффиксов
ксов
ов
овка суффиксов
ортировка суффиксов
ровка суффиксов
ртировка суффиксов
сов
сортировка суффиксов
суффиксов
тировка суффиксов
уффиксов
фиксов
ффиксов

Сегодня благодаря муару в картинке из поста akuklev я узнал, что 11'172 = 19*21*28 корейских иероглифов в unicode с позиции U+AC00 по U+D7A3 - имеют регулярную структуру из 19+21 элементов (из 19*19+19+1 вариантов для пары yz используется 28).

Если нужно провести неточный поиск слова по большому файлу (напр. по дампу википедии), то самое простое - это сгенерить регулярное выражение со всеми нужными вариантами опечаток, и сунуть в хорошую библиотеку регулярных выражений ( стандартный grep - OK, PCRE/python.re - NOT OK ).

Например, слово WORD превращается в регулярку:
.ORD|ORD|W.RD|WRD|W.ORD|WO.D|WOD|WO.RD|WOR.|WOR|WOR.D

Если нужен поиск по UTF-8 файлу - то можно ускорить поиск, используя вместо точки и UTF8-локали - "[^\x80-\xbf][\x80-\xbf]*" и C-локаль.

Если нужен case-insensitive поиск - то при генерации регулярки вместо СЛОВО писать (С|с)(Л|л)(О|о)(В|в)(О|о). И вы сами определяете, что вы хотите - [iI] или [Iiı], ẞ или (ß|ẞ|SS|S-S|ss|SSS|SZ), ё или (е|ё).

Пример генератора, который генерирует регулярку для всех вариантов на расстоянии 1 по Левенштейну: https://gist.github.com/dobrokot/6150988

echo привет | LC_ALL=C grep $'[^\x80-\xbf][\x80-\xbf]*' -o

По юникод-символам JAPANESE OGRE, LOVE HOTEL, JAPANESE GOBLIN, SILHOUETTE OF JAPAN (!), TOKYO TOWER, WOMAN WITH BUNNY EAR и тд. четко становится понятно, из какой страны те странные люди, кто добавляет в юникод упячку вроде PILE OF POO 💩 или бред FISH CAKE WITH SWIRL DESIGN 🍥

Забавно, яндекс умеет искать по этим бредовым значкам, в отличие от гугла и бинга: ( Collapse )

Сиволов в «miscellaneous symbols and pictographs» относящихся явно к японской культуре больше, чем к остальным странам вместе взятым, и то, "француская жаренная картошка FRENCH FRIES" тут скорее всего только благодаря меню японских кафешек. updated: Спасибо esyr, стало понятно, что эти символы - это результат стандартизации SMS-смайликов японских операторов

U+1F46F		👯	WOMAN WITH BUNNY EARS
U+1F3EE		🏮	IZAKAYA LANTERN
U+1F3E9		🏩	LOVE HOTEL
U+1F458		👘	KIMONO
U+1F5FC		🗼	TOKYO TOWER
U+1F5FE		🗾	SILHOUETTE OF JAPAN
U+1F5FF		🗿	MOYAI
U+1F4A2		💢	ANGER SYMBOL
U+1F4A9		💩	PILE OF POO
U+1F4B1		💱	CURRENCY EXCHANGE
U+1F47A		👺	JAPANESE GOBLIN
U+1F479		👹	JAPANESE OGRE

( источник таблицы: http://www.charbase.com/block/miscellaneous-symbols-and-pictographs )

Наткнулся на простую и быструю библиотеку декодирования UTF-8, кроссплатформенную, с валидацией всех возможных ошибок в utf-8 (overlong, surrogate pairs) - http://bjoern.hoehrmann.de/utf-8/decoder/dfa , без бранчинга ( «?:» заменяется на стандатный битхак mask=((int)x-1)>>31), легко векторизуется до чтения dword/qword. Декодирование рассматривается как конечный автомат, конечный автомат загонятся в таблицу [char x state] →state

Протестировал брутфорсом, работает эквивалентно iconv (в плюс iconv - он умеет детектить суррогатные пары, но что с ними делать - оставляет решать пользователю).

Не законом Мура единым ускоряем софт

Придумал тупой алгорим, хорошо извлекающий из куска текста его частые крупные элементы. Компромисс "частый vs крупный" можно подкручивать, соль — в том, что бы не учитывать мелкие куски, которые часть крупных.

Он правда тупой-тупой и жадный, результат средненький, лингвисты и люди пишущие архиваторы будут наверное смеяться, но тем не менее работает гораздо лучше, чем «отсортировать все n-граммы». Ну какой смысл в том, что бы знать что 1-грамма "ь" встречается в «Войне и мире» чаще чем "ться", "Пьер", "опять" и "сказал князь Андрей". А этот алгоритм — выводит ближе к топу осмысленные куски текста: морфему "ться", слова "Пьер", "опять" и даже целые словосочетания со знаками препинания (", – сказал князь Андрей.")

Итак:

КУСКИ = []

for L := 50 to 1:
    for любой КУСОК длины L, который встречается в тексте K раз и K >= 2:
		выкинуть из текста вхождения этого куска
		ЭКОНОМИЯ_БУКВ = (K-1)*L #нужны твики для маленьких К
		добавить в КУСКИ пару (ЭКОНОМИЯ_БУКВ, КУСОК)
		
напечатать пары из списка КУСКИ, отсортированный по (ЭКОНОМИЯ БУКВ).

Алгоритм жует бинарники, сишные исходники. Ему пофиг на кодировку UTF-8 или urlencode, он сам выводит как из байтов составляются буквы. Правда, жадноват и часто ошибается, захватывая в кусок популярные байты D0 и D1 в UTF-8 и % в urlencode. Надо как-то избегать приклеивания к длинному куску популярных коротких n-грамм ( см. ещё пример такого приклеивания - http://dobrokot.ru/pics/i2013-03-02__20-01-14_8kb.png ). Немножко борется изменением константы 2 в K>=2.

И тем более алгоритм выше наших сомнений «как делить на слова URLы и китайские тексты».

Любопытно, может есть что-то более хорошо работающее чем этот велосипед, и не слишком сложнее (updated: Unsupervised Morpheme Segmentation)

Сформулировать формальную задачу можно так: составить словарь «кусков» текста и переписать текст, заменяя куски текста на коды кусков, так что бы минизировать общий размер словаря и текста. Код — Хаффмана, или фиксированный log2(кол-во кусков) битов, или без конкретных кодов считать его длину как (-Log2(p)). Скорее всего после такой минимизации в словаре будут осмысленные кусочки.