--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

2007/07/09

[今日のスクリプト] 似非ハフマン符号化

基本情報の参考書を眺めてたらあったのでやってみた。が、書いてみた後でハフマンの例文にふさわしい文を探すべくハフマンで検索してみたところ、参考書に載ってたやつと符号の割り振りかたが微妙に違う。

今回作ったのは参考書で紹介されていたもので、出現回数の多い順に、0、10、110、と1を1つずつ増やしていっている。

 1 #!/usr/bin/python
 2 #coding:utf-8
 3 
 4 # 暗号化する関数
 5 def to_sign(val):
 6     chrlist = mksortedchrlist(val)
 7     signs = {chrlist[0]:"0"}
 8     for i in range(1, len(chrlist)):
 9         signs[chrlist[i]] = "1" + signs[chrlist[i - 1]]
10     result = ""
11     for c in val:
12         result = result + signs[c]
13     print result
14     return (result, chrlist)
15 
16 # 文字列から文字の出現回数の昇順のリストを生成する関数
17 def mksortedchrlist(val):
18     dict = {}
19     get = dict.get
20     for c in val:
21         dict[c] = get(c, 0) + 1
22     result = []
23     for k in dict.iterkeys():
24         if len(result) == 0:
25             result.append(k)
26         else:
27             i = 0
28             while i < len(result):
29                 if get(k) >= get(result[i]):
30                     result.insert(i, k)
31                     break
32                 elif i == len(result) - 1:
33                     result.append(k)
34                     break
35                 i += 1
36     return tuple(result)
37 
38 # 復号化関数
39 def decode(signs):
40     i = 0
41     result = ""
42     sign = signs[0]
43     chrlist = signs[1]
44     while i < len(sign):
45         cnt = 0
46         while sign[i] != "0":
47             i += 1
48             cnt += 1
49         result = result + chrlist[cnt]
50         i += 1
51     print result
52 
53 def main():
54     base = "tokyotokkyokyokakyoku"
55     print "前:",len(base) * 8
56     signs = to_sign(base)
57     print "後:",len(signs[0])
58     decode(signs)
59 
60 if __name__ == "__main__":
61     main()

結果

前: 168
11101001101011101000110100110100111110011010011110
後: 50
tokyotokkyokyokakyoku

最初に出力されているのが元のサイズ。文字数 * 8 で求めている(ASCIIは1文字8ビットであるため)。2行目は符号化した文字列。3行目は符号化した後のサイズ。4行目は符号化したものから元の文字列に戻したもの。

  • 今度からはもうちょっと使い道のあるスクリプト書くようにしようかなぁ。
  • 最近またちょっとみんpyを見直してみたりしている。読み飛ばしていた標準モジュールのところは今一番知りたいところの1つ。後、クラスの特殊メソッドは今非常に面白いと感じている。Python がどのようにオブジェクト指向言語として実現されたかが伺える部分だと思う。
  • 最近仕事が忙しく、GoogleReaderで購読しているRSSフィードもかなり溜っている。はず。常時100+は当たり前。100+のフォルダが4,5個ある状況。
スポンサーサイト

comment

post




上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。