Kompresja LZW
Kompresor LZW trzyma jeden bieżący ciąg w i przedłuża go o kolejne symbole, dopóki taki ciąg jest w słowniku. Gdy już nie jest, wysyła kod w, dopisuje nowy ciąg do słownika i zaczyna od nowa od ostatniego symbolu. Ogólny opis algorytmu jest na stronie algorytm LZW.
Algorytm
Przebieg dla przykładu
Alfabet A = 0, B = 1. Dane: A B A B A B A.
| Krok | w | c | w + c w słowniku? | Wysłany kod | Nowy wpis |
|---|---|---|---|---|---|
| 1 | "" | A | tak (A) | ||
| 2 | A | B | nie | 0 (A) | AB = 2 |
| 3 | B | A | nie | 1 (B) | BA = 3 |
| 4 | A | B | tak (AB) | ||
| 5 | AB | A | nie | 2 (AB) | ABA = 4 |
| 6 | A | B | tak (AB) | ||
| 7 | AB | A | tak (ABA) | ||
| koniec | ABA | 4 (ABA) |
Zwróć uwagę na krok 7: wpis ABA = 4 powstał w kroku 5 i już w kroku 7 został użyty. Kompresor wysyła więc kod 4 tuż po tym, jak go utworzył. To właśnie ten przypadek wymaga specjalnej obsługi przy dekompresji.
Ile to oszczędza
Przy krótkich danych niewiele: 7 symboli to 4 kody, ale kody muszą mieć więcej bitów niż symbole, bo słownik rośnie. Zysk pojawia się przy długich, powtarzalnych danych. Dla klasycznego przykładu TOBEORNOTTOBEORTOBEORNOT (24 znaki, alfabet 6 liter) LZW daje 16 kodów. Dla obrazu z dużymi plamami jednego koloru jeden kod obejmuje często dziesiątki pikseli.
Słownik w praktyce
Szukanie "czy w + c jest w słowniku" musi być szybkie. Zwykle nie przechowuje się całych ciągów, tylko pary (kod prefiksu, symbol) w tablicy z haszowaniem: ciąg w + c to po prostu (kod(w), c). Dzięki temu każdy krok to jedno wyszukiwanie w tablicy, niezależnie od długości ciągu.
Kod
// dane: tablica symboli 0..alphabetSize-1, wynik: tablica kodów
function lzwCompress(data, alphabetSize) {
const dict = new Map(); // klucz "prefiks,symbol" → kod
let next = alphabetSize;
let w = -1; // kod bieżącego ciągu, -1 = pusty
const out = [];
for (const c of data) {
if (w === -1) { w = c; continue; }
const key = w + ',' + c;
if (dict.has(key)) { w = dict.get(key); continue; }
out.push(w);
dict.set(key, next++);
w = c;
}
if (w !== -1) out.push(w);
return out;
}
lzwCompress([0, 1, 0, 1, 0, 1, 0], 2); // [0, 1, 2, 4]W GIF dochodzą do tego kody o zmiennej długości, kody "wyczyść" i "koniec" oraz pakowanie bitów do bajtów. Opisuje to strona kompresja LZW w GIF.