Лемпель-Зив сложность

Сложность Зива-Зив был впервые представлен в статье О сложности конечных последовательностей (IEEE Trans. На IT-22,1 1976), два израильских ученых - компьютерщиков, Abraham Лемпелом и Якоба Зива . Эта мера сложности связана со сложностью Колмогорова , но единственная функция, которую он использует, - это рекурсивная копия (т.е. мелкая копия).

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

Сложность Лемпеля-Зива может использоваться для измерения повторяемости двоичных последовательностей и текста, например текстов песен или прозы. Также было показано, что оценки фрактальной размерности реальных данных коррелируют со сложностью Лемпеля-Зива ^{[1] [2]} .

Принцип [ править ]

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

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

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

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

Формальные объяснения [ править ]

Метод, предложенный Лемпелем и Зивом, использует три понятия: воспроизводимость, воспроизводимость и исчерпывающая история последовательности, которые мы определили здесь.

Обозначения [ править ]

Пусть S будет двоичной последовательностью длины n (т. Е. N символов, принимающих значение 0 или 1). Пусть S (i, j), с , будет подсловом S от индекса i до индекса j (если j <i, S (i, j) - пустая строка). Длина n матрицы S обозначается l (S), а последовательность Q называется фиксированным префиксом S, если:${\ Displaystyle 1 \ Leq я, J \ Leq п}$

${\displaystyle \exists j<{\text{l(S), s.t. 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.t. }}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, 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), определяемой следующим образом:${\displaystyle 1\leq {\text{m}}\leq l(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),{{\text{ is called component of }}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, который позволяет иметь самую длинную продукцию, называется указателем.${\displaystyle S(1,h_{i}-1)\nrightarrow S(1,h_{i})}$

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

Алгоритм [ править ]

Будем надеяться, что существует очень эффективный метод вычисления этой сложности с использованием линейного числа операций ( для длины последовательности S).${\displaystyle {\mathcal {O}}(n)}$${\displaystyle n=l(S)}$

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

• i = p - 1, p - указатель (см. выше)
• u - длина текущего префикса
• v - длина текущего компонента для текущего указателя p
• vmax - окончательная длина, используемая для текущего компонента (наибольшая из всех возможных указателей p)
• и C - сложность Лемпеля-Зива, увеличиваемая итеративно.

// S - двоичная последовательность размера n i  : =  0 C  : =  1 u  : =  1 v  : =  1 vmax  : =  v while  u  +  v  <=  n  do  if  S [ i  +  v ]  =  S [ u  +  v ],  затем  v  : =  v  +  1  иначе  vmax  : =  max ( v ,  vmax )  i  : =  i  + 1  if  i  =  u  then  // все указатели обработаны  C  : =  C  +  1  u  : =  u  +  vmax  v  : =  1  i  : =  0  vmax  : =  v  else  v  : =  1  end  if  end  if end  while if  v  ! =  1,  то  C  : =  C + 1 конец,  если

Примечания и ссылки [ править ]

Ссылки [ править ]

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

• Абрахам Лемпель и Джейкоб Зив, «О сложности конечных последовательностей», IEEE Trans. по теории информации, январь 1976 г., стр. 75–81, т. 22, № 1

Заявление [ править ]

• «Поп-тексты становятся все более повторяющимися? », Автор Колин Моррис , - это сообщение в блоге, объясняющее, как использовать сложность Лемпеля-Зива для измерения повторяемости текстов песен (с доступным исходным кодом) .
• Burns & Rajan (2015) Объединение показателей сложности данных ЭЭГ: умножение показателей позволяет выявить ранее скрытую информацию. F1000 Исследования. 4: 137. [1] (с общедоступным кодом MATLAB).
• Бернс и Раджан (2019) Математический подход к корреляции объективных спектрально-временных характеристик нелингвистических звуков с их субъективным восприятием людьми. Границы неврологии 13: 794. [2] (с общедоступным кодом MATLAB).

Внешние ссылки [ править ]

• Пример реализации Python и обсуждение StackOverflow # 41336798
• Реализация с открытым исходным кодом (MIT) на Python и Cython на GitHub доступна на PyPi