TAILIEUCHUNG - Lecture Data Structures: Lesson 26

Lecture Data Structures: Lesson 26 provide students with knowledge about huffman encoding; to understand Huffman encoding, it is best to use a simple example; encoding the 32-character phrase: "traversing threaded binary trees"; repeat the process down the left and right subtrees; . | Huffman Encoding Huffman code is method for the compression for standard text documents. It makes use of a binary tree to develop codes of varying lengths for the letters used in the original message. Huffman code is also part of the JPEG image compression scheme. The algorithm was introduced by David Huffman in 1952 as part of a course assignment at MIT. 1 Lecture Data Structures Dr. Sohail Aslam 2 Huffman Encoding To understand Huffman encoding it is best to use a simple example. Encoding the 32-character phrase quot traversing threaded binary trees quot If we send the phrase as a message in a network using standard 8-bit ASCII codes we would have to send 8 32 256 bits. Using the Huffman algorithm we can send the message with only 116 bits. 3 Huffman Encoding List all the letters used including the quot space quot character along with the frequency with which they occur in the message. Consider each of these character frequency pairs to be nodes they are actually leaf nodes as we will see. Pick the two nodes with the lowest frequency and if there is a tie pick randomly amongst those with equal frequencies. 4 Huffman Encoding Make a new node out of these two and make the two nodes its children. This new node is assigned the sum of the frequencies of its children. Continue the process of combining the two nodes of lowest frequency until only one node the root remains. 5 Huffman Encoding Original text traversing threaded binary trees size 33 characters space and newline NL 1 i 2 SP 3 n 2 a 3 r 5 b 1 s 2 d 2 t 3 e 5 g 1 v 1 h 1 y 1 6 Huffman Encoding 2 is equal to sum of the frequencies of the two children nodes. e r a t 5 5 3 3 d i n s 2 SP 2 2 2 2 3 NL b g h v y 1 1 1 1 1 1 7 Huffman Encoding There a number of ways to combine nodes. We have chosen just one such way. e r a t 5 5 3 3 d i n s 2 2 SP 2 2 2 2 3 NL b g h v y 1 1 1 1 1 1 8 Huffman Encoding e r a t 5 5 3 3 d i n s 2 2 2 SP 2 2 2 2 3 NL b g h v y 1 1 1 1 1 1 9 Huffman Encoding e r a t 4 4 5 5 3 3 d i

• Cơ sở dữ liệu
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Data structures
• Huffman encoding
• Binary trees
• Huffman algorithm
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• Programming assignments
• Data structures organize data
• Resource constraints
• Abstract data types
• Tree data structure
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Fundamental data structures
• Computational complexity
• Complexity of algorithms
• Data structure
• Pointers to structures
• Pointers to classes
• Josephus problem
• List data structures
• Doubly linked list
• Circularly linked list
• Code for simulation
• Priority queue
• Tree data structures
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming