кто о чем, а я о сжатии последовательностей

[ded_maxim]

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

Comments

[spamsink.livejournal.com]

Ну да, а если LZ модифицировать так, чтобы он мог ссылаться и на строки задом наперед?

Например,

abcdcba обычным LZ совсем не сжимается, а модифицированным - abcd(1,-3). Здесь первое число в паре - отступ назад, а второе - длина. Отрицательные числа используются для "задом наперед".

[ded-maxim.livejournal.com]

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

[spamsink.livejournal.com]

Да кого бы сейчас LZ интересовал, особенно для таких источников, для которых описанное улучшение будет существенным? Хардверный LZ обычно вообще не 77, а 78 (LZW), а относительно нового софтвера, использующего LZ77, я и не назову...

[ded-maxim.livejournal.com]

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