?

Log in

No account? Create an account
nyaload

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

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

Previous Entry Share Next Entry
*-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: ,

  • 1
прикольно, да

Сделать массив указателей на все байты текста
Отсортировать его по str(i)cmp
???
Вроде должен получаться profit

Да, такая оптимизация напрашивается

Можно даже погулить библиотеки suffix sort, что бы сразу получить быстро работающий вариант

В итоге какой-то BWT transform получается :)

Вряд ли, не всё BWT, что использует массив суффиксов :)

Прямо в лоб не получися вот эта часть - "выкинуть из текста вхождения этого куска".

Если "выкинуть", например затерев нулями - то нарушится сортированность.
Например, была такая сортировка:
ZAKX...
ZAKY...
ZAKY...
ZAKZ...

Удаляем кусок AKY, от этого нарушается группировка ZA:
ZAKX...
Z***...
Z***...
ZAKZ...



Edited at 2013-03-02 06:51 pm (UTC)

А так это не реализация вашего алгоритма, а скорее подход к исходной задаче "найти частые n-граммы и отсортировать их каким-то разумным образом". Потом, по идее, можно посчитать длину наибольшего совместного префикса у пар соседних строк в отсортированном массиве, частые n-граммы - это длинные интервалы больших чисел будут, а там уже фильтровать-сортировать найденное как-то.

Разве здесь не ZAKY удалять нужно?

1) Да, пример не совсем удачный. Ок, будем удалять AKY123:
AKY123..
AKY123..
AKY123..
ZAKX....
ZAKY123.
ZAKY123.
ZAKZ....
-------------------------
******..
******..
******..
ZAKX....
Z******.
Z******.
ZAKZ....


2) Возможно, всё равно можно использовать такой массив суффиксов, просто пропуская строки, где для текущего L есть * в первых L символах

Edited at 2013-03-03 11:31 am (UTC)

  • 1