AB5 Quickselect und Huffman-Kodierung

Implementieren Sie die folgenden Funktionen nur unter Verwendung der bereits importierten Funktionen. Folgende Sprachkonstrukte dürfen nicht verwendet werden:

Teil 1: Quickselect

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
In der vorletzten Zeile ist 0 kleiner als das Pivotelement 9 und muss deshalb links davon stehen. Vertauscht man die beiden Elemente, stehen jedoch die Elemente 18, 22 und 14 ebenfalls links von 9, obwohl wir bereits wissen, dass diese Elemente größer oder gleich 9 sind. Daher müssen zusätzlich 18 und 9 vertauscht werden. Die Partitionierung ist fertig, wenn \(n-1\) Elemente mit dem Pivot verglichen wurden, wobei \(n\) die Länge der Liste ist (\(n=9\) im obigen Beispiel).

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.

Die verbleibende Liste, in der das gesuchte Element sich befindet, merkt sich der Algorithmus durch Start- und Endindex. In den zwei Fällen \(p \neq k-1\) wird die Selektion für die verbleibenden Liste wiederholt. Im obigen Beispiel hat das Pivotelement 9 nach der Partitionierung Index 4 und ist somit das 5-kleinste Element.

partition_list  :: [Int] -> Int -> Int -> Int -> [Int]
partition_pivot :: [Int] -> Int -> Int -> Int -> Int
select :: Int -> [Int] -> Int
Die Funktion 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.
Die Funktion partition_pivot gibt den Index des Pivotelements in der Liste (partition_list arg1 arg2 arg3 arg4) zurück.
Die Funktion 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.
Implementieren Sie die Funktionen, indem Sie die Programme in den Dateien 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.

Teil 2: Huffman-Kodierung

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
Die Funktion 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)).
Beispiele
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"
Die Funktion 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:

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?