春山 征吾のくけー

https://www.unixuser.org/~haruyama/blog/ に移転しました http://wiki.livedoor.jp/haruyama_seigo/d/FrontPage @haruyama タイトルが思いつかないときはそのときかかってた曲をタイトルにしています.

2013年03月

電話番号とかMACアドレスとか携帯の契約者idの単なるハッシュにとどめを刺したい その2

春山 征吾のくけー : 電話番号とかMACアドレスとか携帯の契約者idの単なるハッシュにとどめを刺したい - livedoor Blog(ブログ) では ソートしたんですが, 1億件の電話番号に対して ハッシュの頭文字で 16分割したファイル(各625万行ほど)を作ると, ソートしないで grep でもすぐ結果が返ってきました. これらのファイルを作るのに直列にやって 8分台でした.

単にあるハッシュ値と一致する電話番号探すだけなら, ファイルIOがない分速いです. 1億件は 2,3分で終わります. もちろん並列にやったり GPU 使えばもっと速いです.

電話番号みたいな狭い空間の単なるハッシュ値は, 少しの手間で復元できます. セキュリティに関する目的に利用してはいけません.

080[0-9]{8} な 電話番号のハッシュ値と番号を記述したファイル群

https://app.sugarsync.com/wf/D1955203_142_7316730

ファイル作成に利用したスクリプト

haruyama/tel_hash ・ GitHub

電話番号とかMACアドレスとか携帯の契約者idの単なるハッシュにとどめを刺したい

昨日 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つであり, 携帯の電話番号に限ってしまえばこの方法でも十分いけるでしょう.

QRコード
QRコード
  • ライブドアブログ