Complexité de Lempel-Ziv

La méthode proposée par Lempel et Ziv s'appuie sur plusieurs notions : reproductibilité, productibilité et histoire exhaustive d'une séquence.

Soit S une séquence de longueur n. On note S(i,j) avec ${\displaystyle 1\leq i,j\leq n,}$ le sous-mot de S allant de l'indice i à l'indice j (Si j<i, S(i,j) est la chaîne vide Λ). La longueur n de la séquence est notée l(S) et une séquence Q est un préfixe strict de S si :

${\displaystyle \exists j<{\text{l(S) t.q. S(1,j) = Q .}}}$

Une séquence S de longueur n est dite reproductible à partir de son préfixe S(1,j) (les j premiers caractères de S) si S(j+1,n) est un sous-mot de S(1,n-1). On note S(1,j)→S. Autrement dit, S est reproductible à partir de son préfixe S(1,j) si S(j+1,n) n'est rien d'autre qu'une copie d'un sous mot déjà existant (qui commence à un indice i < j+1) de S(1,n-1). Pour prouver qu'on peut reproduire toute la séquence S en partant de l'un de ses préfixes S(1,j), il faut montrer que :

${\displaystyle \exists p\leq j{\text{ t.q. }}S(j+1,n)=S(p,l(S(j+1,n))+p-1)}$

La productibilité, quant à elle, se définit à partir de la reproductibilité : on dit qu'une séquence S est productible à partir de S(1,j) si S(1,n-1) est reproductible à partir de S(1,j). En d'autres termes, S(j+1,n-1) doit être une copie d'un sous mots de S(1,n-2). Le dernier caractère de S peut être un nouveau caractère (ou pas) entraînant éventuellement l'apparition d'un nouveau sous-mot de S (d'où le terme de productibilité).

D'après la définition de la productibilité, on a Λ=S(1,0) ⇒ S(1,1). Par un processus récursif de production, où à l'étape i on a S(1,h_i) ⇒ S(1,h_i+1), on peut construire S à partir de ses préfixes. Vu que S(1,i) ⇒ S(1,i+1) (en posant h_i+1 =h_i +1) est toujours vrai, ce processus de production de S se fait en au plus l(S) étapes. Soit m, ${\displaystyle 1\leq {\text{m}}\leq l(S)}$, le nombre d'étapes nécessaires au processus de production de S. On peut écrire S sous une forme décomposée, appelée une histoire de S et notée H(S), comme suit :

${\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,}$ ${\displaystyle {\text{où }}h_{0}=0,h_{1}=1,h_{m}=l(S),{\text{est appelée composante de H(S)}}.}$

Une composante H_i(S) est dite exhaustive si S(1,h_i) est la plus longue séquence produite par S(1,h_i-1) (S(1,h_i-1) ⇒ S(1,h_i)) mais S(1,h_i-1) ne reproduit pas S(1,h_i) (notée ${\displaystyle S(1,h_{i}-1)\nrightarrow S(1,h_{i})}$). L'indice p qui permet d'avoir la plus longue production est appelé pointeur. L'histoire de S est exhaustive si toutes ses composantes le sont, avec une éventuelle exception pour la dernière. Une séquence S n'a qu'une seule histoire exhaustive et cette histoire est, parmi les histoires de S, celle qui a le plus petit nombre de composantes. Le nombre de composantes de cette histoire exhaustive est une mesure de complexité de S.

Plus formellement on peut décrire la méthode par l'algorithme ci-dessous :

• i = p - 1
• l est la longueur du préfixe courant
• k est la longueur de la composante courante pour le pointeur p courant
• kmax est la longueur finale retenue pour la composante courante(maximum sur tous les pointeurs p possibles)
• C est la complexité

         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

• (en) Abraham Lempel et Jacob Ziv, « On the Complexity of Finite Sequences », IEEE Trans. on Information Theory,‎ janvier 1976, p. 75–81, vol. 22, n°1 [lecture en ligne]

• Exemple d'une implémentation naïve en Python, et discussions sur StackOverflow #41336798
• Implémentation en Python, Cython et Julia (sous licence MIT) sur GitHub disponible sur PyPi

• Portail des mathématiques
• Portail de l'informatique théorique