Złożoność Lempla-Ziva

Lempla -Ziva to miara, która została po raz pierwszy przedstawiona w artykule On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976) autorstwa dwóch izraelskich informatyków, Abrahama Lempla i Jacoba Ziva . 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 . Mimo że 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ę: sekwencje 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ść Lempla-Ziva można wykorzystać do pomiaru powtarzalności sekwencji binarnych i tekstu, takiego jak teksty piosenek lub proza. Wykazano również, że szacunki wymiarów fraktalnych danych ze świata rzeczywistego korelują ze złożonością Lempla-Ziva.

Zasada

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

Wyobraź sobie, że masz linię ograniczającą, którą można przesuwać w sekwencji podczas obliczeń. Początkowo linia ta jest ustawiana tuż za pierwszym symbolem, na początku sekwencji. Ta początkowa pozycja nazywana jest pozycją 1, skąd musimy ją przenieść 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) jak najbardziej w prawo, tak aby słowo podrzędne między pozycją 1 a pozycją ogranicznika było słowem sekwencji rozpoczynającej się przed pozycją 1 ogranicznika.

Gdy tylko ogranicznik zostanie ustawiony w miejscu, w którym 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). Kontynuuj iterację do końca sekwencji. Złożoność Lempla-Ziva odpowiada liczbie iteracji potrzebnych do zakończenia tej procedury.

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

Wyjaśnienia formalne

Metoda zaproponowana przez Lempela i Ziva wykorzystuje trzy pojęcia: odtwarzalność, wytwarzalność i wyczerpującą historię sekwencji, którą tutaj zdefiniowaliśmy.

Notacje

Niech S będzie ciągiem binarnym o długości n (tj. n symboli przyjmujących wartość 0 lub 1). Niech S ( $<$ ) , gdzie słowem podrzędnym S od indeksu i do indeksu j (jeśli (i, j) jest pustym łańcuchem). Długość n S jest oznaczona l ( S ), a sekwencja Q jest określana jako stały przedrostek S, jeśli:

${\ 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 z jej przedrostka S(1,j), gdy S(j+1,n) jest słowem podrzędnym S(1,j). Jest to oznaczone jako S(1,j)→S.

Innymi słowy, S jest odtwarzalne ze swojego przedrostka S(1,j), jeśli reszta sekwencji, S(j+1,n), jest niczym innym jak kopią innego podsłowa (począwszy od indeksu i < j+ 1) z S(1,n−1).

Aby udowodnić, że sekwencję S można odtworzyć za pomocą jednego z jej przedrostków S(1,j), należy pokazać, że:

${\ Displaystyle \ istnieje p \ równoważnik jot, {\ tekst {st }}S(j+1,n)=S(p,l(S(j+1,n))+p-1)}$

Przykład produktywności Kliknij tutaj

Z drugiej strony, produktywność jest definiowana na podstawie odtwarzalności: sekwencja S jest możliwa do wytworzenia z jej przedrostka S(1,j), jeśli S(1,n-1) jest odtwarzalna z S(1,j). Jest to oznaczone jako S(1,j)⇒S. Mówiąc inaczej, S(j+1,n-1) musi być kopią innego pod-słowa S(1,n-2). Ostatni symbol S może być nowym symbolem (ale nie może nim być), prawdopodobnie prowadząc do wytworzenia nowego pod-słowa (stąd termin produktywność).

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). Zatem 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) (gdzie hi+1 =hi + 1) jest zawsze prawdziwe, ten proces produkcji S zajmuje co najwyżej n=l(S) kroków. $iloczynu$ m , SS . S forma rozłożona, zwana historią S i oznaczona jako H(S), zdefiniowana w następujący sposób:

${\ 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 \ kropka 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

Mówimy, że składowa S, Hi(S) jest wyczerpująca, jeśli S(1,hi) jest najdłuższą sekwencją utworzoną przez S(1,hi-1) (tj. S(1,hi-1) ⇒ S( 1,hi)), ale tak, że S(1,hi-1) nie daje S(1,hi) (oznaczone). ${\ Displaystyle S (1, h_ {i} -1) \ nrightarrow S (1, h_ {i})}$ Indeks p, który pozwala mieć najdłuższa produkcja nazywa się pointer.

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 pokazać, że dowolny ciąg S ma tylko jedną wyczerpującą historię i 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ą Lempla-Ziva S.

Algorytm

$) {$ $displaystyle n$ w liniowej liczbie operacji ( dla długość ciągu S).

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

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


  0
  
  
  
  
      
           
          
   
         // S jest ciągiem binarnym o rozmiarze n  i  :=  C  :=  1  u  :=  1  v  :=  1  vmax  :=  v  while  u  +  v  <=  n  do  if  S  [  i  +  v  ]  =  S  [  u  +  v  ]  wtedy  v  :=  v  +  1  jeszcze  vmax  :=  max  (  v  
          
            
             
             
           
           0
           
      
           
       
    
 
     ,  vmax  )  i  :=  i  +  1  jeśli  i  =  u  to  // wszystkie wskaźniki zostały potraktowane  C  :=  C  +  1  u  :=  u  +  vmax  v  :=  1  i  :=  vmax  :=  v  else  v  :=  1  koniec  , jeśli  koniec  , jeśli  koniec  ,  jeśli  v  !  =  1  wtedy 
      
  C  :=  C  +  1  koniec  jeśli

Zobacz też

LZ77 i LZ78 – Algorytmy kompresji wykorzystujące podobny pomysł znajdowania pasujących podłańcuchów.

Uwagi i odniesienia

Bibliografia

Abraham Lempel i Jacob Ziv, «O złożoności skończonych sekwencji», IEEE Trans. o teorii informacji, styczeń 1976, s. 75–81, tom. 22, nr 1

Aplikacja

« Czy popowe teksty stają się coraz bardziej powtarzalne? », autorstwa Colina Morrisa , to wpis na blogu wyjaśniający, jak wykorzystać złożoność Lempela-Ziva 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: miary mnożenia ujawniają wcześniej ukryte informacje. F1000Badania. 4:137. [1] (z dostępnym publicznym kodem MATLAB).
Burns & Rajan (2019) Matematyczne podejście do korelacji obiektywnych spektro-czasowych cech dźwięków niejęzykowych z ich subiektywnym postrzeganiem u ludzi. Granice w neuronauce 13:794. [2] (z dostępnym publicznym kodem MATLAB).

Linki zewnętrzne