<jupyter_start><jupyter_text>Huffman Coding  **Solution**<jupyter_code>import heapq
from collections import Counter, namedtuple
class Node(namedtuple("Node", ["left", "right"])):
  def walk(self, code, acc): # code - префикс кода, который мы накопили спускаясь от корня к узлу/литу
      self.left.walk(code, acc + "0")
      self.right.walk(code, acc + "1")
class Leaf(namedtuple("Leaf", ["char"])):
  def walk(self, code, acc):
      code[self.char] = acc or "0"<jupyter_output><empty_output><jupyter_text>**Encoding**<jupyter_code>def huffman_encode(s):
  h = []
  for ch, freq in Counter(s).items():
      h.append((freq, len(h), Leaf(ch)))
  
  # h = [(freq, Leaf(ch)) for ch, freq in Counter(s).items()]
  heapq.heapify(h)
  
  count = len(h)
  while len(h) > 1: # пока в очереди есть элем
    freq1, _count1, left = heapq.heappop(h) # достаём элем с минимальной частотой
    freq2, _count2, right = heapq.heappop(h)
    heapq.heappush(h, (freq1 + freq2, count, Node(left, right)))
    count += 1
    
  code = {}  
  if h:  
    [(_freq, _count, root)] = h # корень дерева
    root.walk(code,"")
  
  return code<jupyter_output><empty_output><jupyter_text>**Decoding**<jupyter_code>def huffman_decode(encoded, code):
  sx = []
  enc_ch = ""
  for ch in encoded:
      enc_ch += ch
      for dec_ch in code:
          if code.get(dec_ch) == enc_ch:
              sx.append(dec_ch)
              enc_ch = ""
              break
  return "".join(sx)
def main():
  s = input()
  code = huffman_encode(s)
  """
  закодированная версия строки s 
  отображает каждый симвом в соответствующий ему код
  """
  encoded = "".join(code[ch] for ch in s)
  """
  len(code) - количество различных символов в строке s, словарь
  len(encoded) - длина закодированной строки
  """
  print("\nDictionary =", len(code), "\nLength of string =", len(encoded))
  # описываем как мы кодируем каждый символ
  print("\n")
  for ch in sorted(code):
    print("{}: {}".format(ch, code[ch]))
  print("\nEncoded string: ",encoded) # закодированная строка
  print("\nDecoded string:",huffman_decode(encoded, code))
  
  
if __name__ == "__main__":
  main()<jupyter_output>I saw you in restaurant yesterday

Dictionary = 14 
Length of string = 121


 : 101
I: 10010
a: 011
d: 0100
e: 000
i: 11001
n: 1000
o: 11000
r: 1111
s: 1101
t: 001
u: 0101
w: 10011
y: 1110

Encoded string:  1001010111010111001110111101100001011011100110001011111000110100101101011111011100000110111100001101001000111101000111110

Decoded string: I saw you in restaurant yesterday<jupyter_text>Testing<jupyter_code>import random
import string
def test(n_iter=100):
    for i in range(n_iter):
        length = random.randint(0, 32)
        s = "".join(random.choice(string.ascii_letters) for _ in range(length))
        code = huffman_encode(s)
        encoded = "".join(code[ch] for ch in s)
        assert huffman_decode(encoded, code) == s<jupyter_output><empty_output><jupyter_text>Simple code<jupyter_code>def huffman_encode(s):
  return {ch: ch for ch in s} # кодирует сам в себя (отображает каждый символ в соответствующий ему код)
def main():
  s = input()
  code = huffman_encode(s)
  # закодированная версия строки s 
  # отображает каждый симвом в соответствующий ему код
  encoded = "".join(code[ch] for ch in s)
  # len(code) - количество различных символов в строке s, словарь
  # len(encoded) - длина закодированной строки
  print("\nDictionary =", len(code), "\nLength of string =", len(encoded))
  # описываем как мы кодируем каждый символ
  print("\n")
  for ch in sorted(code):
    print("{}: {}".format(ch, code[ch]))
  print("\n", encoded) # закодированная строка
  
  
if __name__ == "__main__":
  main()<jupyter_output>abcdabcd

Dictionary = 4 
Length of string = 8


a: a
b: b
c: c
d: d
abcdabcd
{'fraction_non_alphanumeric': 0.13227091633466134, 'fraction_numerical': 0.05338645418326693, 'mean_word_length': 3.8035714285714284, 'pattern_counts': {'":': 2, '<': 19, '<?xml version=': 0, '>': 20, 'https://': 0, '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': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '9810', 'license': 'MIT', 'n_tokens_mistral': 1633, 'n_tokens_neox': 1538, 'n_words': 372, 'path': 'Data Compression Methods/Huffman Code/Huffman_code.ipynb', 'repo_name': 'ElizaLo/Practice-Python', 'size': '3765'}