python自習テキスト

wikiで書き始めた。

http://giraffe.topaz.ne.jp/wiki/doku.php/py:python_curriculum

pythonでハフマン符号化

データの出力頻度をもとに、一つずつのデータを可変長にエンコードする。
適当なファイルを filename 変数に入れて実行すると、いろいろ出力が変わる。
ハフマン符号の正規化とかいう処理はしていないので、ツリーの散らばり具合はいいかげん。

出力例は、"The Brothers Karamazov" の全テキストを突っ込んでみたときのもの。
この手法を素直に使うだけでは、そんなに高い効率の圧縮にはならないということかな。

# -*- coding:cp932 -*-

filename = r'any_file.txt'

# 出現頻度取得
freq = dict()
for line in open(filename, 'rb'):
  for c in line:
    freq.setdefault(c, 0)
    freq[c] += 1

# 頻度が少ないものから順に枝をまとめてツリー形成
wtree = [i for i in freq.iteritems()]
while len(wtree) > 1:
  # 出現頻度ワースト2の枝を見つけてまとめる
  wtree.sort(lambda a,b: cmp(b[1], a[1]))
  b2, b1 = (wtree.pop(), wtree.pop())
  wtree.append(((b1[0], b2[0]), b1[1] + b2[1]))

tree = wtree[0][0]
print "frequency tree:"
print tree
orig_bits = wtree[0][1] * 8

# ツリーをもとに変換表生成
def collapse_tree(t, leaf, prefix):
  if type(leaf) == tuple:
    c = 0
    for i in leaf:
      collapse_tree(t, i, prefix + (c,))
      c += 1
  else:
    t.append((leaf, prefix))

e_table = []
collapse_tree(e_table, tree, ())

# 変換表印字
compressed_bits = 0
print "encoding table:"
for i in e_table:
  print "".join([str(j) for j in i[1]]), (i[0], freq[i[0]])
  compressed_bits += freq[i[0]] * len(i[1])

print "data can be compressed from %d bits into %d bits (%f%%)" % \
  (orig_bits, compressed_bits, float(compressed_bits) / orig_bits)

出力例：

frequency tree:
(((' ', (('s', (('.', ('I', (((('z', 'L'), 'G'), '!'), (('P', 'q'), ((('E', ('V'
, ('U', (('4', '0'), ('3', '5'))))), 'C'), ';'))))), ('p', 'b'))), ('r', ('m', '
y')))), (('t', ((('v', ("'", (('-', 'x'), 'A'))), 'w'), 'd')), ((('\n', '\r'), (
'c', ',')), ('l', ('f', 'g'))))), ((('o', 'a'), ('n', (((((('S', 'M'), (('K', ('
R', ':')), 'W')), ('T', (('D', ((('Z', 'J'), ')'), ('(', (('*', (('8', '7'), 'Q'
)), (('2', (('X', '9'), '6')), '1'))))), 'B'))), 'k'), ('"', (((('O', 'N'), 'F')
, 'H'), ('?', ('j', 'Y'))))), 'u'))), (('h', 'i'), 'e')))
encoding table:
000 (' ', 349903)
00100 ('s', 87812)
0010100 ('.', 22205)
00101010 ('I', 10989)
001010110000 ('z', 730)
001010110001 ('L', 675)
00101011001 ('G', 1352)
0010101101 ('!', 2687)
00101011100 ('P', 1293)
00101011101 ('q', 1279)
0010101111000 ('E', 339)
00101011110010 ('V', 165)
001010111100110 ('U', 69)
00101011110011100 ('4', 17)
00101011110011101 ('0', 16)
00101011110011110 ('3', 16)
00101011110011111 ('5', 15)
001010111101 ('C', 592)
00101011111 (';', 1171)
0010110 ('p', 20938)
0010111 ('b', 19549)
00110 ('r', 78044)
001110 ('m', 38521)
001111 ('y', 37053)
0100 ('t', 133524)
0101000 ('v', 18431)
01010010 ("'", 9357)
0101001100 ('-', 2399)
0101001101 ('x', 2172)
010100111 ('A', 4190)
010101 ('w', 32169)
01011 ('d', 64044)
011000 ('\n', 32018)
011001 ('\r', 32018)
011010 ('c', 31099)
011011 (',', 30341)
01110 ('l', 60812)
011110 ('f', 30287)
011111 ('g', 27884)
1000 ('o', 117883)
1001 ('a', 117275)
1010 ('n', 99433)
1011000000 ('S', 2028)
1011000001 ('M', 2019)
10110000100 ('K', 1027)
101100001010 ('R', 517)
101100001011 (':', 474)
1011000011 ('W', 1918)
101100010 ('T', 3586)
10110001100 ('D', 972)
10110001101000 ('Z', 132)
10110001101001 ('J', 119)
1011000110101 (')', 219)
1011000110110 ('(', 219)
101100011011100 ('*', 62)
10110001101110100 ('8', 13)
10110001101110101 ('7', 12)
1011000110111011 ('Q', 23)
1011000110111100 ('2', 21)
101100011011110100 ('X', 6)
101100011011110101 ('9', 5)
10110001101111011 ('6', 10)
101100011011111 ('1', 36)
1011000111 ('B', 1725)
1011001 ('k', 12741)
1011010 ('"', 12521)
10110110000 ('O', 861)
10110110001 ('N', 785)
1011011001 ('F', 1605)
101101101 ('H', 3190)
101101110 ('?', 3114)
1011011110 ('j', 1449)
1011011111 ('Y', 1415)
10111 ('u', 45643)
1100 ('h', 94800)
1101 ('i', 92948)
111 ('e', 177161)
data can be compressed from 15873136 bits into 9016123 bits (0.568011%)

