Algoritmo di compressione LZW (Lempel-Ziv-Welch): cos’è e come funziona

L’algoritmo LZW (Lempel-Ziv-Welch) è un algoritmo di compressione senza perdita dei dati. Funziona cercando e sostituendo sequenze di dati ripetitive con codici più corti.

In pseudo-codice

Leggi P
Scrivi P
C = P
WHILE ci sono caratteri da leggere DO
    leggi C
    IF NEW_CODE non è nel dizionario THEN
        STRING = dizionario( OLD_CODE )
        STRING = STRING+CHARACTER
    ELSE
        STRING = dizionario( NEW_CODE )
    ENDIF
    scrivi STRING
    C = first character in STRING
    add OLD_CODE + C to the translation table
    OLD_CODE = NEW_CODE
END of WHILE

Algoritmo passo passo

Codice: https://gist.github.com/salvatorecapolupo/558151eba2ec27d24593c3af03f9a4ca

Ecco una spiegazione semplificata del funzionamento dell’algoritmo:

  1. Inizializzazione del Dizionario: L’algoritmo inizia con un dizionario che contiene tutte le possibili combinazioni di singoli caratteri. Ad esempio, se stiamo lavorando con caratteri ASCII, il dizionario iniziale conterrà tutti i singoli caratteri da 0 a 255.
  2. Analisi della Stringa di Input: L’algoritmo analizza la stringa di input carattere per carattere.
  3. Costruzione di Sequenze: A mano a mano che analizza la stringa, l’algoritmo costruisce sequenze di caratteri. Inizia con singoli caratteri e, man mano che incontra nuove sequenze, le aggiunge al dizionario.
  4. Sostituzione con Codici: Quando una sequenza è già presente nel dizionario, l’algoritmo la sostituisce con un codice più corto, che rappresenta la sequenza completa.
  5. Aggiornamento del Dizionario: Ogni volta che una nuova sequenza viene aggiunta al dizionario, viene assegnato un nuovo codice.
  6. Generazione dell’Output Compresso: L’output compresso consiste in una sequenza di codici che rappresentano le sequenze di input.
  7. Decompressione: Per decomprimere i dati, il processo viene invertito. I codici vengono letti e sostituiti con le sequenze corrispondenti dal dizionario.

L’efficienza di LZW deriva dalla sua capacità di adattarsi dinamicamente al contenuto dei dati, creando e aggiornando il dizionario durante il processo di compressione. Questo consente di ottenere una buona compressione per dati che contengono pattern ripetitivi o sequenze lunghe.

Tag: