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