基本情報技術者アルゴリズムの問題をPythonでコーディングしてみた【平成31年春】

前回からアルゴリズム過去問のコーディングをやっておりまして
私のレベルでコーディングが一日でできるわけがなく
以前のように毎日記事をアップすることができなくなりました。
これからはのんびりペースです。

さて、今回はハフマン符号化を用いた文字列圧縮のプログラムです。

過去問PDF「出典：平成31年度 春期 基本情報技術者試験 午後 問8」

プログラム1&2

import collections
#符号化する文字列を設定
Text = "AAAABBCDCDDACCAAAAA" #過去問の文字列
#Text = "ABBBBBBBCCCDD"　#設問1確認用

#出現回数をもとめる①
count_dic=collections.Counter(Text)
character = list(count_dic.keys())
freq =list(count_dic.values())
character_num = len(freq) #

#初期化②
parent=[-1]*len(freq)
left = [-1]*len(freq)
right = [-1]*len(freq)
node = list()
size = len(freq)
nsize = 0

#副プログラム：Huffman
def huffman():
    global size,parent,left,right,freq
    
    sort_node()
    while nsize >= 2:
        i = node[0] #最も小さい値をもつ要素組の要素番号
        j = node[1] #二番目に小さい値をもつ要素組の要素番号
        left.append(i)
        right.append(j)
        freq.append(freq[i] + freq[j]) #子の値の合計
        parent.append(-1)
        parent[i] = size #子に親の節の要素番号を格納
        parent[j] = size #子に親の節の要素番号を格納
        size = size + 1
        sort_node()

#副プログラム：SortNode
def sort_node():
    
    global nsize,node
    #初期化
    nsize = 0 
    node = list()
    
    for i in range(0,size):
        if parent[i] < 0 : #親がまだいない場合
            node.append(i)
            nsize = nsize + 1
    sort()

#副プログラムSort③
def sort():

    global node
    freq_node = []
    #nodeに対応する要素番号の要素だけを抽出し、同時ソートのための新リスト作成
    for i in node:
        freq_node.append((freq[i],i))
    freq_node.sort()
    #分解して別々のリストに戻す
    sfreq,node = zip(*freq_node)

#副プログラムencode
def encode(k,parent,left):
    global b  
    if parent[k] >= 0:
        encode(parent[k],parent,left)
        if left[parent[k]] == k:
            b = b + "0" #④
        else:
            b = b + "1" #④
#実行
            
huffman()

#ハフマン符号化結果を表示⑤
bit_list=[]
for k in range(0,character_num):
    b = ""
    encode(k,parent,left)
    bit_list.append(b)

bit_dic = {key:val for key,val in zip(character,bit_list)}
print(bit_dic)

出力結果

{'A': '1', 'B': '010', 'C': '00', 'D': '011'}

過去問との主な相違点は下記
①文字の出現回数を求めるコードを追加
②各リストを初期化するコードを追加
③副プログラムSortを追加
④副プログラムencodeのprint出力部分を変数に格納する仕様に変更
⑤結果の表示形式を辞書式（文字：ハフマン符号）に変更

何気に副プログラムSortに苦労しました。
問題文では省略してあり、ヒントが乏しかったうえ、
プログラムの説明文の
”節を表す要素組の要素番号の配列nodeを受けとり、要素番号に対応する要素組が表す節の値が昇順になるように整列する。”
という説明の意味が分かりにくくて…。

にしてもこれ、最初に考えた人天才。

今回は以上です。
もっとこうすればいいのに、といったご意見ご指摘ありましたら教えてくださるとうれしいです！！

それではまた^^