Shannon Fano-code online bouwen. Shannon-Fano-voorvoegselcode

LABWERK 9

Efficiënte codering

Doel: Effectieve codeertechnieken bestuderen.

1. Construeer een Shannon-Fano-code met behulp van de geselecteerde opties en vat de resultaten samen in tabellen.

2. Construeer een Huffman-code met behulp van de geselecteerde opties en vat de resultaten samen in tabellen. Construeer voor elke geconstrueerde code een codeboom.

Rapporteer over laboratorium werk moet bevatten:

- kort theoretische informatie over de Shannon-Fano-code en de Huffman-code;

– construeer Shannon-Fano- en Huffman-codes voor verschillende opties invoergegevens (selecteer voor elke code willekeurig drie groepen van elk 12 symbolen, wijs een waarschijnlijkheid toe aan elk symbool (de som is gelijk aan één) en construeer de aangegeven codes).

– conclusies.

Basisconcepten en definities

Shannon-Fano-code

De code is als volgt opgebouwd: de karakters van het berichtenalfabet worden in afnemende volgorde van waarschijnlijkheid in de tabel ingevoerd. Ze worden vervolgens in twee groepen verdeeld, zodat de som van de kansen in elke groep zo gelijk mogelijk is. Aan alle tekens in de bovenste helft wordt een “0” toegewezen als eerste teken, en aan alle onderste helften wordt een “1” toegewezen. Elk van de resulterende groepen wordt op zijn beurt verdeeld in twee subgroepen met dezelfde totale kansen, enz. Het proces wordt herhaald totdat er in elke subgroep één teken overblijft.

Voorbeeld 1. Laten we een effectieve codering uitvoeren van een ensemble van acht karakters, waarvan de kenmerken in de tabel worden weergegeven. 3.1.

Tabel 3.1

Rijst. 3.1. Shannon-Fano-groepm

Het is duidelijk dat met het gebruikelijke (zonder rekening te houden statistische kenmerken)-codering vereist drie binaire tekens om elk teken weer te geven. Met behulp van de Shannon-Fano-techniek verkrijgen we een reeks codecombinaties uit de tabel. 3.1.

Omdat karakterkansen gehele negatieve machten van twee zijn, wordt redundantie in de codering volledig geëlimineerd. Het gemiddelde aantal tekens per teken is in dit geval precies gelijk aan de entropie. Laten we dit verifiëren door de entropie te berekenen

,

en het gemiddelde aantal tekens per teken

,

waarbij is het aantal tekens in de codecombinatie die overeenkomt met het teken.

IN algemeen geval voor een alfabet van acht tekens zal het gemiddelde aantal tekens per teken minder dan drie zijn, maar groter dan de entropie van het alfabet.

Voorbeeld 2. Laten we de gemiddelde lengte van een codecombinatie bepalen voor een efficiënte codering van ensembletekens. Gegeven in tabel. 3.2.

De entropie van het ensemble is 2,76. Als resultaat van het vergelijken van individuele karakters van een ensemble van codecombinaties met behulp van de Shannon-Fano-methode (Tabel 3.2), verkrijgen we een gemiddeld aantal symbolen per karakter gelijk aan 2,84.

Tabel 3.2

Kenmerken van een ensemble van acht karakters

Bijgevolg blijft er enige redundantie in karakterreeksen bestaan. Uit de stelling van Shannon volgt dat deze redundantie ook geëlimineerd kan worden als we overstappen op het coderen in voldoende grote blokken.

Hetzelfde bericht kan worden gecodeerd op verschillende manieren. De meest winstgevende code is degene waarin deze kost minimale tijd. Als dezelfde tijd wordt besteed aan het verzenden van elk element van een symbool (bijvoorbeeld 0 of 1), dan is de optimale code degene die de tijd nodig heeft om een ​​bericht van een bepaalde lengte te verzenden minimale hoeveelheid elementaire symbolen. Shannon-Fano-codes zijn voorvoegselcodes, dwz geen enkel codewoord is een voorvoegsel van een ander. Deze eigenschap Hiermee kunt u elke reeks codewoorden ondubbelzinnig decoderen

