[Algorytm] LZW

0

Witam. Może mi ktoś wyjaśnić jak przebiega kompresja LZW? Pare godzin szukałem jakiegoś sensownego wytłumaczenia działania tego algorytmu i nie znalazłem nic godnego uwagi...
Może najpierw powiem co wyczytałem

  1. Wiem, że algorytm LZW grupuje powtarzające się ciągi znaków (ja chcę wykorzystać ten algorytm do kompresji GIF tak więc w tym przypadku będą to liczby z zakresu od 0 do 255 gdyz tyle pozycji ma max paleta kolorow)
  2. Podobno trzeba utworzyć jakiś słownik, który będzie przechowywał jakieś pary ale jakie to ja juz nie mam pojecia...
  3. zreszta co ja będe pisał i tak nic nie rozumiem... :P

Błagam wyjaśnijcie mi to :)

0

Hmm...

STRING = get input character
WHILE there are still input characters DO
CHARACTER = get input character
IF STRING+CHARACTER is in the string table then
STRING = STRING+character
ELSE
output the code for STRING
add STRING+CHARACTER to the string table
STRING = CHARACTER
END of IF
END of WHILE
output the code for STRING

Może na poączatek co to jest "string table", czy jest to zmienna STRING, czy może jakaś inna zmienna która będzie zawierała skompresowane dane?

0

Jesli piszesz cos w rodzaju biblioteki do wyswietlania GIFow, to od razu uprzedzam - algorytm LZW jest licencjonowany - nie mozna go uzywac w celach komercyjnych bez odpowiedniej zgody. Jesli chodzi o szczegoly, to ja nic nie wiem :).

0

Nie zamierzam tego sprzedawac, a jesli juz bym mial taki zamiar to pomysle nad wykupieniem licencji :P

Znalazlem w necie cos takiego
user image

I mam odnosnie tego kilka pytań:

  1. "N = ilość elementów podstawowych". Co to są elementy podstawowe? Wydaje mi się że jest to ciąg znaków na wejściu czyli tekst który chcę skompresować (ewentualnie pixele). Dobrze mi się wydaje?
  2. Co to za funkcja output(); ? Co ona ma niby robić?
  3. Co to za funkcja inc(); ?
  4. Załóżmy, że N było równe 9 (a zmiennej "i" przypisalismy wartosc zmiennej "N"). A w dalszej części przykładu jest napisane T[i] := ... Po co następuje w takim przypadku zapisanie do 9 elementu tablicy ? 9 wcześniejszych pozostaje niewykorzystana? Zapewne coś źle rozumiem i być może tam znajdują się jakieś dane ale na tym etapie rozumowania nie wydaje mi się żeby coś tam było.

pomoze ktos ? :(

0

Przejrzyj tą stronę i obowiązkowo przeanalizuj sobie podany przykład: http://www.cs.cf.ac.uk/Dave/Multimedia/node214.html

0

Spozniles sie pare dni bo kompresje juz rozumiem, jedynie z czym mam problem i w czym moze mi pomozesz to to jak odbudowac slownik przy dekompresji. Mianowicie jesli w skompresowanym ciagu wystapi kod o numerze wiekszym niz maxymalna ilosc kolorow to nie wiem skad niby mam wiedziec co pod danym kodem sie kryje... nie wiem czy wystarczajaco jasno sie wyrazilem. po prostu nie wiem jak odbudowac ciag znakow dla danego kodu... Aha i jeszcze jedno pytanko bo czytalem ze kod moze byc maxymalnie dlugosci 4 bitów a min 1 bitu. Tylko teraz kwestia tego skad mam wiedziec jak akurat zostalo to zakodowane, czy przy uzyciu 1,2,3 czy 4 bitow i w jaki sposob najlepiej wczytywac te kody? Bo nie ma typu ktory wczytywalby tylko 4 bity...

0

Zajrzyj na http://www.dogma.net/markn/articles/lzw/lzw.htm jeśli nie przeszkadza Ci C++.. masz tam przykład programu do kompresji i osobnego do dekompresji. Napisany prostym i przejrzystym językiem.

Osobiście polecam taką metodę:

Każdy bajt kodujesz na przykład 12 bitami (lub 14 jeśli to duży strumień do kompresji). Jeśli na wejściu pojawia się coś czego nie ma w słowniku, dodajesz to do niego i dajesz na wyjście w postaci (cztery bity - zera) + (8 bitów z kodowanego bajtu) = (12 bit). Jeśli coś ze słownika dasz na wyjście, to kod tego będzie na pewno większy niż 255 czyli 8 bitów jedynek, przez co wejdzie na któreś z czterech starszych bitów.

Jeśli teraz odkodowujesz, to na początku pliku (czytając po 12, lub jeśli założono inaczej np.: 14 bitów) na pewno trafisz na znaki w postaci standardowych (cztery bity zer)+(8 bitów znaku). To traktujesz jakbyś dodawał do słownika dekompresji. Więc jeśli dekompresujesz i trafisz na 12 bitów niestandardowych to na pewno, jeśli dobrze zrobiłeś, w słowniku dekompresji taki kod się już pojawił.

0

Patent na LZW już wygasł.
GIF'y moZna podobno zapisywać jako nieskompresowane. Jeżeli zależy Ci na kompresji to wybierz format PNG (i oczywiście bliblitekę libpng) - oferuje dużo lepszy stopień kompresji. Dodoatkowo PNG'i możesz skompresować lepiej programeme pngout ze strony http://www.advsys.net/ken/

Informacje nt. LZW możesz znaleźć na http://www.arturocampos.com/

0
donkey7 napisał(a)

Patent na LZW już wygasł.
GIF'y moZna podobno zapisywać jako nieskompresowane. Jeżeli zależy Ci na kompresji to wybierz format PNG (i oczywiście bliblitekę libpng) - oferuje dużo lepszy stopień kompresji. Dodoatkowo PNG'i możesz skompresować lepiej programeme pngout ze strony http://www.advsys.net/ken/

Informacje nt. LZW możesz znaleźć na http://www.arturocampos.com/

z tego co wiem to wygasł w większości krajów patent UniSys'u. W wielu krajach patent IBM jest nadal aktualny. Nie wiem jak jest w Polsce

0

Mam pytanie, jeśli mam skompresowany ciag danych... i teraz chce go zdekompresować, to skąd mam wiedzieć na ilu bitach zapisane sa te indexy ze słownika... i jak mam odbudować z powrotem słownik... bo nie kapuje tego. Jeśli mam naprzyklad liczbe 258 to jest to informacja ze jest to kod a nie kolor z tablicy kolorow, no dobra ale jak teraz odszukac wartosc dla tego kodu... ?

0

Ilość bitów jest narzucona danemu zostosowaniu (musisz poszukać). Jeśli masz liczbę 258, to oznacza, że już wcześniejsze bajty stworzyły Ci słownik, który ma przynajmniej 3 pozycje (lub jak kto woli 258, przy założeniu, że pojedyncze znaki są w słowniku na starcie).

Odczytując pierwszy kolor (przykładowo: 200), jest on już w słowniku. Czytasz następny (192). Do słownika dodajesz 256 = (200 192), a więc następny znak na jaki trafisz może mieć maksymalnie wartość 256, bo na tym etapie tylko tyle symboli znasz. Im więcej przeczytasz symboli, tym słownik dekompresji ci się bardziej rozwinie, tym większy zakres symboli będziesz mógł dalej spotkac.

//Szczegółowe info o GIF: http://www.daubnet.com/formats/GIF.html

Ze strony:

colordepth codesize
8 9
7 8
6 7
5 6
4 5
3 4
2 3
1 3

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