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