Shannon-Fano freepascal?

I. A kódolandó adathalmazon gyakoriság elemzést kell végrehajtani. Meg kell számolni, hogy melyik szimbólumból hány van.

II. Ezeket a megszámolt szimbólumokat két részre fel kell osztani, úgy, hogy az egyik és a másik rész szimbólumai is legalább közelítőleg azonos számban forduljanak elő.

III. A két részhalmaz egyikéhez nullát, a másikhoz egyet rendelünk.

IV. Ezt az osztást a részhalmazokkal addig végezzük, amíg van mit osztani. Így minden szimbólum mellett kialakul egy egyedi, csak nullákat és egyeseket tartalmazó kód.

V. Az eredeti adathalmazon újra végiglépkedve, az aktuális szimbólumhoz társított kódot írjuk a kimenetre. Ez volna maga az algoritmus.

Semmi nehézséget nem okoz a megértése és szerintem másnak sem. Amit nem tudok, az az, hogy a kimeneti állományból, hogy nyerem vissza az eredeti adatokat? Mert erről mélyen hallgat minden leírás.

Ami még nehéz, az a megfelelő algoritmus kitalálása az osztásra. Nem azzal van bajom, hogy ne tudnám megcsinálni, meg tudom. Csak a lehető legoptimálisabb megoldást szeretném megvalósítani.

Legyen a tömörítendő szó: trattoria

Ez így, ebben az állapotában 9 x 8, azaz 72 bit tárhelyet foglal el, mivel kilenc betűből, azaz karakterből áll és egy-egy betű 8 bitet igényel.

A szón gyakoriságelemzést végezve azt kapjuk, hogy van benne

3 db t,

2 db a,

2 db r,

1 db o és

1 db i.

Ezeket a karaktereket most az eredeti 8 bit helyett annál kisebb kódokkal helyettesítjük be. Még pedig úgy, hogy a legrövidebb kódot a leggyakrabban előforduló karakterek kapják, a leghosszabbakat pedig a legritkábbak.

Legtöbb a t, így az lesz a 0.

A második az a, tehát az lesz 1.

A harmadik az r, ez lesz a 00.

A negyedik az o, ez kapja a 01-et,

az ötödik, az i pedig az 10-t.

Ha le akarnám írni a szót ezekkel a rövid kódokkal, akkor az így nézne ki: 0,00,1,0,0,00,11,01,1

Ha a vesszőket elhagyjuk, akkor kapunk egy kódsorozatot. Ezt eltárolva már le is tömörítettük az eredetileg 72 bit hosszú információt 13 bitre.

Na de kérdés, hogy ebből a 13 bitből hogyan állítom vissza az eredeti szót, a trattoria-t?

Erre a kérdésre könnyű a válasz, sehogy.

Hogy a kódsorból való visszaállítás (ez a kitömörítés) sikerüljön, ahhoz azt is el kell tárolnunk, hogy a 0,1,11,00, stb kódjainkhoz milyen karakter tartozik.

Ehhez fel kell építenünk egy bináris fát, ami magában foglalja a karaktereket. Ez úgy fog kinézni, hogy a bináris fát soronként, balról jobbra eltároljuk. Tehát a fa így fog kinézni egy fájlban;

t,a,r,o,i

Ha ezt is kiírjuk a fájlba a kódsorozatunkkal együtt, akkor már hiánytalanul visszaállíthatjuk az eredeti szöveget. Ehhez csak fel kell építenünk a bináris fát, majd utána a kódsorunkkal végigmenni a fán és lejegyezni annak a karakternek az ascii kódját, amire a kód mutat.

Ami lényeges, hogy a rövid kódokat mindig úgy osszuk ki, hogy abból egy balra tömörített fát alkossunk.

Egyetlen szó tömörítése nem hoz nagy nyereséget, még az is előfordulhat, hogy a tömörített állomány hosszabb lesz a szónál, de hosszabb szövegek esetén már jelentős megtakarítás érhető el. Minél hosszabb a szöveg, annál több helyet takarítunk meg.

A mi esetünkben a fa tárolása 5-ször 8 bit, ami negyven, és ehhez jön a kódsorozatunk, ami még 13 bit. Tehát, az eredetileg 72 bitet igénylő adatot 53 biten sikerült tárolni. Ha mondjuk a trattoria helyett a trattoria trattoria-t kellene tömörítenünk, akkor a nyereség nagyobb lenne, mert csak a kódsor duplázódna, tehát 144 bit tárolásához elég lenne 53+13 bit, ami 66.

Igaz, azt is meg kéne valahogy határozni, hogy a fájlban hol kezdődik a kódsorozat, azaz, hol ér véget a bináris fa. Na meg, hogy milyen hosszú a kódsorozatunk, mert ha nem pont bájtra végződik, tehát ha nem osztható maradék nélkül nyolccal, akkor mi van?

Ezt ki-ki oldja meg maga.

De a lényeg azért, remélem átment.

Ha van kérdés, válaszolok.

Sehogy. A fentebb vázolt algoritmus ugyanis hibás. Nem alkalmazható. A célom az volt vele, hogy megfigyeljem az emberek reakcióját. Kiváncsi voltam rá, hányan verik bele a nózimat a hibámba. Sajnos egyedül csak te figyeltél fel rá.

A dolog megoldása az, hogy a bináris fát másképpen kell megépíteni. A használt kódoknak, ha nem is sokkal, de hosszabbaknak kell lenniük. Ekkor a bináris fa kód alapján történő bejárása fogja elszakaszolni a bináris kódfolyamot, mert ahogy a gyökértől kezdve végiglépkedünk, mindig eljutunk egy pontig, ahonnan már nem lehet sem jobbra, sem balra haladni. Ekkor van vége adott kódnak és következik a másik, ami újfent a fa gyökerétől lépked lefelé, amíg csak tud.

Ennél, ha optimumra törekszünk, akkor a balra tömörített bináris fa nem biztos, hogy megfelelő. Ezért a fa leképezésénél egy bitpatternt is el kell tárolni. Ezt célszerű a tömörített adatokat tartalmazó fájl elejére tenni és a fa építésénél felhasználni, mert csak ott lesz a patternben egyes, ahol a fában is van érték. A tárolás itt is szekvenciális, tömbszerű, ahogy a balra tömörített fa esetében.

A másik lehetőség a fix kódhossz, de annak a tömörítés hatásfoka látja kárát, elég csúnyán.

kódolandó szó: BABA

kódok; b=0, a=1

A bináris fa úgy néz ki, hogy van a gyökér, attól balra le 0, jobbra le pedig 1.

[0]/[root]\[1]

azaz

[B]/[root]\[A]

BABA szó kódja 0101

ABBA szó kódja 1001

ABA szó kódja 101

BAB szó kódja 010