Kompresja LZW

0

Witajcie, mam pytanie związane z algorytmem kompresji LZW, a dokładniej z generowaniem słownika. Powiedziane jest, że algorytm ma kompresować 32 kolorowy obrazek używając 5-ciu bitów do zapisu jednego pixela. Właśnie z tymi pixelami mam mały problem.

Generując słownik na początku dodaję do niego wszystkie kolory (kolor zapisany na 3 bajtach -> jedna składowa RGB na 8 bitach) występujące w obrazku czyli mam już wykorzystane wszystkie kombinacje 5 bitów. Teraz muszę uzupełnić ten słownik zgodnie z działaniem algorytmu => generowanie kolorów, których ułożenie się powtarza. Jeżeli mam już wykorzystane wszystkie 5 bitów to kolejne słowa słownika będą miały po 6 i więcej bitów (ich generowanie będzie się odbywać poprzez dodanie 1 do wcześniejszej wartości kodu w słowniku), ale z drugiej strony będą opisywały więcej niż jeden pixel.
Czy mój tok rozumowania jest dobry?

1

LZW działa tak, że na początku lub tuż po resecie słownika (zakładając, że resetujesz co jakiś czas) w słowniku znajduje się cały alfabet (czyli np w przypadku kompresji jakichkolwiek plików przy ziarnistości jednego bajta słownik LZW będzie zawierał na starcie 256 jednobajtowych ciągów). Słowa kodowe mają taki rozmiar, by móc pomieścić indeks dowolnego ciągu ze słownika, a więc rozmiar słowa kodowego to ceil(log2(rozmiar_słownika)). Inaczej mówiąc, wraz ze zwiększaniem się rozmiaru słownika zwiększa się rozmiar słów kodowych. Rozmiar słowa kodowego zależy tylko od rozmiaru słownika, a nie od pozycji w słowniku, a więc jeśli w danym momencie zakodowałeś ciąg piąty ośmioma bitami, to w którymś późniejszym momencie na ten sam ciąg możesz już np potrzebować trzynastu bitów.

LZW niekoniecznie zawsze musi prowadzić do kompresji. Jeżeli w danym momencie w słowniku nie ma długiego pasującego wpisu, a słowa kodowe nabrały sporych rozmiarów to następuje ekspansja w danym miejscu. Jeżeli takich miejsc jest dużo to następuje ekspansja całego strumienia.

0

@Wibowit dziękuję za zainteresowanie :)
Zdaję sobię sprawę z tego, że LZW nie zawsze prowadzi do kompresji. Moje pytanie jest już nieważne, ponieważ zamysł był taki, żeby słowo wejściowe miało 5 bitów (32 kolory). Wydawało mi się to niemożliwe żeby każdy indeks ze słownika miał max 5 bitów, ale teraz jestem już tego pewien.

Jeszcze raz dziękuję :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1