Złożoność Lempel-Ziv - Lempel-Ziv complexity

Lempel-Ziv złożoność jest to środek, który został po raz pierwszy przedstawiony w artykule od złożoności ciągów skończonych (IEEE Trans. On IT-22,1 1976), przez dwóch izraelskich naukowców komputerowych, Abraham Lempel i Jacob Ziv . Ta miara złożoności jest powiązana ze złożonością Kołmogorowa , ale jedyną używaną przez nią funkcją jest kopia rekurencyjna (tj. kopia płytka).

Mechanizm leżący u podstaw tej miary złożoności jest punktem wyjścia dla niektórych algorytmów bezstratnej kompresji danych , takich jak LZ77, LZ78 i LZW . Choć opiera się na elementarnej zasadzie kopiowania słów, ta miara złożoności nie jest zbyt restrykcyjna w tym sensie, że spełnia główne cechy oczekiwane przez taką miarę: ciągi o pewnej regularności nie mają zbyt dużej złożoności, a złożoność rośnie wraz ze wzrostem długości i nieregularności sekwencji.

Złożoność Lempel-Ziv może być wykorzystana do pomiaru powtarzalności sekwencji binarnych i tekstu, takich jak teksty piosenek lub proza. Wykazano również, że szacunki wymiarów fraktalnych danych ze świata rzeczywistego korelują ze złożonością Lempel-Ziv.

Zasada

Niech S będzie ciągiem binarnym o długości n, dla którego musimy obliczyć złożoność Lempel-Ziv, oznaczoną C(S). Sekwencja jest odczytywana od lewej.

Wyobraź sobie, że masz linię ograniczającą, którą można przesuwać w sekwencji podczas obliczeń. Początkowo linia ta jest ustawiana zaraz po pierwszym symbolu, na początku sekwencji. Ta pozycja początkowa nazywa się pozycją 1, skąd musimy przenieść ją do pozycji 2, która jest uważana za pozycję początkową dla następnego kroku (i tak dalej). Musimy przesunąć ogranicznik (zaczynając od pozycji 1) dalej w prawo, tak aby podsłowo między pozycją 1 a pozycją ogranicznika było słowem z sekwencji, która rozpoczyna się przed pozycją 1 ogranicznika.

Gdy tylko ogranicznik zostanie ustawiony w pozycji, w której ten warunek nie jest spełniony, zatrzymujemy się, przesuwamy ogranicznik do tej pozycji i zaczynamy od nowa, zaznaczając tę ​​pozycję jako nową pozycję początkową (tj. pozycję 1). Powtarzaj do końca sekwencji. Złożoność Lempel-Ziv odpowiada liczbie iteracji potrzebnych do zakończenia tej procedury.

Mówiąc inaczej, złożoność Lempel-Ziv to liczba różnych podciągów (lub podsłów) napotykanych, gdy sekwencja binarna jest postrzegana jako strumień (od lewej do prawej).

Formalne wyjaśnienia

Metoda zaproponowana przez Lempela i Ziva posługuje się trzema pojęciami: odtwarzalnością, produkowalnością i wyczerpującą historią sekwencji, które tutaj zdefiniowaliśmy.

Notacje

Niech S będzie sekwencją binarną o długości n (tj. n symboli o wartości 0 lub 1). Niech S(i,j), gdzie , będzie podsłowem S od indeksu i do indeksu j (jeśli j<i, S(i,j) jest ciągiem pustym). Długość n z S jest oznaczona jako l(S), a sekwencja Q jest uważana za stały przedrostek S, jeśli: ${\displaystyle 1\leq ja,j\leq n}$

${\ Displaystyle \ istnieje j < {\ tekst {l (S), st S (1, j) = Q.}}}$

Odtwarzalność i produktywność

Przykład odtwarzalności Kliknij tutaj

Z jednej strony mówi się, że sekwencja S o długości n jest odtwarzalna ze swojego przedrostka S(1,j), gdy S(j+1,n) jest podsłowem S(1,n-1). Oznaczymy to S(1,j)→S.

Mówiąc inaczej, S można odtworzyć ze swojego prefiksu S(1,j), jeśli reszta sekwencji, S(j+1,n), jest niczym innym jak kopią innego podsłowa (zaczynając od indeksu i < j+ 1) z S(1,n-1).

Aby udowodnić, że ciąg S może być odtworzony przez jeden z jego przedrostków S(1,j), musisz wykazać, że:

${\ Displaystyle \ istnieje p \ leq j, {\ tekst { st }} S (j + 1, n) = S (p, l (S (j + 1, n)) + p-1)}$

Przykład produktywności Kliknij tutaj

