Huffmann-Code

[titus]

Hi, ich würd gerne eine Komprimierung für Strings schreiben.
Nun hab ich mal recherchiert und eine sogenannte Huffman-Codierung gefunden.

Nun da ich leider noch beschränktes Wissen in Sachen Mathe habe, wollte ich fragen, wie man das jetzt anwenden könnte.
Ich hoffe ihr könnt mir helfen.

mfG, titus

[tommie-lie]

Bei der Konkurrenz findet man zwei Huffman-Tutorials: hier und hier.


Edit: Links korrigiert... ist noch früh am morgen...

[ibp]

hi titus,
dafür brauchst du nicht wirklich mathe, vielleicht nur für das verständnis was dahinter steht:

Zitat:

...liegt die Idee nahe, häufig vorkommende Zeichen durch möglichst kurze Codewörter zu codieren...

die genaue konstruktion ist doch dargestellt:

Zitat:

Methode:
erzeuge für jedes Symbol x, das im zu codierenden Text t vorkommt, einen Knoten und markiere den Knoten mit der Häufigkeit, mit der x im Text vorkommt;
wiederhole solange es mehr als einen Knoten gibt, zu dem keine Kante hinführt
suche zwei Knoten u und v mit minimaler Markierung p(u) bzw. p(v), zu denen noch keine Kante hinführt;
erzeuge einen neuen Knoten w und verbinde w mit u und v. Markiere die eine Kante mit 0, die andere mit 1. Markiere den Knoten w mit p(u) + p(v);

erläutere genauer was du nicht verstehst!

[titus]

Zitat:

Zitat von ibp

Zitat:

Methode:
erzeuge für jedes Symbol x, das im zu codierenden Text t vorkommt, einen Knoten und markiere den Knoten mit der Häufigkeit, mit der x im Text vorkommt;
wiederhole solange es mehr als einen Knoten gibt, zu dem keine Kante hinführt
suche zwei Knoten u und v mit minimaler Markierung p(u) bzw. p(v), zu denen noch keine Kante hinführt;
erzeuge einen neuen Knoten w und verbinde w mit u und v. Markiere die eine Kante mit 0, die andere mit 1. Markiere den Knoten w mit p(u) + p(v);

hi ibp, ich verstehe das mit den Knoten nicht, wie die dargestellt sein sollen.
achja ich würde das gerne in PHP schreiben, deshalb nützt mir der delphi-code nix (hab nichma delphi installiert :D), trotzdem danke tommie-lie (werd mir den code natürlich auch anschaun, aber weiß net ob was rauskommt XD).

mfG

[ibp]

wie du das sichtbar machst ist deine sache aber

1. es gibt so viele knoten wie unterschiedliche zeichen du in deinem text hast incl. leerzeichen!
2. schreibe zu diesen knoten das vorkommen der zeichen (z.b. wie oft e im text vorkommt)
3. nimm zwei knoten mit dem kleinsten vorkommen
4. verbinde diese knoten zu einem neuen dritten, der bekommt die anzahl=summe der beiden verbundenen.
5. bezeichne die eine verbindung mit 0 und die andere mit 1
6. mach das so lange(weiter bei schritt 3), bis es nur noch einen knoten gibt!

soweit solltest du erstnal kommen mit php kann ich dir leider nicht helfen..:?

[titus]

Hm hört sich gut an, ich werde mal dran rumexperimentieren.
Und wenn sich ein Ergebnis zeigt werd ich mich melden und es hier posten ;).

mfG