CMPSC 122 Chapter Notes - Chapter 13: Huffman Coding, Binary Tree
7 Nov 2016
School
Department
Course
Professor
Document Summary
13. 4: text compression text compression: given a string x, encode x into a small binary string y. Useful for bandwidth reduction or storing many documents. Ascii uses fixed length binary strings to represent characters. Hc uses code-word strings to encode frequently used characters. Based on the number of times any given character c appears in the string. Convert each character to a variable length code-word. No code-word should be the prefix of another code-word. Each leaf is associated with a character the code word for a character is the sequence of bits created by the edges required to get to the leaf. Each internal node has a frequency that is the sum of the frequencies of its subtrees. Start out with each character and its frequency in a single node binary tree. Combine the two smallest frequency trees into a single tree repeat until there is one tree.
