Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.01.2022


29.12.2021


09.12.2021


09.12.2021


08.11.2021





Яндекс.Метрика





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

14.04.2022

Сложность Лемпеля-Зива (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) с 1 ≤ i , j ≤ n {displaystyle {displaystyle 1leq i,jleq n}} будет подпоследовательностью S с началом i и концом j (если j <i , S (i, j) - пустая строка). Длина n в S обозначена как l(S), а последовательность Q называется фиксированным префиксом S, если:

∃ j < l(S), т.ч. S(1,j) = Q . {displaystyle {displaystyle exists j<{ ext{l(S), т.ч. S(1,j) = Q .}}}}

Воспроизводимость и производительность

С одной стороны, последовательность 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), необходимо показать, что:

∃ p ≤ j ,  т.ч.  S ( j + 1 , n ) = S ( p , l ( S ( j + 1 , n ) ) + p − 1 ) {displaystyle {displaystyle exists pleq j,{ ext{ т.ч. }}S(j+1,n)=S(p,l(S(j+1,n))+p-1)}}

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

H ( S ) = S ( 1 , h 1 ) S ( h 1 + 1 , h 2 ) ⋯ S ( h m − 1 + 1 , h m ) {displaystyle {displaystyle H(S)=S(1,h_{1})S(h_{1}+1,h_{2})dotsm S(h_{m-1}+1,h_{m})}} H i ( S ) = S ( h i − 1 + 1 , h i ) , i = 1 , 2 ⋯ m , where h 0 = 0 , h 1 = 1 , h m = l ( S ) , {displaystyle {displaystyle H_{i}(S)=S(h_{i-1}+1,h_{i}),i=1,2dotsm m,{ ext{where}};h_{0}=0,h_{1}=1,h_{m}=l(S)},} называется компонентом H(S).

Компонент S, H i {displaystyle H_{i}} (S), называется исчерпывающим, если S(1, h i {displaystyle h_{i}} ) - самая длинная последовательность, создаваемая S (1, h i {displaystyle h_{i}} -1) (т. e. S (1, h i {displaystyle h_{i}} -1) ⇒ S(1, h i {displaystyle h_{i}} )) но так, чтобы S (1, h i {displaystyle h_{i}} -1) не создавал S (1, h i {displaystyle h_{i}} ). T.е: S ( 1 , h i − 1 ) ↛ S ( 1 , h i ) {displaystyle {displaystyle S(1,h_{i}-1) rightarrow S(1,h_{i})}} Индекс p, который позволяет иметь самую длинную продукцию, называется указателем.

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

Алгоритм

Для вычисления данной сложности существует эффективный алгоритм за линейное количество операций ( O ( n ) ) {displaystyle ({displaystyle {mathcal {O}}(n)})}

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

  • 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