Memory-Efficient Adaptive Huffman Coding
By Steven Pigeon and Yoshua Bengio
Dr. Dobb's Journal October 1998
Procedure Update_M(a : symbol) { q,p :pointers to leaves ; p = find(a) ; // Leaf/set containing a q = find(p's frequency + 1) ; // where to migrate ? if (q != NIL) { // somewhere to migrate? remove a from p's set ; adjust p's weight ; Add a to q's set ; adjust q's weight ; Rebalance(q); If (p is empty) remove p from the tree ; else Rebalance(p's sibling) ; } else { // Need a new set create a new node t ; t's left child = p ; t's right child = a new node n ; n's set = {a} ; n's weight = p's frequency + 1 ; n's frequency = p's frequency + 1 ; replace the old p in the tree by t ; remove a from p's set ; p's weight = p's weight - p's frequency ; If (p is empty) remove p from the tree ; else Rebalance(p's sibling) ; Rebalance(t) ; } }
Example 1: The Migration algorithm.
Copyright © 1998, Dr. Dobb's Journal