LoginSignup
0
2

More than 3 years have passed since last update.

@ereyester

【高等学校情報科 情報Ⅰ】教員研修用教材：ハフマン法についてのpythonによる実装

Last updated at Posted at 2020-07-19

はじめに

高等学校では学習指導要領の改訂が行われ、科目「情報」でも大きな変更がありました。
一番の大きな変更は高等学校からプログラミングを学ぼうという内容となります。
これに関して文部科学省のほうで教員研修用教材が無料で公開されております。
本記事では今後の高等学校で学ぶプログラミングに関連して補足情報を書いていきたいと思います。

先人エンジニア方々によって様々な記事が既に書かれておりますので、以下のリンクなどをご確認ください。
2020年次期学習指導要領 教科「情報」を紐解く
文科省のPythonはPythonじゃねぇ
教科「情報」の専任教員と将来の夢「ITエンジニア・プログラマー」の現状

教材

高等学校情報科「情報Ⅰ」教員研修用教材（本編）：文部科学省
第2章コミュニケーションと情報デザイン （PDF:6892KB） PDF

環境

新指導要領では、「情報Ⅰ」で主にプログラミング、「情報Ⅱ」で主にデータサイエンスの分野が追加されております。
それを考慮してかpythonによるコードによる説明が多いので、本記事もpythonを使用します。
また、環境構築が楽なGoogle Colabを使用を前提としております。

概要

今回使用する取り上げるのは、「情報Ⅰ」教員研修用教材の「第2章コミュニケーションと情報デザイン」について、
情報Ⅰの暗黙の方針に則って、pythonでプログラミングする上で、教材に書かれていない要素について確認して補足します。
具体的には、教材「第2章コミュニケーションと情報デザイン」のp61-63の

（９）ファイルの圧縮-ハフマン法

のところを確認すると、ハフマン法のアルゴリズムの説明が載っていますが、肝心のプログラミングコードが載っていません。
そこで、pythonコードの実装したいと思います。

その他参考文献等

Python3でハフマン符号化
Pythonでハフマン符号化を実装してみた
ハフマン符号 - Wikipedia

ハフマン法(文字列：intelligenceについて)

手順１

解説

文字を出現回数順に並べる

実装

pythonの辞書型を使用して、出現回数順に並べてみます。


from collections import Counter
target_string = 'intelligence'

print('{0}の文字の出現回数を調べます' .format(target_string))
list_target_string = list(target_string)
counter_target_string = Counter(target_string)
dict_target_string = dict(counter_target_string)
print(dict_target_string)

出力結果

intelligenceの文字の出現回数を調べます
{'i': 2, 'n': 2, 't': 1, 'e': 3, 'l': 2, 'g': 1, 'c': 1}

手順２

解説

出現回数の少ない2つの文字をつなげ、その上に出現回数の合計を書く。
選んだ文字はすでに合計に加算したためそれ以外の５つの文字と②の文字出現回数の合計の中から出現回数の少ない２つの文字を選び合計を記入し、同じ手順で全ての文字がつながり、合計がintelligence(12)になるまで続ける。

実装

class Node:
    def __init__(self, key_char=None, count=None, left=None, right=None):
        self.key_char = key_char
        self.left = left
        self.right = right
        self.count = count

nodes = []

for k, v in dict_target_string.items():
    node_obj = Node(key_char = k, count = v)
    nodes.append(node_obj)

trial_count = 0
while len(nodes) >= 2:
    #nodesを降順に並び替え
    nodes = sorted(nodes, key=lambda x: x.count, reverse=True)

    #枝作成回数
    trial_count += 1

    #nodesのうち出現回数が１番目に小さいものを取り出す
    left = nodes.pop()
    #nodesのうち出現回数２番目に小さいものを取り出す
    right = nodes.pop()

    #leftとrightの出現回数を足したものをnodesに追加
    count = left.count + right.count
    append_node = Node(key_char = left.key_char + right.key_char, count = count, left = left, right = right)
    nodes.append(append_node)

    print("施行回数:", trial_count)
    print(left.key_char, right.key_char,  count)
    print("---------------")

出力結果

施行回数: 1
c g 2
---------------
施行回数: 2
t cg 3
---------------
施行回数: 3
l n 4
---------------
施行回数: 4
i tcg 5
---------------
施行回数: 5
e ln 7
---------------
施行回数: 6
itcg eln 12
---------------

手順３

解説

繋ぎ合わせた全ての部分の左に0を、右に１を入れていく。
繋ぎ合わせた部分に入れた0と1を上から拾っていき、それぞれの文字に圧縮したビット列を割り当てる。

実装

#圧縮結果を取得する
def recursive_code(node, s, temp_encode_dict):
    if len(node.key_char) == 1:
        temp_encode_dict[node.key_char] = s
        return
    recursive_code(node.left, s + "0", temp_encode_dict)
    recursive_code(node.right, s + "1", temp_encode_dict)

encode_dict = {}
tree = nodes[0]
recursive_code(tree, "", encode_dict)
print(encode_dict)

出力結果

{'i': '00', 't': '010', 'c': '0110', 'g': '0111', 'e': '10', 'l': '110', 'n': '111'}

圧縮率

解説

