Der Huffman Code | Algorithmen und Datenstrukturen

Inhalt 📚
Um ein #ASCII-Zeichen im #Computer darzustellen, werden 8 #Bits (also ein #Byte) verwendet, d. h. wenn du ein Wort mit 10 Buchstaben hast, dann werden 80 #Bits (bzw. 10 #Bytes) benötigt, um dieses im #Computer zu speichern. Das muss doch auch einfacher gehen! Ja, man könnte z. B. die einzelnen Zeichen in einem Wort von links nach rechts durchgehen und für jeden "neuen" (d. h. bislang noch nicht aufgetauchten Buchstaben) einen #Binärcode fixer Länge vergeben. Dabei zählst du einfach #binär hoch und weist so den Buchstaben einen #Binärcode (ggf. mit führenden Nullen) zu. Es geht aber noch effizienter, nämlich durch den #Huffman-#Code. Der Buchstabe e kommt nämlich z. B. häufiger in Wörtern der deutschen oder englischen Sprache vor als z. B. das x. Es liegt also der Schluss nahe, häufig vorkommende Buchstaben mit so wenigen Zeichen wie möglich zu codieren. Statt also eine fixe Länge für #Binärcodes vorzugeben, werden mit dem #Huffman-#Code die Zeichen in einem Wort mit #Binärcodes variabler Länge codiert. Der #Huffman-#Code erfüllt übrigens die Fano-Bedingung, d. h. dass kein #Codewort Anfangswort eines anderen Codewortes ist und somit jede codierte Zeichenreihe eindeutig decodierbar ist. Das wirst du im Laufe des Videos noch sehen.

- Vorwort: 0:00
- Intro: 0:05
- Einführung: 0:12
- Wie funktioniert der Algorithmus? 1:19
- Beispiel für die Huffman-Codierung: 2:35
- ENDE: 6:06

EQUIPMENT(*)

SUPPORT
► PayPal

SOCIAL MEDIA

[absence]

wenn's jmd in Python haben will, zeigt auch benötigten Speicherplatz mit und ohne Huffman-Kodierung an:

def huffman(message):
#initilialise stack
stack = sorted([Node(val=a, k=b) for a, b in Counter(message).items()], key=lambda x:x.k, reverse=True)

#create huffman tree
while len(stack)>1:
x=stack.pop()
y=stack.pop()
stack.append(Node(val=None, k=x.k+y.k, left=x, right=y))
stack.sort(key=lambda x:x.k, reverse=True)

#turn tree into translation dict
translator = dict()
def convert(node, s=''):
if node.left: convert(node.left, s+'0')
if node.right: convert(node.right, s+'1')
elif node.val: translator[node.val]=s
convert(stack[0])

for char in message)
print(f'<Translation dict: {translator}>')
print(f'<Storage size using bits for each character: bits>')
print(f'<New storage size: {len(result)} bits>')
return result

[Ufuk]

Wie leicht es ist durch gute Erläuterung, bin echt begeistert

[whogotpwned]

Sehr gut erklärt. Deine Darstellungen und Animationen sind echt gut. Top.

[dominichauff]

Genau was ich gebraucht habe. Nicht mehr und nicht weniger. Daumen hoch

[toniii]

Sehr gut erklärt mit einer echt angenehmen Stimme. Danke!

[JustAnAliasBro]

Hast mir gerade so den Arsch gerettet. Hab Prüfung morgen und hatte keine Ahnung. Erklärungen sind Präzise, Animationen sehr gut, Sehr gute Sprechstimme und alles in allem 1+ für das vid.
Danke <3

[janniswildermuth]

Super erklärt. Das die intuitive Variante mit verglichen wurde finde ich auch toll, sonst wäre die erste Frage bei vielen natürlich direkt, ob das denn überhaupt was bringt.

[anna-lenaklaas]

Sehr gut erklãrt. Versteht sogar ein Boomer

[louispeter]

das Video ist voll gut!! Simple und einfach erklärt, sodass man es auch wirklich verstehen kann :) danke dir

[hakim]

Danke für das Video schreibe morgen meine Arbeit und habe durch das Video viel gelernt.

[nterior]

Super erklärt. Gerne mehr solcher Videos

[dragonminja]

Muss schon sagen, das war echt gut :D

[IAmD]

VOICE CRACK sein vater, aber vielen dank fürs video <3

[TheCelebreties]

Vielen Dank! Mehr kann man dazu nicht sagen :D

[anonym]

Hätte man auch SS und PP als Block nehmen können? Die kommen ja immer nur zusammen vor. So wäre meine Codewort nur 14 Zeichen lang. Oder lässt sich das nur mit gleichlangen Blöcke machen?

[jensharbers]

Super video, muss anmerken, das ich im Studium leider zu spät den Sinn von manchen Datenstrukturen und anderen gesehen habe

[MiauRizius]

Cooles und vorallem interessantes Video.

[BA-pqvr]

Eine Frage: Hätte man auch die Buchstaben I und S verbinden können? Also das dann der Baum symmetrisch ist…

[denizonat]

was kurzes dazu gelernt. Kannst du das programmieren in c und den code erklären?

[Johannes-vbtg]

2:13 dieser Voicecrack haha wollte doch nur für Informatik lernen haha. Starkes Video sonst