Eugene D. Shelwien
задачки - #1

1. Сжатие словаря

 - Зная модель, использованную для генерации данных (с применением гене-
ратора случайных чисел), можно создать на ее основе оптимальный компрес-
сор для таких данных, который будет сжимать их в ~ количество информа-
ции, полученное от ГСЧ.

 - Есть мнение, что для "генерации" текста используется отнюдь не сим-
вольная марковская модель. В этом случае "генератор" обычно оперирует,
как минимум, словами.
Т.о., простейшая аппроксимация будет выглядеть примерно так:

 loop {
  p = randomreal();
  for(
    i=0, low=0;
    prob = Word[i].Probability, low+prob>p;
    i++, low+=prob
  );
  Write( Word[i].Text );
  Write( " " );
 }

Казалось бы, модель для таких данных ничего не стоит построить - взять
арифметик нулевого порядка и считать слова символами. Однако не все так
просто.
   Разных слов бывает довольно много и адаптивно определить их вероят-
ности не слишком легко - для сбора устойчивой статистики требуется го-
раздо больше данных.
   Мало того, ведь неизвестен и сам набор слов! Т.е. при адаптивном мо-
делировании придется работать, фактически, со множеством _всех_ возмож-
ных слов, надеясь, что у "лишних" слов вероятности быстро станут очень
близки к нулевым. Так что имеет смысл, для начала, рассмотреть вариант с
созданием статического словаря/таблицы вероятностей.
   Сжатие таблиц частот мы пока рассматривать не будем (на самом деле, у
меня просто есть для них хорошая модель). А вот вопрос о сжатии словарей
- таблиц слов в лексикографическом порядке - представляет определенный
интерес. Причем не только с т.з. создания улучшенной модели текста, а и
сам по себе - учитывая наличие таких словарей как в тестовом наборе Вер-
нера Бергманса, так и в составе некоторых компрессоров
(entropy,compressia,durilca 0.0)

   А сжать словарь, оказывается, совсем не так просто, как текст вообще.
Универсальные компрессоры сильно промахиваются, пытаясь кодировать сле-
дующее слово в контексте суффикса предыдущего:

english.dic 4,067,439 // (354951 слов) с сайта Бергманс
english.pmm   531,415 // ppmonstr vIr1: -o16 -m100
// а теперь заменим разделитель слов (CR+LF) на
english.p15   456,551 // 15 LF'ов
english.p16   456,493 // 16 LF'ов
english.p17   457,368 // 17 LF'ов

Вот, в p15 в контексте префикса еще "виден" последний символ прошлого
суффикса, а в p17 в контексте из 16 LF появляется лишний символ (LF же)
и портит все дело.
   К сожалению, на кодирование всех этих "лишних" символов тоже есть
накладные расходы, так что вставлять 32 символа-разделителя и кодировать
с order-32 будет невыгодно.

   Есть и еще один момент, который можно "побороть" обработкой данных -
"непонимание" компрессором того факта, что слова отсортированы и префик-
сы соседних слов часто совпадают.
   Он просто не успевает "обучиться" ожидать после разделителя опреде-
ленный префикс, как тот уже меняется.
   Однако, можно ему помочь, обработав словарь таким образом, чтобы 
перед "остатком" каждого слова записывалась длина совпадения с
предыдущим. Получаем:

english.pmm   426,292 // ppmonstr -o16
english.pmm   426,006 // ppmonstr -o32
english.pmm   426,021 // ppmonstr -o128

Интересно, что "длинные" разделители между словами уже можно не писать -
одинаковых префиксов, которые компрессор пытался моделировать в кон-
тексте предыдущих суффиксов, больше нет.
   Hе сказать, чтобы я сильно старался, но дальше усовершенствовать
препроцессинг мне не удалось. Конечно же, на самом деле "универсальные"
модели просто не лучший выбор для таких данных. Ведь не может здесь в
любом контексте появиться любой символ.
   Фактически, правильнее кодировать _множество_ символов, которые могут
возникнуть в данном контексте. Однако если написать препроцессор, кото-
рый будет трансформировать файл соответствующим образом (например, так:

1+2+3+4+5+6+7+8+9+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+w+x+y+z+
0+s+
8+t+
0.
h.
[...]

В первой строке - варианты первого символа слова, затем вторые символы
"слов" с префиксом "1" и т.п. "+" обозначает, что есть слова с символами
в следующей позиции, "." - что нет.),
то окажется, что он сжимается хуже текущего "рекорда" - в 433k. И это
неудивительно, т.к. "универсальная" модель считает множество
"e+k+l+m+n+" более похожим на "k+l+m+n+", чем на "e+k+m+n+". Вдобавок
часто повторяющиеся суффиксы тут (в лучшем случае) выстроены в столбик,
что не способствует сжатию (введение еще одного спецсимвола для записи
"детерминированных" суффиксов в строку тоже не способствует).
   Таким образом, если сделать специализированный компрессор, преобра-
зующий список слов в дерево и эффективно кодирующий затем множества сим-
волов, то, возможно, и удастся улучшить нынешний результат. Проблема,
однако, в том, что и дерево представляется не самой удобной структурой
для таких данных.
   Пример:

congregable     aggregable    segregable
congregant      aggregant     segregant
congregate      aggregate     segregate
                aggregateness segregateness
congregated     aggregated    segregated
congregates     aggregates    segregates
congregating    aggregating   segregating
congregation    aggregation   segregation
congregational  aggregational segregational
congregationist               segregationist
congregations   aggregations
congregative    aggregative   segregative
congregator     aggregator    segregator

Список из этих слов явно эффективнее было бы сжимать, если поместить
префиксы _после_ суффиксов, а уж затем построить дерево.
Hо и это решение - не идеал, т.к. слова, бывает, состоят и из большего
числа морфем. Hасчет оптимальности моделирования множеств именно симво-
лов тоже есть сомнения.

В общем, задача: придумать действительно эффективную модель для словаря.
Согласно "первой аксиоме", для этого не помешала бы модель генерации
такого словаря.