if ... then ... else ...
(benutzen Sie stattdessen if'
sofern importiert)[(i,j) | i <- [1,2], j <- [3,4]]
Der Quickselect-Algorithmus berechnet das \(k\)-kleinste Element einer Liste inplace. Das heißt, dass der Algorithmus außer Zeiger auf die Liste keine zusätzlichen Informationen speichern muss. Der Algorithmus besteht aus zwei Teilen: Partitionierung und Selektion.
Bei der Partitionierung wird eine Liste um ein Pivotelement herum sortiert. Genauer gesagt soll nach der Partitionierung gelten: alle Elemente in der Liste, die kleiner sind als das Pivotelement, stehen links davon und alle anderen rechts davon. Beispiel (rot = Pivotelement, blau = zu vergleichendes Element):
3 | 1 | 12 | 7 | 18 | 22 | 14 | 0 | 9 | 3 < 9 → weiter |
3 | 1 | 12 | 7 | 18 | 22 | 14 | 0 | 9 | 1 < 9 → weiter |
3 | 1 | 12 | 7 | 18 | 22 | 14 | 0 | 9 | 12 ≥ 9 → vertausche |
3 | 1 | 9 | 7 | 18 | 22 | 14 | 0 | 12 | 7 < 9 → vertausche |
3 | 1 | 7 | 9 | 18 | 22 | 14 | 0 | 12 | 18 ≥ 9 → weiter |
3 | 1 | 7 | 9 | 18 | 22 | 14 | 0 | 12 | 22 ≥ 9 → weiter |
3 | 1 | 7 | 9 | 18 | 22 | 14 | 0 | 12 | 14 ≥ 9 → weiter |
3 | 1 | 7 | 9 | 18 | 22 | 14 | 0 | 12 | 0 < 9 → vertausche 2x |
3 | 1 | 7 | 0 | 9 | 22 | 14 | 18 | 12 |
Die Selektion funktioniert nach folgendem Prinzip.
Zuerst wird ein Pivotelement nach einer gegebenen Regel gewählt. Gehen Sie davon aus, dass immer das letzte Element der verbleibenden Liste als Pivot gewählt wird. Dann wird die Liste um dieses Pivotelement partitioniert. Sei \(p\) der Index des Pivotelements nach der Partitionierung.
partition_list :: [Int] -> Int -> Int -> Int -> [Int] partition_pivot :: [Int] -> Int -> Int -> Int -> Int select :: Int -> [Int] -> Int
partition_list
gibt die Liste arg1
zurück, nachdem die verbleibende Liste beginnend ab Index arg2
bis Index arg3
mit Pivotelement auf Index arg4
partitioniert wurde.partition_pivot
gibt den Index des Pivotelements in der Liste (partition_list arg1 arg2 arg3 arg4)
zurück.select
gibt das arg1
-kleinste Element der Liste arg2
zurück.
Sie können annehmen, dass 1 <= arg1 <= (length arg2)
und das arg2
nicht leer ist und keine Duplikate enthält.AB5_1/partition.sp
und AB5_1/select.sp
vervollständigen, sodass diese den obigen Algorithmus implementieren. Fügen Sie keine zusätzlichen Variablen hinzu. Außerdem dürfen alle Variablen außer list
und res
nur Werte zwischen \(0\) und \(n\) annehmen, wobei \(n\) die Länge von list
ist. Die Variable res
darf in keinem Prädikat und in keiner Operation auf der rechten Seite vorkommen.
Die Huffman-Kodierung dient dazu, einer endlichen Menge von Quellsymbolen \(\Sigma\) Codewörter variabler Länge über einem Codealphabet \(\Gamma\) zuzuordnen. Quellsymbole die häufiger auftreten sollen kürzere Codewörter zugeordnet bekommen. Die relative Auftrittshäufigkeit aller Quellsymbole \( p \colon \Sigma \rightarrow [0,1] \) wird als bekannt vorausgesetzt; es wird angenommen, dass jedes Quellsymbol mindestens ein Mal auftritt, d.h. \(p(x) > 0\) für alle \(x \in \Sigma\).
Die Huffman-Kodierung \(h \colon \Sigma \rightarrow \Gamma^* \) wird wie folgt konstruiert. Aus einer Menge von Bäumen entsteht durch Zusammenfassen letztendlich ein einzelner Baum, dessen Blätter den Quellsymbolen entsprechen und der Pfad zu einem Blatt beschreibt dessen Codewort. Die Knoten werden mit Teilmengen \(X\) von \(\Sigma\) beschriftet und die kumulative Auftrittswahrscheinlichkeit einer solchen Menge ist \(p(X) = \Sigma_{x \in X} p(x)\).
Zu Beginn wird für jedes Quellsymbol \(x\) ein Baum bestehend aus einem einzigen Knoten angelegt, welcher mit \(\{x\}\) beschriftet wird. Anschließend wird folgender Schritt wiederholt bis nur noch ein Baum übrig ist.
Wähle die \(|\Gamma|\) Bäume, welche die niedrigste Auftrittswahrscheinlichkeit haben. Die Auftrittswahrscheinlichkeit eines Baums \(T\) ist \(p(X)\), wobei \(X\) die Beschriftung des Wurzelknotens von \(T\) ist. Falls dieses Auswahlkriterium nicht eindeutig ist, dann bevorzuge jene Bäume mit einer geringeren Tiefe. Falls dieses Auswahlkriterium immer noch nicht eindeutig ist, dann bevorzuge jene Bäume dessen Wurzelknoten eine lexikographisch kleinere Beschriftung haben. Fasse diese Bäume zu einem neuen Baum zusammen.
Damit die Eindeutigkeit der Konstruktion gewährt ist, sollen die gewählten Teilbäume immer in lexikographischer Reihenfolge (bzgl. der Beschriftung ihrer Wurzelknoten) an den neuen Baum angehängt werden.
Beispiel: für \(\Sigma = \{a,b,c,d,e\}\), \(\Gamma = \{0,1\}\) und \( p = \left(\begin{smallmatrix}a&b&c&d&e\\\frac{4}{20}&\frac{3}{20}&\frac{8}{20}&\frac{1}{20}&\frac{4}{20}\end{smallmatrix}\right)\) entsteht folgender Baum:type CodeAlphabet = [Char] type Probabilities = Map Char (Int,Int) type HuffmanTree = (Tree [Char]) huffmanTree :: CodeAlphabet -> Probabilities -> HuffmanTree huffmanEncode :: HuffmanTree -> CodeAlphabet -> String -> String huffmanDecode :: HuffmanTree -> CodeAlphabet -> String -> String
huffmanTree
soll für eine Wahrscheinlichkeitsverteilung arg1
und ein Codealphabet arg2
den entsprechenden Huffman-Baum zurückgeben. Die Menge der Quellsymbole ist implizit gegeben durch (map fst (toList arg2))
.
ht1 = huffmanTree "01" (fromList [('a',(4,20)),('b',(3,20)),('c',(8,20)),('d',(1,20)),('e',(4,20))]) "abcde" "ae" "a" "e" "bcd" "bd" "b" "d" "c" ht2 = huffmanTree "01" (fromList [('a',(4,20)),('b',(8,40)),('c',(4,20)),('d',(8,40)),('e',(4,20))]) "abcde" "abe" "ab" "a" "b" "e" "cd" "c" "d" ht3 = huffmanTree "012" (fromList [('a',(6,24)),('b',(2,24)),('c',(6,24)),('d',(2,24)),('e',(5,24)),('f',(2,24)),('g',(1,24))]) "abcdefg" "a" "bdefg" "bdg" "b" "d" "g" "e" "f" "c"
huffmanEncode
soll arg3
in einen String über dem Codealphabet umwandeln. Der \(i\)-te Teilbaum eines Knotens von arg1
soll dem \(i\)-ten Zeichen aus arg2
zugeordnet werden. Beispiele:
huffmanEncode ht1 "01" "abc" = "0010011"
huffmanEncode ht1 "yx" "abc" = "yyxyyxx"
huffmanEncode ht1 "10" "d" = "010"
huffmanEncode ht3 "ABC" "acd" = "ACBAB"
Die Funktion huffmanDecode
soll arg3
zurück in einen String über der Menge der Quellsymbole dekodieren, d.h. (huffmanDecode x y (huffmanEncode x y z)) == z
.
Implementieren Sie die Funktion, indem Sie das Programm in der Datei AB5_2/decode.sp
vervollständigen. Die Variable input
soll wie ein Eingabestream und die Variable output
wie ein Ausgabestream behandelt werden. Das bedeutet, die Variable input
soll nur über die Operation o_next
(liest nächstes Zeichen des Eingabestreams) und das Prädikat p_endOfStream
(wahr gdw. Eingabestream das Ende erreicht hat) benutzt werden. Die Variable output
soll nur über die Operation o_flush
(buffer
wird an output
hinten angehängt) benutzt werden.
Die folgenden Fragen sind ergebnissoffen.
Zusatzfrage 1. Angenommen ein deutscher Text \(T\) der Länge \(n\) bestehend aus den Zeichen a bis z, äöüß, Leerzeichen und Punkt (32 verschiedene Zeichen) ist gegeben. Der Text \(T\) kann durch \(5n\) Bits beschrieben werden. Wie würden Sie die Menge der Quellsymbole \(\Sigma\) für \(T\) wählen, damit die Huffman-codierte Version \(T_H\) von \(T\) möglichst kurz ausfällt (\(\Gamma = \{0,1\}\))?
Was würden Sie erwarten, wie das Verhältnis \(|T_H|/5n\) ausfällt?
Zusatzfrage 2. Wie könnte man die Huffman-Kodierung zum Komprimieren von Binärdateien (Bilder, Musik, Videos, Anwendungen, etc.) verwenden?