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

[ded_maxim]

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

Comments

[ygam.livejournal.com]

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

[juan-gandhi.livejournal.com]

Wow! How obvious, and how refreshing!

[spamsink.livejournal.com]

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

Например,

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

[occuserpens.livejournal.com]

wow!