Huffman-Code Mystery Cache
Hidden : 11/4/2013
Difficulty:
2.5 out of 5
Terrain:
1.5 out of 5

Size: Size: small (small)

Join now to view geocache location details. It's free!

Watch

How Geocaching Works
Looking for a different adventure?

Please note Use of geocaching.com services is subject to the terms and conditions in our disclaimer.

Geocache Description:

Der Huffman-Code

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:

Huffman-Code

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:

Koordinaten-Baum


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

Additional Hints (Decrypt)

Ybpx&Ybpx, ibear erpugf

Decryption Key

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

(letter above equals below, and vice versa)


Advertising with Us

Inventory

There are no Trackables in this cache.

View past Trackables

What are Trackable Items?

Bookmark Lists

View all bookmark lists...