Tekst źródłowy strony LZ78

'''LZ78''' – [[tablica asocjacyjna|słownikowa]] metoda [[kompresja bezstratna|bezstratnej kompresji]] danych. Została opracowana w 1978 roku przez [[Ja’akow Ziw|Ja’akowa Ziwa]] i [[Awraham Lempel|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 (informatyka)|drzewo]] ([[drzewo binarne|binarne]], [[drzewo trie|trie]]) albo [[Tablica mieszająca|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 <math>S</math> zawierający <math>n</math> symboli.

# Wyczyść słownik.
# <math>i := 0</math> (<math>i</math> – indeks pierwszego, nieprzetworzonego symbolu w <math>S</math>).
# Dopóki <math>i < n,</math> wykonuj:
## Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych jeszcze symboli (podciąg <math>S[i\ldots]</math>).
##* Jeśli udało się znaleźć taki podciąg, to wynikiem wyszukiwania jest jego indeks <math>k</math> w słowniku; dodatkowo słowo wskazywane przez ten indeks ma pewną długość <math>m.</math> Na wyjście wypisz parę (indeks, pierwszy niedopasowany symbol), czyli (<math>k,</math> <math>S[i+m]</math>) oraz dodaj do słownika znaleziony podciąg przedłużony o symbol <math>S[i+m]</math> (innymi słowy podciąg <math>S[i\ldots i+m]</math>). Zwiększ <math>i := i + m.</math>
##* Jeśli nie udało się znaleźć żadnego podciągu, to znaczy, że w słowniku nie ma jeszcze symbolu <math>S[i].</math> Wówczas do słownika dodawany jest ten symbol, a na wyjście wypisywana para (<math>0,</math> <math>S[i]</math>). Indeks 0 jest tutaj umowny, w ogólnym przypadku chodzi o jakąś wyróżnioną liczbę. Zwiększ <math>i</math> 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 ==
# Wyczyść słownik.
# Dla wszystkich par (indeks, symbol – ozn. <math>k,</math> <math>s</math>) wykonuj:
## Jeśli <math>k = 0,</math> dodaj symbol <math>s</math> do słownika. Na wyjście wypisz symbol <math>s.</math>
## Jeśli <math>k > 0,</math> weź ze słownika słowo <math>w</math> spod indeksu <math>k.</math> Na wyjście wypisz słowo <math>w</math> oraz symbol <math>s.</math> Do słownika pod kolejnym indeksem dodaj słowo <math>w+s.</math>

== 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), [[LZMW|LZAP]] (1988) – modyfikacja LZW

== Przykład kompresji ==
Zostanie skompresowany ciąg: <code>abbbcaabbcbbcaaac</code>.

{| class="wikitable"
|-
!rowspan="2"| wejście
!rowspan="2"| wyjście
!colspan="2"| SŁOWNIK
!rowspan="2"| komentarz
|-
! indeks
! słowo
|-
| <code>a</code> || (0,<code>a</code>) || 1 || <code>a</code>
| w słowniku nie ma symbolu <code>a</code>
|-
| <code>b</code> || (0,<code>b</code>) || 2 || <code>b</code>
| w słowniku nie ma symbolu <code>b</code>
|-
| <code>bb</code> || (2,<code>b</code>) || 3 || <code>bb</code>
| w słowniku jest ciąg <code>b</code> (indeks 2), nie ma natomiast <code>bb</code>; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo <code>bb</code>
|-
| <code>c</code> || (0,<code>c</code>) || 4 || <code>c</code>
| w słowniku nie ma symbolu <code>c</code>
|-
| <code>aa</code> || (1,<code>a</code>) || 5 || <code>aa</code>
| w słowniku jest ciąg <code>a</code> (indeks 1), nie ma natomiast <code>aa</code>; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo <code>aa</code>
|-
| <code>bbc</code> || (3,<code>c</code>) || 6 || <code>bbc</code>
| w słowniku jest ciąg <code>bb</code> (indeks 3), nie ma natomiast <code>bbc</code>; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo <code>bbc</code>
|-
| <code>bbca</code> || (6,<code>a</code>) || 7
| <code>bbca</code>
| w słowniku jest ciąg <code>bbc</code> (indeks 6), nie ma natomiast <code>bbca</code>; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo <code>bbca</code>
|-
| <code>aac</code> || (5,<code>c</code>) || 8 || <code>aac</code>
| w słowniku jest ciąg <code>aa</code> (indeks 5), nie ma natomiast <code>aac</code>; na wyjście zapisywana jest para (istniejące słowo, symbol), a do słownika dodawane nowe słowo <code>aac</code>
|}

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.

{| class="wikitable"
|-
!rowspan="2"| wejście
!rowspan="2"| wyjście
!colspan="2"| SŁOWNIK
!rowspan="2"| komentarz
|-
! indeks
! słowo
|-
| (0,<code>a</code>) || <code>a</code> || 1 || <code>a</code>
| symbol <code>a</code> jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy <code>a</code>
|-
| (0,<code>b</code>) || <code>b</code> || 2 || <code>b</code>
| symbol <code>b</code> jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy <code>b</code>
|-
| (2,<code>b</code>) || <code>bb</code> || 3 || <code>bb</code>
| na wyjście wypisywane jest słowo <code>b</code> ze słownika (indeks 2), wypisywany jest także symbol <code>b</code>; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 2. i symbolu: <code>bb</code>
|-
| (0,<code>c</code>) || <code>c</code> || 4 || <code>c</code>
| symbol <code>c</code> jest wyprowadzany na wyjście, do słownika jest dodawany ciąg jednoelementowy <code>c</code>
|-
| (1,<code>a</code>) || <code>aa</code> || 5 || <code>aa</code>
| na wyjście wypisywane jest słowo <code>a</code> ze słownika (indeks 1), wypisywany jest także symbol <code>a</code>; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 1. i symbolu: <code>aa</code>
|-
| (3,<code>c</code>) || <code>bbc</code> || 6 || <code>bbc</code>
| na wyjście wypisywane jest słowo <code>bb</code> ze słownika (indeks 3), wypisywany jest także symbol <code>c</code>; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 2. i symbolu: <code>bbc</code>
|-
| (6,<code>a</code>) || <code>bbca</code> || 7
| <code>bbca</code>
| na wyjście wypisywane jest słowo <code>bbc</code> ze słownika (indeks 6), wypisywany jest także symbol <code>a</code>; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 6. i symbolu: <code>bbca</code>
|-
| (5,<code>c</code>) || <code>aac</code> || 8 || <code>aac</code>
| na wyjście wypisywane jest słowo <code>aa</code> ze słownika (indeks 5), wypisywany jest także symbol <code>c</code>; do słownika dodawany jest nowy ciąg będący sklejeniem słowa 5. i symbolu: <code>aac</code>
|}

== Przykładowy program ==
Poniższy program napisany w języku [[Python]] koduje dane metodą LZ78 (<code>LZ78_encode</code>), a następnie dekoduje (<code>LZ78_decode</code>) 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]]:

<pre>
$ 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%
</pre>

'''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.

<syntaxhighlight lang="python">
# -*- 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!"
</syntaxhighlight>

== Zobacz też ==
* [[LZ77]]
* [[LZSS]]
* [[LZW]]
* [[Sequitur]]

== Bibliografia ==
* {{Cytuj książkę |nazwisko = Drozdek |imię = Adam |tytuł = Wprowadzenie do kompresji danych |data = 1999 |wydawca = Wydawnictwa Naukowo-Techniczne |miejsce = Warszawa |isbn = 83-204-2303-1}}

== Linki zewnętrzne ==
* Jacob Ziv, Abraham Lempel; [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1978_variable-rate.pdf ''Compression of Individual Sequences Via Variable-Rate Coding''], IEEE Transactions on Information Theory, September 1978.

[[Kategoria:Algorytmy kompresji bezstratnej]]