pythonで加重ランダム

何かをランダムに出現させたいが、値によって出現率が異なるようにしたい。

bisectモジュールをうまくつかうといいみたい。見つけた元ネタ：
http://code.activestate.com/recipes/576370/

bisectは、ソート済みのリストについて頭出しができるモジュール。

(いろいろテスト)
>>> import bisect
>>> scale = [10, 20, 30, 40, 50]   # ソート済みのリストを使うこと
>>> bisect.bisect(scale, 15)    # 15はどこに位置する?
1
(これはスライス範囲を指定するときの場所。つまり10と20の間ってこと)
>>> bisect.bisect(scale, 46)    # 46は?
4
(この場合は、40と50の間ってこと)

>>> scale = ['a', 'j', 'z']  # 数字以外でも使えるのかな
>>> bisect.bisect(scale, 'q')
2
(できそうですね)

元ネタのコードには何も付け加える余地がないからここでは動作原理のみ書くと、間の空き具合がまちまちな数のリストを準備しておいて、それに乱数を使ってbisect探索するということ。random関数が0.0から1.0の乱数を出すから、値の範囲も0.0から1.0で作ると相性がよい。

下のようなスケールがあるとして、

0.0   0.1           0.3                            1.0
 |-----+-------------+------------------------------|
  範囲A     範囲B                  範囲C

で、ランダム値にこのスケールをあてはめれば、範囲Cが選ばれる確率は70%くらいで、範囲Aは大体10%くらいしか出現しないことになる。

実証したコード：

>>> import bisect
>>> import random
>>> scale, items = [0.1, 0.3, 1.0], ['A', 'B', 'C']
>>> [items[bisect.bisect(scale, random.random())] for i in xrange(100)]
['C', 'C', 'C', 'A', 'B', 'C', 'A', 'A', 'C', 'C', 'C', 'C', 'C', 'B', 'C', 'B',
 'B', 'C', 'C', 'C', 'A', 'C', 'C', 'C', 'C', 'C', 'C', 'B', 'C', 'B', 'C', 'B',
 'B', 'C', 'C', 'C', 'B', 'B', 'B', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C',
 'B', 'C', 'B', 'C', 'A', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'C', 'A', 'B',
 'B', 'C', 'C', 'B', 'C', 'A', 'C', 'A', 'C', 'B', 'C', 'C', 'C', 'C', 'C', 'B',
 'C', 'C', 'C', 'A', 'C', 'C', 'C', 'B', 'C', 'B', 'C', 'A', 'B', 'A', 'B', 'C',
 'B', 'C', 'C', 'C']

Cの出現率が多くて、Aがレア。なるほどねー

pythonでタートルグラフィック

Tkinterモジュールのオマケ?にタートルグラフィックのライブラリがあって、多分一番手っ取り早くCGっぽいことを始められる。

下のスクリプトを適当なファイル名で保存してから実行すると、ペンでグリグリ落書きしているかのようなデモが走る。

from turtle import *
import random

speed('fast')

while True:
  for i in xrange(1000):
     down()
     forward(3)
     up()
     forward(2)
     right(random.randint(-3,10))
  reset()

また、コンソールから、

>>> import turtle
>>> turtle.demo()

とか

>>> import turtle
>>> turtle.demo2()

とかすると、出来あいのデモが見られたりする。

MS-Accessでリンクテーブルを張替え(VBA)

pythonで書きたくても、VBAなんかを書かなくちゃいけないときもある。一応成果メモ。

MS-Accessで、データ自体はどこかの共有フォルダ内のmdbファイルに置いておいて、それを各クライアントがリンクテーブルとして使う、という運用はよくあるパターン。

で、クライアントを新しく配置するごとに、リンクテーブルをちまちま張りなおすのは面倒だなあ、ということで、モジュール化した。refresh_link_tables というサブルーチンを呼ぶと、ネットワークフォルダにドライブ名を振って、リンクテーブルの定義を消して、あたらしくリンクを作り直している。

Function exists_table(ByVal name As String)
    On Error Resume Next
    exists_table = CurrentDb.TableDefs(name).name = name
End Function

Sub connect_net_drive()
    Dim oShell As Object
    Set oShell = CreateObject("WScript.Shell")
    '環境にあわせて適宜変える。最後のTrueは同期実行のしるし
    oShell.Run "NET USE Q: \\some_server\shared_folder passwd1 /USER:user1", , True
    Set oShell = Nothing
