Delphi-PRAXiS

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Programmieren allgemein (https://www.delphipraxis.net/40-programmieren-allgemein/)
-   -   Huffmann-Code (https://www.delphipraxis.net/30473-huffmann-code.html)

titus 25. Sep 2004 12:27


Huffmann-Code
 
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 25. Sep 2004 12:42

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


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

ibp 25. Sep 2004 12:54

Re: Huffmann-Code
 
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 25. Sep 2004 13:56

Re: Huffmann-Code
 
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 25. Sep 2004 14:13

Re: Huffmann-Code
 
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 25. Sep 2004 14:16

Re: Huffmann-Code
 
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


Alle Zeitangaben in WEZ +1. Es ist jetzt 17:29 Uhr.

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz