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

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

Т.о., простейшая аппроксимация будет выглядеть примерно так:

 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

Интересно, что "длинные" разделители между словами уже можно не писать - одинаковых префиксов, которые компрессор пытался моделировать в контексте предыдущих суффиксов, больше нет.

Не сказать, чтобы я сильно старался, но дальше усовершенствовать препроцессинг мне не удалось. Конечно же, на самом деле "универсальные" модели просто не лучший выбор для таких данных. Ведь не может здесь в любом контексте появиться любой символ.

Фактически, правильнее кодировать _множество_ символов, которые могут возникнуть в данном контексте. Однако если написать препроцессор, который будет трансформировать файл соответствующим образом (например, так:

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

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

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