End Sub

Public Sub refresh_link_tables()
    Call connect_net_drive
    tt = Array("master", "master2", "journal1", ...... )  'リンクするテーブルをいくつでも
    For Each table_name In tt
        If exists_table(table_name) Then
            CurrentDb.TableDefs.Delete (table_name)
        End If
        Set tdef = CurrentDb.CreateTableDef(table_name)
        tdef.Connect = ";database=Q:\sample\shared_db.mdb"  '環境にあわせて書き換え
        tdef.SourceTableName = table_name
        CurrentDb.TableDefs.Append (tdef)
    Next
End Sub

補足：WScript.Shell オブジェクトを作ってNTコマンドを外部で実行するというのがなんだか格好悪いと思うなら、WScript.Network オブジェクトの MapNetworkDrive メソッドを使っても似たことができる。まあ、やりたいことが実現するのならなんでもいいや。

pythonでキャッシュサーバーを叩く

WebサーバーにExcelシートなんかを置いて、ダウンロードさせる場合があるとする。ダウンロード経路にsquidとかのキャッシュサーバーがある場合、こいつが旧バージョンのドキュメントをしばらく確保して、なかなか新バージョンが配布できない。HTMLファイルなどだったら[F5]キーで明示的にキャッシュを再取得すればいいんだけど、Excelじゃできない。

キャッシュを回避するためにファイル名を明示的に変えて置いておくという方法があるにはあるが、なんだかムキになってキャッシュ破棄にこだわりたくなった。つまり Pragma:no-cache とかそんなヘッダを投げつければいいんでしょ。結果、下のようなスクリプトを書いた。Tkinter版。print文でデバッグ情報を出力するので、標準出力をどっかに表示できること。

スクリプト中の cache_server 変数には、あらかじめ自分の環境のプロキシサーバーとポート番号を設定する。

# -*- coding: cp932 -*-

import Tkinter as tk
import httplib, urllib

cache_server = "192.168.1.100:3128"  #configure yourself

def clear_cache(url):
    print url
    headers = {"Pragma": "no-cache", }
    conn = httplib.HTTPConnection(cache_server)
    conn.request("GET", url, "", headers)
    response = conn.getresponse()
    print response.status, response.reason
    print response.getheaders()
    conn.close()
    return "%s %s" % (response.status, response.reason)

class CacheRefresherFrame(tk.Frame):

    def __init__(self, parent, **kwag):
        tk.Frame.__init__(self, parent, **kwag)
        self.s1 = tk.StringVar()
        self.s2 = tk.StringVar()
        self.t1 = tk.Entry(self, width=100, textvariable=self.s2)
        self.b1 = tk.Button(self, text='refresh cash', command=self.do_hello)
        self.l1 = tk.Label(self, textvariable=self.s1)
        self.t1.pack()
        self.b1.pack()
        self.l1.pack()
        self.s1.set('ready')
        self.t1.focus()

    def do_hello(self):
        self.t1.configure(state=tk.DISABLED)
        self.b1.configure(state=tk.DISABLED)
        url = self.s2.get()
        self.s1.set('processing %s ...' % url)
        self.update()
        try:
            self.s1.set(clear_cache(url))
        finally:
            self.t1.configure(state=tk.NORMAL)
            self.b1.configure(state=tk.NORMAL)


root = tk.Tk()
root.title(u'キャッシュサーバーにキャッシュ破棄を指示するスクリプト')
CacheRefresherFrame(root).pack()
root.mainloop()

ここまで書いてから、ファイル名を変えずに明示的にキャッシュを回避する方法を思いついてしまった。ダウンロードページのHTMLで、ハテナ記号つきのリンクを張ればよかったんだよね。たとえば、app.xls というシートを配布するときに、リンクのURLに app.xls?ver_2 とか書くってこと。

あと、メソッド名が do_hello とかになっている理由は、公開用に名称を整理するのが面倒だったから。

pythonでsplit

文字列を一定のルールでちょん切って配列にするという仕事はよく生じる。
こんなときは、文字列にsplitメソッドを適用すればよい。

>>> "out of google, out of existence".split(" ")
['out', 'of', 'google,', 'out', 'of', 'existence']

でもsplitメソッドは、不定数の空白文字で区切られたものをうまく扱えない。

>>> "out    of google, out of   existence".split(" ")
['out', '', '', '', 'of', 'google,', 'out', 'of', '', '', 'existence']

perlだと正規表現を使ってsplitもできたのになあ、と不便に思って調べると、ちゃんとpythonでもそれができた。ただ、明示的に正規表現オブジェクトのメソッドとしてこれを使う。

>>> import re
>>> r1 = re.compile("\s+")
>>> r1.split("out    of google, out of   existence")
['out', 'of', 'google,', 'out', 'of', 'existence']

あらよかったね。

あと、例文には何の意味もありません。