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

[ded_maxim]

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

Comments

[ygam.livejournal.com]

Забавно. Ты об этом узнал из какого-то блога?

[ded-maxim.livejournal.com]

Нет, просто я ежедневно слежу за постингами в http://arxiv.org/list/cs.IT/recent и http://arxiv.org/list/cs.LG/recent. Должен же я интересоваться, чем мои коллеги занимаются.

[juan-gandhi.livejournal.com]

Wow! How obvious, and how refreshing!

[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 важен концептуально: идея вероятностного моделирования, в основе которой лежит контекстный парсинг последовательностей, распространяется на такие задачи, как оптимальное управление.

[occuserpens.livejournal.com]

wow!