Home > 3月, 2010

2010.03.07

SimString (類似文字列検索ライブラリ) 1.0 released

SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました.類似文字列検索とは,文字列集合(データベース)の中から,クエリ文字列と似ているものを見つけ出す処理です.コンピュータは,正確に一致する文字列を探すのは得意ですが,表記揺れに出くわすと,途端に対応できなくなります.例えば,「スパゲティ」に対して,レストラン情報などを返すサービスにおいて,「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると,通常のデータベースでは情報を提示することが出来ません.類似文字列検索を用いると,表記揺れが検索クエリに与えられても,「スパゲティ」という既知語を代替クエリとして提案したり,「スパゲティ」の情報をダイレクトに引き出すことができるようになります.

似てる語を探す技術って,文字列処理の基本中の基本で,自然言語処理では当たり前のように使われていてもおかしくないと思うのですが,研究ではほとんど見かけません.2つの文字列が与えられたときに,似てるか似てないかの識別する研究は,色々あるのですが,ある文字列が与えられたときに,どの文字列が近いかを高速に収集する方法は,あまり見かけません.検索エンジンを提供している会社では,検索クエリログに基づくクエリ訂正などを行っていますが,検索クエリログは誰でも入手できるわけではありません.類似文字列検索は,データベースやデータマイニングの分野で盛んに研究がされていますが,単語や用語レベルの文字列が簡単に扱えるツールが見つからなかったので,自分で作ってみました.

SimStringは,「文字列集合の中で,検索文字列との類似度がある閾値以上のものをすべて返す」という処理を高速に行えるように設計されています.類似度関数としては,コサイン係数,ジャッカード係数,ダイス係数,オーバーラップ係数をサポートしています.類似度を計算するときの文字列の特徴として,文字Nグラムを採用しています.

例えば,3グラム(N=3)を用いたとき,「スパゲティ」は「$$ス」「$スパ」「スパゲ」「パゲテ」「ゲティ」「ティ$」「ィ$$」と表現されます.このとき,文字列の先頭と末尾を表す特殊な記号「$」が挿入されていますが,これを用いるか用いないかはカスタマイズ可能です(デフォルトでは用いないことになっている).また,Nグラムの単位(すなわちNの値)も,自由に設定できます.また,日本語などのマルチバイト文字でも正確にNグラムが計算できるように,ユニコードをサポートしています.

SimStringは,類似文字列検索を正確に,かつ高速に行えるように設計されています.Google Web 1Tコーパス の英単語(13,588,391文字列)から,コサイン類似度が0.7以上の文字列を検索するのに必要な時間は,1クエリあたり平均 1.10 [ms] 程度です.

実装はC++で,ヘッダファイルをインクルードするだけで他のアプリケーションに組み込めるようになっています.また,PythonとRubyのSimStringモジュールも,ビルドできるようになっています.他言語のモジュールはSWIGを用いてラッパを自動生成しているので,Perlなどの言語にも対応できるはずです(ビルド報告,サンプルプログラムなど歓迎致します).Pythonで類似文字列が一瞬で検索出来るなんて,楽しい世界が広がると思いませんか?

$ python
Python 2.5.1 (r251:54863, Oct 15 2007, 23:38:19)
[GCC 3.4.6 20060404 (Red Hat 3.4.6-8)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import simstring
>>> db = simstring.reader('web1tuni/web1tuni.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.9
>>> db.retrieve('approximate')
('approximat', 'pproximate', 'approximate', 'approximated', 'approximatel',
'approximates', 'approximatey', 'anapproximate', 'approximatelt', 'approxima
tely', 'reapproximate', 'toapproximate')
>>> db = simstring.reader('web1tja/unigrams.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.7
>>> print(' '.join(db.retrieve('スパゲッティー')))
スパゲッティ スパゲッテー スパゲティー スパッティー スパゲッティー スパゲッ
ティーニ スパゲッティー・ スパッゲッティー スパゲッティーニ・ ・・スパゲッテ
ィー スープスパゲッティー スパゲッティーモンスター
>>>

いろんなクエリを入れながら遊んでいるだけで,研究ネタが浮かんできそうです.この例では,単にコサイン類似度で類似文字列を検索しているだけなので,表記揺れ,語尾変化,派生語,その他別の概念を指すものが混ざって獲得されます.ここからルールや機械学習を用いて,所望の語を選別するのは,別タスクになります.

アルゴリズムの詳細については,今週東大で開催される情報処理学会の全国大会で発表する予定です.学会初日の朝一番の発表(1C-1)ですが,興味のある方は,是非遊びに来て下さい.