SHPORA.net :: PDA

Login:
регистрация

Main
FAQ

гуманитарные науки
естественные науки
математические науки
технические науки
Search:
Title: | Body:

Ahned (greedy) algoritmid. Pakkimine Huffmani puu abil.




Huffmani puu antud teksti jaoks on niisugune koodipuu, mille abil kodeeritud teksti pikkus on minimaalne (kõikvõimalike koodipuude hulgas).



Huffmani puu moodustamine:



1. Kodeeritava teksti eeltöötlus: teeme kindlaks tekstis esinevate sümbolite hulga ning iga sümboli esinemissageduse. Seda etappi ei pruugi teha, kui kasutame mingit standardset ja ettearvutatud sagedustega tähestikku (aga siis ei tule skeem optimaalne).

2. Moodustame tulevase koodipuu lehed, säilitades neis sümbolit ning selle esinemissagedust. Iga lehte käsitleme alampuu juurena.

3. Valime kaks alampuud, mille juurest võetud esinemissagedused on vähimad kõigi alampuude hulgas (kui kaht puud enam valida ei saa, siis on algoritm oma töö lõpetanud). Moodustame nende kohale uue vahetipu, millesse salvestame alluvate esinemissageduste summa ning paneme valitud alampuud selle vahetipu vasakus ja paremaks alluvaks.

4. Jätkame sammuga 3 niikaua, kuni enam kaht puud valida ei saa.