PHP + MongoDB であいまい検索を作った話

先日、ちょっとしたキッカケで「あいまい検索」を作ってみようと思った。
アニメのタイトルで。

が、そもそもどうやって作るのかまったくわからない。
ただ、一応形態素解析とか N-gram とかは知っていたので、この辺を攻めればなんとかなるだろうと思ったのでちょっと考えた。
この時点で形態素解析を使ってしまうと使える範囲が限られてしまって楽しくなさそうなので、N-gram で行こうと最初に決めた。言語に依存しないし未知語に対しても強いし、アニメのタイトルのようなものに対しては相性が良さそうだから。

要するに似たものを出せばいいのだ。
例えば「らき☆すた」と「らきすた」は結構似ているが微妙に違う。Bigram を使うとすると、
らき☆すた：　らき　き☆　☆す　すた　た
らきすた：　らき　きす　すた　た
のように分かれて、強調にした場所のような共通項が存在する。
特に後半の2つは連続でヒットしていて結構重要なデータと言えそうだ。

そういうのを見てスコアリングして順位を決めればいいのではないだろうか？
と考えたので、実装してみた。

データは以下のような構造で保存した。

word コレクション
検索対象になる言葉の全文が入っているコレクション。

{
  "_id": "(MongoDBが適当に素敵な感じのを考えてくれる)",
  "word": "らき☆すた"
}

wordNgram コレクション
検索対象になる語句を N 文字に分割した状態のコレクション。

{
  "_id": "(MongoDBが適当に素敵な感じのを考えてくれる)",
  "w": "らき",
  "p": [
    {
      "_id": "(wordコレクションでの「らき☆すた」の_id)",
      "pos": 0, //「らき☆すた」内での「らき」の出現位置
      "len": 5  //「らき☆すた」の長さ
    }
  ]
}

こんな感じのものを沢山登録していく。
他にも語句を登録した時などに「らき」を持つものを登録する場合は p に追加するようにし、「らき」自体が複数登録されるのを回避した。これで検索時の処理が少し効率化されないかな、などと思ったため。
あと、wordNgram に保存するデータひとつひとつに "len" を保存しているのだが、これはヒットしなかった範囲の大きさを元に減点する処理を書くために必要になったので仕方がなく全部の文字列片に入れた。
同じデータを何度も重複して入れている形になるので本当はどうにかしたい。

どうやって検索するか
保存されたデータを検索するために MapReduce を使用した。
検索用に入力された語句が「らきすた」だとしたら処理の流れはこんな感じ。

「らき」「きす」「すた」「た」に分解する
上記4つのうちいずれかにヒットする項目を wordNgram へ探しに行って Map 処理を行う。
ここで "p" の中に入っているデータを全て "_id" で emit する。
```
emit(p._id, {pos: [p.pos], len: len});
```
のような感じで。
集まったデータを元に Reduce する。Reduce は複数回呼ばれる可能性があるのでここではスコア計算は行わずに Finalize の時に行う。ここで行うのは複数個集まってくる pos を配列に正しくしまうという処理だけ。
Finalize 処理。ここで pos の配列を昇順にソートする。この時点でデータは
```
{pos: [0, 3, 4], len: 5}
```
になっているはず。これをスコアリングしてあげればいい。
連続してヒットすればするほど高得点になるようにしたかったので、
```
Math.pow(3, "(続いた回数)")
```
という式で加点と、
```
"(ヒットしなかったブロックの長さ)" * 0.01
```
という式で減点するようにした。
この減点で長い語句ほどランクが下がりやすくなるが、文字列片が連続でヒットした場合 3**N で一気にスコアが上がるので上位に押し上げられるだろうというのが狙い。
ただ長い語句だとアホみたいにスコアが上がってしまうというのもあるので、もうちょっと上手くやった方がいいかも知れない。

実際に動いているものと、そのソースが以下。

~~http://test.oov.ch/AnimeTitleSearch/~~（公開終了）
https://bitbucket.org/oov/fuzzysearch/src

ここまでではそれなりの速度で結果が返せているのだが、似たような語句が増えると目に見えて検索速度が落ちていく。また、入力される語句が長いと検索対象データが増えてどうしても処理が重くなってしまう。

（わかりやすいところで「もし高校野球の女子マネージャーがドラッカーの『マネジメント』を読んだら」のような長いタイトルが実際に存在する）

2000件ちょっとしかデータが入ってない現状で若干レスポインスが悪くなるのを感じるので、試しに同じデータの尻にゴミを付与して40000件以上にデータを増やして検索させてみたら、遅いわ遅いわ……。

データ量がこれ以上増えないならいいけど、長い目でみるとこのままではイカン、ということがわかってきたところ。

2011-12-09 追記 ----

シンプルな構造にしてインデックス張ってみたけど最初の実装より遅くなったので戻した。

2011-12-13 追記 ----

エイリアス登録機能を追加して、「K-ON!」や「はにはに」のようなものへ対応できるようにした。
「遊☆戯☆王」のように bigram や unigram では「遊戯王」で検索できないようなものに対してもこれで対応できるようになった。
（正規化の時点で記号類を外す、という選択もあるにはあるが……）

あとは細かい処理の見直しなど。

word コレクションへの登録データは以下のようなものに変わった（少し前にキー名も全体的に1文字に変更されている）。

{
  "_id": "(MongoDBが考えたやつ)",
  "w": "けいおん!",
  "a": ["K-ON!"]
}

単純に a という名前で内部に抱え込むだけ。データの節約のため、初回登録時は "a" 自体は登録されていない状態になっている。
wordNgram コレクション側には現状特にエイリアスであることを区別せず同じ形で登録してある。
これで問題ないと思っていたのだが、よく考えてみると MapReduce でのスコア計算時に区別できないとデータが混じってしまい正しいスコア算出がされなくなってしまう……。
エイリアス同士で混じってもいけないのでやはり個別に区別できなきゃ駄目かな……。