Huffman Coding (AQA GCSE Computer Science): Flashcards
📚Flashcards
Practise the cards
14 cards from this deck
ShowHide
Practise the cards
14 cards from this deck
Type of compression used by Huffman coding
Type of compression used by Huffman coding
Lossless data compression
Huffman: Frequent chars get ___ codes
Huffman: Frequent chars get ___ codes
Shorter
Data structure used in Huffman coding
Data structure used in Huffman coding
Binary tree
Starting point of a Huffman tree
Starting point of a Huffman tree
Root node
Huffman coding: Data loss?
Huffman coding: Data loss?
None - it's lossless
First step in creating Huffman code
First step in creating Huffman code
Count character frequencies
Key rule when building Huffman tree
Key rule when building Huffman tree
Combine two lowest frequency nodes first
Frequency of new combined node in Huffman tree
Frequency of new combined node in Huffman tree
Sum of children frequencies
Root node frequency should equal
Root node frequency should equal
Total character count
Binary code for left branches in Huffman tree
Binary code for left branches in Huffman tree
0 (right = 1)
How to find a character's Huffman code
How to find a character's Huffman code
Follow path from root to character, writing 0s and 1s
Huffman coding uses ___ encoding
Huffman coding uses ___ encoding
Variable-length
Bits per character in ASCII encoding
Bits per character in ASCII encoding
8 bits
Huffman coding optimality
Huffman coding optimality
Most efficient variable-length encoding possible