www.jammni.de

Logo - Kleiner Drache
Login
Username:

Passwort:

Daten merken
Auto-Login
Registrieren
 
Online
niemand
 
Forumsuche
Suche nach:

Logo - DracheHaskell-Forum

franzigoth1

Gepostet:
06.12.2007 16:15

Huffman Baum  
Hallo,....

Kann mir jemand bei folgenden Problemen helfen, hab keine Ahnung, wie ich da anfangen soll:

1. Aus einen Huffman Baum eine Codierfunktion macht
z.B. hb = K (K (K (B 'n') (B 'm')) (B 'i')) (B 'e')
cf = bilde_CF hb
cf 'e' == "1"
cf 'm' == "001"
2. eine codierfunktion zur codierung einer Zeichenkette umwandeln

3. einen Huffman Baum dekodieren, und
z.B. hb = K (K (K (B 'n') (B 'm')) (B 'i')) (B 'e')
c = "0010100010001000"
decodiere hb c == "minenen"
4. einen Huffman Baum bilden
z.B. bilde_HB [('n',1),('m',1),('i',8),('e',20)] ==
K (K (K (B 'n') (B 'm')) (B 'i')) (B 'e')

Ich hab keine Ahnung, auch Internet bietet nicht viel...
Bin für jede Idee und Hifle dankbar.
Zum Seitenanfang ICQ    
 
Siracusa

Gepostet:
06.12.2007 22:32

   
Hallo nochmal!

"Ich hab keine Ahnung, auch Internet bietet nicht viel..." - Da muß ich sagen, hast du schlecht gesucht! Für die Stichwörter: Huffman Codierung Haskell wirft dir Google gleich auf Platz 1 und 3 der Trefferliste umfangreiche Erklärungen zur Umsetzung einer Huffman-Codierung- und Decodierung in Haskell.


Viele Grüße,

Siracusa
Zum Seitenanfang    
 
franzigoth1

Gepostet:
10.12.2007 17:06

   
Du hast recht, hab echt falsch gesucht, danke für die Hilfe :-)
Zum Seitenanfang ICQ    
 
franzigoth1

Gepostet:
25.12.2007 14:08

Lösungsansatz?  
Hallo,
hab mich mal mit der Aufgabe 4. beschäftigt und folgendes implementiert:

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 eine Helfen...
Zum Seitenanfang ICQ    
 
Siracusa

Gepostet:
27.12.2007 16:25

   
Hallo,

c1, c2, n1 und n2 sind innerhalb der Funktion mkHTree nicht definiert. Statt der Muster b1 und b2 also (c1,n1) und (c2,n2) verwenden.


Viele Grüße,

Siracusa
Zum Seitenanfang