Huffman-codes: voorbeelden, toepassingen

Op dit moment denken maar weinig mensen erover nahoe werkt bestandscompressie. In vergelijking met het verleden is het gebruik van een pc veel eenvoudiger geworden. En bijna iedereen die met het bestandssysteem werkt, gebruikt archieven. Maar weinig mensen denken na over hoe ze werken en volgens welk principe bestandscompressie plaatsvindt. Huffman-codes werden de allereerste versie van dit proces en ze worden nog steeds gebruikt in verschillende populaire archiveringsprogramma's. Veel gebruikers denken niet eens na over hoe eenvoudig de bestandscompressie is en met welk schema het werkt. In dit artikel zullen we bekijken hoe compressie plaatsvindt, welke nuances helpen bij het versnellen en vereenvoudigen van het coderingsproces, en we zullen ook begrijpen wat het principe van het bouwen van een coderingsboom is.

Algoritme geschiedenis

Het allereerste algoritme voor effectief uitvoerencodering van elektronische informatie was de code die Huffman in het midden van de twintigste eeuw voorstelde, namelijk in 1952. Hij is op dit moment het belangrijkste basiselement van de meeste programma's die zijn ontworpen om informatie te comprimeren. Momenteel is een van de meest populaire bronnen die deze code gebruiken ZIP, ARJ, RAR en vele andere.

Dit Huffman-algoritme wordt ook gebruikt voorCompressie van JPEG-afbeeldingen en andere grafische objecten. Welnu, alle moderne faxen gebruiken ook codering, uitgevonden in 1952. Ondanks het feit dat er zoveel tijd is verstreken sinds het maken van de code, wordt het tot op de dag van vandaag gebruikt in de nieuwste shells en op apparatuur van de oude en moderne types.

Het principe van efficiënte codering

Het Huffman-algoritme is gebaseerd op een circuit,zodat u de meest waarschijnlijke, meest voorkomende tekens kunt vervangen door binaire systeemcodes. En degenen die minder vaak voorkomen, worden vervangen door langere codes. De overgang naar lange Huffman-codes vindt pas plaats nadat het systeem alle minimumwaarden heeft gebruikt. Met deze techniek kunt u de codelengte voor elk teken van het oorspronkelijke bericht als geheel minimaliseren.

Het belangrijke punt is dat in het beginhet coderen van de waarschijnlijkheid van het voorkomen van letters zou al bekend moeten zijn. Van hen zal het uiteindelijke bericht worden samengesteld. Op basis van deze gegevens wordt de Huffman-codeboom opgebouwd, op basis waarvan het proces van het coderen van letters in het archief zal worden uitgevoerd.

Huffman Code Voorbeeld

Neem om het algoritme te illustrerengrafische versie van de codeboomconstructie. Om deze methode effectief te gebruiken, is het de moeite waard om de definitie te verduidelijken van enkele waarden die nodig zijn voor het concept van deze methode. De set van veel bogen en knooppunten die van knooppunt naar knooppunt worden geleid, wordt een grafiek genoemd. De boom zelf is een grafiek met een reeks specifieke eigenschappen:

• elk knooppunt mag niet meer dan één van de bogen bevatten;
• een van de knooppunten moet de wortel van de boom zijn, dat wil zeggen dat deze helemaal geen bogen mag bevatten;
• als u vanaf de wortel langs bogen begint te bewegen, zou dit proces u in staat moeten stellen om absoluut elk van de knooppunten te bereiken.

Er zit ook zo'n concept in de codesHuffman is als een blad van een boom. Het is een knooppunt waarvan geen bogen mogen worden afgesloten. Als twee knooppunten met elkaar zijn verbonden door een boog, dan is een van hen een ouder, de andere is een kind, afhankelijk van welk knooppunt de boog verlaat en waar het binnenkomt. Als twee knooppunten hetzelfde bovenliggende knooppunt hebben, worden ze meestal zusterknooppunten genoemd. Als er naast bladeren meerdere bogen verschijnen op de knooppunten, wordt deze boom binair genoemd. Precies zo is de Huffman-boom. Een kenmerk van de knooppunten van deze constructie is dat het gewicht van elke ouder gelijk is aan de som van het gewicht van al zijn nodale kinderen.

