Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|LZW}} A pszeudókódok forrása: http://www.dogma.net/markn/articles/lzw/lzw.htm (© miatt :)) ==LZW betömörítés== ===Informálisan=…”

2012-10-21T20:02:17Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|LZW}} A pszeudókódok forrása: http://www.dogma.net/markn/articles/lzw/lzw.htm (© miatt :)) ==LZW betömörítés== ===Informálisan=…”

Új lap

{{GlobalTemplate|Infoalap|LZW}}

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===
<pre>
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
</pre>

==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:
# 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.
# 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
# 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.
# 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 ===
<pre>
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
</pre>

-- [[BrezinaP|Brez]] - 2005.12.01.

[[Category:Infoalap]]

LZW (Lempel-Ziv-Welch) - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|LZW}} A pszeudókódok forrása: http://www.dogma.net/markn/articles/lzw/lzw.htm (© miatt :)) ==LZW betömörítés== ===Informálisan=…”