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 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

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

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

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

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

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

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

Wie komm ich beim ASCII Code direkt von Z zu A?

Guten Tag,

ich habe folgende Aufgabe:

"Eine einfache und alte Verschlüsselungmethode für Texte ist die Caesar-Verschlüsselung. Ausgangspunkt ist ein Buchstabe b und ein Schlüssel k ∈ N. Das Verfahren arbeitet so, dass der Buchstabe durch den Buchstaben ersetzt wird, der k Buchstaben weiter im Alphabet erscheint. Dabei ist zu beachten, dass beim “Hinauslaufen“ über Z mit A weiter gezählt wird. Der nächste Buchstabe nach Z ist also A. Beispiel: b = H und k = 1 ergibt als Ergebnis I. Schreiben Sie ein Java-Programm Caesar, das für einen Schlüssel k mit k ∈ N (also z.B. k = 100) und einen Großbuchstaben b den verschlüsselten Großbuchstaben auf dem Bildschirm ausgibt. Die beiden Argumente werden über die Tastatur dem Programm übergeben, zuerst der Schlüssel k in einer Zeile und anschließend der Buchstabe b in einer Zeile. Die Ausgabe besteht nur aus dem kodierten Resultatbuchstaben zu Beginn der Ausgabezeile gefolgt von einem Zeilenumbruch. Beispiel: Für die Eingabe 5 X ist die Ausgabe C Überlegen Sie sich, wie Sie mit den Hilfmitteln, die bis jetzt bekannt sind, das “Hinauslaufen“ geeignet behandeln können. Nutzen Sie Eigenschaften der Zeichencodierung aus sowie geeignete arithmetische Operationen. Wie könnte die Dekodierung funktionieren? Hinweise: Modulo-Operation, Zeichen - ’A’, Typumwandlung zwischen int und char."

Ich bin schon so weit, dass der Buchstabe sich ändert je nachdem wie die Zahl ist. Aber ich habe noch das Problem, dass ich nicht weiß wie ich das "Hinauslaufen" programmieren kann. Kann mir da jemand helfen?

Vielen Dank im Voraus und freundliche Grüße, Lebenne.

...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

Dabei soll die groß und kleinschreibung berückstichtigt werden.

Mit freundlichen Grüßen

...zum Beitrag

Wie muss ich eine Funktion int sucheZeichen(const char s[], char c) erstellen und damit anzahl von Buchstaben ermitteln?

Hallo,

ich muss eine Funktion namens: int sucheZeichen(const char s[], char c) aufstellen ,

wobei der Rückgabewert der Häufigkeit des Characters c im Char-Array s entspricht.

Das Programm soll so aussehen:

Bitte Namen eingeben: Tim

Tim hat 3 Zeichen.

Ich bin neu beim Programmieren und wollte fragen ob mir jemand kurz zeigen kann, wie genau das kleine Programm aussehen muss. Habe schon viel probiert aber komme nicht weiter.

Da ich unter Zeitdruck stehe wäre es vielleicht auch sehr nett mir einfach das kleine Programm komplett zu programmieren.

MfG

...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

Tabelle mit Datentypen und Attributen?

Hey,

Ich brauche eure Hilfe. Ich verstehe leider die Aufgabe 2 und 3 nicht. (siehe Foto)

Dort muss man die Datentypen notieren die bei dem Erstellen der Tabelle "Musiker" (siehe Text) mit den genannten Atrributen zu verwenden ist.

Und die dritte Aufgabe verstehe ich einfach nicht.

Danke!

...zum Beitrag

Zahlen, Buchstaben, Wörter und Texte werden am Desktop farbig, geschwärzt, verschwommen, schattiert und oder überhaupt nicht angezeigt. Was kann ich tun?

Moin,

ich habe Probleme, weiß aber nicht, ob es Probleme am Betriebssystem bzw. Desktop ist, oder ob es am Bildschirm, Grafikkarte oder an den Kabeln liegt.

Die Zahlen, Buchstaben, Wörter und Texte werden am Desktop farbig, geschwärzt, verschwommen, schattiert und oder überhaupt nicht angezeigt.

__________

Vorweg: Manchmal tauchen die Probleme gleichzeitig oder vereinzelt auf, deswegen „und oder“.

Problem 1:

Die Titeln bei den Tabs und die URL Suchen werden an manchen Tagen manchmal und an anderen Tagen öfters nicht angezeigt und oder einige Buchstaben werden nicht angezeigt. Nur wenn man mit dem Mauszeiger drüber zeigt, sieht man die Titeln der Tabs und die URL-Suchen wieder.

Problem 2:

Manche Buchstaben in den Titeln und Google-Suchen werden manchmal komplett pink, rot und oder neonblau angezeigt.

Problem 3:

Beim hoch und runter scrollen werden wenige und oder viele einzelne Buchstaben, ganze Wörter und oder Texte in Google Suchen und in Webseiten verschwommen, geschwärzt, farbig und farbig-schattiert in pink, grün, rot, neonblau und oder überhaupt nicht angezeigt.

Problem 4:

Beim Scrollen wird manchmal das komplette Bildschirm für 1-2 Sek. grün.

Problem 5:

Vereinzelte Buchstaben, Wörter und oder ganze Texte sind in Google Suchen und oder in Webseiten manchmal grün oder pink umrandet.

__________

PC-Infos

Windows 10 Education

Prozessor: AMD PRO A12-9800 R7, 12 COMPUTE CORES 4C+8G 3.80 GHz, 4 Kern(e), 4 logische(r) Prozessor(en)

RAM: 8,00 GB (7,43 GB verwendbar)

Systemtyp: 64-Bit-Betriebssystem, x64 basierter Prozessor

Grafikkarte: AMD Radeon R7 Graphics

Bildschirm: Iiyama Prolite E2483hs

__________

Woran könnte das liegen?

...zum Beitrag

Was möchtest Du wissen?

Deine Frage stellen