WikiPortallus: LZW.html

Lempel-Ziv-Welch (skracane zwykle do LZW) – metoda strumieniowej bezstratnej kompresji słownikowej, będąca modyfikacją metody LZ78.

Pomysłodawcą algorytmu jest Terry A. Welch. Metodę opisał w 1984 roku, w artykule "A technique for high-performance data compression" opublikowanym w numerze 6. Computer (str. 8-19).

Metoda LZW jest względnie łatwa do zaprogramowania, daje bardzo dobre rezultaty. Wykorzystywany jest m.in. w programach ARC, PAK i UNIX-owym compress, w formacie zapisu grafiki GIF, w formatach PDF i Postscript (filtry kodujące fragmenty dokumentu) oraz w modemach (V.32bis). LZW było przez pewien czas algorytmem objętym patentem, co było przyczyną podjęcia prac nad nowym algorytmem kompresji obrazów, które zaowocowały powstaniem formatu PNG.

edytuj Zmiany w stosunku do LZ78

Przewaga LZW nad LZ78 to krótsze wyjście kodera: w metodzie LZ78 na wyjście wypisywane są pary (kod, symbol s), w metodzie LZW wypisuje się tylko kod.

Uzyskano to dzięki pierwszemu etapowi algorytmu, tj. wstępnemu wypełnieniu słownika alfabetem (wszystkimi symbolami). W metodzie LZ78 słownik początkowo jest pusty i przy kodowaniu trzeba brać pod uwagę, czy wczytany symbol s znajduje się w słowniku, czy może pojawił się po raz pierwszy.

edytuj Algorytm kompresji (kodowania)

W pojedynczym kroku algorytmu wyszukiwany jest w słowniku najdłuższy prefiks niezakodowanych jeszcze danych. Na wyjście wypisywany jest wówczas kod związany z tym słowem, zaś do słownika dodawana nowa pozycja: konkatenacja słowa i pierwszej niedopasowanej litery.

O efektywności kompresji w dość dużym stopniu decyduje sposób zapisu kodów (liczb).

edytuj Algorytm dekompresji

Algorytm dekompresji jest nieco bardziej złożony, bowiem dekoder musi wykryć przypadki ciągów scscs (które nie znajdują się w słowniku), gdzie ciąg sc jest już w słowniku, a podciąg c jest dowolny, być może także pusty.

edytuj Modyfikacje algorytmu

edytuj Przykład kompresji

Zostanie zakodowany ciąg składający się z 24 znaków: "abccd_abccd_acd_acd_acd_".

Zakodowane dane składają się z 15 indeksów: 1, 2, 3, 3, 4, 5, 6, 8, 10, 1, 9, 11, 16, 15, 10.

Jeśli przyjąć, że indeksy oraz symbole są zapisane na tej samej liczbie bitów, to współczynnik kompresji wyniesie ok. 37%. Jeśli natomiast przyjąć minimalną liczbę bitów potrzebną do zapisania danych, tj. 3 bity na symbol (w sumie 72 bity), 4 na indeks (w sumie 60 bitów), współczynnik kompresji wyniesie ok. 15%.

edytuj Przykładowy program

Poniższy program napisany w języku Python koduje dane metodą LZW (LZW_encode) a następnie dekoduje (LZW_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:

Uwaga: jak wspomniano 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 LZW_encode(data):
 
	# krok. 1
	D = {}	# D - słownik: ciąg -> kod
	n = 0	# n - kod ciągu (liczba)
	for i in xrange(256):
		Dchr(i) = n
		n = n + 1
 
	# krok 2.
	c = data0
	result = 
 
	# krok 3.
	for s in data1::
		if c + s in D:
			# przypadek 1. (c+s w słowniku)
			c = c + s
		else:
			# przypadek 2.
			result.append(Dc)
			Dc + s = n
			n = n + 1
			c = s
 
	# krok 4.
	result.append(Dc)
 
	# zwrócenie wyniku
	return result
 
 
def LZW_decode(data):
	# krok 1.
	D = {}	# D - słownik: kod -> ciąg
	n = 0	# n - kod ciągu (liczba)
	for i in xrange(256):
		Dn = chr(i)
		n = n + 1
 
	# krok 2.
	pk = data0
 
	# krok 3.
	result = Dpk
 
	# krok 4.
	for k in data1::
		pc = Dpk
		if k in D:
			# przypadek pierwszy: D[k] istnieje
			Dn = pc + Dk0
			n = n + 1
			result.append(Dk)
		else:
			# przypadek specjalny: dekodowany jest
			# ciąg postaci scscs
			Dn = pc + pc0
			n = n + 1
			result.append( pc + pc0 )
		pk = k
 
	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.argv1).read()
	comp   = LZW_encode(data)
	decomp = LZW_decode(comp)
 
	if data == decomp:
		k  = len(comp)
		n  = int(ceil(log(max(comp), 2.0)))
 
		l1 = len(data)
		l2 = (k*n + 7)/8
 
		print "Liczba kodów: %d" % k
		print "Maks. liczba bitów potrzebna do zapisania kodu: %d" % n
		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!"

LZW.html

Spis treści

edytuj Zmiany w stosunku do LZ78

edytuj Algorytm kompresji (kodowania)

edytuj Algorytm dekompresji

edytuj Modyfikacje algorytmu

edytuj Przykład kompresji

edytuj Przykładowy program

edytuj Bibliografia

edytuj Zobacz też

edytuj Linki zewnętrzne