Kompresja LZW w GIF
Ta strona pokazuje, jak osiem pikseli przykładowego pliku zamienia się w pięć bajtów 04 12 30 13 05. Zasady są opisane na stronach kompresja LZW i LZW w GIF.
Dane wejściowe
Przebieg
| Krok | w | c | Wysłany kod | Bity | Nowy wpis | Długość po kroku |
|---|---|---|---|---|---|---|
| start | 4 (CLEAR) | 3 | 3 | |||
| 1 | 0 | 0 | 0 | 3 | 6 = 0 0 | 3 |
| 2 | 0 | 1 | 0 | 3 | 7 = 0 1 | 3 |
| 3 | 1 | 1 | 1 | 3 | 8 = 1 1 | 4 (następny wolny 9 > 8) |
| 4 | 1 | 0 | 1 | 4 | 9 = 1 0 | 4 |
| 5 | 0 | 3 | 0 | 4 | 10 = 0 3 | 4 |
| 6 | 3 | 3 | 3 | 4 | 11 = 3 3 | 4 |
| 7 | 3 | 1 | 3 | 4 | 12 = 3 1 | 4 |
| koniec | 1 | 1 | 4 | |||
| 5 (END) | 4 |
Żaden z dopisanych wpisów nie został użyty, bo obraz jest za krótki, żeby ciągi zdążyły się powtórzyć. Dlatego 8 pikseli po 2 bity (16 bitów) zamieniło się w 36 bitów: kompresja zwiększyła dane. Przy prawdziwych obrazach słownik szybko się zapełnia długimi ciągami i jeden kod obejmuje wiele pikseli.
Pakowanie bitów
W każdym bajcie wcześniejszy kod zajmuje młodsze bity, więc czytając bajt od lewej, widzi się kody od końca. Na przykład bajt 1 to: 4 bity drugiego kodu 1 (0001), 3 bity pierwszego kodu 1 (001) i najstarszy bit kodu 0, który zaczął się w bajcie 0 (0).
Koder
// data: indeksy pikseli, wynik: bajty LZW (przed podziałem na podbloki)
function gifLzwEncode(data, minCodeSize) {
const clear = 1 << minCodeSize, eoi = clear + 1;
let width, next, dict;
const reset = () => { width = minCodeSize + 1; next = eoi + 1; dict = new Map(); };
const bytes = [];
let acc = 0, bits = 0;
const emit = (code) => {
acc |= code << bits; bits += width;
while (bits >= 8) { bytes.push(acc & 255); acc >>= 8; bits -= 8; }
};
reset();
emit(clear);
let w = data[0];
for (let i = 1; i < data.length; i++) {
const c = data[i];
const key = w * 256 + c;
if (dict.has(key)) { w = dict.get(key); continue; }
emit(w);
dict.set(key, next++);
if (next > 1 << width && width < 12) width++;
if (next === 4096) { emit(clear); reset(); } // słownik pełny: zacznij od nowa
w = c;
}
emit(w);
emit(eoi);
if (bits > 0) bytes.push(acc & 255);
return bytes;
}
gifLzwEncode([0, 0, 1, 1, 0, 3, 3, 1], 2); // [0x04, 0x12, 0x30, 0x13, 0x05]Koder przetestowano na losowych obrazach do 256 × 256 pikseli i 256 kolorów, także z wielokrotnym zapełnieniem słownika. Pliki odczytuje bez błędów niezależny dekoder systemowy.