La complessità di Lempel-Ziv (in inglese: Lempel-Ziv Complexity) è una misura presentata per la prima volta nell'articolo intitolato On the Complexity of Finite Sequences (IEEE Trans. On IT-22,1 1976), dagli informatici israeliani Abraham Lempel e Jacob Ziv. Questa misura di complessità è correlata alla complessità di Kolmogorov, sebbene utilizzi unicamente come funzione la copia ricorsiva (cioè la copia superficiale)<ref>In inglese shallow copy': crea una nuova copia di un oggetto, ma se l'oggetto contiene riferimenti ad altri oggetti, questi riferimenti vengono copiati e non gli oggetti a cui puntano. Ciò significa che l'originale e la copia condividono gli stessi oggetti interni. Le modifiche apportate a questi oggetti interni saranno visibili in entrambe le copie, mentre le modifiche all'oggetto di primo livello non influenzeranno l'originale.</ref>.

Il meccanismo alla base di questa misura di complessità è il punto di partenza per alcuni algoritmi di compressione dati senza perdita, come LZ77 e LZ78 e LZW. Anche se si basa su un principio elementare di copia delle parole, questa misura di complessità non è troppo restrittiva, nel senso che soddisfa le principali qualità richieste da una misura di questo tipo: le sequenze con una certa regolarità non hanno una complessità eccessiva e la complessità aumenta con l'aumentare della lunghezza e dell'irregolarità della sequenza.

La complessità di Lempel-Ziv può essere utilizzata per misurare la ripetitività di sequenze binarie e testi, come i testi delle canzoni o la prosa. È stato anche dimostrato che le stime della dimensione frattale dei dati del mondo reale sono correlate alla complessità di Lempel-Ziv.

Principio di funzionamento Sia S una sequenza binaria di lunghezza n, per la quale si deve calcolare la complessità di Lempel-Ziv, indicata con C(S). La sequenza viene letta da sinistra a destra. Si immagini di avere una linea di demarcazione, che può essere spostata nella sequenza durante il calcolo. All'inizio, questa linea è posizionata subito dopo il primo simbolo, posto all'inizio della sequenza. Questa posizione iniziale è chiamata posizione 1 da cui occorre spostarsi alla posizione 2, che è considerata la posizione iniziale per il passo successivo (e così via). Si deve spostare il delimitatore (partendo dalla posizione 1) il più possibile a destra, in modo che la sotto-stringa tra la posizione 1 e la posizione del delimitatore sia una parola della sequenza che inizia prima della posizione 1 del delimitatore.

Non appena il delimitatore viene impostato su una posizione in cui questa condizione non è più soddisfatta, ci si deve fermare, spostando il delimitatore in quest'ultima posizione che deve essere contrassegnata questa posizione come nuova posizione iniziale (cioè posizione 1). Si continua a iterare fino alla fine della sequenza. La complessità di Lempel-Ziv corrisponde al numero di iterazioni necessarie per completare questa procedura.

In altre parole, la complessità di Lempel-Ziv è il numero di sottostringhe (o sottocelle) diverse incontrate quando la sequenza binaria viene visualizzata come un flusso (da sinistra a destra).

Algoritmo

Fortunatamente, esiste un metodo molto efficiente per calcolare questa complessità, in un numero di operazioni di calcolo che cresce lineramente con la lunghezza della sequenza S''.

Una descrizione formale di questo metodo è fornita dal seguente algoritmo: i = p − 1, p è il puntatore u è la lunghezza del prefisso corrente v è la lunghezza della componente corrente per il puntatore corrente p vmax è la lunghezza finale utilizzata per la componente corrente (la più grande su tutti i puntatori possibili p) C è la complessità di Lempel-Ziv, incrementata iterativamente. // S è una sequenza bnaria di dimensione 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

Note

Bibliografia Abraham Lempel and Jacob Ziv, « On the Complexity of Finite Sequences », IEEE Trans. on Information Theory, January 1976, p. 75–81, vol. 22, n°1 Applicazioni « Are Pop Lyrics Getting More Repetitive? », By Colin Morris, is a blog post explaining how to use the Lempel–Ziv complexity to measure repetitiveness of song lyrics (con il codice sorgente aperto). Burns & Rajan (2015) Combining complexity measures of EEG data: multiplying measures reveal previously hidden information. F1000Research. 4:137. (con il codiceMATLAB pubblicamente disponibile). Burns & Rajan (2019) A Mathematical Approach to Correlating Objective Spectro-Temporal Features of Non-linguistic Sounds With Their Subjective Perceptions in Humans. Frontiers in Neuroscience 13:794. (con il codiceMATLAB pubblicamente disponibile).

Voci correlate LZ77 e LZ78

Collegamenti esterni Example of a Python implementation and discussion on StackOverflow #41336798 Open-Source (MIT) implementation on Python and Cython on GitHub disponibile su PyPi

Categoria:Teoria della calcolabilità Categoria:Compressione dei dati Categoria:Teoria della complessità computazionale