<jupyter_start><jupyter_text>Huffman_compression Use less bits to represent symbol with higher frequency.     sort symbol by frequency from small to large     add up and group smaller frequency to form sub trees      group such subtrees with larger frequency symbols      path from root to leaf gives binary representation reference: https://algorithm.yuanbin.me/zh-hans/basics_data_structure/huffman_compression.html<jupyter_code>import heapq
import collections

def compression_rate(compressed_binary, uncompressed_bits):
    return len(compressed_binary)*100/uncompressed_bits

class SimpleCompression:
    def __init__(self, string):
        self.symbols = set(string) #set('1223') -> {'1','2','3'}
        self.bit_len=1
        while 2**self.bit_len<len(self.symbols):
            self.bit_len+=1
        self.string = string
        
        self.s2b={}
        self.b2s={}
        i=0
        for s in self.symbols:
            b=bin(i)[2:] #bin(6) -> '0b110'
            if len(b)<self.bit_len: #if length of b is smaller than bit_len
                b = (self.bit_len-len(b))*'0'+b #convert b to length of bit_len
            self.s2b[s] = b
            self.b2s[b] = s
            i+=1
            
    def compress(self):
        bits=''
        for s in self.string:
            bits += self.s2b[s]
        return bits
    
    def uncompress(self, bits):
        string = ''
        for i in range(0, len(bits), self.bit_len):
            string += self.b2s[bits[i:i+self.bit_len]]
        return string
def HuffmanCompression:
    class Trie:
        def __init__(self,val,char=''):
            self.val = val
            self.char = char
            self.coding = ''
            self.left = self.right = None
        def __eq__(self, other):
            return self.val==other.val
        def __lt__(self, other):
            return self.val<other.val
        def __gt__(self,other):
            return self.val > other.val
    def __init__(self,string):
        self.string = string
        counter = collections.Counter(string)#collections.Counter('122234')->Counter({'1': 1, '2': 3, '3': 1, '4': 1})
        heap = []
        for char, cnt in counter.items():
            heapq.heappush(heap, HiffmanCompression.Trie(cnt,char)) #heapq. heappush (heap, item)
        while len(heap)!=1:
            left = heapq.heappop(heap)
            right = heapq.heappop(heap)
            trie = HiffmanCompression.Trie(left.val+right.val)
            trie.left, trie.right = left,right
            heapq.heappush(heap,trie)
        self.root = heap[0]
        self.s2b={}
        self.bfs_encode(self.root, self.s2b)
        
    def bfs_encode(self,root,s2b):
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if node.char:
                s2b[node.char] = node.coding
            if node.left:
                note.left.coding = node.coding+'0'
                queue.append(node.left)
            if node.right:
                node.right.coding = node.coding+'1'
                queue.append(node.right)
                
    def compress(self):
        bits=''
        for char in self.string:
            bits+=self.s2b[char]
        return bits
    
    def uncompress(self,bits):
        string=''
        root = self.root
        for bit in bits:
            if bit=='0':
                root = root.left
            else:
                root = root.right
            if root.char:
                string += root.char
                root = self.root
        return string
collections.Counter('122234')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11049875998897768, 'fraction_numerical': 0.016257922292642602, 'mean_word_length': 1.8074245939675173, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '462949', 'license': 'MIT', 'n_tokens_mistral': 1142, 'n_tokens_neox': 1104, 'n_words': 255, 'path': 'basics/L2_Huffman_Compression.ipynb', 'repo_name': 'qyangaa/algorithm_practice', 'size': '3629'}