Сложность Лемпеля-Зива (Lempel-Ziv Complexity) - алгоритм для вычисления максимальной Колмогоровской сложности, который может быть исполнен на любом языке программирования, поддерживающем операции копирования и вставки в строку. Несмотря на простоту данного алгоритма, он является очень мощным и быстрым.

Сложность Лемпеля-Зива была впервые представлена в статье под названием On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976) двумя израильскими учеными, Авраамом Лемпелем и Яаковом Зивом. Данная мера сложности связана с Колмогоровской сложностью, но единственная функция, которую она использует - рекурсивная копия.

Механизм, лежащий в основе данного измерения сложности, является отправной точкой для некоторых алгоритмов сжатия без потерь, таких как LZ77, LZ78 и LZW. Несмотря на то, что она основана на элементарном принципе копирования слов, эта мера сложности не слишком ограничительна в том смысле, что она удовлетворяет основным качествам, ожидаемым такой мерой: последовательности с определенной регулярностью не имеют слишком большой сложности, и сложность возрастает по мере увеличения длины и неоднородности.

Сложность Лемпеля-Зива можно использовать для измерения повторяемости бинарных последовательностей и текста, например, текстов песен.

Принцип вычисления Пусть S - двоичная последовательность длины n, для которой мы хотим вычислить сложность Лемпеля-Зива, обозначенную как C(S). Последовательность рассматривается слева направо.

Представим, что у нас имеется разделяющая линия, которую мы можем перемещать в двоичной последовательности по мере вычисления. Вначале эта линия устанавливается сразу после первого символа, в начале последовательности. Обозначим данную позицию - позицией 1, откуда мы должны переместить ее в позицию 2, которая считается начальной позицией для следующего шага, и так далее. Мы должны переместить разделитель (начиная с позиции 1) еще дальше вправо, чтобы слово между позицией 1 и позицией разделителя было подсловом последовательности, которая начинается перед позицией 1 разделителя.

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

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

Математическое объяснение

Обозначения Обозначим S, как двоичную последовательность длины n. Пусть S (i, j) с будет подпоследовательностью S с началом i и концом j (если j <i , S (i, j) - пустая строка). Длина n в S обозначена как l(S), а последовательность Q называется фиксированным префиксом S, если:

Воспроизводимость и производительность С одной стороны, последовательность 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 < j +1) из S (1, n-1).

Чтобы доказать, что последовательность 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, ) ⇒ S (1, +1), поэтому мы можем построить S из его префиксов. И так как S (1, i) ⇒ S (1, i+1) (с +1 = +1) всегда верно, этот процесс производства S занимает не более n = l(S) шагов. Пусть m, , будет количеством необходимых шагов для этого процесса S. S может быть записана в разложенном виде, называемом историей S, и обозначена H(S), определяемая как:

называется компонентом H(S).

Компонент S, (S), называется исчерпывающим, если S(1, ) - самая длинная последовательность, создаваемая S (1,-1) (т. e. S (1, -1) ⇒ S(1, )) но так, чтобы S (1, -1) не создавал S (1, ). T.е: Индекс p, который позволяет иметь самую длинную продукцию, называется указателем.

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

Алгоритм Для вычисления данной сложности существует эффективный алгоритм за линейное количество операций

Формальное описание этого метода задается следующим алгоритмом:

i = p-1, p-указатель (см. выше) u-длина текущего префикса

v-длина текущего компонента для текущего указателя p vmax-конечная длина, используемая для текущего компонента (наибольшая из всех возможных указателей p)

C-сложность Лемпеля-Зива, увеличивающаяся итеративно. i := 0 C := 0 u := 0 v := 0 vmax := 0 while u + v <= n do if S[i + v] = S[u + v] then v := v + 1 else vmax := max(v, vmax) i := i + 1 v := 1 if i = u then C := C + 1 u := u + vmax i := 0 end if end if end while if v != 1 then C := C + 1 end ifКод на JavaScript (Сложность выше линейной)function isSubArray(subArr, mainArr) { var length = mainArr.length - subArr.length; for(var i = 0; i <= length; ++i) { for(var j = 0; j < subArr.length; ++j) { if(subArr[j] !== mainArr[i + j]) break; if(j + 1 === subArr.length) return true;

return false; } function C(arr) { var start = 0; var ptr = 1; var steps = 0;

while(ptr <= arr.length) { while(ptr <= arr.length && isSubArray(arr.slice(start, ptr), arr.slice(0, start))) ++ptr; start = ptr; ++ptr; ++steps;

return steps; }

Библиография

Abraham Lempel and Jacob Ziv, « On the Complexity of Finite Sequences », IEEE Trans. on Information Theory, January 1976, p. 75–81, vol. 22, n°1

Категория:Алгоритмическая теория информации