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

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

>>> from huffman import *
>>> input = "aababcabcd"
>>> huffman(input)
({'a': '0', 'c': '111', 'b': '10', 'd': '110'}, '0010010111010111110')
>>> len(input) * 8, len(huffman(input)[1])
(80, 19)
>>> input = "the quick brown fox jumps over the lazy dog" 
>>> huffman(input)
({' ': '00', 'a': '10000', 'c': '10011', 'b': '110000', 'e': '1010', 'd': '111111', 'g': '110111', 'f': '01001', 'i': '110101', 'h': '11110', 'k': '110011', 'j': '111110', 'm': '110001', 'l': '110010', 'o': '1011', 'n': '01000', 'q': '10010', 'p': '110110', 's': '110100', 'r': '11101', 'u': '0101', 't': '11100', 'w': '01111', 'v': '10001', 'y': '01100', 'x': '01110', 'z': '01101'}, '111001111010100010010010111010110011110011001100001110110110111101000000100110110111000111110010111000111011011010000101110001101011101001110011110101000110010100000110101100001111111011110111')
>>> len(input) * 8, len(huffman(input)[1])
(344, 192)
>>> import urllib
>>> input = urllib.urlopen("http://docs.python.org/lib/front.html").read()
>>> len(input) * 8, len(huffman(input)[1])
(57808, 36340)
>>> input = file("wrnpc12.txt").read()
>>> len(input) * 8, len(huffman(input)[1])
(26281320, 14962010)

 最初の2つの例は、入力文字列の文字が少ないほど、圧縮がよく働くことを示している。また、最後の2つの例では、より大きな元データを用いてテストを行っている。1つ目はPythonのドキュメントのウェブサイトであり、句読点を含む多数の文字が含まれている。また、2つ目は「War and Peace」のテキスト全体で、Huffman符号化を用いた結果、文字列のサイズが半分になっている。

 Huffman符号化は圧縮に対するもう一つのアプローチだ。繰り返し出現するパターンに対して何かを行うのではなく、文字集合のサイズを限定することで圧縮を成し遂げるのである。そのため、元データに多種多様な文字が含まれている場合は、Huffman符号化によって得られるメリットは大きく減少してしまうだろう。

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