Сложность Лемпеля — Зива

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Сложность Лемпеля-Зива (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-сложность Лемпеля-Зива, увеличивающаяся итеративно.
 1 i := 0
 2 C := 0
 3 u := 0
 4 v := 0
 5 vmax := vmax
 6 while u + v <= n do
 7     if S[i + v] = S[u + v] then 
 8         v := v + 1
 9     else 
10         vmax := max(v, vmax)
11         i := i + 1
12         if i = u then 
13             C := C + 1
14             u := u + vmax
15             v := 1
16             i := 0
17             vmax := vmax
18         else 
19             v := 1
20         end if
21     end if
22 end while
23 if v != 1 then
24     C := C + 1
25 end si

Библиография[править | править код]

  • 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