Huffmann Codebaum erstellen?

Muss für eine Aufgabe einen Huffmann codebaum erstellen. Hier die Aufgabe : Erstellen Sie für den Text ‘sieben Fliegen fliegen flink’ den Huffman-Kode (mittels des Huffman- Kodebaums) und führen Sie damit die Kodierung des Textes durch. Wie viel Bits spart man bei dem Huffman-kodierten Text, wenn man annimmt, dass der unkodierte Text mit 8 Bit je Buchstabe dargestellt ist (beachten Sie auch die Leerzeichen zwischen den Wörtern).

Bild zum Beitrag

Was mache ich falsch? Edit: die Anfangsknoten über den Buchstaben müssen nach der Häufigkeit sortiert werden.

Bild zum Beitrag

2 Antworten

Vom Beitragsersteller als hilfreich ausgezeichnet

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Informatik

20.12.2019, 14:19

    8           8            12
   / \       /     \        /  \
  n   i     4       4      e    6
          /   \    / \         /  \
         2     2  g   f       _    l
        / \   / \
       b   s F   k

Also ich komme schon auf einen ähnlichen Baum (Die Reihenfolge bei gleichwertiger Häufigkeit ist natürlich nicht eindeutig und natürlich können 0 und 1 ihre Rollen tauschen).

Axel324

Beitragsersteller

20.12.2019, 15:16

ja, das war auch meine Überlegung. Auf jeden Fall scheint, dass dann bei mir auch richtig zu sein(wenn man die Summen auf gleicher Ebene schreibt. Werde es mir merken.) Super vielen Dank.

KarlRanseierIII

20.12.2019, 15:24

@Axel324

Essentiell für die Aufgabe sind ja die sich ergebenden Bitstringlängen, da ist die Varianz zwischen den Geschwistern in der Regel nicht von Bedeutung.

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Informatik

20.12.2019, 12:40

Fast: Du ornest nach der Häufigkeit, nimmst die Beiden Knoten mit der niedrigsten rel. Häufigkeit und machst sie zu Kindern eines neuen Knotens, dieser bekommt die Summe der Häufigkeiten.

Nun ordnest Du den neuen Knoten in die bestehende KnotenMenge ein und wiederholst, bis der Baum fertig ist.

Hierdurch gewähleistest Du, daß der Buchstabe mit größter Häufigkeit direkter Nachfolger der Wurzel ist, während jede mit niedrigster Blätter in der tiefsten Ebene sind.

KarlRanseierIII

20.12.2019, 13:00

Äääh, die größte Häufigkeit ist natürlich nicht zwingend direkter NAchfolger der Wurzel, sondern steht ihr am nächsten.

Ich würde mal oben am Blatt mit der Knotenliste anfangen udn dann zeilenweise nach unten aufbauen - auch wenn es mehr Platz benötigt.

Da passieren einem weniger Flüchtigkeitsfehler, wegen der Übersichtlichkeit.

Axel324

Beitragsersteller

20.12.2019, 13:19

@KarlRanseierIII

hab ich gemacht, ich komme aber auf das gleiche Ergebnis.

Axel324

Beitragsersteller

20.12.2019, 13:29

@Axel324

Wie würdest du denn das machen(stell doch einfach deine Zeichnung hier rein, vielleicht erkenne ich den Fehler)

KarlRanseierIII

20.12.2019, 13:30

@Axel324

Wieso steht da eigentlich ganz rechts zweimal der gleiche Buchstabe?

Axel324

Beitragsersteller

20.12.2019, 13:35

@KarlRanseierIII

der zweite Buchstabe soll ein b sein.(Also s b k und F haben die Werte 1)

Ähnliche Beiträge

mittlere Codelänge --> Informatik

In Informatik arbeiten wir zurzeit mit Kodierungen. Ich verstehe nur noch nicht, wie man eine mittlere Codelänge (bezogen auf die Häufigkeit der Buchstaben des Alphabets) berechnen kann. Im Internet finde ich dazu leider nichts. Vielen Dank für jede Hilfe!!! Mfg Schokolexi

...zum Beitrag

Wie kann man in der ASCII‐Kodierung einen Groß‐ in einen Kleinbuchstaben umwandeln, wenn der Buchstabe (a) dezimal, (b) binär, (c) hexadezimal kodiert ist?

ASCII

...zum Beitrag

Wie berechne ich die Bits, die ich bei der Huffmankodierung benötigen würde, ich soll nicht die Huffmankodierung durchführen, sondern nur die Bits berechnen?

Hi sagen wir ich habe diesen text:

dqwdqwqwddwdqkkdf
fkdkgddkgfkgdkkk
oijoijio
kioi

Ich soll nicht die komplette huffmancodierung durchführen, sondern nur sagen wie viele Bits ich zur Kodierung benötigen würde und wie viele Bits pro zeichen.

Wie soll man das berechnen? Ich muss doch die komplette Codierung vornehmen um darauf zu kommen oder?

...zum Beitrag

Kann mir jemand mit Informatik weiterhelfen?

