Huffman se algoritme word gebruik om data saam te pers of te kodeer. Normaalweg word elke karakter in 'n tekslêer gestoor as agt bisse (syfers, óf 0 óf 1) wat na daardie karakter toewys met behulp van 'n kodering genaamd ASCII. 'N Huffman-gekodeerde lêer breek die rigiede 8-bis-struktuur af, sodat die karakters wat die meeste gebruik word in slegs 'n paar bisse gestoor word (' a 'kan' 10 'of' 1000 'wees eerder as die ASCII, wat' 01100001 'is)). Die minste algemene karakters sal dus baie meer as 8 bisse beslaan ('z' kan '00100011010' wees), maar omdat dit so selde voorkom, skep Huffman -kodering in die geheel 'n baie kleiner lêer as die oorspronklike.
Stappe
Deel 1 van 2: Kodering
Stap 1. Tel die frekwensie van elke karakter in die lêer wat gekodeer moet word
Sluit 'n dummy -karakter in om die einde van die lêer te merk - dit sal later belangrik wees. Noem dit vir eers die EOF (einde van die lêer) en merk dit as 'n frekwensie van 1.
As u byvoorbeeld 'n tekslêer met die naam "ab ab cab" wil kodeer, het u 'a' met frekwensie 3, 'b' met frekwensie 3, '' (spasie) met frekwensie 2, 'c' met frekwensie 1, en EOF met frekwensie 1
Stap 2. Stoor karakters as boomknope en plaas dit in 'n prioriteitsry
U bou 'n groot binêre boom met elke karakter as 'n blaar, dus moet u die karakters in 'n formaat stoor sodat dit 'n knoop van die boom kan word. Plaas hierdie nodusse in 'n prioriteitsry met die frekwensie van elke karakter as die prioriteit van die knoop.
- 'N Binêre boom is 'n dataformaat waar elke data 'n knoop is wat tot een ouer en twee kinders kan hê. Dit word dikwels as 'n vertakte boom geteken, vandaar die naam.
- 'N Tou is 'n gepaste naam vir data -insameling, waar die eerste ding om in die ry te kom, ook die eerste ding is wat uitkom (soos om in die ry te wag). In 'n prioriteitswaglys word die data in volgorde van hul prioriteit gestoor, sodat die eerste ding wat uitkom, die dringendste is, die ding met die kleinste prioriteit, eerder as die eerste ding wat ingewag is.
- In die voorbeeld van 'ab ab cab' sou u prioriteitswag so lyk: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Stap 3. Begin met die bou van u boom
Verwyder (of dequeue) die twee dringendste dinge uit die prioriteitsry. Skep 'n nuwe boomknooppunt om die ouer van hierdie twee nodusse te wees, en stoor die eerste knoop as sy linkerkind en die tweede as sy regterkind. Die prioriteit van die nuwe knoop moet die som van die prioriteite van sy kind wees. Gee dan hierdie nuwe node in die prioriteitswaglys.
Die prioriteitsry lyk nou so: {'': 2, nuwe node: 2, 'a': 3, 'b': 3}
Stap 4. Voltooi die bou van u boom:
herhaal die bogenoemde stap totdat daar slegs een knoop in die ry is. Let daarop dat, benewens die nodusse wat u vir die karakters en hul frekwensies geskep het, u ook ontknop, bome word en ouerknope herleef, nodusse wat reeds bome is.
- As u klaar is, is die laaste knoop in die ry die wortel van die koderende boom, met al die ander nodusse wat daaruit vertak.
- Die karakters wat die meeste gebruik word, is die blare wat die naaste aan die bokant van die boom is, terwyl die karakters wat selde gebruik word, onderaan die boom, verder weg van die wortel, geplaas sal word.
Stap 5. Skep 'n koderingskaart. Loop deur die boom om elke karakter te bereik. Elke keer as u die linker kind van 'n knoop besoek, is dit 'n '0'. Elke keer as u die regte kind van 'n knoop besoek, is dit 'n '1'. As u by 'n karakter kom, stoor u die karakter met die volgorde van 0'e en 1'e wat nodig was om daar te kom. Hierdie volgorde is hoe die karakter in die saamgeperste lêer gekodeer sal word. Stoor die karakters en die volgorde daarvan op 'n kaart.
- Begin byvoorbeeld by die wortel. Besoek die linkerkind van die wortel en besoek dan die linkerkind van die knoop. Aangesien die knoop wat u nou het, geen kinders het nie, het u 'n karakter bereik. Dit is ''. Aangesien u twee keer links gestap het om hier te kom, is die kodering vir '' '00'.
- Vir hierdie boom sal die kaart so lyk: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Stap 6. In die uitvoer lêer, sluit die kodering kaart as 'n kop
Dit sal toelaat dat die lêer gedekodeer word.
Stap 7. Kodeer die lêer
Vir elke karakter in die lêer wat gekodeer moet word, skryf die binêre volgorde wat u op die kaart gestoor het, neer. As u klaar is met die kodering van die lêer, moet u die EOF by die einde voeg.
- Vir die lêer "ab ab cab" sal die gekodeerde lêer so lyk: "1011001011000101011011".
- Lêers word as grepe (8 bisse of 8 binêre syfers) gestoor. Omdat die Huffman Encoding-algoritme nie die 8-bis-formaat gebruik nie, het die gekodeerde lêers dikwels nie lengtes van veelvoude van 8. Die oorblywende syfers word met 0s ingevul. In hierdie geval word twee 0'e bygevoeg aan die einde van die lêer, wat soos 'n ander spasie lyk. Dit kan 'n probleem wees: hoe sou die dekodeerder weet wanneer om op te hou lees? Omdat ons egter 'n einde-van-lêer-karakter ingesluit het, sal die dekodeerder hierby uitkom en dan stop en niks anders ignoreer wat daarna bygevoeg is nie.
Deel 2 van 2: Dekodering
Stap 1. Lees in 'n Huffman-gekodeerde lêer
Lees eers die opskrif, wat die koderingskaart moet wees. Gebruik dit om 'n dekoderingsboom te bou op dieselfde manier as wat u die boom gebou het waarmee u die lêer gekodeer het. Die twee bome moet identies wees.
Stap 2. Lees die binêre een syfer op 'n slag in
Gaan deur die boom terwyl jy lees: as jy in 'n '0' lees, gaan na die linkerkind van die knoop waarby jy is, en as jy in 'n '1' lees, gaan na die regte kind. As u 'n blaar bereik ('n knoop sonder kinders), kom u by 'n karakter uit. Skryf die karakter in die gedekodeerde lêer.
As gevolg van die manier waarop die karakters in die boom gestoor word, het die kodes vir elke karakter 'n voorvoegsel -eienskap, sodat geen karakter se binêre kodering ooit kan plaasvind aan die begin van die kodering van 'n ander karakter nie. Die kodering vir elke karakter is heeltemal uniek. Dit maak dekodering baie makliker
Stap 3. Herhaal totdat u die EOF bereik
Baie geluk! Jy het die lêer gedekodeer.
