Bekijk de volgende zin van twintig tekens. ‘een eend is een dier’



Dovnload 23.88 Kb.
Datum20.08.2016
Grootte23.88 Kb.
compressie

Bekijk de volgende zin van twintig tekens.


‘een eend is een dier’.
Als deze zin in een tekstbestand opgeslagen wordt, worden er twintig ascii-codes achter elkaar gezet. Omdat elke ascii-code 8 bits lang is, neemt het bestand 20x8=160 bits ruimte in.

Het valt echter op dat er in deze korte tekst erg veel e’s voorkomen, terwijl de r maar heel weinig voorkomt. We kunnen de tekst misschien korter opslaan als we veelvoorkomende letter met een korte code zouden opslaan en weinig voorkomende tekens met een lange code.

Boomstructuren

Alle morsecodes zijn in een boomstructuur weer te geven (de boom staat onderste boven!).

Begin bovenaan bij de wortel. Elke stap naar links is een punt (korte code) en een stap naar rechts is een streep (lange code)

Extra: in deze boom kun je ook zien dat veel codes ook het begin van de code van een andere letter kunnen zijn:


De E is .

De I is ..

De S is …

De H is ….


De code .. kan dus I of EE betekenen als we geen pauzes zouden gebruiken!

We moeten tussen codes dus steeds een bijzonder teken invoegen om aan te geven dat er een nieuwe teken begint. Dat heet met een mooi woord een prefix.


Het is echter ook mogelijk om bomen te bedenken waarin de code van een teken nooit het begin van de code van een ander teken is. We kunnen dan de code van een nieuw teken meteen beginnen zonder eerst een prefix op te schrijven.

De letters moeten dan natuurlijk aan het eind van een vertakking staan, bijvoorbeeld:


Als we afspreken dat een stap naar links als 0 geschreven wordt, en en stap naar rechts als 1, krijgen we de volgende codes:


I 0

R 10


P 110

J 111
Zo een codering heet een prefix-vrije codering.


Huffman

We willen dus voor een tekst een prefix-vrije codering bedenken die ook nog eens korte codes geeft voor tekens die veel voorkomen.


Stel dat in een bepaalde tekst de letter A t/m F met de volgende frequentie’s voorkomen:

De letter moeten aflopend op frequentie gesorteerd staan. In dit voorbeeld is dat ‘toevallig’ al zo.

We kunnen nu op de volgende manier een geschikte boom construeren.


stap 1

We voegen een vertakking (knoop) toe bij de twee letters met de laagste frequentie (E en F). Deze knoop krijgt als frequentie de som van de frequenties van die twee letters (4+3=7).


stap 2

We proberen weer twee tekens samen te voegen, maar dan zo dat we een zo laag mogelijk som krijgen. We proberen D + (EF) = 4 + 7 = 11.

C + D levert echter een lagere som (6+4 = 10), dus nemen we die!

Andere combinaties hebben een som groter dan 10.

Als er (in een andere situaties) meerdere mogelijkheden met dezelfde som zijn, mag je er willekeurig kiezen.

stap 3

We gaan weer op zoek naar een combinatie van twee knopen die de laagste som oplevert. In dit geval is dat EF + B = 7 + 7 = 14



stap 4

En zo gaan we verder tot we alle tekens in de boom hebben opgenomen.

In deze stap voegen we CD + EFB samen.


stap 5

We kunnen nu A + CDEFB samen voegen. Dit is de laatste stap, want we hebben nu alle letters in de boom ondergebracht (bovendien is 39 de som van alle frequenties: 15+7+6+4+4+3).



Als links weer als 0 genoteerd wordt en rechts als 1, krijgen we de volgende codes:
A is 0

C is 100


B is 111

D is 101


E is 1100

F is 1101

>> Schrijf zelf de codes van de overige letters op!

Meer details kun je lezen op: http://goethe.ira.uka.de/seminare/rftk/huffman/




Oefening

Bekijk de volgende zin: ‘de aap at aardappels’.
onderdeel a

Hoeveel bits heb je nodig om deze zin op te slaan als je elk teken als ASCII-teken opslaat?


onderdeel b

Maak een frequentietabel voor deze zin.


onderdeel c

Codeer deze zin met het Huffman-algoritme. Laat stap voor stap zien hoe je te werk gaat (dat is veel werk). Geef aan het einde een code voor elk teken (je mag dat doen door een derde kolom bij de frequentietabel te maken.


onderdeel d

Hoeveel tekens heb je nu nodig om de zin binair te coderen? Wat is de compressie factor ()


Uitwerking


  1. 20 letters * 8 = 160 bits



Letter

Frequentie

Code voor teken

d

2

011

e

2

010

a

6

10

p

3

00

spatie

3

111

t

1

11000

r

1

11001

l

1

11010

s

1

11011




  1. Zie onderdeelc1.jpg en onderdeelc2.jpg

  2. Als we de tekst met de code opschrijven wordt het:

011 010 111 10 10 00 111 10 11000 10 10 11001 011 10 00 00 010 11010 11011

Dit bevat 56 bits


Compressiefactor = 56/160 x 100 = 35 %







De database wordt beschermd door het auteursrecht ©opleid.info 2017
stuur bericht

    Hoofdpagina