Kompresja LZW

Odpowiedz Nowy wątek
2014-12-21 11:57
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?

edytowany 1x, ostatnio: bryla33, 2014-12-21 11:58

Pozostało 580 znaków

2014-12-21 16:39

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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2014-12-21 16:41

Pozostało 580 znaków

2014-12-23 11:16
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ę :)

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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