сжатие строк

← →
картман © (2015-10-29 23:30) [0]

Всем привет!
Есть много строк:

мана
мама
машина

нужно сделать что-то вроде:
Array[] a = ("ма","на","ши");
тогда строки будут представлены в виде:
мана = [0,1];
мама = [0,0];
машина = [0,2,1];

чтобы найденные "кусочки" способствовали максимальному(или близко к нему) сжатию?

← →
Pavia © (2015-10-29 23:37) [1]

Суффиксное дерево.

← →
Sha © (2015-10-29 23:48) [2]

LZW

← →
картман © (2015-10-29 23:48) [3]

> Pavia © (29.10.15 23:37) [1]
>
> Суффиксное дерево.

искать умучаюсь

← →
Sha © (2015-10-29 23:58) [4]

так тебе сжать или искать?

← →
картман © (2015-10-30 00:12) [5]

в смысле, искать оптимальные кусочки для сжатия. А потом да, потом искать.
Не понял LZW((

1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы W первым символом сообщения.
2.Найти в словаре строку W наибольшей длины, которая совпадает с последними принятыми символами.
3.Считать очередной символ K из кодируемого сообщения.
4.Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для W, иначе.
5.Если фраза WK уже есть в словаре, присвоить входной фразе W значение WK и перейти к Шагу 3, иначе выдать код W, добавить WK в словарь, присвоить входной фразе W значение K и перейти к Шагу 3.
6.Конец.

← →
картман © (2015-10-30 00:20) [6]

лучше так описать задачу:
нужно сделать поиск по словарю, каждое слово состоит из приставки, корня, суфикса и окончания. Любая из частей может быть опущена. Ну и в моем случае все эти части слов могут быть одним и тем же, т.е. храниться в одном списке. Как получить эти приставки-окончания для минимизации словаря в памяти?

← →
Sha © (2015-10-30 01:01) [7]

В [5] описано нечто, похожее на алгоритм сжатия данных LZW.
Для [6] проще всего хешировать.
Для хранения в памяти слов естественного языка со всеми словоформами довольно эффективно и проще всего реализуется дельта-кодирование расстояний между словами. Например, древовидная 3-х уровневая структура блоков, в которых хранится начальное слово и расстояния до каждого следующего слова в блоке. Как правило, на слово достаточно 1-2 байта.

← →
картман © (2015-10-30 01:45) [8]

> Sha © (30.10.15 01:01) [7]
>
> В [5] описано нечто, похожее на алгоритм сжатия данных LZW.
>

да, разобрался по другому описанию.

> Для хранения в памяти слов естественного языка со всеми
> словоформами

имена собственные, много, со словоформами

> Например, древовидная 3-х уровневая структура блоков

эээ... можно подробнее?

> нужно сделать поиск по словарю, каждое слово состоит из
> приставки, корня, суфикса и окончания. Любая из частей может
> быть опущена. Ну и в моем случае все эти части слов могут
> быть одним и тем же, т.е. храниться в одном списке. Как
> получить эти приставки-окончания для минимизации словаря
> в памяти?

Это трудная задача. Читай словарь Зализняка там описано.
Гораздо проще использовать псевдо суффиксы.

Таки не понял чем суффиксное дерево не устроило?

> Например, древовидная 3-х уровневая структура блоков, в
> которых хранится начальное слово и расстояния до каждого
> следующего слова в блоке. Как правило, на слово достаточно
> 1-2 байта.

хотелось бы подробнее.

> имена собственные, много, со словоформами

Это мало )

> хотелось бы подробнее

Идея в том, что в естественном языке с большим количеством словоформ они (формы) лежат достаточно плотно. Т.е. если ввести некую нумерацию форм, рассматривая буквы как цифры в N-ричной системе счисления, то для упорядоченных по алфавиту форм разница в весе между соседними формами обычно будет небольшой. Конечно, иногда будут скачки в районе длинных слов типа "машиностроительный", но их относительная доля невелика. Таким образом, вместо хранения слов можно хранить эти самые дельты - числа переменной длины. Все они собираются в блоки. Каждый блок имеет имя, совпадающее с первым словом в блоке. Если блоков слишком много, добавляем еще один уровень иерархии. Для оценки: примерно 400..500k памяти - и уже становится очень трудно найти слово, которого нет в словаре.

> Таки не понял чем суффиксное дерево не устроило?

ну вот получил я суффиксы. Нашел наибольшие. А как узнать, что их использование даст наибольшую или близкую к ней экономию памяти? Берем "часть1", вырезаем ее из всех слов, - строим другое дерево, и еще, и еще?.. как-то коряво получается.

> Sha © (30.10.15 09:41) [10]

ясно, спасибо.

> А как узнать, что их использование даст наибольшую или близкую
> к ней экономию памяти

2х проходность. на первом проходе оценку весов, на втором непосредственное сжатие или как там нужно?)

сжатие строк Найти похожие ветки