LZ78

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 $S$ zawierający $n$ symboli.

Wyczyść słownik.
$i:=0$ ( $i$ – indeks pierwszego, nieprzetworzonego symbolu w $S$ ).
Dopóki $i<n,$ $i<n,$ wykonuj:
1. Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych jeszcze symboli (podciąg $S[i\ldots ]$ $S[i\ldots ]$ ).
  - 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 $S[i\ldots i+m]$ ). 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.

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. $k,$ $k,$ $s$ $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.$

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
wejście	wyjście	indeks	słowo	komentarz
`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
wejście	wyjście	indeks	słowo	komentarz
(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.