nyaload

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

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

Entries by tag: text

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


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

Tags: ,

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

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

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

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

(no subject)
nyaload
_winnie
Восьмерята и Десятибристы.

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

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

суффиксов
а суффиксов
в
вка суффиксов
иксов
ировка суффиксов
ка суффиксов
ксов
ов
овка суффиксов
ортировка суффиксов
ровка суффиксов
ртировка суффиксов
сов
сортировка суффиксов
суффиксов
тировка суффиксов
уффиксов
фиксов
ффиксов
Tags: ,

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

hangyl unicode
Tags:

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

UTF-8 grep hack
nyaload
_winnie
echo привет | LC_ALL=C grep $'[^\x80-\xbf][\x80-\xbf]*' -o
Tags: ,

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

Забавно, яндекс умеет искать по этим бредовым значкам, в отличие от гугла и бинга: Read more...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 )
Tags: ,

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

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

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

?

Log in