昨日 2013/03/20に突然 電話番号とかMACアドレスとか携帯の契約者idの単なるハッシュにとどめを刺したくなりました.
とりあえず 080[0-9]{8} 形式の電話番号のすべてについて,
"ハッシュ値(16進)\t電話番号\n"
なソート済みファイルを作りました. 全部で 4.2GB になりました.
手元の計算機で, 電話番号からハッシュ値の計算に数分, ソートに30分, 分割に数分といったところです.
2013/03/21 追記: ハッシュ値の頭文字で16分割し 625万行ずつのファイルにすると ソートせずに grep しても余裕でした. 時間も1億件やるのに8分台です. ちなみに単に1つのハッシュ値を照合するだけならファイルIOがないので総当たりで3分もかかりません. 春山 征吾のくけー : 電話番号とかMACアドレスとか携帯の契約者idの単なるハッシュにとどめを刺したい その2 - livedoor Blog(ブログ) で詳述してます.
unixuser であればlook(1) で高速に検索できます. 手元のDebian sid(x86_64, bsdmainutils 9.0.4)の look(1) は どうやら 1GB 以上のファイルを扱えないようなので, 2500万行ずつの4ファイルに分割しました. 1ファイルに対する検索は(エントリがあれば)2秒くらいで終わります.
ファイルをどこかで公開しようと思いましたが, 1GB(bzip -9 で圧縮しても 300MB以上になります)のファイルを置けて公開できるサービスがすぐにみつからなかったのでまだしていません.
電話番号には, 070 や 090, 固定電話がまだありますし, 表記としても ハイフン区切りあるなしがあります.
ハッシュ関数もMD5以外に多数あります. 汎用的にするにはもっと空間効率のよいデータ構造を利用したほうがよさそうです(レインボーテーブルなりなんなり).
とはいえ, ある1つのサブシステムで利用される表記やハッシュ関数は通常1つであり, 携帯の電話番号に限ってしまえばこの方法でも十分いけるでしょう.
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。