Haal-naar-vorencodering
De haal-naar-vorencodering is een transformatie die een tekenreeks gemakkelijker te bewerken maakt. Een tekenreeks zal na toepassen van haal-naar-vorencodering uit een reeks relatief kleine getallen bestaan. Dat is er een reden voor dat de codering in de datacompressie wordt gebruikt. Het is vooral als reorganisatiestap handig. Het is na de codering gemakkelijker om de huffmancodering toe te passen. Vergelijk het ook met de Burrows-Wheelertransformatie en het gebruik van bzip2.
Het Alt-Tabsysteem in Microsoft Windows is in feite een haal-naar-vorensysteem. Er is een lijst van vensters en de gebruiker kiest door de Tab een aantal malen in te drukken welk venster vooraan in de lijst komt te staan. Op deze manier minimaliseer je het aantal tab-aanslagen als je vaak tussen twee vensters wisselt.
Voorbeeld bewerken
Stel we willen een tekenreeks ananas in het alfabet [a-z]* coderen. Er wordt om de codering uit te voeren, een andere tekenreeks bijgehouden. Deze is in de beginsituatie gelijk aan de tekens van het gebruikte alfabet. We mogen de volgorde zelf kiezen, als we bij het ontsleutelen maar dezelfde volgorde gebruiken. De tekenreeks die extra wordt gebruikt is:
abcdefghijklmnopqrstuvwxyz
Loop nu achtereenvolgens alle tekens in de tekenreeks af, die we willen versleutelen. Voor ieder teken
- noteren we de positie in de hulpreeks
- verplaatsen we het teken in de hulpreeks naar de meest linkse positie
Voor ananas wordt het:
|
abcdefghijklmnopqrstuvwxyz |
a op positie 1. a naar voren |
De haal-naar-vorencodering van ananas is 1,14,2,2,2,19. Een rij van veel kopieën van hetzelfde teken bestaat na toepassing van het algoritme bijvoorbeeld uit aan het begin een nummer, gevolgd door een zeker aantal keer een 1. Als vuistregel geldt dat een symbool dat pasgeleden is langsgekomen, een laag nummer als uitvoer geeft, terwijl een symbool dat minder kort geleden is langsgekomen, een hoger nummer krijgt.
De transformatie kan ongedaan worden gemaakt. Dit gaat op dezelfde manier als het toepassen van de transformatie, met als enige verschil dat we niet ieder teken van de originele reeks opzoeken in de hulpreeks, maar dat we het teken gebruiken op de positie aangegeven in de getransformeerde rij.