Huffman kodoj: ekzemploj aplikaĵo

Nuntempe, malmultaj homoj pensas pri tio, kiel faras dosieron kunpremo. Kompare kun la antaŭa uzo de la persona komputilo fariĝis multe pli facila. Kaj preskaŭ ĉiu persono laboranta kun la dosiersistemon uzas dosierojn. Sed malmultaj homoj pensas pri kiel ili funkcias kaj sur kio bazo estas dosiero kunpremo. La unua versio de ĉi tiu procezo estis la Huffman kodoj, kaj estas uzataj hodiaŭ en diversaj popularaj archivers. Multaj uzantoj eĉ ne pensas kiel facile dosieron kunpremo okazas kaj ĝi laboras en skemo. En ĉi tiu artikolo ni rigardas kiel la compresión estas kion nuancoj helpo rapido supren kaj simpligi la procezo de kodigo, kaj ankaŭ vidi, kiel la principo de la arbo kodita.

Historio algoritmo

La unua algoritmo de efika kodigo de elektronikaj informo fariĝis kodo Huffman proponis jam en la mezo de la dudeka jarcento, nome en 1952. Estis li, kiu nuntempe estas la bazo elemento de la plimulto de la programoj kreitaj por kunpremi la informon. Nuntempe, unu el la plej popularaj fontoj uzante tiun kodon estas arkivoj ZIP, ARJ, RAR kaj multaj aliaj. Ankaŭ, la Huffman algoritmo estas uzata por kunpremi JPEG-bildoj kaj aliaj grafika objektoj. Nu, ĉiuj faksoj ankaŭ uzante modernajn kodigo, inventita en 1952. Malgraŭ tio, ke ekde la kreado de la kodo prenis tiom da tempo gxis nun gxi estas uzata en vario de novaj membranoj kaj la teamo malnovaj kaj modernaj tipoj.

La principo de efika kodigo

La bazo de la Huffman algoritmo inkludas skemo kiu permesas anstataŭi la plej kredinda, plej ofte okazantaj simboloj kodita duumaj sistemo. Kaj tiuj, kiuj estas malpli ofta, anstataŭita per pli longaj kodoj. Iri longe Huffman kodoj okazas nur post la sistemo uzas ĉiuj minimumajn valorojn. Tiu tekniko permesas vin minimumigi la longo de la kodo por ĉiu simbolo de la originala mesaĝo kiel tuto. La grava punkto estas, ke komence de la kodita probablo de apero de la literoj devus esti jam konata. Estas de ili estos preparita kaj la fina mesaĝo. Bazita sur tiuj datumoj, ĝi efektivigis la konstruon de la Huffman kodo arbo, surbaze de kiu okazos literoj kodoprezenton procezo en la arkivo.

Huffman kodo, ekzemple

Por ilustri la algoritmo, konsideri grafika varianto de konstruo de la kodo arbo. Por uzi tiun metodon por esti efika, necesas klarigi la difinon de certaj valoroj necesa por la koncepto de la procezo. La aro de la pluralidad de nodoj kaj arkoj, kiuj estas direktitaj de nodo al nodo, nomita grafo. La arbo mem estas grafeo kun aro de specifaj ecoj:

• en ĉiu nodo povas inkluzivi ne pli ol unu el la arkoj;
• unu el la nodoj devas esti la radiko de la arbo, kiu estas, ĝi ne devus esti parto de la arko ajn;
• se la tigo komencis la movadon laŭ la arkoj, la procezo devus permesi akiri tute en iu el la nodoj.

Estas ankaŭ tia afero, parto de la Huffman kodoj kiel folio de la arbo. Estas nodo de kiu ne iru ajna arko. Se du nodoj estas konektitaj de arko, unu el ili estas la gepatroj de la alia infano, depende de kiu nodo la arko eliras, kaj kio estas inkluzivita. Se du nodoj havas la saman patro nodo, ili estas nomataj-ejojn. Se, en la folioj, parto de la nodoj de pluraj arkoj, tiam ĝi estas nomita duuma arbo. Ĝuste tiel estas la Huffman arbo. La propreco de la konstruo de unuoj estas ke la pezo de ĉiu patro estas egala al la sumo de la pezoj de ĉiuj siaj infanoj nodoj.

Algoritmo por konstrui la arbo Huffman

La konstruado de la Huffman kodo estas enigo de la literoj de la alfabeto. Generita listo de retejoj kiuj estas liberaj en la estonteco kodo arbo. La pezo de ĉiu nodo en la listo devas esti la sama kiel la probablo de apero de la literoj afiŝojn responda al tiu nodo. En ĉi tiu kazo, kiu pezas la malplej estas elektitaj el inter pluraj liberaj lokoj de la estonteco arbo. En ĉi tiu kazo, se la minimuma indicoj estas observita en pluraj lokoj, oni povas libere elekti iun el la paroj. Tiam venas la kreo de la patro nodo, kiu devas pezas kiom la sumo de la pezoj de la paro de nodoj. Poste, gepatroj sendi la liston laŭ libera necesejojn, kaj la infanoj estas forigitaj. En ĉi tiu arko estas konvenaj indikiloj, kaj nuloj. Ĉi tiu procezo ripetas kiom necesas por teni nur sola nodo. Tiam skribi la duumaj ciferoj de supre sube.

Plibonigi la efikecon de compresión

Por pliigi la compresión efikeco, necesas dum arbo konstruaĵo kodo por uzi ĉiujn datumojn sur la probablo de apero de la literoj en aparta dosiero, ligita al arbo kaj ne permesas la fakto ke gxi estis disjxetita sur grandan nombron da teksto dokumentoj. Se la antaŭ-promeno tra ĉi dosiero, vi tuj povas kalkuli la statistiko de kiom ofte estas leteroj de la instalaĵo subjekto al la compresión.

Akcelo de la procezo de compresión

Por plirapidigi la algoritmo, la difino de la literoj devus esti farita ne laŭ la probablo de apero de aparta letero, kaj la ofteco de ĝia malhelpo. Kun ĉi tiu algoritmo plifaciliĝas, kaj labori kun ili multe pli rapide. Ĝi ankaŭ evitas la operacioj asociitaj kun la punkto flotante divido. Krome, laborante en ĉi tiu modo, la dinamika Huffman kodo, aŭ pli ĝuste la algoritmo mem ne subjekto al ajna ŝanĝojn. Tio estas ĉefe pro la fakto ke la probabloj estas rekte proporcia al la frekvenco. Ĝi valoras paganta atenton al la fakto ke la pezo fino de la dosiero, aŭ la tiel nomataj radika nodo estas egala al ŝin adicias de la nombro de signoj en la objekton por esti traktita.

konkludo

Huffman kodoj - simpla kaj longe establita algoritmo, kiu estas ankoraŭ uzata de multaj bone konataj programoj kaj entreprenoj. Lia simpleco kaj klareco povas atingi efikan rezultojn kunpremi dosierojn de ajna volumo kaj signife redukti la spacon en disko stokado. Alivorte, la Huffman algoritmo - estas delonge esploris kaj laboro diagramo kiu urĝeco ne reduktas de hodiaŭ. Kaj kun la kapablo por redukti la grandecon de la dosieroj, kopii ilin sur reto aŭ per aliaj rimedoj ĝi estas pli simpla, rapida kaj oportuna. Laborante kun la algoritmo, oni povas kunpremi ajnan informon tute sen malutili al ĝia strukturo kaj kvalito, sed kun maksimuma efiko por redukti la pezo dosiero. Alivorte, la kodita de la Huffman kodo estis kaj restas la plej populara kaj grava metodo de kunpremante la dosieron grandeco.