01:198:112 Lecture Notes - Lecture 14: Huffman Coding
Document Summary
E. g. compress characters and symbols to a smaller data size so that it is easier to send and store. A file with 100 characters, 8 bits/1 byte for a character. Saving the file as is will have a file size of 800 bytes. Say the file only has the characters a,b,c,d,e,f. We can use 0 and 1"s to represent these characters instead. With 1 bit we can represent 2 things. With 2 bits we can represent 4 things. With 3 bits we can represent 8 things. The number of bits can be rearranged to create patterns to represent different things. In this case with only 6 characters, we need three bits. Use a shorter coding system for frequent appearance of characters. Use a longer coding system for infrequent appearances of. Total code is 010 000 101 100. To encode the file we only need 300 bits. For each supported character create a bt with a single node.