LZW
Z Wikipedii
Lempel-Ziv-Welch (skracane zwykle do LZW) – metoda strumieniowej bezstratnej kompresji słownikowej, będąca modyfikacją metody LZ78.
Pomysłodawcą algorytmu jest Terry A. Welch. Metodę opisał w 1984 roku, w artykule "A technique for high-performance data compression" opublikowanym w numerze 6. Computer (str. 8-19).
Metoda LZW jest względnie łatwa do zaprogramowania, daje bardzo dobre rezultaty. Wykorzystywany jest m.in. w programach ARC, PAK i UNIX-owym compress, w formacie zapisu grafiki GIF, w formatach PDF i Postscript (filtry kodujące fragmenty dokumentu) oraz w modemach (V.32bis). LZW było przez pewien czas algorytmem objętym patentem, co było przyczyną podjęcia prac nad nowym algorytmem kompresji obrazów, które zaowocowały powstaniem formatu PNG.
Spis treści |
[edytuj] Zmiany w stosunku do LZ78
Przewaga LZW nad LZ78 to krótsze wyjście kodera: w metodzie LZ78 na wyjście wypisywane są pary (kod, symbol s), w metodzie LZW wypisuje się tylko kod.
Uzyskano to dzięki pierwszemu etapowi algorytmu, tj. wstępnemu wypełnieniu słownika alfabetem (wszystkimi symbolami). W metodzie LZ78 słownik początkowo jest pusty i przy kodowaniu trzeba brać pod uwagę, czy wczytany symbol s znajduje się w słowniku, czy może pojawił się po raz pierwszy.
[edytuj] Algorytm kompresji (kodowania)
- Wypełnij słownik alfabetem źródła informacji.
- c := pierwszy symbol wejściowy
- Dopóki są dane na wejściu:
- Wczytaj znak s.
- Jeżeli ciąg c + s znajduje się w słowniku, przedłuż ciąg c, tj. c := c + s
- Jeśli ciągu c + s nie ma w słowniku, wówczas wypisz kod dla c (c znajduje się w słowniku), dodaj ciąg c + s do słownika oraz przypisz c := s.
- Wypisz na wyjście kod związany c.
O efektywności kompresji w dość dużym stopniu decyduje sposób zapisu kodów (liczb).
Przykład: Dla ciągu abccd_abccd_acd_acd_acd_ mamy słownik:
-
- 1. a
- 2. b
- 3. c
- 4. d
- 5. _
- 6. ab
- 7. bc
- 8. cc
- 9. cd
- 10. d_
- 11. _a
- 12. abc
- 13. ccd
- 14. d_a
- 15. ac
- 16. cd_
- 17. _ac
- 18. cd_a
- 19. acd
Słowa mają numery od 1 do 19. Numery od 1 do 5 to słowa wchodzące w skład podstawowego słownika języka utworzonego na początku.
I zakodowany ciąg:
1 2 3 3 4 5 6 8 10 1 9 11 16 15 10
[edytuj] Algorytm dekompresji
Algorytm dekompresji jest nieco bardziej złożony, bowiem dekoder musi wykryć przypadki ciągów scscs (które nie znajdują się w słowniku), gdzie ciąg sc jest już w słowniku, a podciąg c jest dowolny, być może także pusty.
- Wypełnij słownik alfabetem źródła informacji.
- pk := pierwszy kod skompresowanych danych
- Wypisz na wyjście ciąg związany z kodem pk, tj. słownik[pk]
- Dopóki są jeszcze jakieś słowa kodu:
- Wczytaj kod k
- pc := słownik[pk] - ciąg skojarzony z poprzednim kodem
- Jeśli słowo k jest w słowniku, dodaj do słownika ciąg (pc + pierwszy symbol ciągu słownik[k]), a na wyjście wypisz cały ciąg słownik[k].
- W przeciwnym razie (przypadek scscs) dodaj do słownika ciąg (pc + pierwszy symbol pc) i tenże ciąg wypisz na wyjście.
- pk := k
[edytuj] Przykładowy program
Poniższy program napisany w języku Python koduje dane metodą LZW (LZW_encode) a następnie dekoduje (LZW_decode) i na końcu stwierdza, czy proces kodowania i dekodowania przebiegł prawidłowo, wyświetlając przy okazji podsumowanie.
Przykładowe wynik działania programu, gdy kompresji zostało poddane źródło artykułu Python:
$ python LZW.py python-artykul.txt Liczba kodów: 8297 Maks. liczba bitów potrzebna do zapisania kodu: 14 Rozmiar danych wejściowych: 23805 bajtów Rozmiar danych skompresowanych: 14520 bajtów Stopień kompresji: 39.00%
Uwaga: jak wspomniano stopień kompresji zależy również od sposobu zapisu kodów - w tym programie do obliczeń rozmiaru danych skompresowanych i stopnia kompresji założono, że każdy kod zajmuje stałą liczbę bitów. W praktycznych aplikacjach rozwiązania mogą być inne.
# -*- coding: iso-8859-2 -*- def LZW_encode(data): # krok. 1 D = {} # D - słownik: ciąg -> kod n = 0 # n - kod ciągu (liczba) for i in xrange(256): D[chr(i)] = n n = n + 1 # krok 2. c = data[0] result = [] # krok 3. for s in data[1:]: if c + s in D: # przypadek 1. (c+s w słowniku) c = c + s else: # przypadek 2. result.append(D[c]) D[c + s] = n n = n + 1 c = s # krok 4. result.append(D[c]) # zwrócenie wyniku return result def LZW_decode(data): # krok 1. D = {} # D - słownik: kod -> ciąg n = 0 # n - kod ciągu (liczba) for i in xrange(256): D[n] = chr(i) n = n + 1 # krok 2. pk = data[0] # krok 3. result = [D[pk]] # krok 4. for k in data[1:]: pc = D[pk] if k in D: # przypadek pierwszy: D[k] istnieje D[n] = pc + D[k][0] n = n + 1 result.append(D[k]) else: # przypadek specjalny: dekodowany jest # ciąg postaci scscs D[n] = pc + pc[0] n = n + 1 result.append( pc + pc[0] ) pk = k return ''.join(result) if __name__ == '__main__': import sys from math import log, ceil if len(sys.argv) < 2: print "Podaj nazwę pliku" sys.exit(1) data = open(sys.argv[1]).read() comp = LZW_encode(data) decomp = LZW_decode(comp) if data == decomp: k = len(comp) n = int(ceil(log(max(comp), 2.0))) l1 = len(data) l2 = (k*n + 7)/8 print "Liczba kodów: %d" % k print "Maks. liczba bitów potrzebna do zapisania kodu: %d" % n print "Rozmiar danych wejściowych: %d bajtów" % l1 print "Rozmiar danych skompresowanych: %d bajtów" % l2 print "Stopień kompresji: %.2f%%" % (100.0*(l1-l2)/l1) # print data # print decomp else: print "Wystąpił jakiś błąd!"
[edytuj] Bibliografia
- Adam Drozdek, Wprowadzenie do kompresji danych, WNT 1999
[edytuj] Zobacz też
[edytuj] Linki zewnętrzne
- http://www.cs.duke.edu/courses/spring03/cps296.5/papers/welch_1984_technique_for.pdf - skan artykułu Terrego A. Welcha
