Entwicklung eines datenkomprimierenden Dienstprogramms auf Basis von Huffman-Codes mit Haskell

Implementierung eines Datenkomprimierungsprogramms mit Huffman-Codierung

• Was ist ein Huffman-Code?
  • Führt Datenkomprimierung durch, indem jedes Zeichen einer eindeutigen Bitsequenz zugeordnet wird
  • Häufig vorkommende Zeichen werden auf kurze Bitsequenzen abgebildet, seltene Zeichen auf lange Bitsequenzen
  • Beispiel: Beim String aaab wird a auf 1 und b auf 0 abgebildet und so zu 1110 komprimiert

Präfixfreier Code

• Was ist ein präfixfreier Code?
  • Kein Codewort darf Präfix eines anderen Codeworts sein
  • Beispiel: Bei aaabc wird a auf 1, b auf 00 und c auf 01 abgebildet und so zu 1110001 komprimiert

Erzeugung präfixfreier Codes

• Methode zur Erzeugung präfixfreier Codes
  • Alle Zeichen werden als Blätter in einem vollständigen Binärbaum angeordnet
  • Der linke Ast wird mit 1, der rechte Ast mit 0 beschriftet
  • Der Pfad von der Wurzel zum Blatt beschreibt das Codewort jedes Zeichens

Schreiben des Encoders

• Typdefinitionen

  • Definition der Typen Bit, Code, FreqMap, CodeMap, Weight, HTree
  • HTree besteht aus Leaf und Fork

• Encoding-Funktion

  • Funktion zur Umwandlung eines Strings in Bits
  • Berechnet mit FreqMap die Häufigkeit jedes Zeichens und erzeugt darauf basierend einen Huffman-Baum
  • Erzeugt aus dem Huffman-Baum das Codewort für jedes Zeichen

• Decoding-Funktion

  • Funktion zur Rückumwandlung von Bits in den ursprünglichen String
  • Dekodiert Bits sequenziell mithilfe des Huffman-Baums

Anbindung an Binärdateien

• Encoding binärer Daten
  • Liest Bytes als Zeichen mit dem Modul Data.ByteString.Char8
  • Kodiert binäre Daten mit dem Text-Encoder

Serialisierung

• Serialisierungsfunktion
  • Wandelt FreqMap und Bits in tatsächliche Bytes um und speichert sie in einer Datei
  • Erzeugt mit der Put-Monade effizient ein ByteString

Deserialisierung

• Deserialisierungsfunktion
  • Wandelt aus einer Datei gelesene Daten in FreqMap und Bits um
  • Deserialisiert FreqMap mit der Get-Monade

Integration des gesamten Codes

• Funktionen zum Komprimieren und Entpacken von Dateien
  • compress-Funktion: Liest eine Datei, erzeugt eine Frequenz-Map, kodiert die Daten und speichert sie als komprimierte Datei
  • decompress-Funktion: Liest eine komprimierte Datei, dekodiert die Daten und speichert sie wieder als ursprüngliche Datei

Verbesserungen

• Multithreading

  • Dekodiert Dateiabschnitte parallel
  • Ermöglicht Parallelverarbeitung durch Hinzufügen einer Tabelle, die Abschnittsgrenzen und die erwartete Dekodierungsgröße angibt

• Single-Pass-Encoding

  • Erzeugt die Frequenz-Map während des Encodings in Echtzeit
  • Es ist nicht nötig, die Frequenz-Map am Anfang der Datei einzubetten

• Kanonische Huffman-Codes

  • Dekodiert mit O(1) Zeitkomplexität durch Indexierung eines Vektors statt durch Traversierung des Baums

• Schnellere Codeerzeugung

  • Falls Single-Pass-Encoding versucht wird, muss die Erzeugung der Codemap beschleunigt werden

Meinung von GN⁺

• Vorteile der Huffman-Codierung

  • Ermöglicht effiziente Datenkomprimierung, indem häufig vorkommende Zeichen auf kurze Bitsequenzen abgebildet werden
  • Kann große Datenmengen verarbeiten und dabei den Speicherverbrauch minimieren

