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

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

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

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

Принцип

Пусть 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 \ существует j <{\ text {l (S), st 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 \ существует п \ Leq J, {\ text {st}} 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 {\ текст {м}} \ 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 {называется компонентом}} 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}} (п)}$ ${\ Displaystyle п = л (S)}$

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

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

// S is a binary sequence of size n
i := 0
C := 1
u := 1
v := 1
vmax := v
while u + v <= n do
   if S[i + v] = S[u + v] then
      v := v + 1
   else
      vmax := max(v, vmax)
      i := i + 1
      if i = u then  // all the pointers have been treated
         C := C + 1
         u := u + vmax
         v := 1
         i := 0
         vmax := v
      else
         v := 1
      end if
   end if
end while
if v != 1 then
    C := C+1
end if

Смотрите также

LZ77 и LZ78 - алгоритмы сжатия, которые используют аналогичную идею поиска совпадающих подстрок.

Примечания и ссылки

использованная литература

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

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

заявка

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

Languages

In other projects