« | »

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)ですが,興味のある方は,是非遊びに来て下さい.

Comment & Trackback

Comments and Trackback are closed.

[…] Não Aqui! » SimString (類似文字列検索ライブラリ) 1.0 released (tags: nlp) […]

C++から使えるということですが、C#版があるとうれしいなと思いました。
ご検討ください。

コメントありがとうございます.

C#のバインディングはswig経由で作れるはずなので,後でトライしてみようと
思いますが,私はまったくC#を使わないので,きちんとメンテできる自信が・・・.

swig/export.iとswig/export.cppから以下のドキュメントを見ながら作れる
とは思いますが,Windowsの場合はUTF-8からwchar_tへの変換を担当している
iconvをリンクしなければならないので,さらに一手間いるかもしれません.
http://www.swig.org/Doc1.3/CSharp.html

論文を見てプログラミングしながら思い付いたのですが、
特徴集合のサイズ別に転置インデックスを分けて探索範囲を削るのなら
ついでに特徴集合の偶数の個数も数えれば
探索範囲をさらに小さくできるのでは。

例えば、
X: (サイズ 6, うち偶数 4個) o o o o x x
Y: (サイズ 7, うち偶数 2個) o o x x x x x

なら、最大4個までしかオーバーラップしないのは明白ですし。

コメントありがとうございます.「特徴集合の偶数の個数」というのを
正しく理解できていないかもしれませんが,○×のカウントはクエリが
与えられるまでできないので,探索範囲が減らせる理由が分かり
ませんでした.

コメント欄もしくはメールなどで教えて頂けると幸いです.

了解しました。
現在、必要なオーバーラップ数に届かない転置インデックスを検索から除外する為に
インデックスを集合のサイズ別に分けて作成しています。
これを同じサイズでも、偶数の個数でさらに細かく分けて作成すれば
無駄な検索をさらに少なく出来るのではないだろうか、というのが上の趣旨です。

私の乱筆により誤解が生じたかもしれませんので、補足をお許しください。

偶数の個数とは、末尾1ビットが0である要素の個数というふうに解釈して下さい。
XとYの○×の並び順の比較が必要と誤解を与えたかも知れませんが、必要ではありません。
必要なのは、特徴集合の作成時に判明する集合のサイズと偶数の個数だけです。