Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2011:journals:charles:chapter4 [2011/02/20 02:39] – [4.7 Clustering] gouldc | courses:cs211:winter2011:journals:charles:chapter4 [2011/02/20 02:45] (current) – [4.8 Huffman Codes and Data Compression] gouldc |
|---|
| A variation of Kruskal's Algorithm solves it (4.26) //The components C1, C2, ..., Ck formed by deleting the k - 1 most expensive edges of the minimum spanning tree T constitute a k-clustering of maximum spacing.// | A variation of Kruskal's Algorithm solves it (4.26) //The components C1, C2, ..., Ck formed by deleting the k - 1 most expensive edges of the minimum spanning tree T constitute a k-clustering of maximum spacing.// |
| ===== 4.8 Huffman Codes and Data Compression ===== | ===== 4.8 Huffman Codes and Data Compression ===== |
| Huge research area. The main example is language: n letters, each letter has a different frequency in the language. It's possible to encode the letters in log(n) bits... but we want to encode the more frequent letters with fewer bits to reduce the average bits per letter (ABL). Huffman coding makes this possible. | Huge research area. Think languages. If there are n letters in a language, it's possible to encode the letters in log(n) bits. But we know that letters come up with different frequencies. Suppose we are given the individual frequencies of each letter; is it possible to encode the more frequent letters with fewer bits so as to reduce the average bits per letter (ABL)? |
| | |
| | Yeah, Huffman coding is one way. |
| ===== 4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm ===== | ===== 4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm ===== |
| Under construction... | Under construction... |
