Az S. 68. feladat (2012. január)

S. 68. Adatok tömörítésének egyik módja a Huffman kódolás. Az októberben kitűzött I. 276. feladatban a kódolás menetét kellett egy prezentációban bemutatnunk, most feladatunk a kódolást végző program elkészítése.

A módszer lényege, hogy az eredeti állomány minden bájtját különböző hosszúságú bitsorozatra cseréli úgy, hogy a ritkábban előforduló bájtok hosszabb, a gyakoribb bájtok rövidebb bitsorozatot kapnak. A kód létrehozásának alapja, hogy az eredeti állomány egyes bájtjainak gyakorisága alapján létrehozunk egy bináris fát, majd megfelelő módon bejárjuk.

A fa felépítésének lépései a következők:

1. Először minden bájtot a gráf egy izolált pontjának tekintünk, amelynek nincsenek leágazásai, és értéke a benne szereplő karakter gyakorisága.

2. Ezután a két legkisebb gyakoriságú bájt pontját összevonjuk, és befűzzük őket egy olyan új gráfpont bal és jobb ágába, amelynek értéke a két karakter gyakoriságának összege, majd a két eredeti gráfpontot töröljük.

3. A 2. pontot ismételjük addig, amíg az összes betűt föl nem fűztük egy bináris fába.

Az így létrejött fában a gyökérelemtől indulva megkapjuk az egyes karakterek Huffman kódját úgy, hogy a karakterhez vezető úton minden balra lépés 0-ás bitet és minden jobbra lépés 1-es bitet jelent.

Készítsük programot s68 néven, amely a parancssor első argumentumaként megadott állomány bájtjainak egy lehetséges Huffman kódját előállítja, és a parancssor második argumentumaként megadott szöveges állományba írja soronként az egyes bájtokhoz rendelt új bitsorozatot és azok hosszát a kapott kód hossza, illetve azon belül ABC sorrendben a mintának megfelelő formában. Az ASCII tábla szerint nem nyomtatható karakterek és a szóköz helyett a karakter kódja jelenjen meg. A program ezen kívül írja a standard kimenetre a bemeneti állomány eredeti és kódolt méretét bit mértékegységben.

Beküldendő egy tömörített s68.zip állományban a program forráskódja (s68.pas, s68.cpp, ...) az .exe és más fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s68.txt, s68.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrás melyik fejlesztő környezetben fordítható.

A megoldás teszteléséhez fölhasználható állományok: s68.zip

(10 pont)

A beküldési határidő 2012. február 10-én LEJÁRT.

Mintamegoldásként Adrián Patrik debreceni 12. osztályos tanuló kritika és dokumentációját (s68ap-kritika-dokumentacio.pdf) valamint programját (s68ap.c), és Szabó Attila pécsi 11. osztály diák dokumentációját (s68sza.pdf) valamint programját(s68sza.c) adjuk közre.

Statisztika:

15 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Hoffmann Áron, Jákli Aida Karolina, Kucsma Levente István, Szabó 928 Attila.
9 pontot kapott:	Havasi 0 Márton, Marussy Kristóf, Strenner Péter.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	4 versenyző.
6 pontot kapott:	2 versenyző.

A KöMaL 2012. januári informatika feladatai