Dekompresja LZW

Dekompresor dostaje same kody, bez słownika. Słownik odtwarza na bieżąco: każdy wpis, który kompresor dopisał, dekompresor dopisuje krok później. Prawie zawsze to wystarcza. Raz na jakiś czas przychodzi kod, którego dekompresor jeszcze nie zna, i trzeba go wywnioskować.

Algorytm

słownik = wszystkie pojedyncze symbole poprzedni = słownik[pierwszy kod]; wypisz poprzedni dla każdego kolejnego kodu k: jeśli k jest w słowniku: wpis = słownik[k] w przeciwnym razie (k to następny wolny numer): wpis = poprzedni + pierwszy symbol(poprzedni) ← KwKwK wypisz wpis dopisz poprzedni + pierwszy symbol(wpis) do słownika poprzedni = wpis

Dopisywany wpis to "poprzedni ciąg + pierwszy symbol obecnego". Kompresor dopisał dokładnie ten sam ciąg, tylko krok wcześniej: w chwili, gdy po poprzednim ciągu zobaczył symbol, który rozpoczyna obecny.

Przebieg dla przykładu

Kody z kompresji: 0 1 2 4, alfabet A = 0, B = 1.

Kod	Znany?	Wpis	Wypisane	Nowy wpis w słowniku
0	tak	A	A
1	tak	B	B	A + B = AB = 2
2	tak	AB	AB	B + A = BA = 3
4	nie	AB + A = ABA	ABA	AB + A = ABA = 4

wynik: A B AB ABA = A B A B A B A

Przypadek KwKwK

Gdy przychodzi kod 4, słownik dekompresora kończy się na 3. Kod 4 to akurat wpis, który dekompresor ma dopisać w tym kroku. Skąd wiadomo, co w nim jest?

Kompresor wysłał kod 4 zaraz po jego utworzeniu. To możliwe tylko wtedy, gdy dane mają postać K w K w K, gdzie K to symbol, a w to ciąg: K w jest w słowniku, kompresor dopisuje K w K i od razu go używa. Nowy wpis zaczyna się więc od tego samego, od czego zaczynał się poprzedni ciąg, i jest równy:

wpis = poprzedni + pierwszy symbol(poprzedni) u nas: poprzedni = AB → wpis = AB + A = ABA

Pominięcie tego przypadku to najczęstszy błąd we własnych implementacjach. Dekoder działa wtedy na większości plików i psuje się na nielicznych, zwykle tych z długimi jednolitymi obszarami, gdzie wzorzec K w K w K jest częsty.

Kod

// codes: tablica kodów, wynik: tablica symboli
function lzwDecompress(codes, alphabetSize) {
  const dict = [];
  for (let i = 0; i < alphabetSize; i++) dict.push([i]);
  let prev = dict[codes[0]];
  const out = [...prev];
  for (const k of codes.slice(1)) {
    const entry = k < dict.length ? dict[k] : [...prev, prev[0]];   // KwKwK
    out.push(...entry);
    dict.push([...prev, entry[0]]);
    prev = entry;
  }
  return out;
}

lzwDecompress([0, 1, 2, 4], 2);   // [0, 1, 0, 1, 0, 1, 0]

Przechowywanie całych ciągów w słowniku jest proste, ale zużywa dużo pamięci. Dekodery GIF trzymają zwykle dla każdego wpisu tylko kod prefiksu i ostatni symbol, a ciąg odtwarzają od końca. Szczegóły dla GIF są na stronie dekompresja LZW w GIF.