Hallo, ich schreibe morgen eine Klassenarbeit in Informatik und versuche deswegen eine Lernaufgabe zu lösen, welche mein Lehrer uns gegeben hat. Ich steige aber garnicht durch, deswegen hier die Frage ob mir jemand helfen kann. Das ist die Aufgabe: Erstelle ein Programm (Struktogramm oder Snap!-Programm), das den gro ̈ßten Buchstaben eines eingegebenen Textes ausgibt, also denjenigen Buchstaben, der am weitesten hinten im Alphabet steht. Der gro ̈ßte Buchstabe von ’roboter’ ist z.B. ’t’.

in dem Bild Aufgabe 2a

...zum Beitrag

Text soll von Binär in Buchstaben umgewandelt werden

Hallo,

Eine gute Freundin schickte mir folgenden Binärcode:

1001 0011 1000

1100 1001 0101 0010 0101

0100 1001 0011 1000

Ich solle diesen übersetzten. Leider scheine ich einfach zu unfähig zu sein diese Aufgabe zu lösen. Das einzige was ich erhalte ist folgendes: “Œ•%I8

Ich denke mal das ist nicht richtig.

Kann mir vllt jemand helfen ? Wichtig sie sagt es sollen buchstaben dabei rauskommen.

Mit Freundlichen Grüßen ProxyOps

...zum Beitrag

Java .txt Datei zu Array?

Angenommen man hat ein Text-Dokument (.txt) mit folgendem Aufbau:

Die erste Zeile besteht aus zwei Zahlen, die durch ein Leerzeichen getrennt sind
Die darauffolgenden Zeilen (angenommen es sind immer 3 Stück) bestehen aus Buchstaben auf die zwei Leerzeichen folgen oder aus einer Kombination aus Buchstabe und Zahl, worauf nur ein Leerzeichen folgt

Hier ein Beispiel zur Veranschaulichung:

4 9

A X2 a D

J d r2 L

U K q w

Wie ist es mit möglichst wenig code und nur essenziellen Importen möglich in Java diese Datei (text1.txt) so einzulesen, dass man am Ende einen Array erhält, der alle Elemente der Text-Datei enthält, die jeweils durch ein oder zwei Leerzeichen getrennt sind. Das Ganze sollte dann für diese Beispiel so aussehen (würde man den Array einfach manuell erstellen):

String[] Array = {4, 9, A, X2, a, D, J, d, r2, L, U, K, q, w}

...zum Beitrag

Java: Text einlesen und Häufigkeit der Buchstaben analysieren?

Hey! Ich möchte einen Text einlesen und die Häufigkeit der Buchstaben analysieren. Dazu habe ich folgenden Code geschrieben. Leider ist dort irgendwo ein Logikfehler versteckt, den ich aber nicht finde :( Das Programm tut nicht, was es soll. Es wird für alle Buchstaben die Anzahl 0 ausgegeben, was ja nicht sein kann. Ich wäre sehr dankbar, wenn jemand meinen Denkfehler findet. Dankeschön! P.S: hab erst vor 2 Wochen mit Programmieren angefangen, also verurteilt meinen Code nicht gleich ^^

import java.io.*;

public class Buchstabenstatistik { public static void main(String[] args) throws IOException{

    // Es werden 180 000 Buchstaben des Textes "time" eingelesen und in einem char Array 'buchstaben' gespeichert
    FileReader reader = new FileReader("d:\\time.txt");
    int n1 = 180000;
    char[] buchstaben = new char[n1];
    reader.read(buchstaben);
    reader.close();
    
    // Alle Buchstaben des englischen Alphabets werden in einem char Array 'alphabet' gespeichert
    char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x', 'y', 'z'};
    
    // Es wird ein neues int Array 'counter'angelegt, mit dem später gezählt werden soll, wie oft ein 
    // einzelner Buchstabe im Text vorgekommen ist
    int a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
    a = b = c = d = e = f = g = h = i = j = k = l = m = n = o = p = q = r = s = t = u = v = w = x = y = z = 0;
    // Anfangs wird jedem Element des counters der Wert 0 zugewiesen, da ja noch keine Buchstaben gezählt wurden
    int[] counter = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z};
    for (int i1 = 0; i1 < counter.length; i1 ++){
        counter[i1] = 0;    
    }
    
    // Jeder Buchstabe im Text (gespeichert im char Array 'buchstaben') wird mit jedem Buchstaben des englischen Alphabets
    // verglichen. Wenn sie übereinstimmen, wird der Array 'counter' an der jeweiligen Stelle im Array, der für einen
    // bestimmten Buchstaben steht, um 1 erhöht
    for (int k1 = 0; k < buchstaben.length; k++) {
        for (int k2 = 0; k2 < alphabet.length; k2 ++) {
            if (buchstaben[k1] == alphabet[k2]) {
                counter[k2] = counter[k2] + 1;
            }
        }   
    }
    // Die Anzahl jedes Buchstaben, der im Text vorgekommen ist, wird ausgegeben
    System.out.println("Anzahl der Buchstaben: ");
    for (int k3 = 0; k3 < counter.length; k3 ++) {
        System.out.println(alphabet[k3] + " : " + counter[k3]);
    }
    //Die prozentuale Häufigkeit der Buchstaben soll berechnet und ausgegeben werden
    // (Anzahl des Buchstaben im Text / Anzahl aller Buchstaben im Text) * 100% 
    System.out.println();
    System.out.println("Häufigkeit der Buchstaben in Prozent: ");
    double h1 = 0;
    for (int k4 = 0; k4 < counter.length; k4 ++) {
        h1  = (counter[k4] / n1) * 100;
        System.out.println(alphabet[k4] + " : " + h1 + " % ");
    }

}

}