Laten we eens kijken naar het principe van het construeren van een van de eerste compressie-algoritmen, die werd geformuleerd door de Amerikaanse wetenschappers Shannon en Fano met behulp van het voorbeeld van letters uit het Russische alfabet. Het algoritme maakt gebruik van codes variabele lengte, d.w.z. een veel voorkomend teken wordt gecodeerd met een code van kortere lengte, en een zelden voorkomend teken wordt gecodeerd met een code van grotere lengte.

Om zo'n code samen te stellen, moet je uiteraard weten hoe vaak letters in de Russische tekst voorkomen. Deze frequenties worden weergegeven in Tabel 1. De letters in de tabel zijn gerangschikt in afnemende volgorde van frequentie.

Tabel 1

Frequentie van verschijnen van letters van het Russische alfabet

Met behulp van de tabel kunt u de meest economische code maken op basis van overwegingen met betrekking tot de hoeveelheid informatie. Het is duidelijk dat de code het meest economisch zal zijn wanneer elk elementair symbool de maximale informatie overbrengt. Beschouw een elementair symbool (dat wil zeggen het signaal dat het vertegenwoordigt) als fysiek systeem met twee mogelijke toestanden: 0 en 1. De informatie die dit symbool geeft is gelijk aan de entropie van dit systeem en is maximaal in het geval dat beide toestanden even waarschijnlijk zijn; in dit geval geeft het elementaire symbool de informatie 1 (binaire één) door. Daarom zal de basis voor een optimale codering de eis zijn dat elementaire karakters in de gecodeerde tekst gemiddeld even vaak voorkomen.

Het idee van het coderen is dat de gecodeerde karakters (letters of lettercombinaties) in twee ongeveer even waarschijnlijke groepen worden verdeeld: voor de eerste groep karakters wordt 0 op de eerste plaats van de combinatie geplaatst (het eerste karakter van de binair getal dat het teken vertegenwoordigt); voor de tweede groep - 1. Vervolgens wordt elke groep opnieuw verdeeld in twee ongeveer even waarschijnlijke subgroepen; voor symbolen uit de eerste subgroep wordt 0 op de tweede plaats geplaatst; voor de tweede subgroep - één, enz.

Laten we het principe van het construeren van de Shannon-Fano-code demonstreren aan de hand van het voorbeeld van materiaal uit het Russische alfabet (zie Tabel 1). Laten we de eerste zes letters tellen (van “−” tot “t”); als we hun kansen (frequenties) optellen, krijgen we 0,498; alle andere letters van “n” tot “f” hebben ongeveer dezelfde waarschijnlijkheid van 0,502. De eerste zes letters (van “-” tot “t”) hebben in de eerste plaats een binaire 0. De overige letters (van “n” tot “f”) zullen in de eerste plaats een 1 hebben. Vervolgens verdelen we de eerste groep opnieuw in twee ongeveer even waarschijnlijke subgroepen: van “−” tot “o” en van “e” tot “t”; Voor alle letters van de eerste subgroep zetten we een nul op de tweede plaats, en een eenheid in de tweede subgroep. We zullen het proces voortzetten totdat er in elke divisie precies één letter overblijft, die in een bepaalde letter zal worden gecodeerd binair getal. Het constructiemechanisme wordt weergegeven in Tabel 2 en de code zelf wordt weergegeven in Tabel 3.

Tabel 2

Het mechanisme voor het construeren van de Shannon-Fano-code aan de hand van het voorbeeld van het Russische alfabet

Tabel 3

Het resultaat van het coderen van letters van het Russische alfabet met behulp van de Shannon - Fano-code

Voorbeeld 4. Laten we de zinsnede 'coderingsmethode' schrijven met behulp van de Shannon-Fano-code.

Oplossing: Laten we Tabel 3 gebruiken en het volgende resultaat krijgen:

