[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秒
件数の1.5乗のオーダーで処理時間が増えている、かな?
市町村規模の名簿の名寄せはムリっぽいですが、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"例)氏名,〒,住所1,住所2,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