...zum Beitrag

Bit und Byte (Umrechnung)?

Moin leute,

und zwar habe ich ein Problem bei der Aufgabe c2)! Die c1) habe ich schon gemacht, aber ich verstehe halt nur nicht die c2). Kann mir das jemand bitte sagen?

c1) Berechnen Sie, wie viele Textdateien theoretisch in diesem Arbeitsspeicher abgelegt werden können, wenn pro Textdatei 50 Zeilen mit je 80 Buchstaben und 200 Seiten (*.txt-Format) angenommen werden.

c2) Gilt diese Berechnung auch für MS Office-Dateien (z.B. *.docx) ? Zeigen Sie anhand verschiedener Textdokumenten (*.txt, *.rtf, *.doc, *.docx, *pdf) den Speicherbedarf, wenn der Inhalt des Textes gleich ist.

Ich bedanke mich schonmal im voraus.

...zum Beitrag

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?

...zum Beitrag

PYTHON - Zählen wie oft Buchstabe in einer Zeichenkette vorkommt?

Ich soll folgende Aufgabe lösen: "Definieren Sie eine Zeichenkette text mit beliebiger Länge und einen string buchstaben mit dem Wert abc.

Erstellen Sie ein Dictionary, dass als Schlüssel die einzelnen Buchstaben von buchstaben, also a, b und c, enthält. Der Wert soll angeben, wie oft der entsprechende Buchstabe in Ihrem text vorkommt.

Überprüfen Sie Ihre Lösung mit verschiedenen strings für text und buchstaben!

Hinweis Verwenden Sie z.B. for..in.. und if..in..."

Ich habe als text Folgendes: "Es war einmal vor langer Zeit" buchstaben = "abc"

Nur wie mache ich jetzt weiter? Wie zähle ich wie oft meine Buchstaben "abc" in meiner Zeichenkette text vorkommen? Ich soll wie gesagt zB eine for-Schleife verwenden, da wir das vor kurzem erst durchgemacht haben.

...zum Beitrag

Python buchstaben zählen?

Ich möchte mit mit Python ein kleines Programm schreiben dass Buchstaben zählt sieht bei mir so aus: text = "Das ist ein Test" print(len(text))

allerdings zählt das Programm logischerweise jedes Zeichen mit also auch Leerzeichen, wie sage ich dem Programm dass es nur die Buchstaben zählen soll

...zum Beitrag

Wird bei einer RSA-Kryptifizierung die kodierte Datei größer als die Quelle?

Habe zur RSA-Verschlüsselung leider nur ein Halbwissen.

Meistens wird diese Kodierung für die sichere Übertragung von wenigen Bytes eingesetzt. Das ist mir klar, will ich hier aber nicht weiter betrachten.

Wenn ich einen Wert für N = p•q mit beispielsweise 1024 Bit habe, so kann ich doch nur Werte < N kodieren? Ist das richtig?

Falls dieses Halbwissen stimmt, dann lassen sich alle Werte bis 1023 Bit Länge sowie einige bis 1024 Bit Länge kodieren, aber nicht alle.

Daraus folgt dann, dass eine Datei von beispielsweise 10 MB in Häppchen zu 1023 Bit und nicht zu 1024 Bit zu zerteilen ist und die Codes der Häppchen aber 1024 Bits haben. Damit würde die Datei um knapp 1 ‰ größer werden.

Frage: ist dieser Gedanke richtig oder liege ich da völlig daneben?

Falls mein Gedanke falsch ist: wie wird eine 10 MB Datei dann in Häppchen zerlegt?

Ich bitte, die Frage nicht zu verändern. Ich möchte von 10 MB alles per RSA und einen 1024 Bit N verschlüsseln (theoretisches Beispiel). Ich suche eine wissenschaftliche Antwort und keine für die Anwendung.

...zum Beitrag

Wie kann man solche Text Bilder erstellen?

Wie kann man am besten solche Bilder erstellen mit verschiedenen Buchstaben die alle bisjen anders aussehen, siehe Beispielbild:

Was benutzt man da am besten um sowas zu erstellen?

...zum Beitrag

Processing Text mit einem Buchstaben ersetzen?

Hallo,

und zwar versuche ich mir das Programmieren anzueignen.

Meine Aufgabe ist es die in einem Text die Vokale durch eine bestimmte Buchstabe a-z zu ersetzen.

Bsp: Drei

Vokal: a

Lösung: Draa