Tags: text

nyaload

Чем дальше в лес, тем толще тоньше

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


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

nyaload

и/или

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

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

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

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

(no subject)

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

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

suffix array sort

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

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

Хангыль

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

hangyl unicode
nyaload

fuzzy search grep своими руками

Если нужно провести неточный поиск слова по большому файлу (напр. по дампу википедии), то самое простое - это сгенерить регулярное выражение со всеми нужными вариантами опечаток, и сунуть в хорошую библиотеку регулярных выражений ( стандартный 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
nyaload

👯

По юникод-символам 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 )
nyaload

fast utf-8 validation

Наткнулся на простую и быструю библиотеку декодирования 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 - он умеет детектить суррогатные пары, но что с ними делать - оставляет решать пользователю).

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

*-gramms, — сказал князь Андрей.

Придумал тупой алгорим, хорошо извлекающий из куска текста его частые крупные элементы. Компромисс "частый 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)). Скорее всего после такой минимизации в словаре будут осмысленные кусочки.