ハフマン符号化(完)
ハフマン符号化できた
前に断念していた、ハフマン符号化 - なんというていたらくが完成。
まぁ、これは明日提出の講義の宿題なんだけどもｗ
別に言語はなんでもよかったんだけど、Pythonの練習がてら書いてみた。
少しだけどPythonさんとの距離が縮まった気がする。
課題
適当なテキストファイル（事象数25個以上、データ量500事象以上程度）をハフマン符号化し、固定長符号による符号化と比較した圧縮率を求めよ。
今回はOfficial Google Blog: New search ad formatsから文章のみコピペして、
全て大文字に置換 && 改行、スペース、コンマ、ピリオドを除いてハフマン符号化してみた。
圧縮まではできてません。
時間あればやってみたい。
回答ソース
# coding: UTF-8 # Python --version: 2.6.5 # from heapq import * from math import * import re class Node: def __init__(self, code, count = 0, left = None, right = None): self.code = code self.count = count self.left = left self.right = right def __cmp__(x, y): return x.count - y.count #ハフマン木を作成 def make_tree(sym_table): q = [] #ヒープ for x in sym_table: if x.count > 0: heappush(q, x) while True: n1 = heappop(q) if len(q) == 0: if n1.code is not None: #奇数だった場合 for x in sym_table: if x.count == 0: return Node(None, 0, n1, x) return n1 n2 = heappop(q) heappush(q, (Node(None, n1.count + n2.count, n1, n2))) #符号化 def make_code(s, node): if node.code: if not s: codes[node.code] = "0" else: codes[node.code] = s else: make_code(s+"0", node.left) make_code(s+"1", node.right) #ハフマン符号化 def huffman(words, wordsCount): #ノードを生成 sym_table = [Node(c, n) for (c, n) in wordsCount.items()] root = make_tree(sym_table) make_code("", root) print wordsCount print codes #ハフマン符号長 huffmanLen = 0 for (x, y) in codes.items(): huffmanLen += wordsCount[x]*len(y) print "%s: %f %s" % (u"ハフマン符号化", float(huffmanLen), "bit") #固定符号長 fixedLen = (ceil(log(len(wordsCount),2)))*len(words) print "%s: %f %s" % (u"固定長符号化", float(fixedLen), "bit") #圧縮率 print "------------------------------------------------" print "%s: %f %s" % (u"圧縮率", float(huffmanLen)/float(fixedLen)*100, "%") #ファイルを開いて文字列を分解 f = open("googleBlog.txt", 'r') filter = re.compile(r'[\s*\,\.]') text = filter.sub("", f.read().upper()) print text words =[] for x in text: words.append(x) #単語の出現回数をカウントしソート wordsCount = {} for word in words: if word in wordsCount: wordsCount[word] += 1 else: wordsCount[word] = 1 codes = {} huffman(words, wordsCount)
こんな感じ？
まだまだ無駄な書き方がいっぱいで萎える。
きれいに書けるようになりたいなー
