CODEWITHSUNDEEP
algorithmhuffman-code
user2375464
user2375464

Reputation:

Huffman coding is based on what Greedy Approach or Dynamic Programming

Can we solve Problem of Huffman Coding by using Dynamic Programming, Is there any algorithm

Upvotes: 3

Views: 3898

Answers (3)

vikky.rk
vikky.rk

Reputation: 4149

[Update]: I think the solution I mentioned below generates an optimal prefix code, but not necessarily same as Huffman code. Huffman code, by definition, is generated by taking the greedy approach. While it is optimal, it is not the only solution. (For example, once the Huffman tree is generated, you could interchange the leaves in the same level to give them different codes while still being optimal)

I think this can be solved using Dynamic Programming, although it won't be that efficient. The approach here is very similar to finding the Optimal Binary Search Tree, since as you go one level down you add one more bit to the leaves.

enter image description here

Here is the link for the code to calculate the minimum number of total bits. Of course this is exponential, but if you use DP it can be solved in O(n^2) time. I haven't tried generating the encoding, but should be possible I believe.

Upvotes: 1

user2273202
user2273202

Reputation:

As per my knowledge about algorithms, I beleive huffman coding is based on Greedy approach. As we do in Activity selection problem. Task scheduling and knapsack problem are another examples of it.

Upvotes: 2

Deepu
Deepu

Reputation: 7610

Huffman Coding works by creating a binary tree of nodes. These can be stored in a regular array, the size of which depends on the number of symbols, n. Huffman Coding can be implemented in O(n logn) time by using the Greedy Algorithm approach. Huffman Coding is not suitable for a Dynamic Programming solution as the problem does not contain overlapping sub problems.

Upvotes: 3

Related Questions