Лемпель-Зив сложность - Lempel-Ziv complexity - Wikipedia
В Лемпель-Зив сложность впервые был представлен в статье О сложности конечных последовательностей (IEEE Trans. On IT-22,1 1976) двумя израильскими учеными-компьютерщиками, Авраам Лемпель и Джейкоб Зив. Эта мера сложности связана с Колмогоровская сложность, но единственная функция, которую он использует, - это рекурсивная копия (то есть неглубокая копия).
Механизм, лежащий в основе этой меры сложности, является отправной точкой для некоторых алгоритмов для сжатие данных без потерь, подобно LZ77, LZ78 и LZW. Несмотря на то, что он основан на элементарном принципе копирования слов, эта мера сложности не является слишком строгой в том смысле, что она удовлетворяет основным качествам, ожидаемым от такой меры: последовательности с определенной регулярностью не имеют слишком большой сложности, а сложность растет по мере увеличения длины и неравномерности последовательности.
Сложность Лемпеля-Зива можно использовать для измерения повторяемости двоичных последовательностей и текста, например текстов песен или прозы.
Принцип
Пусть S - двоичная последовательность длины n, для которой мы должны вычислить сложность Лемпеля-Зива, обозначенную C (S). Последовательность читается слева.
Представьте, что у вас есть ограничивающая линия, которую можно перемещать в последовательности во время расчета. Сначала эта строка устанавливается сразу после первого символа, в начале последовательности. Эта начальная позиция называется позицией 1, откуда мы должны переместить ее в позицию 2, которая считается начальной позицией для следующего шага (и так далее). Мы должны переместить разделитель (начиная с позиции 1) как можно дальше вправо, чтобы подслово между позицией 1 и позицией разделителя было словом последовательности, которая начинается перед позицией 1 разделителя.
Как только разделитель устанавливается в положение, в котором это условие не выполняется, мы останавливаемся, перемещаем разделитель в это положение и начинаем снова, отмечая эту позицию как новую исходную позицию (то есть позицию 1). Продолжайте повторять до конца последовательности. Сложность Лемпеля-Зива соответствует количеству итераций, необходимых для завершения этой процедуры.
Иными словами, сложность Лемпеля-Зива - это количество различных подстрок (или подслов), встречающихся при просмотре двоичной последовательности как потока (слева направо).
Формальные объяснения
Метод, предложенный Лемпелем и Зивом, использует три понятия: воспроизводимость, воспроизводимость и исчерпывающая история последовательности, которые мы определили здесь.
Обозначения
Пусть S будет двоичной последовательностью длины n (т.е. n символов, принимающих значение 0 или 1). Пусть S (i, j), где , быть подсловом S от индекса i до индекса j (если j
Воспроизводимость и воспроизводимость

С одной стороны, последовательность S длины n называется воспроизводимой из своего префикса S (1, j), когда S (j + 1, n) является подсловом S (1, n-1). Это обозначается S (1, j) → S.
Другими словами, S воспроизводится из своего префикса S (1, j), если остальная часть последовательности, S (j + 1, n), является не чем иным, как копией другого подслова (начиная с индекса i
Чтобы доказать, что последовательность S может быть воспроизведена одним из ее префиксов S (1, j), вы должны показать, что:

С другой стороны, воспроизводимость определяется из воспроизводимости: последовательность S получается из своего префикса S (1, j), если S (1, n-1) воспроизводится из S (1, j). Это обозначается S (1, j) ⇒S. Другими словами, S (j + 1, n-1) должен быть копией другого подслова S (1, n-2). Последний символ S может быть новым символом (но не может быть), что, возможно, приведет к созданию нового подслова (отсюда и термин «производимость»).

Исчерпывающая история и сложность
Из определения воспроизводимости пустая строка Λ = S (1,0) ⇒ S (1,1). Таким образом, с помощью рекурсивного производственного процесса на шаге i мы имеем S (1, hi) ⇒ S (1, hi + 1), поэтому мы можем построить S из его префиксов. И поскольку S (1, i) ⇒ S (1, i + 1) (при hi + 1 = hi + 1) всегда истинно, этот производственный процесс S занимает не более n = l (S) шагов. Пусть m, , - количество шагов, необходимых для этого процесса продукта S. S можно записать в разложенной форме, называемой историей S и обозначаемой H (S), определяемой следующим образом:

Компонент S, Hi (S), называется исчерпывающим, если S (1, hi) - самая длинная последовательность, произведенная S (1, hi-1) (т. Е. S (1, hi-1) ⇒ S ( 1, hi)), но так, что S (1, hi-1) не производит S (1, hi) (обозначено). Индекс p, который позволяет иметь самую длинную продукцию, называется указателем.
История S называется исчерпывающей, если исчерпывающими являются все ее компоненты, кроме, возможно, последней. Из определения можно показать, что любая последовательность S имеет только одну исчерпывающую историю, и это история с наименьшим числом компонентов из всех возможных историй S. Наконец, количество компонентов этой уникальной исчерпывающей истории S называется сложностью Лемпеля-Зива группы S.
Алгоритм
Надеюсь, существует очень эффективный метод вычисления этой сложности с помощью линейного числа операций ( за длина последовательности S).
Формальное описание этого метода дается следующим алгоритм:
- i = p - 1, p - указатель (см. выше)
- u - длина текущего префикса
- v - длина текущего компонента для текущего указателя p
- vmax - окончательная длина, используемая для текущего компонента (наибольшая из всех возможных указателей p)
- и C - сложность Лемпеля-Зива, увеличиваемая итеративно.
// S - двоичная последовательность размера nя := 0C := 1ты := 1v := 1vmax := vпока ты + v <= п делать если S[я + v] = S[ты + v] тогда v := v + 1 еще vmax := Максимум(v, vmax) я := я + 1 если я = ты тогда // все указатели обработаны C := C + 1 ты := ты + vmax v := 1 я := 0 vmax := v еще v := 1 конец если конец есликонец покаесли v != 1 тогда C := C+1конец если
Примечания и ссылки
Библиография
- Абрахам Лемпель и Джейкоб Зив, «О сложности конечных последовательностей», IEEE Trans. по теории информации, январь 1976 г., стр. 75–81, т. 22, № 1
Заявление
- «Поп-тексты становятся все более повторяющимися? », Колин Моррис, это сообщение в блоге, объясняющее, как использовать сложность Лемпеля-Зива для измерения повторяемости текстов песен. (с доступным исходным кодом).