Huffman codis: exemples d'aplicació

De moment, poques persones pensen sobre el fet, com funciona la compressió d'arxius. En comparació amb l'ús anterior de l'ordinador personal s'ha convertit en molt més fàcil. I gairebé totes les persones que treballen amb el sistema d'arxius fa servir l'ordinador. Però poques persones pensen sobre com funcionen i en què es basa és la compressió d'arxius. La primera versió d'aquest procés van ser els codis de Huffman, i s'utilitzen avui en dia en una varietat d'arxivadors populars. Molts usuaris ni tan sols pensa en el fàcil compressió d'arxius es porta a terme i que està treballant en un esquema. En aquest article veurem com la compressió és el matisa ajuda accelerar i simplificar el procés de codificació, així com veiem el que el principi de la codificació arbre.

algoritme de la història

El primer algoritme de codificació eficient de la informació electrònica s'ha convertit en un codi de Huffman va proposar ja a la meitat del segle XX, concretament el 1952. Va ser ell qui en aquest moment és l'element base de la majoria dels programes creats per comprimir la informació. De moment, una de les fonts més populars per a aquest codi són arxius ZIP, ARJ, RAR i molts altres. A més, l'algoritme de Huffman s'utilitza per comprimir JPEG-imatges i altres objectes gràfics. Així, tots els faxos també estan utilitzant la codificació moderna, inventat el 1952. Tot i que des de la creació del codi va prendre tant de temps per a aquest dia s'utilitza en una varietat de noves membranes i els equips dels tipus antics i moderns.

El principi de la codificació eficaç

La base de l'algoritme de Huffman inclou un esquema que li permet reemplaçar els més creïbles, més sovint símbols que apareixen codificats en binari sistema. I els que són menys comuns, substituïts per codis més llargs. Passant llargs codis de Huffman es produeix només després que el sistema utilitza tots els valors mínims. Aquesta tècnica permet reduir al mínim la longitud del codi per a cada símbol del missatge original en el seu conjunt. El punt important és que al principi de la probabilitat de codificació d'ocurrència de les lletres ha de ser ja conegut. És a partir d'ells serà preparat i el missatge final. Sobre la base d'aquestes dades, es va dur a terme la construcció de l'arbre de codi Huffman, sobre la base dels quals es durà a terme cartes procés de codificació a l'arxiu.

codi de Huffman, exemple

Per il·lustrar l'algoritme, consideri una variant gràfica de construcció de l'arbre de codi. Per utilitzar aquest mètode sigui efectiu, cal aclarir la definició de certs valors necessaris per al concepte del procés. El conjunt de la pluralitat de nodes i arcs, que es dirigeixen de node a node, anomenat gràfic. L'arbre en si és un gràfic amb un conjunt de propietats específiques:

• en cada node pot incloure no més d'un dels arcs;
• un dels nodes ha de ser l'arrel de l'arbre, és a dir, que no ha de ser part de l'arc en absolut;
• Si la tija comencen a moure al llarg dels arcs, el procés ha de permetre aconseguir per complet en qualsevol dels nodes.

També hi ha una cosa tal, part dels codis de Huffman com una fulla de l'arbre. És un node des del qual no ha de passar qualsevol arc. Si dos nodes estan connectats per un arc, un d'ells és el pare de l'altre nen, depenent de quina node s'apaga l'arc, i el que està inclòs. Si dos nodes tenen el mateix node pare, se'ls crida llocs germans. Si, en les fulles, les fulles dels nodes de diversos arcs, llavors es diu un arbre binari. Només així és l'arbre de Huffman. La peculiaritat de la construcció d'unitats és que el pes de cada pare és igual a la suma dels pesos de tots els seus nodes fills.

Un algoritme per construir l'arbre de Huffman

La construcció del codi de Huffman és l'aportació de les lletres de l'alfabet. Generat una llista de llocs que estan lliures en el futur arbre de codi. El pes de cada node en la llista ha de ser la mateixa que la probabilitat d'ocurrència dels llocs de lletres corresponents a aquest node. En aquest cas, el que pesa menys és seleccionat entre diversos llocs lliures del futur arbre. En aquest cas, si els tipus mínims s'observen en diversos llocs, es pot seleccionar lliurement qualsevol dels parells. Després ve la creació del node pare, que ha de pesar tant com la suma dels pesos dels parells de nodes. Després d'això, els pares envien a la llista amb els banys lliures, i els nens es retiren. En aquest arc són indicadors apropiats, uns i zeros. Aquest procés es repeteix tant com sigui necessari per mantenir un únic node. A continuació, escriure els dígits binaris de dalt a baix.

La millora de l'eficiència de la compressió

Per tal d'augmentar l'eficiència de compressió, és necessari durant el codi de construcció de l'arbre d'utilitzar totes les dades sobre la probabilitat d'ocurrència de les lletres en un arxiu en particular, que s'adjunta a un arbre, i no permetre que el fet que estan dispersos en un gran nombre de documents de text. Si el pre-passeig a través d'aquest arxiu, es pot calcular immediatament les estadístiques de la freqüència amb la que hi ha cartes de la instal·lació subjecta a la compressió.

L'acceleració del procés de compressió

Per accelerar l'algoritme, la definició de les lletres s'ha de fer no en termes de la probabilitat d'ocurrència d'una lletra en particular, i la freqüència de la seva ocurrència. Amb aquest algoritme es torna més fàcil, i treballar amb ells molt més ràpid. També evita les operacions associades amb la divisió de coma flotant. A més, treballar en aquesta manera, el codi de Huffman dinàmic, o més aviat el propi algorisme no està subjecta a cap canvi. Això es deu principalment al fet que les probabilitats són directament proporcionals a la freqüència. Val la pena parar atenció al fet que el pes final de l'arxiu, o l'anomenat node arrel és igual a la suma del nombre de caràcters en l'objecte a tractar.

conclusió

codis de Huffman - algoritme simple i de llarga data, que encara és utilitzat per molts programes i companyies ben conegudes. La seva simplicitat i la claredat poden aconseguir resultats eficaços comprimir arxius de qualsevol volum i reduir significativament l'espai d'emmagatzematge en disc. En altres paraules, l'algoritme de Huffman - Durant molt temps s'ha investigat i el diagrama de treball que la urgència no es redueix en aquest dia. I amb la capacitat de reduir la mida dels arxius, transferir-los a través d'una xarxa o per altres mitjans és més senzilla, ràpida i còmoda. Treballar amb l'algoritme, es pot comprimir qualsevol informació totalment sense dany a la seva estructura i qualitat, però amb un efecte màxim per reduir l'arxiu de pes. En altres paraules, la codificació del codi de Huffman ha estat i segueix sent el mètode més popular i rellevant de comprimir la mida del fitxer.