ITADN

Implementing Huffman coding for the compression challenge

#82Pull Requestbrianpzaide 创建于 2024-11-08已合并
B
brianpzaidecommented
@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 条评论