CSEP 590 Data CompressionAutumn 2007Adaptive Huffman CodingCSEP 590 - Lecture 2 - Autumn 2007 2Adaptive Huffman Coding• One pass• During the pass calculate the frequencies• Update the Huffman tree accordingly– Coder – new Huffman tree computed after transmitting the symbol– Decoder – new Huffman tree computed after receiving the symbol• Symbol set and their initial codes must be known ahead of time. • Need NYT (not yet transmitted symbol) to indicate a new leaf is needed in the tree.CSEP 590 - Lecture 2 - Autumn 2007 3Optimal Tree Numbering• a : 5, b: 2, c : 1, d : 3ac bdCSEP 590 - Lecture 2 - Autumn 2007 4Weight the Nodes• a : 5, b: 2, c : 1, d : 311631 253ac bdCSEP 590 - Lecture 2 - Autumn 2007 5Number the Nodes• a : 5, b: 2, c : 1, d : 311631 253ac bdNumber the nodes as they are removed from the priority queue.2756341CSEP 590 - Lecture 2 - Autumn 2007 6Adaptive Huffman Principle• In an optimal tree for n symbols there is a numbering of the nodes y1<y2<... <y2n-1such that their corresponding weights x1,x2, ... , x2n-1satisfy:– x1< x2< ... < x2n-1– siblings are numbered consecutively• And vice versa– That is, if there is such a numbering then the tree is optimal. We call this the node number invariant.CSEP 590 - Lecture 2 - Autumn 2007 7Initialization• Symbols a1, a2, ... ,am have a basic prefix code, used when symbols are first encountered.• Example: a, b ,c, d, e, f, g, h, i, j0000000001 11111111ahgfedcbjiCSEP 590 - Lecture 2 - Autumn 2007 8Initialization• The tree will encode up to m + 1 symbols including NYT.• We reserve numbers 1 to 2m + 1 for node numbering.• The initial Huffman tree consists of a single node02m + 1weightnode numberNYTCSEP 590 - Lecture 2 - Autumn 2007 9Coding Algorithm1. If a new symbol is encountered then output the code for NYT followed by the fixed code for the symbol. Add the new symbol to the tree.2. If an old symbol is encountered then output its code.3. Update the tree to preserve the node number invariant.CSEP 590 - Lecture 2 - Autumn 2007 10Decoding Algorithm1. Decode the symbol using the current tree.2. If NYT is encountered then use the fixed code to decode the symbol. Add the new symbol to the tree.3. Update the tree to preserve the node number invariant.CSEP 590 - Lecture 2 - Autumn 2007 11Updating the Tree1. Let y be leaf (symbol) with current weight x.*2. If y the root update x by 1, otherwise,3. Exchangey with the largest numbered node with the same weight (unless it is the parent).**4. Update x by 15. Let y be the parent with its weight x and go to 2. *We never update the weight of NYT** This exchange will preserve the node number invariantCSEP 590 - Lecture 2 - Autumn 2007 12Example• aabcdad in alphabet {a,b,..., j}021output = 000fixed codeNYTfixed code for aCSEP 590 - Lecture 2 - Autumn 2007 13Example• aabcdad019output = 000 11200121aNYTCSEP 590 - Lecture 2 - Autumn 2007 14Example• aabcdad0output = 0001110121aNYT1920CSEP 590 - Lecture 2 - Autumn 2007 15Example• aabcdad0output = 0001 210121aNYT1920CSEP 590 - Lecture 2 - Autumn 2007 16Example• aabcdad0output = 00010001220121NYTfixed code for baNYT1920CSEP 590 - Lecture 2 - Autumn 2007 17Example• aabcdadoutput = 00010001 220121a20019a01701801bNYTCSEP 590 - Lecture 2 - Autumn 2007 18Example• aabcdadoutput = 00010001 220121a20019a01711801bNYTCSEP 590 - Lecture 2 - Autumn 2007 19Example• aabcdadoutput = 00010001 220121a20019a11711801bNYTCSEP 590 - Lecture 2 - Autumn 2007 20Example• aabcdad230121a20019a11711801boutput = 0001000100010NYTfixed code for cNYTCSEP 590 - Lecture 2 - Autumn 2007 21Example• aabcdad19output = 0001000100010 23200121a117118010 a01501601NYTabcCSEP 590 - Lecture 2 - Autumn 2007 22Example• aabcdad19output = 0001000100010 23200121a117118010 a01511601NYTabcCSEP 590 - Lecture 2 - Autumn 2007 23Example• aabcdad19output = 0001000100010 23200121a117118010 a11511601NYTabcCSEP 590 - Lecture 2 - Autumn 2007 24Example• aabcdad19output = 0001000100010 23200121a217118010 a11511601NYTabcCSEP 590 - Lecture 2 - Autumn 2007 25Example• aabcdad1924200121a217118010 a11511601NYTabcoutput = 0001000100010000011NYTfixed code for dCSEP 590 - Lecture 2 - Autumn 2007 26Example• aabcdad1924200121a21711801a11511601NYTabcoutput = 0001000100010000011 0 a1301401d0CSEP 590 - Lecture 2 - Autumn 2007 27Example• aabcdad1924200121a21711801a11511601NYTabcoutput = 0001000100010000011 0 a1311401d0CSEP 590 - Lecture 2 - Autumn 2007 28Example• aabcdad1924200121a21711801a11511601NYTabcoutput = 0001000100010000011 0 a1311401d1exchange!CSEP 590 - Lecture 2 - Autumn 2007 29Example• aabcdad192420012121711801a11511601NYTabcoutput = 0001000100010000011 0 a1311401d1CSEP 590 - Lecture 2 - Autumn 2007 30Example• aabcdad192420012121711801a21511601NYTabcoutput = 0001000100010000011 0 a1311401d1exchange!CSEP 590 - Lecture 2 - Autumn 2007 31Example• aabcdad192420012121711801a21511601NYTabcoutput = 0001000100010000011 0 a1311401d1CSEP 590 - Lecture 2 - Autumn 2007 32Example• aabcdad192420012131711801a21511601NYTabcoutput = 0001000100010000011 0 a1311401d1CSEP 590 - Lecture 2 - Autumn 2007 33Example• aabcdad192520012131711801a21511601NYTabcoutput = 000100010001000001100 a1311401d1Note: the first a is codedas 000, the second as 1, and the third as 0CSEP 590 - Lecture 2 - Autumn 2007 34Example• aabcdad193520012131711801a21511601NYTabcoutput = 000100010001000001100 a1311401d1CSEP 590 - Lecture 2 - Autumn 2007 35Example• aabcdad193620012131711801a21511601NYTabcoutput = 0001000100010000011011010 a1311401d1exchange!CSEP 590 - Lecture 2 - Autumn 2007 36Example• aabcdad193620012131711801a21511601NYTadcoutput = 0001000100010000011011010 a1311401b1CSEP 590 - Lecture 2 - Autumn 2007 37Example• aabcdad193620012131721801a21511601NYTadcoutput = 0001000100010000011011010 a1311401b1CSEP 590 - Lecture 2 - Autumn 2007 38Example• aabcdad193620012141721801a21511601NYTadcoutput = 0001000100010000011011010 a1311401b1CSEP 590 - Lecture 2 - Autumn 2007 39Example• aabcdad193720012141721801a21511601NYTadcoutput = 0001000100010000011011010 a1311401b1CSEP 590 - Lecture 2 - Autumn 2007 40Data Structure for Adaptive Huffmanabcd...j1. Fixed code table2. Binary tree withparent pointers3. Table of pointersnodes into tree4. Doubly linked listto rank the nodesNYT37014201a2101NYTadc0 a101b1CSEP 590 - Lecture 2 - Autumn 2007 41In Class Exercise• Decode using adaptive Huffman coding assuming the following fixed code• 00110000a gfeb c d h0000 0001 11111 1CSEP
View Full Document
Unlocking...