Wolna encyklopedia

LZ78 jest nazwą słownikowej metody bezstratnej kompresji danych. Została opracowana w 1978 roku przez J. Ziva i A. Lempela i opisana w IEEE Transactions on Information Theory, w artykule pt. "Compression of individual sequences via variable-rate encoding" (str. 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).

Panowie Ziv i Lempel 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 rozszerzany w miarę potrzeb i żaden ciąg występujący w przetwarzanych 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 najpowszechniej używany jest wariant LZ78 nazywany LZW.

Algorytm kompresji

Kompresowany jest ciąg S zawierający n symboli.

1. Wyczyść słownik.
2. i: = 0 (i - indeks pierwszego, nieprzetworzonego symbolu w S).
3. Dopóki i < n wykonuj:
   1. 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 k w słowniku; dodatkowo słowo wskazywane przez ten indeks ma pewną długość m. Na wyjście wypisz parę (indeks, pierwszy niedopasowany symbol), czyli (k, S[i + m]) oraz dodaj do słownika znaleziony podciąg przedłużony o symbol S[i + m] (innymi słowy podciąg ). Zwiększ i: = i + m.
      • Jeśli nie udało się znaleźć żadnego podciągu, to znaczy, że w słowniku nie ma jeszcze symbolu S[i]. Wówczas do słownika dodawany jest ten symbol, a na wyjście wypisywana para (0, S[i]). Indeks 0 jest tutaj umowny, w ogólnym przypadku chodzi o jakąś wyróżnioną liczbę. Zwiększ i o jeden!

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.

Algorytm dekompresji

1. Wyczyść słownik.
2. Dla wszystkich par (indeks, symbol - ozn. k, s) wykonuj:
   1. Jeśli k = 0 dodaj symbol s do słownika. Na wyjście wypisz symbol s.
   2. Jeśli k > 0 weź ze słownika słowo w spod indeksu k. Na wyjście wypisz słowo w oraz symbol s. Do słownika pod kolejnym indeksem dodaj słowo w + s.

Przykład kompresji

Zostanie skompresowany ciąg: abbbcaabbcbbcaaac.

Można zauważyć, że do słownika dodawane są coraz dłuższe słowa.

Przykład dekompresji

Zostaną zdekompresowane dane z poprzedniego przykładu.

Przykładowy program

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!"

Bibliografia

• Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999. ISBN 83-204-2303-1. 

Linki zewnętrzne

• Jacob Ziv, Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding, IEEE Transactions on Information Theory, September 1978.

Zobacz też

• LZ77
• LZSS
• LZW