Hoe om data te komprimeer met behulp van huffman-kodering

Huffman se algoritme word gebruik om data te komprimeer of te kodeer. Gewoonlik word elke karakter in `n tekslêer gestoor as agt stukkies (syfers, óf 0 of 1) daardie kaart met die gebruik van `n kodering genaamd ASCII. `N Huffman-gekodeerde lêer breek die stewige 8-bis-struktuur af sodat die mees gebruikte karakters in net `n paar bisse gestoor word (` A `kan wees "10" of "1000" eerder as die ASCII, wat is "01100001"). Die minste algemene karakters sal dan dikwels veel meer as 8 bisse opneem (`Z` kan wees "00100011010"), maar omdat hulle so selde voorkom, skep Huffman-kodering, oor die algemeen `n veel kleiner lêer as die oorspronklike.

Stappe

Deel 1 van 2:
Oppervlakkamsel
  1. Image getiteld kompress data met behulp van Huffman Encoding Stap 1
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 nou die EOF (einde van die lêer) en merk dit as `n frekwensie van 1.
  • Byvoorbeeld, as jy `n teks lêer lees wil kodeer "ab ab cab," Jy sal `n `met frekwensie 3,` B `hê met frekwensie 3,` `(ruimte) met frekwensie 2,` C `met frekwensie 1, en EOF met frekwensie 1.
  • Image getiteld Compress data met behulp van Huffman Encoding Stap 2
    2. Stoor karakters as boom nodusse en sit dit in `n prioriteit tou. Jy sal `n groot binêre boom met elke karakter as `n blaar bou, sodat jy die karakters in `n formaat moet stoor sodat hulle nodusse van die boom kan word. Plaas hierdie nodusse in `n prioriteit tou met elke karakter se frekwensie as die nodus se prioriteit.
  • `N Binêre boom is `n data-formaat waar elke stuk data `n nodus is wat tot een ouer en twee kinders kan hê. Dit word dikwels as `n vertakkingboom geteken, vandaar die naam.
  • `N Waglys is `n gepaste aangewese data-versameling waar die eerste ding om in die tou te gaan, ook die eerste ding is om uit te kom (soos om in lyn te wag). In a prioriteit Waglys word die data gestoor in volgorde van hul prioriteit, sodat die eerste ding om uit te kom, die mees dringende ding is, die ding met die kleinste prioriteit, eerder as die eerste ding wat aangevuur word.
  • In die "ab ab cab" Voorbeeld, jou prioriteit tou sal so lyk: {`C`: 1, EOF: 1, ``: 2, `A`: 3, `B`: 3}
  • Image getiteld kompress data met behulp van Huffman Encoding Stap 3
    3. Begin om jou boom te bou. Verwyder (of dequeue) die twee mees dringende dinge van die prioriteit ry. Skep `n nuwe boomknoop om die ouer van hierdie twee nodusse te wees, wat die eerste nodus as sy linker kind en die tweede as sy regte kind stoor. Die prioriteit van die nuwe nodus moet die som van die prioriteite van sy kind wees. Dan, so `n nuwe nodus in die prioriteitswachtrij.
  • Die Priority Queue lyk nou soos volg: {``: 2, Nuwe Node: 2, `A`: 3, `B`: 3}
  • Image getiteld kompress data met behulp van Huffman Encoding Stap 4
    4. Voltooi jou boom: Herhaal die bogenoemde stap totdat daar net een nodus in die tou is. Let daarop dat bykomend tot die nodusse wat jy vir die karakters en hul frekwensies geskep het, ook deurdring, in bome te draai, en die ouer nodes, nodusse wat alreeds bome is, hervee.
  • Wanneer jy klaar is, sal die laaste nodus in die tou die wortel van die kodering boom, met al die ander nodusse wat daaruit vertak.
  • Die mees gebruikte karakters sal die blare die naaste aan die bokant van die boom wees, terwyl die selde gebruikte karakters aan die onderkant van die boom geplaas sal word, verder weg van die wortel.
  • Image getiteld kompress data met behulp van Huffman Encoding Stap 5
    5. Skep `n kodering kaart. Loop deur die boom om elke karakter te bereik. Elke keer as jy `n nodus se linker kind besoek, is dit `n `0`. Elke keer as jy `n nodus se regte kind besoek, is dit `n `1`. Wanneer jy `n karakter kry, stoor die karakter met die volgorde van 0s en 1s wat dit geneem het om daar te kom. Hierdie volgorde is wat die karakter soos in die saamgeperste lêer gekodeer sal word. Stoor die karakters en hul rye in `n kaart.
  • Byvoorbeeld, begin by die wortel. Besoek die wortel se linker kind, en besoek dan die nodus se linker kind. Aangesien die nodus is wat jy nou nie kinders het nie, het jy `n karakter bereik. Dit is ``. Aangesien jy twee keer geloop 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"}.
  • Image getiteld Compress data met behulp van Huffman Encoding Stap 6
    6. In die uitsetlêer, sluit die koderingskaart as `n koptekst in. Dit sal die lêer toelaat om gedekodeer te word.
  • Image getiteld Compress data met behulp van Huffman Encoding Stap 7
    7. Encode die lêer. Vir elke karakter in die lêer wat gekodeer moet word, skryf die binêre volgorde wat jy in die kaart gestoor het. Sodra jy klaar is met die kodering van die lêer, maak seker dat jy die EOF tot die einde toe voeg.
  • Vir die lêer "ab ab cab", Die gekodeerde lêer sal so lyk: "1011001011000101011011".
  • Lêers word gestoor as bytes (8 bisse of 8 binêre syfers). Omdat die Huffman-enkodering-algoritme nie die 8-bis-formaat gebruik nie, sal gekodeerde lêers dikwels nie lengtes hê wat veelvoude van 8 is nie. Die oorblywende syfers sal ingevul word met 0s. In hierdie geval sal twee 0`s aan die einde van die lêer bygevoeg word, wat soos `n ander ruimte lyk. Dit kan `n probleem wees: hoe sal die dekodeerder weet wanneer om op te hou om te lees? Aangesien ons egter `n einde-van-lêer karakter ingesluit het, sal die dekodeerder dit kry en stop dan en ignoreer enigiets anders wat bygevoeg is.
    • Deel 2 van 2:
    Dekodering
    1. Beeld getiteld Compress data met behulp van Huffman Encoding Stap 8
    1. Lees in `n Huffman-gekodeerde lêer. Lees eers die kop, wat die kodering kaart moet wees. Gebruik dit om `n dekoderende boom te bou op dieselfde manier as wat jy die boom gebou het wat jy gebruik het om die lêer te kodeer. Die twee bome moet identies wees.
  • Image getiteld kompress data met behulp van Huffman Encoding Stap 9
    2. Lees in die binêre een syfer op `n slag. Traverse die boom soos jy lees: As jy in `n `0` lees, gaan na die linker kind van die nodus waarheen jy is, en as jy in `n `1` lees, gaan na die regte kind. Wanneer jy `n blaar bereik (`n nodus sonder enige kinders), het jy by `n karakter aangekom. 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 eiendom, Sodat geen karakter se binêre kodering ooit kan plaasvind aan die begin van `n ander karakter se kodering nie. Die kodering vir elke karakter is heeltemal uniek. Dit maak dekodering baie makliker.
  • Beeld getiteld kompress data met behulp van Huffman Encoding Stap 10
    3. Herhaal totdat jy die EOF bereik. Baie geluk! Jy het die lêer afgekodeer.

    • Wenke

    Deel op sosiale netwerke:
    Soortgelyk