• Vorteile von Haskell

  • Ermöglicht modularen Code durch Nutzung der Vorteile der funktionalen Programmierung
  • Kann den Speicherverbrauch durch Lazy Evaluation optimieren

• Projekte mit ähnlicher Funktionalität

  • Es gibt verschiedene Datenkomprimierungswerkzeuge wie gzip und bzip2
  • Es ist wichtig, die Vor- und Nachteile der einzelnen Werkzeuge zu vergleichen und das passende auszuwählen

• Aspekte bei der Einführung neuer Technologien

  • Der geeignete Algorithmus sollte unter Berücksichtigung von Performance und Speicherverbrauch gewählt werden
  • Die Effizienz kann durch den Einsatz von Optimierungstechniken wie Single-Pass-Encoding erhöht werden

[GN⁺]

Hacker-News-Kommentare

• Es gibt einen arraybasierten In-Place-Algorithmus, der den Bedarf reduziert, Bäume zu allokieren und Zeigern zu folgen

  • Als man an der Universität den baumbasierten Ansatz lernte, war nicht bekannt, dass es andere Methoden gibt
  • Der Baumansatz ist intuitiv und lehrreich, aber wenn viele Daten schnell verarbeitet werden müssen, ist die Verwendung von In-Place-Arrays sinnvoller
  • Referenz: "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• Dass sichergestellt werden muss, dass ein Codewort nicht zum Präfix eines anderen Codeworts wird, ist technisch nicht korrekt

  • Die Klasse eindeutig decodierbarer Codes ist eine Obermenge der Präfixcodes
  • Zum Beispiel ist die Umkehrung eines Präfixcodes immer noch eindeutig decodierbar
  • Beispielcode:

    a 1
    b 00
    c 10
    

  • Der Code von „a“ ist ein Präfix des Codes von „c“, aber bei Verarbeitung in umgekehrter Reihenfolge ist er eindeutig decodierbar

• Es wird gefragt, ob es ein ähnliches Tutorial gibt, das fortgeschrittenere Funktionen zum Schreiben von Haskell-Programmen behandelt, etwa Monad-Transformer, Lenses usw.

• Im funktionalen Programmierkurs von Coursera (Scala) gibt es eine ähnliche Huffman-Coding-Aufgabe

  • Link: Coursera Scala Functional Programming

• Mit Huffman-Codes wurde ein MICMAC-Prozessor-Makroprogramm mit einer minimalen Anzahl von Mikrozyklen und Mikroinstruktionen ausgeführt

  • Es wurde ein Histogramm der Makroinstruktionen erstellt und darauf basierend ein Microcode-Programm für progressive Decodierung geschrieben
  • In der Praxis wäre es vermutlich langsam und unhandlich gewesen
  • Der Vorteil von Huffman-Codes besteht darin, dass sich die Präfixtiefe an die Verteilung der Werte anpassen lässt
  • In einem nicht überlappten Pipeline-Prozessormodell musste Branch Prediction behandelt werden

• Weitere Informationen zu Huffman-Coding: Rosetta Code Huffman Coding

• Frage an Haskell-Programmierer: Wie steht es um die Performance von Haskell für Entwickler, die optimierten Code schreiben wollen?

  • Insbesondere besteht Interesse an der Performance numerischer Berechnungen mit Matrixoperationen und der Nutzung von SIMD

• Ein Kommentar bedankt sich fürs Teilen

• In der Tabelle im Abschnitt "Creating prefix-free codes" gibt es einen Tippfehler

  • D sollte „0010“ sein (derzeit fälschlich als „0110“ angegeben)
  • Davon abgesehen war es ein großartiger Lesestoff

• Arithmetische Codes sind in fast jeder Hinsicht besser

  • Sie lassen sich mit weniger RAM und weniger Code implementieren
  • Sie bieten bessere Kompressions- und Dekompressionsraten
  • Es ist einfacher, die Wahrscheinlichkeit des Auftretens anderer Symbole während des Streams dynamisch zu aktualisieren
  • Huffman-Codes wurden verwendet, weil sie zuerst erfunden wurden und arithmetische Codes patentiert waren
  • Da die Patente inzwischen abgelaufen sind, sollte ein besseres Design verwendet werden