Huffman Baum in Haskell < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | Eine vielfach genutzte Methode zur Komprimierung von Texten benutzt die sogenannten Huffman-Bäume. Ein
Huffman-Baum ist ein binärer Baum, in dem jeder Knoten ein Blatt ist oder zwei Söhne hat. Alle Blätter sind
mit Zeichen markiert. Die entsprechende Datenstruktur in Haskell ist:
data Huffman_Baum = B Char | K Huffman_Baum Huffman_Baum
Hier ist B der Konstruktor für ein Blatt, der Parameter vom Typ Char ist dessen Marke und K ist der Konstruk-
tor für einen nicht-Blatt-Knoten mit den beiden Söhnen.
Als Code eines Zeichens dient seine Adresse im Baum. Die Codierung einer Zeichenfolge ist einfach die Verket-
tung der Codes aller Zeichen der Folge.
Um einen Text zu codieren, verwendet man eine Codierfunktion, die zu jedem Zeichen seinen Code zuordnet.
Diese Codierfunktion kann man aus dem Huffman-Baum gewinnen.
Um einen Text zu decodieren, traversiert man entsprechend der anliegenden Folge aus {0,1}*, beginnend an
der Wurzel, durch den Huffman-Baum, bis man zu einem Blatt gelangt. Die Marke dieses Blattes ist das erste
decodierte Zeichen. Dann fängt man wieder neu bei der Wurzel an.
Damit die Codierung einen Komprimierungseffekt hat, wird für häufig auftretende Zeichen ein sehr kurzer Code
vergeben. Das bedeutet, dass solche Zeichen als Marke von Blättern mit kleiner Adresse auftreten. Kennt man
die Häufigkeit der einzelnen auftretenden Zeichen, so kann man einen optimalen Huffman-Baum folgendermaßen
konstruieren:
1. Man startet damit, dass jedes Zeichen in einen separaten Huffman-Baum gespeichert wird. Die Wurzel
eines solchen Baumes ist zunÄachst das einzige Blatt, das mit dem entsprechenden Zeichen markiert ist.
Jeder dieser Bäume erhÄalt eine Häufigkeit entsprechend der Häufigkeit des gespeicherten Zeichens.
2. Schrittweise werden dann zwei entstandene Huffman-Bäume kombiniert, indem eine neue Wurzel erzeugt
wird und beide als deren SÄohne eingetragen werden. Es ist belanglos, welcher der zur Kombination aus-
gewählten Bäume als linker oder rechter Sohn eingetragen werden. Der entstandenen Huffman-Baum
erhält als Häufigkeit die Summe der Häufigkeiten seiner Söhne.
Kombiniert werden immer zwei Bäumen, die unter allen vorhandenen Bäumen die kleinsten Häufigkeiten
haben. Wenn mehrere vorhandene Bäume in Frage kommen, wählt man beliebig zwei aus.
3. Das Verfahren endet, wenn alle Bäume zu einem einzigen Huffman-Baum kombiniert sind.
Es seien folgende Typen vorgegeben:
data Huffman_Baum = B Char | K Huffman_Baum Huffman_Baum
type Codierung = String
type Haeufigkeits_Liste = [(Char,Int)]
type Codierfunktion = Char->Codierung
Implementieren Sie in Haskell
1. Eine Funktion bilde_CF::Huffman_Baum->Codierfunktion, die aus einem Huffman-Baum eine Codier-
funktion aufbaut.
2. Eine Funktion codiere::Codierfunktion->String->Codierung zur Codierung einer Zeichenkette.
3. Eine Funktion decodiere::Huffman_Baum->String->String zur Decodierung.
4. Eine Funktion bilde_HB::Haeufigkeits_Liste->Huffman_Baum, die einen optimalen Huffman-Baum
konstruiert. |
Hallo erstmal,...
Ich habe da eine Frage zu Aufgabe 4, also ich habe folgende Implementierung:
data HTree = Blatt Char | Knoten HTree HTree
deriving (Eq, Show)
type Zeichen = (Char,Int)
qsortlist :: [Zeichen] -> [Zeichen] -- sortiert Liste nach ihrer Größe, absteigend
qsortlist [] = []
qsortlist ((x,n):xs) = qsortlist kleiner
++ [(x,n)]
++ qsortlist groesser
where kleiner = [(y,m)| (y,m)<-xs, m<n]
groesser = [(y,m)| (y,m)<-xs, m>=n]
mkBlatt :: (Char,Int) -> HTree -- macht aus einem Zeichen ein Blatt
mkBlatt (c,n) = Blatt c
list2tree :: [Zeichen]->[HTree] -- wandelt Zeichenliste in Baumliste um
list2tree xs = map mkBlatt (qsortlist xs)
verschmelzen ::[(Char,Int)]-> HTree -- links den Baum mit dem größeren Gewicht
verschmelzen [(c1,n1),(c2,n2)]
| n1 <= n2 = Knoten b1 b2
| otherwise = Knoten b2 b1
where b1 = mkBlatt (c1,n1)
b2 = mkBlatt (c2,n2)
mkHTree :: [HTree] ->[(Char,Int)]-> [HTree] -- schrittweise verschmelzen der Bäume
mkHTree = [b] -- Stoppfall
mkHTree (b1:b2:bs) = mkHTree (insTreeInList b bs)
where b = verschmelzen [(c1,n1),(c2,n2)] -- -> Fehler
-- einfügen eines Baums in eine Liste von Bäumen
-- entsprechend dem Baumgewicht, absteigend
insTreeInList :: HTree -> [HTree] -> [HTree]
insTreeInList b [] = [b]
insTreeInList b (x:xs) = b:x:xs
makeHuffmantree :: [Zeichen] -> HTree --Ziel
makeHuffmantree xs = head (mkHTree (list2tree xs))
Mein Problem liegt an der Stelle 'mkHTree' und zwar bei 'where b = verschmelzen [(c1,n1),(c2,n2)]'
Er sagt immer, das n1 eine undefinierte Variable sei.
Bsp: [('n',1),('m',1),('i',8),('e',20)] ... c1 ist das Zeichen, hier z.B. 'n' und n1 ist die dazugehörige Zahl, also 1, nur wie kann ich das Haskell klar machen???
Kann mir einer Helfen...
Oder vielleicht hat jemand einen anderen Lösungsvorschlag. Bin für alles offen.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 02.01.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
