Složitost Lempel-Ziv

Složitost Lempel-Ziv se poprvé představil v článku na složitosti konečných sekvencí (IEEE Trans. On IT 22,1 1976), dva izraelské počítačových odborníků, Abraham Lempel a Jacob Ziv . Toto měřítko složitosti souvisí s Kolmogorovovou složitostí , ale jako jedinou funkci používá pouze rekurzivní kopii.

Mechanismus implementovány v této složitosti opatření je původem z bezztrátové komprese dat algoritmů LZ77 , LZ78 a LZW . Ačkoli je toto měřítko složitosti založeno pouze na elementárním principu překompilování slov, není příliš omezující v tom smyslu, že respektuje hlavní vlastnosti očekávané od takového opatření: neposkytuje sekvencím s určitými pravidelnostmi velkou složitost a tato složitost je o to větší, že posloupnost je dlouhá a nepravidelná.

Zásada

Vzhledem k posloupnosti S o délce n, jejíž složitost lze vypočítat, označenou C (S), se posloupnost prochází počínaje zleva. Představte si, že máme lištu sloužící jako oddělovač, že se bude během výpočtu pohybovat po celé posloupnosti . Na začátku je tento pruh umístěn hned za prvním znakem sekvence. Tato počáteční poloha pruhu se bude nazývat poloha 1, poté se pokuste ji přesunout do polohy 2, která se při další iteraci bude považovat za její počáteční polohu. Snažíme se co nejvíce posunout lištu (která je v poloze 1) tak, že slovo, které je mezi pozicí 1 a aktuální pozicí, je slovo posloupnosti, která začíná před pozicí 1 uzavřeného.

Jakmile je lišta v poloze, kde již není respektována tato podmínka (má-li mezi pozicí 1 a aktuální pozicí slovo již existující sekvence), zastavíme, umístíme lištu na toto místo označením této polohy jako novou počáteční pozici (pozice 1) pruhu a opakujeme ji až do konce sekvence. Složitost Lempel-Ziv odpovídá počtu iterací nezbytných k dosažení konce sekvence sledováním tohoto procesu.

Formální vysvětlení

Metoda navržená Lempelem a Zivem je založena na několika pojmech: reprodukovatelnost, produkovatelnost a vyčerpávající historie sekvence.

Zápisy

Nechť S je posloupnost délky n. Označíme S (i, j) s podslovem S přecházejícím z indexu i do indexu j (Si j <i, S (i, j) je prázdný řetězec Λ). Délka n posloupnosti je označena l (S) a posloupnost Q je přísná předpona S, pokud: $1 \ leq i, j \ leq n,$

$\ existuje j <{\ text {l (S) tq S (1, j) = Q.}}$

Reprodukovatelnost a doručitelnost

O sekvenci S o délce n se říká, že je reprodukovatelná ze své předpony S (1, j) (prvních j znaků S), pokud S (j + 1, n) je podslovem S (1, n-1). Označíme S (1, j) → S. Jinými slovy, S je reprodukovatelné ze své předpony S (1, j), pokud S (j + 1, n) není nic jiného než kopie již existujícího pod slova (které začíná indexem i <j + 1) S (1, n-1). Abychom dokázali, že můžeme reprodukovat celou sekvenci S počínaje jednou z jejích předpon S (1, j), musíme ukázat, že:

$\ existuje p \ leq j {\ text {tq}} S (j + 1, n) = S (p, l (S (j + 1, n)) + p-1)$

Produkovatelnost je definována z reprodukovatelnosti: říkáme, že posloupnost S je vyrobitelná z S (1, j), pokud je S (1, n-1) reprodukovatelná z S (1, j). Jinými slovy, S (j + 1, n-1) musí být kopií podslovu S (1, n-2). Posledním znakem S může být nový znak (nebo ne), který může zahrnovat vzhled nového podslovu S (odtud termín doručitelnosti).

Komplexní historie a složitost

Podle definice doručitelnosti máme Λ = S (1,0) ⇒ S (1,1). Rekurzivním výrobním procesem, kde v kroku i máme S (1, h i ) ⇒ S (1, h i + 1 ), můžeme postavit S z jeho předpon. Jelikož S (1, i) ⇒ S (1, i + 1) (nastavením h i + 1 = h i +1) je vždy pravda, probíhá tento proces výroby S maximálně v l (S) krocích. Nechť m je počet kroků nezbytných pro výrobní proces S. Můžeme psát S v rozložené formě, nazývané historie S a poznamenal H (S), takto: $1 \ leq {\ text {m}} \ leq l (S)$

$H (S) = S (1, h_ {1}) S (h_ {1} + 1, h_ {2}) \ dotsm S (h _ {{m-1}} + 1, h_ {m})$

$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 {se nazývá součást H (S)}}.$

O složce H i (S) se říká, že je vyčerpávající, pokud S (1, h i ) je nejdelší sekvence produkovaná S (1, h i-1 ) (S (1, h i-1 ) ⇒ S (1, h i )), ale S (1, h i-1 ) nereprodukuje S (1, h i ) (uvedeno ). Index p, který umožňuje mít nejdelší produkci, se nazývá ukazatel . Historie S je vyčerpávající, pokud jsou vyčerpávající všechny jeho komponenty, s možnou výjimkou pro poslední. Sekvence S má pouze jeden komplexní příběh a tento příběh je mezi příběhy S ten, který má nejmenší počet komponent. Počet komponent tohoto komplexního příběhu je měřítkem složitosti S. $S (1, h_ {i} -1) \ nvpravo S (1, h_ {i})$

Algoritmus

Formálně můžeme metodu popsat níže uvedeným algoritmem :

i = p - 1
l je délka aktuální předpony
k je délka aktuální složky pro aktuální ukazatel p
kmax je konečná délka zachovaná pro aktuální komponentu (maximum na všech možných ukazatelích p)
Je to složitost

i := 0 C := 1 l := 1 k := 1 Kmax=k tant que l+k <= n faire si S[i+k] = S[l+k] alors k := k+1 sinon Kmax := max(k,Kmax) i := i+1 si i = l alors // tous les pointeurs ont été traités) C := C + 1 l := l + Kmax k := 1 i := 0 kmax := k sinon k := 1 fin si fin si fin tant que si k != 1 alors C := C+1 fin si

Poznámky a odkazy

Bibliografie

(en) Abraham Lempel a Jacob Ziv , „ O složitosti konečných sekvencí “ , IEEE Trans. o teorii informací ,leden 1976, str. 75–81, roč. 22, č. 1 [ online čtení ]

externí odkazy