Egftnjytyk

LZ78 – sł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" (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).

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 S{displaystyle S} zawierający n{displaystyle n} symboli.

1. Wyczyść słownik.


2. 
   i:=0{displaystyle i:=0} (i{displaystyle i} – indeks pierwszego, nieprzetworzonego symbolu w S{displaystyle S}).


3. Dopóki i<n{displaystyle i<n}, wykonuj:
   
   1. Wyszukaj w słowniku najdłuższy podciąg równy początkowi nieprzetworzonych jeszcze symboli (podciąg S[i…]{displaystyle S[ildots ]}).
      
      
      
      • Jeśli udało się znaleźć taki podciąg, to wynikiem wyszukiwania jest jego indeks k{displaystyle k} w słowniku; dodatkowo słowo wskazywane przez ten indeks ma pewną długość m{displaystyle m}. Na wyjście wypisz parę (indeks, pierwszy niedopasowany symbol), czyli (k{displaystyle k}, S[i+m]{displaystyle S[i+m]}) oraz dodaj do słownika znaleziony podciąg przedłużony o symbol S[i+m]{displaystyle S[i+m]} (innymi słowy podciąg S[i…i+m]{displaystyle S[ildots i+m]}). Zwiększ i:=i+m{displaystyle 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]{displaystyle S[i]}. Wówczas do słownika dodawany jest ten symbol, a na wyjście wypisywana para (0{displaystyle 0}, S[i]{displaystyle S[i]}). Indeks 0 jest tutaj umowny, w ogólnym przypadku chodzi o jakąś wyróżnioną liczbę. Zwiększ i{displaystyle 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 |

1. Wyczyść słownik.


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

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.

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


• Sequitur