Pythonの技法:Huffman符号化の実装

文:Nick Gibson(Builder AU)  翻訳校正:原井彰弘
2008-01-08 19:13:01
  • このエントリーをはてなブックマークに追加

 ここでは、itertoolsモジュールで提供されているgroupby関数を用いて最初の重みを計算し、その上でheapq優先順位付きキューを用いてノードの順位付けを行っている。なお、このプログラムでは元データの文字列はinputと呼ぶことにする。

from itertools import groupby
from heapq import *

itemqueue =  [Node(a,len(list(b))) for a,b in groupby(sorted(input))]
heapify(itemqueue)
while len(itemqueue) > 1:
l = heappop(itemqueue)
r = heappop(itemqueue)
n = Node(None, r.weight+l.weight)
n.setChildren(l,r)
heappush(itemqueue, n)

 このステップが終わると、itemqueueはツリーのルートノードとなる要素一つのみを保持しているはずである。

 次にすべきことは、ツリーをたどって各アイテムの符号を調べることである。ここでは、それぞれの文字に対してツリーを最初からたどることはせず、ツリーすべてを一度で巡回し、その結果をディクショナリに格納している。

codes = {}

def codeIt(s, node):
if node.item:
if not s:
codes[node.item] = "0"
else:
codes[node.item] = s
else:
codeIt(s+"0", node.left)
codeIt(s+"1", node.right)

codeIt("",itemqueue[0])

 この例では、再帰関数を利用することによって、符号を積み重ねながら各節の枝をたどっている。

 さて、上に例としてあげた2つのコードの断片をhuffmanという関数で統合すると、以下のようなコードで関連情報を返すことが可能になる。

def huffman(input):
# above code 

return codes, "".join([codes[a] for a in input])

 これですべて完了だ。この関数は、アイテムから符号へのディクショナリ(逆にすると復号化に使用できる)、および符号化した文字列を返す。それでは、例を用いて以下のように試してみよう。

  • コメント(1件)
#1 shapes   2013-04-04 16:54:33
Pythonはインデントを厳密に見る言語なので、
HTMLで表示するときにインデントが崩れていると
どこまでがスコープなのかがはっきりしません。
このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]