Huffman Tree-algoritme

Huffman-code is gemaakt van lettersinvoer alfabet. Er wordt een lijst gevormd met de knooppunten die vrij zijn in de toekomstige codeboom. Het gewicht van elk knooppunt in deze lijst moet hetzelfde zijn als de kans dat een berichtletter overeenkomt met dat knooppunt. Bovendien wordt onder de weinige vrije knooppunten van de toekomstige boom degene geselecteerd die het minst weegt. Bovendien, als de minimumindicatoren in verschillende knooppunten worden waargenomen, kunt u vrijelijk een van de paren kiezen.

Waarna de creatie van de ouderknooppunt, dat evenveel moet wegen als de som van dit paar knooppunten. Daarna wordt de ouder met gratis knooppunten naar de lijst gestuurd en worden de kinderen verwijderd. In dit geval krijgen de bogen de bijbehorende indicatoren, eenheden en nullen. Dit proces wordt zoveel als nodig herhaald om slechts één knooppunt over te houden. Vervolgens worden binaire cijfers geschreven in de richting van boven naar beneden.

Verhoog de compressie-efficiëntie

Om de compressie-efficiëntie te verhogen, moet uhet is tijd om een ​​codeboom te bouwen om alle gegevens te gebruiken met betrekking tot de waarschijnlijkheid dat letters verschijnen in een bepaald bestand dat aan de boom is gekoppeld en niet toe te staan ​​dat ze over een groot aantal tekstdocumenten worden verspreid. Als u dit bestand voor het eerst doorloopt, kunt u onmiddellijk de statistieken berekenen van hoe vaak letters van het te comprimeren object worden gevonden.

Versnel het compressieproces

Om het algoritme te versnellen, de definitie van lettershet is noodzakelijk om niet te leiden door de indicatoren van de waarschijnlijkheid van het verschijnen van een letter, maar door de frequentie van het voorkomen ervan. Hierdoor wordt het algoritme eenvoudiger en wordt het werken aanzienlijk versneld. Dit vermijdt ook drijvende-komma- en delingsbewerkingen.

Bovendien is het werken in deze modus dynamischHuffman-code, of liever het algoritme zelf, is niet onderhevig aan wijzigingen. Dit komt voornamelijk doordat de kansen recht evenredig zijn met de frequenties. Bijzondere aandacht verdient het feit dat het uiteindelijke gewicht van het bestand of het zogenaamde rootknooppunt gelijk is aan de som van het aantal letters in het te verwerken object.

conclusie

Huffman-codes - Eenvoudig en lang gemaakteen algoritme dat nog steeds wordt gebruikt door veel bekende programma's en bedrijven. Zijn eenvoud en begrijpelijkheid maken het mogelijk om effectieve resultaten te bereiken van bestandscompressie van elke grootte en de ruimte die ze op de opslagschijf innemen aanzienlijk te verminderen. Met andere woorden, het Huffman-algoritme is een lang bestudeerd en ontwikkeld schema, waarvan de relevantie tot op de dag van vandaag niet afneemt.

En dankzij de mogelijkheid om de bestandsgrootte te verkleinen,hun overdracht via het netwerk of op andere manieren wordt gemakkelijker, sneller en handiger. Als u met het algoritme werkt, kunt u absoluut alle informatie comprimeren zonder de structuur en kwaliteit ervan te schaden, maar met het maximale effect van het verminderen van het bestandsgewicht. Met andere woorden, Huffman-codering was en blijft de meest populaire en relevante methode om de bestandsgrootte te comprimeren.