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