Optimal merge pattern

Question

Is there any difference in between draw tree for huffman coding and optimal merge pattern if yes please give detailed explanation.

Comments

 

Optimal Merge:

merge n sorted sequences of different lengths into one output while minimizing reads. Only two sequences can be merged at once. At each step, the two shortest sequences are merged.

Merging sequences by length is the same as joining trees by frequency in Huffman coding.

For example, let there be a set of sorted sequences of the following lengths: D={3,5,7,9,12,14,15,17}. Building the optimal merge tree goes as follows. Note that merged sequences are replaced by the sum of their lengths. For instance, the first step merges the sequence of length 3 and the sequence of length 5 to get a sequence of length 8. Check the reference link for full example.

Reference: https://xlinux.nist.gov/dads/HTML/optimalMerge.html

External path length: 

wi as the weight of ci or of its external node

P =  $\sum$ wi * δi .

Since δi is the depth of the leaf ci , P is also known as the weighted external path length of the corresponding tree.

Ref: https://www2.cs.duke.edu/courses/fall08/cps230/Lectures/L-05.pdf

Answer 1

Huffman code is the optimal way to draw tree for optimal merge pattern

Answer 2

there is no difference b/w huffman coading and optimal merge pattern. both are working as same .

the answer of the above question will be 140