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

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

${\displaystyle \exists j<{\text{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), необходимо показать, что:

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

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

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

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

Алгоритм

Для вычисления данной сложности существует эффективный алгоритм за линейное количество операций $({\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