Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


informatik artikel (Interpretation und charakterisierung)

Kodierung mit variabler länge (variable-length encoding)


1. Java
2. Viren

Dieses Datenkompressionsverfahren spart beträchtlich Platz bei Textdateien.
Nehmen wir an wir wollen eine Zeichenfolge "ABRACADABRA" kodieren, und dieses mit dem herkömmlichen Verfahren des binären-Codes, bei einer Binärdarstellung mit Hilfe von 5 Bits zur
Darstellung eines Buchstabens.

Dann lautet die Bitfolge so:
0000100010100100000100011000010010000001000101001000001

Um diese zu dekodieren, nimmt man sich 5 Bits her und wandelt sie nach dem Binärcode um.
Nun ist dieses ziemlich unpraktisch, denn der Buchstabe D kommt nur einmal vor und der Buchstabe A jedoch 5 mal und man muß A jedesmal, die selbe Bitfolge, aufschreiben und wieder dekodieren.
Es wäre doch besser, wenn man versuchen würde, häufig verwendete Buchstaben eine kürzere Bitfolge zuzuweisen, indem man sagt A wird mit 0 kodiert, B mit 1, R mit 01, C mit 10 und D
mit 11, so daß dann aus ABRACADABRA dann diese

0 1 01 0 10 0 11 0 1 01 0

Bitfolge dann werden würde. Diese ist schon wesentlich kürzer denn diese Bitfolge benutzt nur mehr 15 Bits anstatt 55 Bits, so wie die vorhergehende. Dieser Code hat jedoch einen Haken, denn es ist kein wirklicher Code, da er abhängig ist von den Leerzeichen, ohne diese Leerzeichen würde nämlich

010101001101010 als
RRRARBRRA heraus kommen.

Also muß man die Zahl mit Begrenzern dekodieren, aber dann noch ist die Zahl von 15 Bits plus
10 Begrenzern noch immer kleiner als der Standard-Code.

Wenn kein Zeichencode mit dem Anfang eines anderen übereinstimmt werden keine Begrenzer benötigt. Deswegen werden wir die zu kodierenden Buchstaben anders wählen, nämlich:
A mit 11, B mit 00, C mit 010,D mit 10 und R mit 011

so gäbe es nur eine Möglichkeit, die 25 Bits Zeichenfolge

1100011110101110110001111

zu dekodieren.

Eine noch einfachere Methode zur Darstellung eines Codes ist ein Trie.

Dazu ein Bsp.: Wir wollen wieder ABRACADABRA kodieren, aber dieses mal mit dem Trie.
Dazu sollte man wissen, daß man bei einem Trie immer von der "Wurzel"
ausgeht und so sein Zeichen bestimmt. Wenn man bei einem Knoten angelangt
ist, muß man sich entscheiden ob nach links oder rechts.
Für links muß man mit 0 codieren und für rechts mit 1.



Nun, man sieht hier, daß der rechte Code um 2 Bits kürzer ist als der linke.
Die Trie-Darstellung garantiert also, daß kein Code für ein Zeichen mit dem Anfang eines anderen Zeichen übereinstimmt, so daß sich die Decodierung für die Zeichenfolge eindeutig

festlegen läßt.
Doch welchen Trie soll man Benutzen? Hier gibt es eine Lösung bei der man bei gegebener Zeichenfolge einen Trie berechnen kann und der eine minimale Bitfolge hat.
Dieses Verfahren wird Huffman Kodierung genannt.

 
 

Datenschutz
Top Themen / Analyse
indicator Pornographie und sexuelle Gewalt im Internet
indicator V.- und X.- Schnittstellen
indicator Was fällt weg? (im Vergleich zu C/C++)
indicator AMD-K6®-III Prozessor
indicator Behandlung von Laufzeitfehlern in Visual Basic-
indicator Einige Anregungen, warum man sich speziell als Lehrer mit dem Internet auseinandersetzen sollte
indicator Die Schiebebefehle
indicator Der Informatiker
indicator Datenbankmodelle der 2. Generation:
indicator GRUNDWISSENSCHAFT DES COMPUTERS: DAS ZÄHLEN


Datenschutz
Zum selben thema
icon Netzwerk
icon Software
icon Entwicklung
icon Windows
icon Programm
icon Unix
icon Games
icon Sicherheit
icon Disk
icon Technologie
icon Bildung
icon Mp3
icon Cd
icon Suche
icon Grafik
icon Zahlung
icon Html
icon Internet
icon Hardware
icon Cpu
icon Firewall
icon Speicher
icon Mail
icon Banking
icon Video
icon Hacker
icon Design
icon Sprache
icon Dvd
icon Drucker
icon Elektronisches
icon Geschichte
icon Fehler
icon Website
icon Linux
icon Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.
dsolution