作成したハフマン符号を用いて「intelligence」を圧縮したビット列で表すと，に 33 ビットとなる
「intelligence」の１文字を 3 ビットで表していた場合は 36 ビットだったので，約 92% に圧縮されたことになる。

実装

print(target_string,'の圧縮率比較')
bitlength = len(str(bin(len(dict_target_string) - 1))) - 2
before_size = target_len * bitlength
print('圧縮前のサイズ')
print(target_len,'*',bitlength ,'=', before_size, 'bits')

encode_bits_string = ''
for v in list_target_string:
    encode_bits_string += encode_dict[v]
print('圧縮後のビット列')
print(encode_bits_string)
print('圧縮後のサイズ')
print(len(encode_bits_string),'bits')

出力結果

intelligence の圧縮率比較
圧縮前のサイズ
12 * 3 = 36 bits
圧縮後のビット列
001110101011011000011110111011010
圧縮後のサイズ
33 bits

教材との実装結果の比較・修正

教材の解説は以下のようになります。

SnapCrab_NoName_2020-7-19_19-52-2_No-00.png
SnapCrab_NoName_2020-7-19_19-57-8_No-00.png

こちらで実装した出力結果と比べてみます。

intelligenceの文字の出現回数を調べます
{'i': 2, 'n': 2, 't': 1, 'e': 3, 'l': 2, 'g': 1, 'c': 1}

{'i': '00', 't': '010', 'c': '0110', 'g': '0111', 'e': '10', 'l': '110', 'n': '111'}

・・・あれ？
出力結果が違います。
枝の生成方法と枝の左右への振り分け方が、実装を無視してロジックだけを説明している内容になっているので、これでは教材の通りの結果にはならなりません。
以下の点に注意する必要があります。

  • 文字列に対して出現回数ごとに並べる際は、安定なソートで並べる必要がある。
  • 出現回数の少ないものを2つ選択するが、できる限りアルファベットが同じ数になるようなものを選択する。（1個目のアルファベットの連結文字数と同じものを優先して２個目とする）
  • 枝の左右への指定の仕方は、連結されたアルファベットの結合数が少ないほうが左に割り当てそうでないものを右に割り当て、そうでない場合は１個目に取得したものを右、２個目に取得したものを左とする。

したがって、この条件に従って実装します。

手順２’

実装


class Node:
    def __init__(self, key_char=None, count=None, left=None, right=None):
        self.key_char = key_char
        self.left = left
        self.right = right
        self.count = count

nodes = []
encode_dict = {}

for k, v in dict_target_string.items():
    node_obj = Node(key_char = k, count = v)
    nodes.append(node_obj)

trial_count = 0
while len(nodes) >= 2:
    #nodesを降順に並び替え
    nodes = sorted(nodes, key=lambda x: x.count, reverse=True)

    #枝作成回数
    trial_count += 1

    #nodesのうち出現回数が１番目に小さいものを取り出す
    first = nodes.pop()
    #nodesのうち出現回数２番目に小さいものを取り出す
    second = nodes.pop()

    #temp_nodes
    temp_nodes = []

    #firstとsecondのアルファベット結合数が同じかどうか判定する
    if (len(first.key_char) != len(second.key_char)):
        print('firstとsecondのアルファベット結合数が違う')

        #nodesがまだ１個以上はいっているとき、３個目以降を取得する
        while len(nodes) >= 1:
            overthird = nodes.pop()
            if (second.count == overthird.count):
                print('secondとoverthirdの出現回数が一致している')
                if (len(first.key_char) == len(overthird.key_char)):
                    print('firstとoverthirdのアルファベット結合数が一致している')
                    nodes.append(second)
                    second = overthird
                    break
                else:
                  temp_nodes.append(overthird)
            else:
                nodes.append(overthird)
                break

    #popしたものを戻す
    nodes += temp_nodes

    #firstとsecondの出現回数を足したものをnodesに追加
    count = first.count + second.count

    print("施行回数:", trial_count)

    if len(first.key_char) < len(second.key_char): 
        append_node = Node(key_char = first.key_char + second.key_char, count = count, left = first, right = second)
    else:
        append_node = Node(key_char = second.key_char + first.key_char, count = count, left = second, right = first) 

    print(append_node.left.key_char, append_node.right.key_char,  count)

    nodes.insert(0, append_node)
    print("---------------")

無駄に冗長な処理になりました。一気にクソコードに

出力結果

施行回数: 1
g c 2
---------------
施行回数: 2
l t 3
---------------
施行回数: 3
i n 4
---------------
firstとsecondのアルファベット結合数が違う
secondとoverthirdの出現回数が一致している
firstとoverthirdのアルファベット結合数が一致している
施行回数: 4
lt gc 5
---------------
firstとsecondのアルファベット結合数が違う
施行回数: 5
e in 7
---------------
firstとsecondのアルファベット結合数が違う
施行回数: 6
ein ltgc 12
---------------

修正結果

再び手順３を実行した結果

{'e': '00', 'i': '010', 'n': '011', 'l': '100', 't': '101', 'g': '110', 'c': '111'}

となり、教材の説明と一応一致しました。
ちなみに、圧縮率を比較すると、

intelligence の圧縮率比較
圧縮前のサイズ
12 * 3 = 36 bits
圧縮後のビット列
010011101001001000101100001111100
圧縮後のサイズ
33 bits

ソースコード

0
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
2