Differences

This shows you the differences between two versions of the page.

--- chess:programming:huffman:example [2021/10/29 13:28] – peter
+++ chess:programming:huffman:example [2021/10/29 13:56] (current) – [Stepping through the code] peter
@@ Line 172: / Line 172: @@
 ----
-Now we just need an algorithm that will build a tree with minimal cost.
+===== Build the low-cost tree =====
+<code>
+Huffman (C)
+  n = the size of C
+  // Insert all the elements of C into Q, using the value of the node as the priority.
+  for i in 1..n-1 do
+    z = a new tree node
+    x = Extract-Minimum (Q)
+    y = Extract-Minimum (Q)
+    left node of z = x
+    right node of z = y
+    f[z] = f[x] + f[y]
+    Insert (Q, z)
+  end for
+  return Extract-Minimum (Q) as the complete tree
+</code>
+<WRAP info>
+**NOTE:**  In the following algorithm,
+  * **B(T)** is defined as above;
+    * it can be stored efficiently in an array indexed by characters.
+    * It is extended as needed to accommodate the values of internal tree nodes.
+  * **C** is the set of characters represented as leaf tree nodes.
+  * **Q** is a priority queue of tree nodes where we can quickly extract the minimum element;
+    * this can be done with a heap where the heap property is reversed.
+    * We build the tree in a bottom up manner, starting with the individual characters and ending up with the root of the tree as the only element of the queue.
+At first, the queue contains all the leaf nodes as a "forest" of singleton binary trees.
+  * Then the two nodes with least value are grabbed out of the queue, joined by a new tree node, and put back on the queue.
+  * After n-1 iterations, there is only one node left in the queue: the root of the tree.
+</WRAP>
+----
+==== Stepping through the code using the Huffman algorithm ====
+Here are the contents of **Q** after each step through the for loop:
+Initially, all nodes are leaf nodes.
+We stick all 8 in Q:
+<code>
+(space)  a    b    c    d    e    f    .
+    12    4    5   19   12    4    4
+</code>
+We join two of the nodes with least value; now there are 7 things in Q:
+<code>
+
+                / \   (space) a    b    c    d    e
+               f   .    17   12    4    5   19   12
+   4
+</code>
+----
+Then the next two with least value, Q has 6 elements:
+<code>
+                    9
+                / \   (space) a      / \     d    e
+               f   .    17   12     b   c   19   12
+   4                4   5
+</code>
+----
+Now the two nodes with least values are the two trees we just made, and Q has 5 elements:
+<code>
+
+                      __/   \__
+                   __/         \__
+                  /               \
+                 9
+                / \               / \     d    e  (space)  a
+               f   .             b   c   19   12    17    12
+   4             4   5
+<code>
+----
+The next two with least value, Q has 4 elements:
+<code>
+
+                      __/   \__
+                   __/         \__
+                  /               \              24
+                 9            /  \
+                / \               / \     d    e    a   (space)
+               f   .             b   c   19   12    12    17
+   4             4   5
+</code>
+----
+The next two with least value, three items left:
+<code>
+
+                                    ______/   \_____
+                             ______/                \_____
+                            /                            (space)
+                               17
+                      __/   \__
+                   __/         \__
+                  /               \                      24
+                 9                    /  \
+                / \               / \                  e    a      d
+               f   .             b   c                12    12     19
+   4             4   5
+</code>
+----
+The next two with least value, two big trees left:
+<code>
+
+                                    ______/   \_____
+                             ______/                \_____
+                            /                          (space)
+                             17
+                      __/   \__                             43
+                   __/         \__                         /  \
+                  /               \                      24    d
+                 9                    /  \  19
+                / \               / \                  e    a
+               f   .             b   c                12    12
+   4             4   5
+</code>
+Finally, we join the whole thing up:
+<code>
+
+                                               __________________/  \_______
+                                              /                             \
+                               43
+                                    ______/   \_____                        /  \
+                             ______/                \_____                24    d
+                            /                          (space)           /  \  19
+                             17             e   a
+                      __/   \__                                        12  12
+                   __/         \__
+                  /               \
+                 9
+                / \               / \
+               f   .             b   c
+   4             4   5
+</code>
+<WRAP info>
+**NOTE:** At each point, we chose the joining that would force less frequent characters to be deeper in the tree.
+</WRAP>
+----
+So an optimal prefix code is:
+<code>
+	(space)
+	a
+	b
+	c
+	d
+	e
+	f
+	.
+</code>
+And
+<code>
+B(T) = 17 * 2 + 12 * 3 + 4 * 4 + 5 * 4 + 19 * 2 + 12 * 3 + 4 * 4 = 196 bits
+</code>
+<WRAP info>
+**NOTE:**  A savings of 15% in the size of the data.
+</WRAP>