fork download 
  1. #! /usr/bin/env python3
  2.  
  3. from functools import reduce
  4.  
  5. def createValue2Code(data):
  6.  
  7.     # 各要素の発生回数を数える
  8.     def countDatum(): # ローカル関数の場合、スコープが createValue2Code の data を捕捉する
  9.         def foo(d, elt):
  10.             try:
  11.                 d[elt] += 1
  12.             except KeyError:
  13.                 d[elt] = 1
  14.             finally:
  15.                 return d
  16.         return sorted([[v, k]for k, v in reduce(foo, list(data), {}).items()])
  17.  
  18.     # ハフマン木を生成
  19.     def generateHuffman(lst):
  20.         return reduce(lambda acc, elt: elt if acc == [] else [elt[0] + acc[0], [elt, acc]], lst, [])
  21.  
  22.     # 符号情報を作成
  23.     def codeInfo(n):
  24.         return sum([2 ** i for i in range(1, n + 1)])
  25.  
  26.     def value2code(tree):
  27.         def foo(x, y):
  28.             match y:
  29.                 case [parent, [left, []]]:
  30.                     return [parent, [left, x]]
  31.         acc = []
  32.         while True:
  33.             match tree:
  34.                 case [x, xs]:
  35.                     if isinstance(xs, str):
  36.                         return reduce(foo, acc, [1 + codeInfo(x - 1), xs])
  37.                     match xs:
  38.                         case [[m, left], [n, right]]:
  39.                             k = codeInfo(x)
  40.                             tree, acc = [x + 1, right], [[x, [[k, left], []]]] + acc
  41.  
  42.     def dfs(tree):
  43.         acc = []
  44.         while True:
  45.             match tree:
  46.                 case [a, [b, bs]]:
  47.                     match bs:
  48.                         case [x, xs]:
  49.                             if isinstance(xs, str):
  50.                                 lst = lambda: reversed([bs, b, *acc])
  51.                                 return {xs: x for x, xs in lst()}, dict(lst())
  52.                             tree, acc = bs, [b] + acc
  53.  
  54.     return dfs(value2code([0] + generateHuffman(countDatum())[1:]))
  55.  
  56. def compress(data):
  57.     compress_table, uncompress_table = createValue2Code(data)
  58.     return [compress_table[key] for key in data], uncompress_table
  59.  
  60. if __name__ == '__main__':
  61.     # Wikipedia での実行例に比べるとDとEが逆に思うかもしれんが気にしない事。
  62.     # Dの出現率とEの出現率は全く同じで、ソーティングアルゴリズムによっては
  63.     # 順序を取り替えたり、あるいは保持したり、する場合がある(安定ソートと不安定ソート)。
  64.     # どちらにせよ、「理論的には」同値の順序はどっちでもいい。
  65.     print(compress("DAEBCBACBBBC"))
  66.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
Traceback (most recent call last):
  File "/usr/lib/python3.9/py_compile.py", line 144, in compile
    code = loader.source_to_code(source_bytes, dfile or file,
  File "<frozen importlib._bootstrap_external>", line 918, in source_to_code
  File "<frozen importlib._bootstrap>", line 228, in _call_with_frames_removed
  File "./prog.py", line 28
    match y:
          ^
SyntaxError: invalid syntax

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python3.9/py_compile.py", line 150, in compile
    raise py_exc
py_compile.PyCompileError:   File "./prog.py", line 28
    match y:
          ^
SyntaxError: invalid syntax
stdout 
Standard output is empty
https://ideone.com/Skda1Z
language:
Python 3 (python  3.9.5)
created:
232 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!