(1001)s (110011)p (001)o (1001)s (001)o (111010)b (000)spatie

(10111)k (001)o (110010)d (0110)i (10100)r (001)o (10101)c

(0101)a (1000)n (0110)i (110110)i

Merk op dat het hier niet nodig is om de letters van elkaar te scheiden speciaal teken, aangezien zelfs zonder dit decodering ondubbelzinnig wordt uitgevoerd vanwege de prefix-eigenschap: geen kortere codecombinatie is het begin van een langere codecombinatie. Uit Tabel 3 blijkt inderdaad dat de kortste codes voor de tekens “spatie” en “o” gelden. Bovendien heeft geen enkele andere langere code 000 (“spatie”) en 001 (“o”) aan het begin van de reeks. Hetzelfde kan worden waargenomen voor alle andere binaire reeksen van de Shannon-Fano-code, die in Tabel 3 worden gegeven.

Opgemerkt moet worden dat elke fout tijdens het coderen (willekeurige verwarring van 0 of 1 tekens) met een dergelijke code desastreus is, aangezien het decoderen van alle tekst die volgt op de fout onmogelijk wordt.

Voorbeeld 5. Laten we bepalen of de code die we hebben overwogen optimaal is als er geen fouten zijn?

Oplossing: Laten we de gemiddelde informatie per elementair symbool (0 of 1) vinden en vergelijken met het maximum mogelijke informatie, wat gelijk is aan één. Om dit te doen, vinden we eerst de gemiddelde informatie in één letter van de verzonden tekst, dat wil zeggen de entropie per letter (zie formule 8):

Met behulp van Tabel 1 bepalen we het gemiddelde aantal elementaire symbolen per letter:

De informatie per teken ligt dus zeer dicht bij de bovengrens van één, en deze code zeer dicht bij optimaal.

Bij gebruik van vijf cijfers binaire code informatie per karakter:

Voorbeeld 6. Laat een bericht (een woord in het Russisch) gecodeerd met de Shannon-Fano-code: 10111001110010010010100 ontvangen via een communicatiekanaal.

Het is noodzakelijk om deze reeks te decoderen.

Oplossing: Het decoderingsproces is gebaseerd op de prefix-eigenschap van de code en wordt van links naar rechts uitgevoerd. Uit Tabel 3 blijkt dat de minimale codelengte drie bits is. Het telt drie bits vanaf het begin van de ontvangen codecombinatie, we krijgen - 101. Een dergelijke code staat niet in de tabel, dus we voegen nog een bit toe, we krijgen - 1011. Deze code staat daarom ook niet in de tabel , we moeten nog een bit toevoegen, we krijgen de combinatie - 10111, wat overeenkomt met de letter "k". De codecombinatie 10111 is uitgesloten van de geaccepteerde codecombinatie en wordt vervangen door het oorspronkelijke teken (de letter “k”). Het proces van het decoderen van de resterende letters van het ontvangen bericht wordt op dezelfde manier uitgevoerd.

Het volledige decoderingsproces wordt weergegeven in Tabel 4. Het “-” teken in de tabel betekent dat de geselecteerde code niet in Tabel 3 staat.

Tabel 4

Berichtdecoderingsproces

Het woord dat wordt verkregen als resultaat van het decoderen van de ontvangen codecombinatie is dus "coder".

Codelengte si) in de resulterende tabel is gelijk aan int(-log p(c(i))), als de tekens in groepen met dezelfde frequentie kunnen worden verdeeld, anders is de codelengte int(-lg p(c(i))) + 1.

