[pukiwiki]
Pythonで名寄せするプログラムを書いてみました。
（まだ年賀状のリスト作りには早いですけれども。）

参考文献
-[[【PDF】 圧縮を用いた類似度判定のための計算実験:http://www.tani.cs.chs.nihon-u.ac.jp/g-2008/shu/tyukan_shu.pdf]]

文字列類似度の判定には、こちらの式を、ほぼ　そのまま使用しています。
[/pukiwiki]

[pukiwiki]
zlib(gzip)による圧縮を利用しているので、たぶん　[[Nグラム>ググる:Nグラム]]による比較に近い結果が得られるんじゃないかという期待から、上記のアルゴリズムを使用しました。
—-
具体的には、表記にブレのある住所録ファイルsample.csvについて、似た文字列同士が隣り合わせになるように並べなおします。
（むしろ、クラスタリングに近いかも）

動作確認　CPython2.5 vista
IronPythonでは動かないみたいです。
（文字列.encodeメソッドでコケるのですが、どう直したらよいやらわからず）

動作スピード 一例 。 Core2Duo T7250 2GHzにて
手持ちの住所録等にて実験。
-35件　ー＞ 0.64秒
-1000件　－＞　169秒　＝　2分49秒

件数の１．５乗のオーダーで処理時間が増えている、かな？
市町村規模の名簿の名寄せはムリっぽいですが、1000件ぐらいなら　実用に使える速度になった模様。（自画自賛）

//35件のほうについては、こちらのサンプルデータを使用しました
//-[[データバンク Repoラボ:http://lab.irepo.jp/identification/service.php]]
//sample.csvとして保存

*今後の課題
今回は単純に一軒ごとに文字列データとして比較しました。
使用したサンプルのようにcsvデータの場合、AdrSortクラスの scoreメソッドにて、カンマで分解、項目ごとに細かいスコアリングをすると精度が上がるかも。
（たとえば、電話番号が一致してたら、他が全部違っても名寄せする、とか）

また、[[GIS>ググる:GIS]]を利用する、というのも一つの方法かも。
ただし、住所をやたらとAPIに投げるのは厭っぽいですが。。。

[/pukiwiki]
—-
以下コード

adrsort.py
カレントディレクトリの sample.csvを似ている順に並べなおし、sorted.csvとして保存

# -*- coding: utf-8 -*-
import csv
import codecs
import difflib
import unicodedata
import re
from mycollections import namedlist

Address=namedlist("Address","name post tel address")
Dat=namedlist("Dat","idx ln n z a")

def minus(x):
    ret=[]
    g=x.groups()
    if g==[None,None,None,None] :return 
    for i in g:
        if not i :continue        
        i=re.match("\d+",i).group()
        ret.append(i)
    return "-".join(ret)+" "

def rep(t,
    pat=re.compile(r"(?P<a>\d+\s?"    u"丁目"   r")?"      r"(?P<b>\d+\s?"   u"番地"    r")?"\
                   r"(?P<c>\d+\s?"   u"号"    r")?"        r"(?P<d>\d+\s?)?")
               ):

    t=pat.sub(minus,t)
    return t

#表記のブレを正規化
def normal_adr(txt):
    return rep(normal(txt))
def normal(txt):
    txt=txt.replace(u"　","")
    return unicodedata.normalize("NFKC",txt)
def normal_tel(txt):
    t=normal(txt)
    t=t.replace("-","")
    return t


class ScoreZ(object):
    def __init__(self):
        self.z_dict={}

    def score(self,t1,t2):
        #完全一致のときゼロを返す
        t1,t2=sorted( [t1,t2])
        t12=t1+t2
        tlist=[t1,t2,t12]
        for t in tlist:
            if not t in self.z_dict:
                self.z_dict[t]=len(t.encode("zlib"))
        sz1,sz2,sz12=[ self.z_dict[t] for t in tlist]
        szmin,szmax=sorted([sz1,sz2])
        
        #return float(max(len(t1),len(t2)))*(sz12-szmin)/szmax
        return 100*(sz12-szmin)/szmax
        
class AdrSort(object):
    nlist=[normal,normal_tel,normal_adr,normal_tel,normal]
    def __init__(self,datlist,threashold=45):
        self.datlist=datlist
        self.donelist=[]
        self.yetlist=range(len(datlist))
        self.scorez=ScoreZ()
        self.threashold=threashold
    def score(self,txt1,txt2):
#txt1, tx2がcsvの場合、カンマで区切って、それぞれ
#適宜 スコアリングの係数を変えたり、正規化の手法を変えると
#精度が上がるかも。
        scorez=self.scorez
        txt1=normal_adr(txt1)
        txt2=normal_adr(txt2)
        return scorez.score(txt1,txt2)
    
    def search(self,idx):
        datlist=self.datlist
        yetlist=self.yetlist
        donelist=self.donelist
        t1=datlist[idx]
        scorez=self.scorez
        sclist=[]
        threashold=self.threashold
        for y in yetlist :
            t2=datlist[y]
            sc=self.score(t1,t2)
            sclist.append((sc,y))
        return [ y for sc,y in sorted(sclist) if sc <threashold] 
    def sort(self):
        datlist=self.datlist
        yetlist=self.yetlist
        donelist=self.donelist

        scorez=self.scorez
        sclist=[]
        threashold=self.threashold
        while yetlist:
            idx1=yetlist.pop(0)
            print idx1,
            donelist.append(idx1)
            candies=self.search(idx1)
            for c in candies:
                donelist.append(c)
                yetlist.pop(yetlist.index(c))                
            for c in candies:
                candies2=self.search(c)
                for c2 in candies2:
                    donelist.append(c2)
                    yetlist.pop(yetlist.index(c2))



def load():
    #fp=codecs.open("sample.csv",encoding="cp932")
    fp=codecs.open("sample.csv",encoding="utf8")

    lines=fp.read().splitlines()

    fp.close()
    lines=list(set(lines))
    lines.sort()
    return lines
def main():
    datlist=load()
    
    print len(datlist)
    a=AdrSort(datlist)
    import time
    print time.localtime()
    t0=time.time()
    a.sort()

    print time.localtime()
    print time.time()-t0
    ret=[ datlist[i] for i in a.donelist]
    ret.append("")

    fp=open("sorted.csv","wb")
    fp.write("\n".join(ret))
    fp.close()
if __name__=="__main__":
    main()
    

カスタマイズ例 scoreメソッドを差し替え

class AdrSort2(AdrSort):
    nlist=[normal,normal_tel,normal_adr,normal_tel,normal]
    def score(self,txt1,txt2):
        scorez=self.scorez
        u"例）氏名,〒,住所１,住所２,TEL,備考"
        name1,post1,adr1a,adr1b,tel1,memo1=txt1.split(",")
        name2,post2,adr2a,adr2b,tel2,memo2=txt2.split(",")
        adr1=adr1a+adr1b
        adr2=adr2a+adr2b
        dlist1=[name1,post1,adr1,tel1,memo1]
        dlist2=[name2,post2,adr2,tel2,memo2]
        sc=[]
        for i in xrange(5):
            d1=dlist1[i]
            d2=dlist2[i]
            n=self.nlist[i]
            dlist1[i]=n(d1)
            dlist2[i]=n(d2)
        s=scorez.score("".join(dlist1),"".join(dlist2))
        return s