On 20 May 98 at 5:04,   > wrote:
> Nem is azert erdekel mert le akarnam programozni, de egy nagyon
> "elegans" algoritmus !
Tenyleg nagyon elegans. Es ami meg az erdekessege, hogy tablazaton
alapulo tomorites, megsem kell a tablazatot magat a tomoritett
adattal egyutt atadni, valamint egy menetben (on-line) lehet
tomoriteni, es ugyancsak on-line kitomoriteni (vagy hogy mondjuk a
decompress-t magyarul?)
Ja, meg egy erdekesseg: Valamikor tanultam az egyetemen a (ha jol
emlekszem) Shannon tetelt, ami az informaciotartalomrol szol, vagyis,
hogy egy adott adatot mennyire lehet informaciovesztes nelkul
tomoriteni. Es ehhez volt a ha jol emlekszem Shannon-Fano tomorites,
ami idealis tomorites, bizonyitasa is van neki, hogy ennel kisebbre
nem lehet tomoriteni, a bizonyitast mar szinten elfelejtettem. :)
No az LZW szinte mindig kisebbre tomoriti az adatot, mint a
Shannon-Fano!
Vegulis jobban belegondolva nincs benne semmi csodalatos, mert a
Shannon tetelben van egy alapfelteves, vagyis, hogy az adatok
egymastol fuggetlenek, ami a gyakorlatban sosincs meg, hiszen ha
leirunk egy massalhangzot, akkor eleg nagy valoszinuseggel utana
maganhangzo kovetkezik, hogy csak a legegyszerubbet emlitsem. Az LZW
tomorites is, meg a tobbi manapsag hasznalt tomorites is viszont pont
azt hasznalja ki, hogy az adatok egymastol nem fuggetlenek, sokszor
van bennuk ismetlodes, stb.
Szoval, a kodolas: Kiindulaskent vegyunk fel egy 256 elembol allo
string-tablazatot, tegyuk bele az osszes 1 hosszusagu stringet
(tehat a 0-tol 255-ig tejedo erteku byte-okat) es rendeljuk hozzajuk
a 0-tol 255-ig tarto szamokat, mint kodot.
(Termeszetesen, ha a bejovo (kodolando) adatok nem 8 bites egysegek,
vagy [szokasos elnevezes szerint] a kodolando abc nem 0-tol 255-ig
tart, akkor erdemes szukiteni azt, es csak azokat az 1 elemu
stringeket betenni a tablazatba, amik az elofordulo 'betuket'
tartalmazzak, ekkor rovidebb lesz a kiindulo tablazatunk. Ez "csak"
elvi megfontolas, a gyakorlatban senki nem hasznalja ki, hogy
mondjuk 0x80-nal nagyobb betukod nincs egy ekezet nelkuli szovegben.)
Ahogy jonnek az input byte-ok, keressuk meg, hogy van-e a
stringtablaban 1, 2, 3, stb. minel hosszabb ugyanolyan string, mint a
bejovo byte-ok. (Indulaskor persze csak 1 hosszu stringgel fogunk
azonosat talalni, mert nincs mas a tablazatban.) Ha a rakovetkezo
byte mar olyan stringet ad, ami nem lenne benne a tablazatban, akkor
irjuk ki az outputra az elozo string kodjat a tablazatbol, es
generaljunk be a tablazatba egy uj stringet, ami az elozo string
plusz az uj byte altal eloallo n+1 hosszusagu string lesz, es kodkent
rendeljuk hozza a rakovetkezo kodszamot (tehat legeloszor a 256-ot).
Ez utan ujra indul az elet, az a byte, ami mar nem fert bele a
stringbe az elobb, az fogja az uj string elso byte-jat alkotni, amit
az inputrol olvasott byte-okkal kiegeszitve keressuk megint a minel
hosszabb stringet.
Tehat pl. ha a bejovo string az, hogy "abcbcbcbd", akkor igy
alakul:
"abcbcbcbd"
a: van
ab: nincs, tehat write kod("a") [=0x61], put("ab",256)
b: van
bc: nincs, tehat write kod("b") [=0x62], put("bc",257)
c: van
cb: nincs, tehat write kod("c") [=0x63], put("cb",258)
b: van
bc: van
bcb: nincs, tehat write kod("bc") [=257], put("bcb",259)
b: van
bc: van
bcb: van
bcbd: nincs, tehat write kod("bcb") [=259], put("bcbd",260)
d: van
d<EOF>: nincs, tehat write kod("d") [=0x64], es vege
Dekodolas:
Allitsuk elo ugyanazt az indulo 256 elemu stringtablazatot,
mint az elobb, ugyanolyan kodolassal. Olvassuk a bemenetrol sorra a
kodokat. Ha olyan kod jon, ami mar szerepel a stringtablaban
(indulaskor 0..255), akkor a hozza tartozo stringet kell az outputra
irni, es (a legelso esettol eltekintve) generalni kell a tablazatba
egy uj stringet, ami ugy all elo, hogy az elozo kod stringjehez
hozzatesszuk ezen kod stringjenek elso betujet. (A legelso esetben
nincs meg elozo kod, ezert ott ezt nem kell tenni.)
Latszik, hogy dekodolaskor eggyel elmaradunk a kodolashoz kepest
abban, hogy mikor generaljuk be az uj kodot a stringtablazatba.
No most kicsit meg jobban :) kell figyelni: Ha olyan kod jon, ami meg
nincs a stringtablaban, az ezen elozo mondat szerint csak ugy
lehetett, hogy kodolaskor rogton ismetlodott az a sorozat, amit eppen
az elobb generalt a stringtablaba a kodolo. Vagyis volt egy 'eSTRu'
string, ('e' az elso betu, mogotte egy string, 'u' az utolso betu)
amibol 'eSTR' 'u'-val megtoldva mar uj stringet adna, ezert 'eSTR'
kodja kerult az outputba (ez az elozo kod, amit olvastunk), es a
kodolo berakta stringjei koze kovetkezo kodkent 'eSTRu'-t, es eppen
ez a string is kovetkezett. Fontos eszrevenni, hogy mivel ez a
kovetkezo string az 'u'-val jelolt betuvel indul, ezert 'e' azonos
kell legyen 'u'-val! Az eredeti input szovegreszlet pedig 'eSTReSTRe'
jellegu volt.
Ezek szerint tehat ilyen esetben azt a stringet kell az outputra
irni, ami az elozo kod stringje plusz meg moge rakva ugyancsak az
elozo kod stringjenek elso betujet ('eSTRe'). Azon kivul, hogy ezt az
outputra irjuk, be is kell vennunk a stringtablaba kovetkezo
elemkent, vagyis kovetkezo koddal.
Igy a kodok olvasasaval parhuzamosan dekodolaskor fel is epitjuk
ugyanazt a kodtablat, ami a kodolaskor is keletkezett.
Pl. az elozo eset dekodolasa: A bejovo kodok:
0x61,0x62,0x63,257,259,0x64
0x61: van, write string(0x61) [="a"], elso kod volt, nincs put
0x62: van, write string(0x62) [="b"], put("ab",256)
0x63: van, write string(0x63) [="c"], put("bc",257)
257: van, write string(257) [="bc"], put("cb",258)
259: nincs, write string(257)+first(257) [="bcb"], put("bcb",259)
0x64: van, write string(0x64) [="d"], put("bcbd",260)
Es kijott belole az "abcbcbcbd".
A kodok irasahoz-olvasasahoz meg annyi tartozik, hogy mivel a
tablazatba generalt kodok mindig eggyel novekvo szamok, ezert mindig
pontosan tudjuk, hogy a kovetkezo kod max. milyen erteku lehet, es
igy azt is, hogy max mennyi ertekes bit lehet az ertekeben. Ezert
indulaskor elegendo 9 bites kodokat irni az outputra (illetve olvasni
dekodolaskor), aztan amikor begeneraljuk a tablazatba az 512-es
kodot, utana mar 10 biteset, stb. (Olvasaskor a kodgeneralas eggyel
elmarad az irastol, ezert ott mar az 511-es kod generalasa utan 10
bitre kell valtani.)
Masik kerdes, hogy meddig erdemes tolteni a stringtablat. A
gyakorlatban azt szoktak csinalni, hogy max 12 bites kodokat
hasznalnak, tehat 4096 elemu stringtablat, es ha betelik, akkor
reset-elik az egeszet, es ujra indul az elet 'ures' (256 elemu)
stringtablaval. (Lehetne meg olyat is csinalni, hogy amikor betelt,
akkor mar egyszeruen nem generalunk bele uj kodokat, hanem a mar
feltoltott tablazatot hasznaljuk a kodolasra. Ez viszont nem annyira
adaptiv, vagyis, ha a file vegen masmilyen stringek ismetlodnek
tobbszor, mint az elejen, akkor a reset-elos modszer hatekonyabb.)
E miatt a reset dolog miatt szokott lenni meg egy 'clear' kod is, a
256-os, amit begeneralnak a file-ba, nehogy maskor reset-eljen a
dekodolo, mint a kodolo. Ezen kivul van meg egy masik elore definialt
kod, a 257-es, ami EOF-ot jelent. Igy valojaban az elso igazi kod nem
is 256, mint fentebb mutattam, hanem 258.
István
-- Istvan Marosi -- http://www.sch.bme.hu/~marosi --
-- Recosoft Ltd. -- mailto: --
|
