Implementing Huffman coding for the compression challenge
@plutov Hi,
This PR aims to solve the issue #79.
#### Is your solution the most efficient way to solve a problem? Why?
No. If the dataset is small, Huffman coding may not be the most efficient because the tree-building overhead can outweigh the benefits of compression.
Huffman coding is not context-aware, meaning it generates codes only based on individual character frequencies. In cases where there are patterns or repetitions of groups of symbols, algorithms like LZ (Lempel-Ziv) could be more efficient, as they build dictionaries of repeating patterns and replace them with shorter codes.
#### Have you used any specific algorithm?
Yes, I have implemented Huffman coding algorithm for data compression
#### What is time and space complexity of your solution?
Assumptions:
`n` : total number of characters in the input data.
`k`: number of unique characters.
##### Time Complexity
Counting the frequency for each character: `O(n)`.
Building Priority Queue(Min Heap) : Inserting K unique items takes `O(kLog(k))`.
Building Huffman Tree: Extrating minimum element from the priority queue takes `O(logk)`, doing for `k-1` times takes `O(kLog(k))`.
Generating Huffman Codes: Traversing the Huffman tree to generate codes for each character `O(k)` (as we visit each node only once in a binary tree, and the tree has k leaves).
Over all time complexity: `O(n + kLog(k))`.
##### Space Complexity
Frequency Map: Storing `k` unique items takes `O(k)` space.
Priority Queue(Min Heap): Storing `k` unique items takes `O(K)` space.
Huffman Tree: The tree has `k` leaves takes `O(k)` space.
Over all space complexity: `O(k)`.
合并状态:已合并 合并于 2024-11-09 关闭于 2024-11-09 1 条评论