Python 3: Ich habe Fragen zur Implementation des Huffman-Code. Könnt ihr mir helfen?
Hallo Leute,
ich hoffe, dass ich hiermit nicht den Shitstorm of Doom heraufbeschwöre, aber ich komme seit fünf Tagen partout nicht weiter.
1) (2 Punkte) Gegeben sei folgende Nachricht: ”Mississippi River in Ontario isn’t Mississippi River in Mississippi!”
Zeichne den zugehörigen Huffman-Baum und stelle die Codetabelle auf, wie sie es in der Vorlesung gelernt haben. Geben Sie alle erforderlichen Werte an! Wie lautet die oben angegebene Nachricht in ihrer codierten Form?
2) (2 Punkte) Schreibe ein Python 3.7.x Programm, welches die in der Aufgabe 11.1 aufgestellte Codetabelle beinhaltet. Das Programm soll Befehle encode und decode verstehen und die darauffolgende Eingabe codieren oder decodieren können. Falsche Eingaben sind mit einer Warnung in der Konsole zu quittieren. Geben jeweils 5 Testfälle für Codierung und Decodierung an. Zusätzlich gebe an, wie Deine Implementierung die Nachricht
3) (4 Punkte) Schreibe ein in Python 3.7.x Programm, welches eine Eingabe (Nachricht) über die Konsole entgegennimmt, sie analysiert und basierend darauf eine Codetabelle aufbaut.
- Gebe diese Codetabelle in der Konsole aus.
- Gebe die codierte Eingabe in der Konsole aus.
- Implementiere eine Funktion zur Decodierung und gebe die decodierte Nachricht zur Verifikation in der Konsole aus.
Setze die Befehle newbase und showtable um. Ermögliche damit eine neue Eingabe und lasse für diese eine neue Codetabelle berechnen und gegebenenfalls ausgeben. Setze weiterhin Befehle encode und decode um, wie Du es in der Aufgabe 11.2 gemacht hast.
Hinweise:
Zur Lösung dieser Aufgabe dürfen built-in Sortiermethoden verwendet werden. Denke daran, dass nicht alle Datentypen geordnet sind. Dennoch können hier auch solche Datentypen sehr hilfreich sein.
Nicht lauffähige Programme werden nicht bewertet, dabei gilt als Maßstab NUR die Ausführbarkeit in der Konsole!
Aufgabe 1 hab ich noch lösen können,
Ich weiß, im Netz gibt es gefühlt 3000 Huffman Code-Tutorials, aber die sind alle auf fortgeschrittenen Niveau und erklären auch nicht, wie ich diese Code-Tabelle implementieren soll. Zur Erklärung:
- Spalte 1: Die relative Häufigkeit, wie oft ein Zeichen allgemein im String vorkommt.
- Spalte 2: Der Logarithmus dualis:
- Spalte 3: Blockcode der Reihe nach aufgeschrieben
- Spalte 4: Der Huffman Code (auf den 0 und 1 in der Grafik basierend)
- Spalte 5: Gewichtete Codelänge (Anzahl der Bits im Huffman-Code * Relative Häufigkeit)
Wie kann ich das in Python berechnen lassen und zusätzlich noch in so einer Tabellenform ausgeben? Dazu müsste man doch alle Werte von diesem Baum manuell eintragen, oder nicht?
Kann ich bei Aufgabe 2) nicht einfach die Variablen neu definieren, z.B. "M == 000" oder ist das geschummelt?
