LZW (for Lempel-Ziv-Welch ) er en algoritme for datakomprimering uten tap. Det er en forbedring av LZ78- algoritmen som ble oppfunnet av Abraham Lempel og Jacob Ziv i 1978. LZW ble opprettet i 1984 av Terry Welch , derav navnet.
LZW-algoritmen var patentert av selskapet Unisys (et programvarepatent som bare er gyldig i USA). Den ble brukt i modemer (standard V42 bis) og brukes fortsatt i formatene til digitalt bilde GIF eller TIFF og lydfiler MOD .
Algoritmen er designet for å være rask å kode, men mesteparten av tiden er den ikke optimal fordi den utfører begrenset analyse av dataene som skal komprimeres.
Komprimeringsalgoritmen bygger en oversettelsestabell med tegnstrenger fra teksten som skal komprimeres. Denne tabellen kobler koder med fast størrelse (vanligvis 12- bit ) til tegnstrenger. Tabellen er initialisert med alle tegnene (256 oppføringer når det gjelder tegn kodet på 8 bits). Når kompressoren undersøker teksten, legger den til hver 2 tegnstreng i tabellen som en kode og tegnsammenheng , med koden som tilsvarer det første tegnet i strengen. Samtidig som den registrerer disse strengene, sendes det første tegnet ut. Hver gang en streng som allerede er oppstått leses, bestemmes den lengste strengen som allerede er oppdaget, og koden som tilsvarer den strengen med det sammenhengende tegnet (neste tegn i den innkommende strømmen) lagres i tabellen. Koden for den lengste delen av strengen du opplever, sendes ut, og det siste tegnet brukes som grunnlag for neste streng.
Dekompresjonsalgoritmen trenger bare komprimert tekst som inndata. Faktisk rekonstruerer den en identisk tegnstreng / kodetabell når den regenererer originalteksten. Imidlertid synes en uvanlig tilfelle når den tegn / snor / tegn / snor / karakter sekvens (med de samme tegn for hvert tegn , og det samme tegnstrengen streng ) er oppstått på inngang og tegn / streng allerede er til stede i tabell. Når dekompresjonsalgoritmen leser koden for tegn / streng / tegn , kan den ikke behandle den fordi den ennå ikke har lagret denne koden i tabellen. Dette spesielle tilfellet kan håndteres fordi dekompresjonsprogrammet vet at det ekstra tegnet er det forrige tegnet .
FONCTION LZW_Compresser(Texte, dictionnaire) w ← "" TANT QUE (il reste des caractères à lire dans Texte) FAIRE c ← Lire(Texte) p ← Concaténer(w, c) SI Existe(p, dictionnaire) ALORS w ← p SINON Ajouter(p, dictionnaire) Écrire dictionnaire[w] w ← c FIN TANT QUE
Følgende tabell viser resultatet av å kjøre komprimeringsalgoritmen på følgende streng:
TOBEORNOTTOBEORTOBEORNOTAnta at vi bruker en 256 tegn (8-biters) ASCII-kode som grunnordbok. Lengden på denne strengen er 24 tegn. Det krever derfor 24 * 8 = 192 biter lagringsplass.
| w | vs. | toalett | exit | ordbok |
|---|---|---|---|---|
| T | T | |||
| T | O | TIL | T | TO = <256> |
| O | B | OB | O | OB = <257> |
| B | E | VÆRE | B | BE = <258> |
| E | O | EO | E | EO = <259> |
| O | R | GULL | O | ELLER = <260> |
| R | IKKE | RN | R | RN = <261> |
| IKKE | O | NEI | IKKE | NEI = <262> |
| O | T | OT | O | OT = <263> |
| T | T | TT | T | TT = <264> |
| T | O | TIL | ||
| TIL | B | TOB | <256> | TOB = <265> |
| B | E | VÆRE | ||
| VÆRE | O | BEO | <258> | BEO = <266> |
| O | R | GULL | ||
| GULL | T | ORT | <260> | ORT = <267> |
| T | O | TIL | ||
| TIL | B | TOB | ||
| TOB | E | Å VÆRE | <265> | TOBE = <268> |
| E | O | EO | ||
| EO | R | EOR | <259> | EOR = <269> |
| R | IKKE | RN | ||
| RN | O | RNO | <261> | RNO = <270> |
| O | T | OT | ||
| OT | <263> |
Etter komprimering får vi en 9-bits kodesekvens på utgangen:
TOBEORNOT<256><258><260><265><259><261><263>Det krever 16 × 9 = 144 bits lagringsplass, i stedet for de 192 bitene i den opprinnelige strengen.
Dette eksemplet er bygget med {a, b, c} som basisalfabet, som gir en ordbok av størrelse 3 ved komprimering eller dekompresjon (array indeksert fra 0 til 2). Vi tar som en streng for å komprimere ababcbababaaaaaaa. Flyten av kompresjon på dette enkle eksemplet er detaljert i bildene nedenfor.
FONCTION LZW_Décompresser(Code, dictionnaire) n ← |Code| v ← Lire(Code) Écrire dictionnaire[v] w ← chr(v) POUR i ALLANT DE 2 à n FAIRE v ← Lire(Code) SI Existe(v, dictionnaire) ALORS entrée ← dictionnaire[v] SINON entrée ← Concaténer(w, w[0]) Écrire entrée Ajouter(Concaténer(w,entrée[0]), dictionnaire) w ← entrée FIN POUR
Resultatet av dekompresjonsalgoritmen, på den komprimerte sekvensen av 9-bits koder, presenteres i denne tabellen:
TOBEORNOT<256><258><260><265><259><261><263>| vs. | w | Inngang | w + inngang [0] | exit | ordbok |
|---|---|---|---|---|---|
| T | T | T | |||
| O | T | O | TIL | O | TO = <256> |
| B | O | B | OB | B | OB = <257> |
| E | B | E | VÆRE | E | BE = <258> |
| O | E | O | EO | O | EO = <259> |
| R | O | R | GULL | R | ELLER = <260> |
| IKKE | R | IKKE | RN | IKKE | RN = <261> |
| O | IKKE | O | NEI | O | NEI = <262> |
| T | O | T | OT | T | OT = <263> |
| <256> | T | TIL | TT | TIL | TT = <264> |
| <258> | TIL | VÆRE | TOB | VÆRE | TOB = <265> |
| <260> | VÆRE | GULL | BEO | GULL | BEO = <266> |
| <265> | GULL | TOB | ORT | TOB | ORT = <267> |
| <259> | TOB | EO | Å VÆRE | EO | TOBE = <268> |
| <261> | EO | RN | EOR | RN | EOR = <269> |
| <263> | RN | OT | RNO | OT | RNO = <270> |
Ved hvert trinn dekoder vi koden som dekomprimeres: vi ser etter den tilsvarende strengen i ordboken og sammenkobler den til allerede oppnådd resultat. Deretter sammenkobler vi den dekodede strengen like før (i rødt) med den første bokstaven i strengen som nettopp er blitt dekodet (i grønt), og vi legger den til ordboken hvis det er et nytt ord.
For visse stadier av dekompresjonen (kode 7, 9 og 10) vil vi være i det spesielle tilfellet der koden som skal dekomprimeres, ikke er i ordboken ennå. I dette tilfellet, som forklart i artikkelen, tar vi tegnstrengen dekodet like før (i rødt), og vi sammenføyer det med det første tegnet for å oppnå strengen som tilsvarer koden som dekomprimeres og ordet som skal legges til ordboken.
Spesielle koder kan eksistere avhengig av applikasjonen, for eksempel for å signalisere slutten på datastrømmen (kode <257> for LZW-komprimering av TIF-bilder), for å utføre en delvis rengjøring av ordboken, etc.
Når ordboken utvides, ender antall koder over grensen for antall biter som lar dem skrives. Koderen øker deretter antall biter skrevet per kode. For eksempel med 9-biters bredde per kode i eksemplet ovenfor, vil den første breddeøkningen være nødvendig når du legger til den 511. ordbokoppføringen . Dekoderen vil gjøre det samme når det legger til 511 th adgang til sin ordbok. Økningen gjengis hver gang kreftene til 2 krysses (1023, 2047,…).
For å forhindre at ordboken vokser uforholdsmessig (antall biter som skal skrives per kode blir uoverkommelig for å opprettholde effektiv komprimering), kan et maksimalt antall oppføringer i ordboken tilveiebringes. Når dette tallet er nådd, setter koderen inn en spesiell kode og tømmer ordboken helt. Kodingsprosessen begynner deretter igjen som for første tegn. Dekoderen renser ordboken når den møter denne spesielle koden.
Denne spesialkoden er verdien <256> for LZW-komprimering av TIF-bilder, og er ekskludert fra "normale" ordbokoppføringer.