In der digitalen Kommunikation gibt es viele Arten der Kodierung, um Informationen zu übertragen. Der Huffman-Code ist ein Code, mit dem Daten verlustfrei komprimiert werden können. Dadurch kann eine schnellere Übertragung (oder Speicherplatzersparnis: "zippen") erreicht werden. Hierzu werden die verwendeten Codewörter optimiert, d.h. in ihrer Länge so gewählt, dass häufig vorkommenden Daten kurzen Codewörtern, selten vorkommenden Daten langen Codewörtern zugeordnet sind. Zusätzlich ist zu beachten, dass der Code "präfixfrei" sein muss, d.h. kein Codewort darf Beginn eines anderen sein. (Dies gilt beispielsweise auch bei Telefonnummern: Es wäre sehr problematisch, wenn die Ziffern "110" Anfangsteil (d.h. Präfix) einer anderen Telefonnummer wären.)
Die Codewörter werden mit einem Huffman-Baum ermittelt: Die benutzten Daten werden mit ihrer entsprechenden Häufigkeit als "Blätter" nebeneinander notiert. Dann werden immer die beiden kleinsten Werte miteinander verknüpft, die Häufigkeitswerte addiert und dieser Wert eine Ebene tiefer eingetragen. Dies wird so lange wiederholt, bis ein Wert, die "Wurzel" des Baums, übrigbleibt. Anschließend werden die Codewörter von der Wurzel des Baums ausgehend bestimmt. Rechts ergibt eine (hinten angehängte) "1", links eine "0".
Die Daten "geocaching" können so dargestellt werden:
Die komprimierten Daten von "geocaching" lauten demnach (der Beginn eines neuen Codeworts ist rot markiert):
000100111011001011011110111100
Gegenüber einem Code mit fester Länge von 8 Bit (z.B. ASCII), bei dem für diese 10 Buchstaben insgesamt 80 Bit benötigt werden, eine Komprimierungsrate von 62.5%!
Beim Dekodieren wird einfach entsprechend dem jeweilige Bit dem Pfad von der Wurzel bis zu einem Blatt gefolgt und damit das gesuchte Element gefunden. Sind noch Bits übrig, wird der nächste Pfad wieder an der Wurzel begonnen.
Die Koordinaten des Caches können problemlos mit Hilfe des folgenden Baums ermittelt werden:
Wer den Huffman-Code verstanden hat, darf sich bei
00000101001110011010111111011010010001110110100111001001111111110001100
in das Logbuch eintragen!
Du kannst Deine Lösung bei Geochecker.com überprüfen.
http://de.wikipedia.org/wiki/Huffman-Kodierung