39 bits lang. Gezien het feit dat het origineel een lengte had van 136 bits, krijgen we een compressieverhouding van ~28% - niet zo slecht.
Als we naar de resulterende reeks kijken, rijst de vraag: "Hoe kan ik dit nu decomprimeren?" We kunnen niet, zoals bij codering, elke 8 bits van de invoerstroom vervangen door code met variabele lengte. Bij het decomprimeren moeten we het tegenovergestelde doen: de code met variabele lengte vervangen door een symbool van 8 bits lang. IN in dit geval, zou het het beste zijn om een ​​binaire boom te gebruiken, waarvan de bladeren karakters zullen zijn (analoog aan een Huffman-boom).
Shannon-Fano-codering is een vrij oude compressiemethode en is tegenwoordig niet meer van praktisch belang (behalve als oefening in een cursus datastructuren). In de meeste gevallen is de lengte van de gecomprimeerde reeks gelijk deze methode, is gelijk aan de lengte van de gecomprimeerde reeks met behulp van Huffman-codering. Maar bij sommige sequenties worden nog steeds niet-optimale Shannon-Fano-codes gevormd, dus compressie met de Huffman-methode wordt als effectiever beschouwd. Beschouw bijvoorbeeld een reeks met de volgende tekeninhoud: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. De Huffman-methode comprimeert deze tot 77 bits , maar Shannon-Fano tot 79 bits.

Vanwege dergelijke onzekerheid hebben sommige mensen zelfs de volgende gedachten: "... het programma wijst soms enkele symbolen toe..." enzovoort - redeneren over de lengte van codes. Als je geen AI schrijft, klinkt het concept van een "programma dat soms" iets doet, belachelijk. Rechts geïmplementeerd algoritme- werkt strikt gedefinieerd.

Het Shannon-Fano-algoritme is een van de eerste compressie-algoritmen, voor het eerst geformuleerd door de Amerikaanse wetenschappers Shannon en Fano, en vertoont grote overeenkomsten met het Huffman-algoritme. Het algoritme is gebaseerd op herhalingsfrequentie. Een vaak voorkomend teken wordt dus gecodeerd met een code van kortere lengte, en een zelden voorkomend teken wordt gecodeerd met een code van grotere lengte.
De tijdens het coderen verkregen codes zijn op hun beurt een voorvoegsel. Hiermee kunt u elke reeks codewoorden ondubbelzinnig decoderen. Maar dit is allemaal een introductie.

Om te werken moeten beide algoritmen een tabel met frequenties van elementen van het alfabet hebben.

Het Huffman-algoritme werkt dus als volgt:

1. De ingang ontvangt gegevens geordend op niet-stijgende frequenties..
2. De twee letters van het alfabet met de laagste frequentie worden geselecteerd en er wordt een ouder gemaakt (de som van de twee frequenties van deze “bladeren”).
3. Afstammelingen worden verwijderd en de ouder wordt op hun plaats geschreven, de “takken” van de ouder worden genummerd: de linker tak krijgt “1” toegewezen, de rechter tak “0”.
4. Stap twee wordt herhaald totdat de hoofdouder, de ‘wortel’, is gevonden.

Het Shannon-Fano-algoritme werkt als volgt:

1. De ingang ontvangt gegevens geordend op niet-stijgende frequenties.
2. Er is een middelpunt dat het alfabet in ongeveer twee delen verdeelt. Deze delen (sommen van alfabetfrequenties) zijn ongeveer gelijk. De linkerkant krijgt de waarde “1” en de rechterkant “0”, dus we krijgen de bladeren van de boom
3. Stap 2 wordt herhaald totdat we een enkel element van de reeks krijgen, d.w.z. blad

Nou, nadat je de informatie snel hebt begrepen, kun je de code voor het Shannon-Fano-algoritme in Pascal schrijven. Ze vroegen mij om erover te schrijven. Daarom zal ik de lijst samen met opmerkingen verstrekken.

