Algorithms For Dummies

 

»

Manage prefix-free coding using a specific strategy. Huffman encoding 

manages prefix-free codes by using binary trees in a smart way. Binary trees 

are a data structure discussed in Chapters 6 and 7. The Huffman algorithm uses 

binary trees (called Huffman trees) in an advanced fashion. You can read more 

about the internals of the algorithm in the tutorial at 

https://www.siggraph.

org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_ 

tutorial.html

.

The algorithm used to perform Huffman encoding uses an iterative process that 

relies on heaps, which are specialized tree-based data structures (mentioned in 

Chapter 6). A heap is a complex data structure. Because of the manner in which 

you use a heap to arrange data, it’s useful for achieving a greedy strategy. In the 

next chapter, which is devoted to greedy algorithms, you test Huffman encoding 

yourself, using the working examples in the downloadable code accompanying the 

book (the Huffman Compression example in the 

A4D; 15; Greedy Algorithms.

ipynb

 file; see the Introduction for details).

For the moment, as an example of a Huffman encoding output, Figure 14-1 shows 

the Huffman encoding binary tree used to encode a long sequence of ABCDE letters 

distributed in a way that A is more frequent than B, B more than C, C more than D, 

and D more than E.

---

CHAPTER 14