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.

👇 Da non perdere 👇



Trovalost.it esiste da 4639 giorni (13 anni), e contiene ad oggi 4348 articoli (circa 3.478.400 parole in tutto) e 22 servizi online gratuiti. – Leggi un altro articolo a caso
Numero di visualizzazioni (dal 21 agosto 2024): 0
Pubblicità – Continua a leggere sotto :-)
Segui il canale ufficiale Telegram @trovalost https://t.me/trovalost
Seguici su Telegram: @trovalost
Privacy e termini di servizio / Cookie - Il nostro network è composto da Lipercubo , Pagare.online e Trovalost
Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Questo sito contribuisce alla audience di sè stesso.