Programma ShannonFano; gebruikt crt; const a:array of char = ("a", "b", "c", "d", "e", "f"); ( karakters ) af:array van gehele getallen = (10, 8, 6, 5, 4, 3); (tekenfrequentie) (Procedure voor het zoeken naar de code van elke letter) procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer); var dS:reëel; (Matrixgemiddelde) i, m, S:geheel getal; ( m - nummer van de middelste letter in de reeks, S - som van cijfers, linkertak) c_branch:string; (huidige geschiedenis van beurten per vertakking) beginnen (controleer of dit een nul-invoer is en wis vervolgens de geschiedenis) als (a<>" ") dan c_branch:= volledige_branch + branch else c_branch:= ""; (Exitcriterium: als de karakterposities overeenkomen, dan is dit het einde) if (start_pos = end_pos) then begin WriteLn(a, " = ", c_branch); Uitgang; einde; (Berekenen van de gemiddelde frequentiewaarde in een reeks) dS:= 0; for i:=start_pos tot end_pos do dS:= dS + af[i];

dS:= dS/2;

(Hier kun je er een hebben

voor lus , terwijl, herhaal zoeken naar het midden ) S:= 0;= 2). De letters (of eventuele te coderen berichten) van het oorspronkelijke alfabet worden geschreven in volgorde van afnemende waarschijnlijkheid. De op deze manier geordende reeks letters is verdeeld in twee delen, zodat de totale kansen van deze subsets ongeveer gelijk zijn. Aan alle karakters (letters) van de bovenste helft wordt het code-element 1 toegewezen als het eerste karakter, en aan alle lagere karakters wordt de waarde 0 toegewezen. Vervolgens wordt elke subset opnieuw verdeeld in twee subsets met dezelfde voorwaarde van gelijkheid van waarschijnlijkheden en met dezelfde voorwaarde voor toewijzing van code-elementen als tweede teken. Deze verdeling gaat door totdat de subset slechts één letter van het gecodeerde alfabet bevat. Bij elke splitsing krijgen de letters in de bovenste subset een code-element van 1 toegewezen, en krijgen de letters in de onderste subset een code-element van 0 toegewezen.

Voorbeeld. Voer een efficiënte codering uit van een ensemble van acht karakters:

2.7 en
.

Zoals je kunt zien, l gemiddelde = H Daarom is de resulterende code optimaal.

Merk op dat bij uniforme (zonder rekening te houden met statistische kenmerken) codering wordt gebruikt , terwijl, herhaal zoeken naar het midden ) S:= 0;=2 tekens zal het aantal elementen in de codereeks zijn l loggen , terwijl, herhaal zoeken naar het midden ) S:= 0; N= log 2 8 = 3, d.w.z. Er zouden drie binaire tekens nodig zijn om elk teken van het gebruikte alfabet weer te geven.

Bij het coderen met de Shannon-Fano-methode blijft er in de regel enige redundantie in tekenreeksen bestaan ​​( l Wo > H).

Deze overtolligheid kan worden geëlimineerd door te verhuizen naar codering groot genoeg blokken .

Voorbeeld. Laten we eens kijken naar de procedure voor het efficiënt coderen van berichten die zijn gevormd met behulp van een alfabet dat uit slechts twee tekens bestaat X 1 en X 2 met respectievelijk de waarschijnlijkheid van optreden

P(X 1) = 0,9; P(X 2) = 0,1.

Omdat de kansen niet gelijk zijn, zal de reeks van dergelijke letters redundant zijn. Met letter-voor-letter codering zullen we echter geen enkel effect bereiken. De overdracht van elke letter vereist inderdaad een 1- of 0-symbool, terwijl de entropie gelijk is aan
, d.w.z. blijkt
.

Bij het coderen van blokken die twee letters bevatten, krijgen we de volgende codes:

Omdat de tekens niet statistisch gerelateerd zijn, worden de blokkansen bepaald als het product van de kansen van de samenstellende tekens. Gemiddeld aantal tekens per blok
en voor de letter 1,29/2 = 0,645, d.w.z. benaderd N= 0,47, en dus was het mogelijk om de codeerefficiëntie te vergroten.

Het coderen van blokken met drie karakters geeft een nog groter effect:

Het gemiddelde aantal symbolen per blok is 1,59 en per teken 0,53, wat slechts 12% meer entropie is.