Z drugiej strony, produkowalność jest definiowana z odtwarzalności: sekwencja S jest produkowana ze swojego przedrostka S(1,j), jeśli S(1,n-1) jest odtwarzalna z S(1,j). Jest to oznaczone jako S(1,j)⇒S. Inaczej mówiąc, S(j+1,n-1) musi być kopią innego podsłowa S(1,n-2). Ostatni symbol S może być nowym symbolem (ale nie może nim być), prawdopodobnie prowadzącym do powstania nowego podsłowa (stąd termin „produkowalność”).

Porównanie odtwarzalności i produktywności Kliknij tutaj

Wyczerpująca historia i złożoność

Z definicji produktywności pusty ciąg Λ=S(1,0) ⇒ S(1,1). Czyli w rekurencyjnym procesie produkcyjnym w kroku i mamy S(1,hi) ⇒ S(1,hi+1), więc możemy zbudować S z jego przedrostków. A ponieważ S(1,i) ⇒ S(1,i+1) (przy hi+1 =hi+1) jest zawsze prawdziwe, ten proces produkcji S zajmuje co najwyżej n=l(S) kroków. Niech m, , będzie liczbą kroków potrzebnych do tego procesu produktu S. S można zapisać w postaci rozłożonej, zwanej historią S, i oznaczonej jako H(S), zdefiniowanej w następujący sposób: ${\ Displaystyle 1 \ leq {\ tekst {m}} \ leq l (S)}$

${\ Displaystyle H (S) = S (1, h_ {1}) S (h_ {1}+1, h_ {2}) \ kropki S (h_ {m-1} + 1, h_ {m})}$ ${\ Displaystyle H_ {i} (S) = S (h_ {i-1} + 1, h_ {i}), i = 1,2 \ kropki m {\ tekst {gdzie}} \; h_ {0} =0,h_{1}=1,h_{m}=l(S),{{\text{ nazywamy składową }}H(S)}.}$

Porównanie odtwarzalności i produktywności Kliknij tutaj

Składnik S, Hi(S) jest określany jako wyczerpujący, jeśli S(1,hi) jest najdłuższym ciągiem utworzonym przez S(1,hi-1) (tzn. S(1,hi-1) ⇒ S( 1,hi)) ale tak, że S(1,hi-1) nie daje S(1,hi) (oznaczone ). Indeks p, który pozwala na najdłuższą produkcję, nazywa się wskaźnikiem. ${\ Displaystyle S (1, h_ {i} -1) \ nrightarrow S (1, h_ {i})}$

Mówi się, że historia S jest wyczerpująca, jeśli wszystkie jej składniki są wyczerpujące, z wyjątkiem być może ostatniego. Z definicji można wykazać, że dowolna sekwencja S ma tylko jedną wyczerpującą historię, a ta historia jest tą, która ma najmniejszą liczbę składowych ze wszystkich możliwych historii S. Wreszcie liczba składowych tej jedynej wyczerpującej historii S nazywa się złożonością Lempel-Ziv S.

Algorytm

Na szczęście istnieje bardzo wydajna metoda obliczania tej złożoności, w liniowej liczbie operacji ( dla długości ciągu S). ${\ Displaystyle {\ Mathcal {O}} (n)}$${\ Displaystyle n = l (S)}$

Formalny opis tej metody podaje następujący algorytm :

• i = p - 1, p jest wskaźnikiem (patrz wyżej)
• u to długość bieżącego prefiksu
• v jest długością bieżącego składnika dla bieżącego wskaźnika p
• vmax to ostateczna długość użyta dla bieżącego komponentu (największa ze wszystkich możliwych wskaźników p)
• a C to złożoność Lempel-Ziv, zwiększana iteracyjnie.

// 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

Zobacz też

• LZ77 i LZ78 – Algorytmy kompresji, które wykorzystują podobną ideę znajdowania pasujących podciągów.

Uwagi i referencje

Bibliografia

Bibliografia

• Abraham Lempel i Jacob Ziv, „O złożoności ciągów skończonych”, IEEE Trans. o teorii informacji, styczeń 1976, s. 75–81, t. 22, nr 1

Podanie

• « Czy popowe teksty stają się bardziej powtarzalne? », autorstwa Colin Morris , to wpis na blogu wyjaśniający, jak wykorzystać złożoność Lempel-Ziv do pomiaru powtarzalności tekstów piosenek (z dostępnym kodem źródłowym) .
• Burns i Rajan (2015) Łączenie miar złożoności danych EEG: mnożenie miar ujawnia wcześniej ukryte informacje. F1000Badania. 4:137. [1] (z dostępnym publicznym kodem MATLAB).
• Burns & Rajan (2019) Matematyczne podejście do korelacji obiektywnych cech spektro-czasowych dźwięków niejęzykowych z ich subiektywną percepcją u ludzi. Granice w neuronauce 13:794. [2] (z dostępnym publicznym kodem MATLAB).

Zewnętrzne linki

• Przykład implementacji Pythona i dyskusja na StackOverflow #41336798
• Implementacja Open-Source (MIT) w Pythonie i Cythonie na GitHub dostępna na PyPi