LZ78

LZ78słownikowa metoda bezstratnej kompresji danych. Została opracowana w 1978 roku przez Jacoba Ziva i Abrahama 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

Kompresowany jest ciąg zawierający symboli.

  1. Wyczyść słownik.
  2. ( – indeks pierwszego, nieprzetworzonego symbolu w ).
  3. Dopóki 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 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.

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

  1. Wyczyść słownik.
  2. Dla wszystkich par (indeks, symbol – ozn. ) wykonuj:
    1. Jeśli dodaj symbol do słownika. Na wyjście wypisz symbol
    2. 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

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

Zostanie skompresowany ciąg: abbbcaabbcbbcaaac.

wejściewyjścieSŁOWNIKkomentarz
indekssłowo
a(0,a)1aw słowniku nie ma symbolu a
b(0,b)2bw słowniku nie ma symbolu b
bb(2,b)3bbw 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)4cw słowniku nie ma symbolu c
aa(1,a)5aaw 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)6bbcw 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)7bbcaw 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)8aacw 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

Zostaną zdekompresowane dane z poprzedniego przykładu.

wejściewyjścieSŁOWNIKkomentarz
indekssłowo
(0,a)a1asymbol a jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy a
(0,b)b2bsymbol b jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy b
(2,b)bb3bbna 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)c4csymbol c jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy c
(1,a)aa5aana 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)bbc6bbcna 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)bbca7bbcana 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)aac8aacna 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

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ż

Bibliografia

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

Linki zewnętrzne