A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. 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ó. |