8
Huffman-Code Gierige Methoden "kurzsichtig handeln, langfristig gewinnen"

Huffman -Code

  • Upload
    adina

  • View
    124

  • Download
    0

Embed Size (px)

DESCRIPTION

Huffman -Code . Gierige Methoden "kurzsichtig handeln, langfristig gewinnen". Übersicht. Funktionsweise der Huffman-Codierung Beispiel zum Codieren und Decodieren Aufgabe zum Huffman-Verfahren. Ideale Codierung. Ziel: Inhalte so kurz wie möglich zu speicher n - PowerPoint PPT Presentation

Citation preview

Page 1: Huffman -Code

Huffman-Code Gierige Methoden

"kurzsichtig handeln, langfristig gewinnen"

Page 2: Huffman -Code

Übersicht• Funktionsweise der Huffman-Codierung • Beispiel zum Codieren und Decodieren • Aufgabe zum Huffman-Verfahren

Page 3: Huffman -Code

Ideale Codierung• Ziel: Inhalte so kurz wie möglich zu speichern

• ASCII-Codierung mit 8-Bit (= 1 Byte)• Trennzeichen zwischen jeder Codierung• Keine Trennzeichen

Bei fester Zeichenanzahl kein ProblemSchwierigkeit bei variabler Zeichenanzahl

Anfang von Codierung muss unterscheidbar vom Ende der Codierung sein

• Binär Baum bzw. Codierungsbaum

Page 4: Huffman -Code

Lösung von Huffman

Die beiden Buchstaben/Bäume mit

der geringsten Häufigkeit werden zu

einem Binär-Baum zusammengefasst

Ab der Wurzel sinkt die Häufigkeit der

Buchstaben

Dieser Baum wird wieder in die Liste der

Häufigkeiten einsortiertDer Baum besitzt die

Häufigkeit von der Summe der

Häufigkeiten seiner beiden Teilbäume

Der zu codierende Inhalt/Text muss eingelesen werden

Häufigkeit aller Buchstaben wird ermittelt

Sortieren der Buchstaben nach Häufigkeit

Page 5: Huffman -Code

Beispiel für die Codierung von Huffman

Die beiden Buchstaben/Bäume mit

der geringsten Häufigkeit werden zu

einem Binär-Baum zusammengefasst

Ab der Wurzel sinkt die Häufigkeit der

Buchstaben

Dieser Baum wird wieder in die Liste der

Häufigkeiten einsortiertDer Baum besitzt die

Häufigkeit von der Summe der

Häufigkeiten seiner beiden Teilbäume

„aaacef“

A = 3 , B = 0, C = 1, D = 0, E = 1, F =1 …

C, A

11101000011

Page 6: Huffman -Code

AufgabenSortiere die folgenden Häufigkeiten:

a = 651 g = 301 m = 253

s = 727 y = 4

b = 189 h = 476 n = 978

t = 615 z = 113

c = 306 i = 755 o = 251 u = 435d = 508 j = 27 p = 79 v = 67e = 1740

k = 121 q = 2 w = 189

f = 166 l = 344 r = 700 x = 3Erstelle dir auf Grundlage der ersten Aufgabe einen Huffman Baum!Codiere basierend auf Aufgabe 2 folgendes Wort:„Huffman“

Page 7: Huffman -Code

Noch Fragen?

Page 8: Huffman -Code

Danke für eure Aufmerksamkeit

(Präsentation von: Angelika Richter, Benno Ommerborn, Etibar, Charlotte Smid, Gernot Götz vom Informatik LK 12.1 VDB 2009)