![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
Известно, что алгоритм Лемпеля-Зива обладает свойством универсальности по сравнению с классом всех конечных автоматов: любую достаточно длинную последовательность символов, принимающих конечное число значений, алгоритм Лемпеля-Зива может сжать почти настолько же, насколько это можно сделать при помощи любого конечного автомата (включая любые КА, которые можно построить, зная последовательность наперед). Недавно появилась статья, в которой утверждается, что алгоритм Лемпеля-Зива не универсален по отношению к классу магазинных автоматов: авторы статьи построили последовательность, которую алгоритм Лемпеля-Зива практически не может сжать, но которая сжимается по крайней мере наполовину с помощью магазинного автомата.
no subject
Date: 2007-04-19 08:54 pm (UTC)no subject
Date: 2007-04-19 08:58 pm (UTC)no subject
Date: 2007-04-19 10:30 pm (UTC)no subject
Date: 2007-04-19 11:14 pm (UTC)Например,
abcdcba обычным LZ совсем не сжимается, а модифицированным - abcd(1,-3). Здесь первое число в паре - отступ назад, а второе - длина. Отрицательные числа используются для "задом наперед".
no subject
Date: 2007-04-20 12:49 am (UTC)no subject
Date: 2007-04-20 01:05 am (UTC)no subject
Date: 2007-04-22 04:24 am (UTC)no subject
Date: 2007-04-22 01:53 am (UTC)