LZ78 – Wikipedia, wolna encyklopedia
LZ78 – słownikowa metoda bezstratnej kompresji danych. Została opracowana w 1978 roku przez Ja’akowa Ziwa i Awrahama Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. „Compression of individual sequences via variable-rate encoding” (s. 530–536).
Kompresja polega na zastępowaniu ciągów symboli indeksami do słownika przechowującego ciągi symboli, które wcześniej wystąpiły w kompresowanych danych. Dzięki temu wielokrotnie powtarzające się ciągi symboli (np. te same słowa, czy frazy w tekście) są zastępowane o wiele krótszymi indeksami (liczbami).
Autorzy LZ78 rok wcześniej opracowali metodę LZ77, w której słownik miał stałą wielkość, co powodowało, że jego zawartość zmieniała się cały czas wraz z napływaniem nowych danych. Skutkiem tego, jeśli na wejściu powtórzył się pewien ciąg, który co prawda występował wcześniej, ale w słowniku już go nie było, musiał zostać zapamiętany raz jeszcze.
Ogólnie metoda LZ78 jest bardzo zbliżona do LZ77, z tym jednak wyjątkiem, że słownik jest zewnętrzny i rozszerzany w miarę potrzeb, tak że żaden ciąg występujący w przetworzonych już danych nie jest tracony. Dzięki temu uzyskuje się lepszy współczynnik kompresji kosztem skomplikowania dostępu do słownika – ze względu na szybkość dostępu do poszczególnych słów jest on realizowany jako drzewo (binarne, trie) albo tablica haszująca.
Dużą zaletą metody jest to, że potencjalnie bardzo dużego słownika w ogóle nie trzeba zapamiętywać – zostanie on odtworzony przez dekoder na podstawie zakodowanych danych (patrz: przykład dekompresji). Jednak pewną wadą jest praktycznie jednakowa złożoność kodu kompresującego i dekompresującego.
W praktyce powszechnie używany jest wariant LZ78 nazywany LZW.
Algorytm kompresji
[edytuj | edytuj kod]Kompresowany jest ciąg zawierający symboli.
- Wyczyść słownik.
- ( – indeks pierwszego, nieprzetworzonego symbolu w ).
- Dopóki wykonuj:
- Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych jeszcze symboli (podciąg ).
- Jeśli udało się znaleźć taki podciąg, to wynikiem wyszukiwania jest jego indeks w słowniku; dodatkowo słowo wskazywane przez ten indeks ma pewną długość Na wyjście wypisz parę (indeks, pierwszy niedopasowany symbol), czyli ( ) oraz dodaj do słownika znaleziony podciąg przedłużony o symbol (innymi słowy podciąg ). Zwiększ
- Jeśli nie udało się znaleźć żadnego podciągu, to znaczy, że w słowniku nie ma jeszcze symbolu Wówczas do słownika dodawany jest ten symbol, a na wyjście wypisywana para ( ). Indeks 0 jest tutaj umowny, w ogólnym przypadku chodzi o jakąś wyróżnioną liczbę. Zwiększ o jeden.
- Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych jeszcze symboli (podciąg ).
W praktycznych realizacjach słownik ma jednak ograniczoną wielkość – koder (i dekoder) różnie reaguje na fakt przepełnienia słownika; słownik może być:
- zerowany;
- dodawanie nowych słów zostaje wstrzymane;
- usuwane są te słowa, które zostały dodane najwcześniej;
- usuwane są te słowa, które występowały najrzadziej.
W uniksowym programie compress dodawanie słów zostaje wstrzymane, ale gdy współczynnik kompresji spadnie poniżej określonego poziomu, słownik jest zerowany.
Algorytm dekompresji
[edytuj | edytuj kod]- Wyczyść słownik.
- Dla wszystkich par (indeks, symbol – ozn. ) wykonuj:
- Jeśli dodaj symbol do słownika. Na wyjście wypisz symbol
- Jeśli weź ze słownika słowo spod indeksu Na wyjście wypisz słowo oraz symbol Do słownika pod kolejnym indeksem dodaj słowo
Modyfikacje algorytmu
[edytuj | edytuj kod]Metoda LZ78 na przestrzeni lat była ulepszana, oto lista najbardziej znaczących modyfikacji:
- LZW (Terry Welch, 1984), LZC (1985) – praktyczna implementacja LZW
- LZJ (Matti Jakobson, 1985)
- LZT (J. Tischer, 1987), modyfikacja LZW
- LZMW (1985), LZAP (1988) – modyfikacja LZW
Przykład kompresji
[edytuj | edytuj kod]Zostanie skompresowany ciąg: abbbcaabbcbbcaaac
.
wejście | wyjście | SŁOWNIK | komentarz | |
---|---|---|---|---|
indeks | słowo | |||
a | (0,a ) | 1 | a | w słowniku nie ma symbolu a |
b | (0,b ) | 2 | b | w słowniku nie ma symbolu b |
bb | (2,b ) | 3 | bb | w słowniku jest ciąg b (indeks 2), nie ma natomiast bb ; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo bb |
c | (0,c ) | 4 | c | w słowniku nie ma symbolu c |
aa | (1,a ) | 5 | aa | w słowniku jest ciąg a (indeks 1), nie ma natomiast aa ; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo aa |
bbc | (3,c ) | 6 | bbc | w słowniku jest ciąg bb (indeks 3), nie ma natomiast bbc ; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo bbc |
bbca | (6,a ) | 7 | bbca | w słowniku jest ciąg bbc (indeks 6), nie ma natomiast bbca ; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo bbca |
aac | (5,c ) | 8 | aac | w słowniku jest ciąg aa (indeks 5), nie ma natomiast aac ; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo aac |
Można zauważyć, że do słownika dodawane są coraz dłuższe słowa.
Przykład dekompresji
[edytuj | edytuj kod]Zostaną zdekompresowane dane z poprzedniego przykładu.
wejście | wyjście | SŁOWNIK | komentarz | |
---|---|---|---|---|
indeks | słowo | |||
(0,a ) | a | 1 | a | symbol a jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy a |
(0,b ) | b | 2 | b | symbol b jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy b |
(2,b ) | bb | 3 | bb | na wyjście wypisywane jest słowo b ze słownika (indeks 2), wypisywany jest także symbol b ; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 2. i symbolu: bb |
(0,c ) | c | 4 | c | symbol c jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy c |
(1,a ) | aa | 5 | aa | na wyjście wypisywane jest słowo a ze słownika (indeks 1), wypisywany jest także symbol a ; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 1. i symbolu: aa |
(3,c ) | bbc | 6 | bbc | na wyjście wypisywane jest słowo bb ze słownika (indeks 3), wypisywany jest także symbol c ; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 2. i symbolu: bbc |
(6,a ) | bbca | 7 | bbca | na wyjście wypisywane jest słowo bbc ze słownika (indeks 6), wypisywany jest także symbol a ; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 6. i symbolu: bbca |
(5,c ) | aac | 8 | aac | na wyjście wypisywane jest słowo aa ze słownika (indeks 5), wypisywany jest także symbol c ; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 5. i symbolu: aac |
Przykładowy program
[edytuj | edytuj kod]Poniższy program napisany w języku Python koduje dane metodą LZ78 (LZ78_encode
), a następnie dekoduje (LZ78_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 LZ78.py python-artykul.txt Liczba par: 6295 Maks. liczba bitów potrzebna do zapisania kodu: 13 Maks. liczba bitów potrzebna do zapisania pary: 13 + 8 = 21 Rozmiar danych wejściowych: 23805 bajtów Rozmiar danych skompresowanych: 16525 bajtów Stopień kompresji: 30.58%
Uwaga: 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 LZ78_encode(data): D = {} n = 1 c = '' result = [] for s in data: if c + s not in D: if c == '': # specjalny przypadek: symbol 's' # nie występuje jeszcze w słowniku result.append( (0, s) ) D[s] = n else: # ciąg 'c' jest w słowniku result.append( (D[c], s) ) D[c + s] = n n = n + 1 c = '' else: c = c + s return result def LZ78_decode(data): D = {} n = 1 result = [] for i, s in data: if i == 0: result.append(s) D[n] = s n = n + 1 else: result.append(D[i] + s) D[n] = D[i] + s n = n + 1 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 = LZ78_encode(data) decomp = LZ78_decode(comp) if data == decomp: k = len(comp) n = int(ceil(log(max(index for index, symbol in comp), 2.0))) l1 = len(data) l2 = (k*(n+8) + 7)/8 print "Liczba par: %d" % k print "Maks. liczba bitów potrzebna do zapisania kodu: %d" % n print "Maks. liczba bitów potrzebna do zapisania pary: %d + %d = %d" % (n, 8, n+8) 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!"
Zobacz też
[edytuj | edytuj kod]Bibliografia
[edytuj | edytuj kod]- Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999. ISBN 83-204-2303-1.
Linki zewnętrzne
[edytuj | edytuj kod]- Jacob Ziv, Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding, IEEE Transactions on Information Theory, September 1978.