雪ん子パースペクティヴ

読むとちょっとタメになるエントリー。コメントあると嬉しいです。

基本情報技術者試験のデータ構造及びアルゴリズム問題をPythonで実装する（平成三十一年度春期）。

python

ハフマン符号って普通ですか？

 

はろー、yukiです。

 

少し前にプログラミングに数学は必要かどうか、話題になったことがありました。

必要かどうかは、何を開発するかによるので、議論としては不毛ですかね。

どちらかというと、コードの保守がしっかりできるエンジニアの方が優れていると思います。

職業エンジニアとしては。

 

とはいっても、プログラミングに数学的考えがあると良いのは事実です。

それと、しっかりとデータ構造やアルゴリズムを知っておくのも良いと思います。

プログラミング以外の場でも、そういったことが時折役立つこともありますよね。

 

さて、今回の内容はハフマン符号について。

試験では、アルファベットA, B, C, Dの4種類の文字からなる文字列を圧縮します。

出現回数の多い文字時を短く、少ないものを長くビット列を割り当てます。

 

実装したコードは下記。

 

# H31春

text = "AAAABBCDCDDACCAAAAA"
# text = "ABBBBBBBCCCDD"

strList = []
freq = []

# To set values to array and sort ascending.
for i in text:
    strList.append(i)

sortedStrList = sorted(set(strList), key=strList.index)

# To count values.
for i, s in enumerate(sortedStrList):
    if s in text:
        # set count values.
        freq.append(text.count(s))

# Initialize
size = len(freq)
# To set -1 to all elements.
parent = [-1] * len(freq)
left = [-1] * len(freq)
right = [-1] * len(freq)
nsize = 0
node = []

def Huffman(size, parent, left, right, freq):
    
    i = 0
    j = 0

    SortNode(size, parent, freq)

    while nsize >= 2:
        i = node[0]
        j = node[1]
        left.append(i)
        right.append(j)
        freq.append(freq[i] + freq[j])

        # size become len + 1, so parent add one elem for SortNode().
        parent.append(-1)

        parent[i] = size
        parent[j] = size
        size = size + 1

        SortNode(size, parent, freq)

def SortNode(size, parent, freq):
    global nsize, node
    nsize = 0
    node = []

    for i in range(0, size):
        if parent[i] < 0:
            node.append(i)
            nsize = nsize + 1

    Sort(freq, nsize)

def Sort(freq, nsize):
    # node is global variable. The values store in SortNode().
    # and node type is tuple for unzip sortFreq.
    # If node is argument, node type is list.
    # This case is NOT be used values after unzip sortFreq.
    global node

    sortFreq = []

    # The array is elem's number and value. Ascending order by value.
    # freq has values of A-D and node has number(order).
    for i in node:
        # ex.) ('A', 0), ('A', 1), ('A', 2)...('B', 4)...('D', 7)...
        sortFreq.append((freq[i], i))
    
    sortFreq.sort()

    # unzip
    sortedFreq, node = zip(*sortFreq)

def Encode(k, parent, left):
    global param
    if parent[k] >= 0:
        Encode(parent[k], parent, left)

        if left[parent[k]] == k:
            # print("0")
            param = param + '0'

        else:
            # print("1")
            param = param + '1'


Huffman(size, parent, left, right, freq)

# Result
resultBit = []

for k in range(len(sortedStrList)):
    param = ''
    Encode(k, parent, left)
    resultBit.append(param)

resultList = list(zip(sortedStrList, resultBit))
print(resultList)

 

変数textに与えている文字列は二通り。

「AAAABBCDCDDACCAAAAA」と「ABBBBBBBCCCDD」です。

前者は順番に、A -> C -> D -> Bとなります。

後者は順番に、B -> C -> D -> Aとなります。

よって、

前者は、[('A', '1'), ('B', '010'), ('C', '00'), ('D', '011')]が出力結果となります。

後者は、[('A', '010'), ('B', '1'), ('C', '00'), ('D', '011')]が出力結果となります。

仕組み自体は試験問題の図2を見ると分かると思います。

 

 

 

以上

 

 

 

Googleアドセンス