LZW (Lempel-Ziv-Welch)

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

A pszeudókódok forrása: http://www.dogma.net/markn/articles/lzw/lzw.htm (© miatt :))

LZW betömörítés

Informálisan

Adott a kezdeti nehany kod. Elkezded olvasni azt amt kodolni akarsz. Ha latod,hogy olyan van amit ismersz akkor annak atkuldod a jelet, majd hozzaveszed a kov karaktert es a ket betunek egy uj kodot adsz, majd mesz tovabb. Ha latod ezt a ket betut akkor hazsnalod az uj hozzarednelt kodot es a kovetkezot veszed hozza. Nagyon egyszeru pelda: a-1,b-2,c-3 Szo: abbcbbbabb Elso betu: "a" , kiadjuk az 1et. Megnezzuk mi a kov betu : "b" ok akkor kiadjuk a "b"-t es az "ab"-t felvesszuk mint 4es kod. Utana "b" jon, es kiadjuk a "b" kodjat a 2-t,de mivel ismerjuk az elozo b-t igy a bb-t felveszuk mint 5. utana "c" jon, kiadjuk a 3-t, felvesszuk a "bc"-t mint 6-os kod. Utana lass csodat "bb" jon, ami mar szerepel, ezert kiadjuk a 5-t es hozzaveszsuk a kov karaktert ami nem mas mint "bbb" ez legyen 7es kod. A 2 "b" utan jon egy harmadik, ezt kiadjuk mint 2, utana jon egy "a" ezert felvesszuk mint "ba" 8as koddal. Azutan jon az "a" de mogotte b van ezert kiadjuk "ab" kodjat ami 4, majd felvesszuk az "abb"-t mint 9es kod. Majd kiadjuk az utolso karaktert ami "b", kettes koddal. Nekem igy kijottek az eddigi peldak, remelem most sem rontottam el es ertheto is volt... Szoval figyelni kell hogy mit kodolunk es ha mar ismert szo van akkor hozzaveszsuk a kov betut es ezzel uj szabalyt alkot.

Formálisan: Routine LZW_COMPRESS

	 STRING = get input character
	 WHILE there are still input characters DO
		  CHARACTER = get input character
		  IF STRING+CHARACTER is in the string table then
				STRING = STRING+character
		  ELSE
				output the code for STRING
				add STRING+CHARACTER to the string table
				STRING = CHARACTER
		  END of IF
	 END of WHILE
	 output the code for STRING

LZW kitömörítés

Informálisan

Alapelv: kicsit az enkóder fejével kell gondolkodni. Tehát a dekódolásnál is építeni kell a szótárat.

Szóval:

1. beolvasod az első indexet (vagyis sorszámot a szótárban), és a szótár annyiadik elemét (ez kezdetben csak egybetűs lehet, mert az abc betűivel rajtol a szótár) kiadod a kimenetre.
2. utána minden egyes beolvasott újabb indexre: kinézed, mi van a szótárban annál az indexnél, és azt a szót írod a kimenetre, valamint
3. az előző szót (amelyiket e most kiírt szó előtt írtál ki) összeolvasztod az éppen most kiírt szó első karakterével, és az így kapott új szót felveszed a szótárba, a következő bejegyzésként.
4. ha még nincs vége az inputnak, 2-re ugrunk.

Tehát: a-1, b-2, c-3 a szótár, és a tömörítvény 12235242. Nahát, 1. lépés: 1->a. 2. lépés: 2-> b, így már ab-t fejtettünk meg. 3. lépés: ab -> 4-es elem a szótárba. 2. lépés: 2-> b, így már abb-t fejtettünk meg. 3. lépés: bb -> 5-ös elem a szótárba. 2. lépés: 3-> c, így már abbc-t fejtettünk meg. 3. lépés: bc -> 6. elem a szótárba. 2. lépés: 5-> bb, így már abbcbb-t fejtettünk meg. 3. lépés: cb -> 7. elem a szótárba. 2. lépés: 2-> b, így már abbcbbb-t fejtettünk meg. 3. lépés: bbb -> 8. elem a szótárba. 2. lépés: 4-> ab, így már abbcbbbab-t fejtettünk meg. 3. lépés: ba -> 9. elem a szótárba. 2. lépés: 2-> b, így már abbcbbbabb-t fejtettünk meg. 3. lépés: abb -> 10. elem a szótárba. és 4. lépésben kilépünk, mert EOF.

Aki kiváncsi, nézze meg fent, hogy a feladó vajon az 'abbcbbbabb' sztringet akarta-e elküldeni. Kihagytam az egyetlen csalit, ami a dologban van. Ugyanis az enkóder 2-t és 3-t fordítva csinálja. Ha a 2-nél olyan indexet olvasunk, ami a szótár épp rákövetkező eleme lenne, de még nincs meg, akkor ez azt az elemet jelenti, amelyiket a következő 3. lépésnél alkotnánk csak meg, de előre gondolkodva ki lehet találni az első betűjét (hiszen egy kódszóhoz egy betűt fűzve jön létre), és csak az hiányzik. Tehát az előző kódszóhoz hozzáfűzzük a saját első betűjét, és így jön létre az új bejegyzés. Ez is le van írva mindkét szürke könyvben.

Formálisan: Routine LZW_DECOMPRESS

Read OLD_CODE
output OLD_CODE
CHARACTER = OLD_CODE
WHILE there are still input characters DO
	 Read NEW_CODE
	 IF NEW_CODE is not in the translation table THEN
		  STRING = get translation of OLD_CODE
		  STRING = STRING+CHARACTER
	 ELSE
		  STRING = get translation of NEW_CODE
	 END of IF
	 output STRING
	 CHARACTER = first character in STRING
	 add OLD_CODE + CHARACTER to the translation table
	 OLD_CODE = NEW_CODE
END of WHILE

-- Brez - 2005.12.01.