日本語文書の全文検索 2015-11-20
Groongaで学ぶ全文検索 2015-11-20 に参加して来た。遅れそうで「遅れます」って連絡してたら、15分くらい早く着いてしまって時間のお見積りが不正確で大変申し訳ございませんでした。
今日のテーマは日本語での全文検索。
以前、英語での全文検索の仕組みについてはやった（http://apehuci-kitaitimakoto.sqale.jp/apehuci/?date=20150918 ）。今回は軽くそれを復習した後、日本語では英語の場合と違ってどういうところを頑張る必要があるかという話だった。最初に、知ってるだろと説明役を振られそうになったけど「日本語の方は分からないんですよ」と言って断った。が、日本語で分かってない部分（分かち書きの仕方）まで辿り着かなかったので、引き受けておけばよかったなあ。
さておき、まず、英語での全文検索のおさらい。以下、話を単純化するため、一語のみでの検索という前提にする。
全文検索は検索語を入力として、それが含まれた文書を返すもの。単純に、検索語に対して、登録されている文書の一つ一つを調べていくと、文書が増えるにつれどんどん検索が遅くなってしまう。これを防ぐために、インデックスを作り、それに対して検索するようにする。
例えば、「Groonga」で検索した時、登録されている文書から「Groonga」という言葉が含まれている文書（のIDなど）の一覧を返す。この時インデックスにはどういったデータが入っていると嬉しいか？ どういう構造になっていると嬉しいか？ キーが分かると値がすぐに分かる類のデータ構造がよい。配列やハッシュテーブルなどである。
このデータ構造を使って、キーには検索でキーワードとしてヒットさせたい物（「Groonga」「Mroonga」……）が入っているようにする（逆に言うと、ここに入っている物だけが、キーワードとして検索可能 になる）。値には、そのキーワードを含む文書（のIDなど）の一覧を入れておく。すると、「Groonga」で検索した時に、このハッシュテーブルなりを使えば、すぐに「『Groonga』を含む文書一覧」が手に入る。
英語だろうが日本語だろうが、ここまでの考え方は同じ。英語ではここまでで大枠の話は尽きる。データ構造のキーに入れる物が、英単語と一致すること殆どだからだ。多くの場合、検索は、単語で行う。「Groonga」を含む文書が欲しい時に「Groo」みたいな中途半端な文字列で検索したりはしない。こうして検索語の種類（英単語）とインデックスのキーの種類（英単語）が一致するので、英語の場合は概ねこれで要求を満たせる。
ところが日本語ではそうはいかない。
例えば東京都について書かれた文書を探したい時に、検索キーワードとして「東京都」を使うこともあれば「東京」を使うこともある。インデックスのキーに「東京都」だけ入れておけばよいということにはならない。そうしてしまうと、「東京」で検索した時に、その語に一致 するキーが無いわけなので、「東京を含む文書がない」という結果になってしまう。これは、日本語では、単語の区切りが明確ではないという性質に由来する。「単純に単語を入れておけばいいというわけではない。なぜなら単語で検索しない（複合語などで検索する）かも知れないからだ」といこと。（最初に「一単語で検索する」という前提を置いたけど、そもそも日本語では「一単語がどこまでか」が自明ではない、ということだと思う。ちょっとここ自信無い。）
さて、この問題の解決には大きく分けて二種類のアプローチがある。一つは、英語同様単語をキーワードにすること（アプローチA）。「花が咲いた」という短い文書があった時、「花」「が」「咲いた」をキーとしてインデックスに入れる（「咲いた」は微妙かも知れないけどここではそうする）。こうしておくと、「花」で検索した時、「が」で検索した時……に、正しくこの文書を見付けられる。
もう一つは、単語を気にせず何でもキーにしてしまうこと（アプローチB）。「花が」みたいな複合語も「咲い」みたいな単語になってない文字列（ということにしてください）も何でも、意味を気にせずキーにする。
この二種類のアプローチがあって、両方よく使われている。なぜ一つでなく二つあるかというと、アプローチAにある種の難しさがあるからだ。どういう難しさかというと、
「すもももももももものうち」みたいに、単語の切り方が難しい（「スモモも桃も桃のうち」） 「ここではきもの」みたいに、切り方に複数の候補があって選ぶのが難しい（「ここでは、着物」「ここで、履物」） など（他にもある？）。
アプローチAは、検索時にやることが少なくなりやすいという特徴がある。多くの場合、検索語は単語になる。今、インデックスのキーとしては単語を入れているので、単純にハッシュテーブルなどを引けばよくなり、速い。
アプローチBは、例えば上で説明したように、文書を二文字ずつ区切ってキーにしている場合。この場合は、検索語が「咲いた」だと三文字なので、そんなキーは存在せず、（本来ヒットするべき）文書がヒットしない。これを防ぐために検索語の方も、インデックスのキーの長さ（二文字）に合わせてばらばらにする必要がある。（まず、この処理の分、検索時にはすることが増え、遅くなる。でも多分、これはあまり気にしなくていい遅さで、次の話のほうが支配的だろう。ということをまとめ発表で言ったら、@ktou さんが訂正してくれた。アプローチAでも分割しているらしい。検索クエリーが単語になってくれていれば、そういう制約を設けることができれば分割しなくていいが、そうでない場合がほとんどなので。……振り返ると、アプローチA＝形態素解析を使った全文検索で、クエリーも解析しているのは知っていたはずだった……。 ）
「咲いた」を二文字でバラバラにすると「咲い」と「いた」。このそれぞれのキーについて文書を検索する。すると、「『咲い』を含む文書一覧」と「『いた』を含む文書一覧」が手に入る。これらの文書には「『咲い』は含まれるが『いた』は含まれない、従って『咲いた』は含まれない」という文書と、この「咲い」と「いた」の関係をひっくり返した文書が含まれていて、これらはユーザー（プログラム）に渡す検索結果からは除きたい。しかも、除くだけでは不十分で、「花が咲いていた」という文書も、現時点での「正解」の文書リストには含まれてしまっている。でもここに「咲いた」の語はない。「咲い」と「いた」がこの順番で隣り合っていないといけないわけだ。今手に入っている文書のうち、この点も満たす文書を更に絞り込む必要がある。
この絞り込みの方法は二つある。一つは、インデックスの、それぞれのキーに対応する情報に、（文書IDなどの識別子のほか）文書中の出現位置（何文字目に出現するキーか）という情報も入れておく方法。こうしておけば、検索時に「『咲い』と『いた』を含み、その出現位置が一文字違い」という文書を探せばよいことになる。（説明されなかったが、「『咲い』を含み、その出現位置の次の位置が『いた』である」という検索方法だと、集合としては同じ結果が得られるけど、だいぶ遅くなってしまうはず。「咲い」を含む文書一覧を取得した後、それぞれの中身を先頭から一文字ずつ調べていく必要があるので、文書自体を読み込んだり、文字検索用のカーソルを動かしたりする必要が出てきてしまう。）
もう一つは、無駄を承知で、まず、「咲い」を含む文書一覧と「いた」を含む文書一覧を両方取得してしまう。「『咲い』と『いた』を両方含む文書一覧」を取得して、（これも訂正してもらった。） その後に文書それぞれを調べて、キーが隣り合っているか（「咲いた」と連続しているか）を調べる。
アプローチBはこうして、アプローチAよりも処理が増えているので、難しさは減るが、検索時に遅くなってしまう。
というのが理屈。ここまで説明したところで、専門用語が導入された。
アプローチA … 形態素解析 アプローチB … N-gram（Nのところは文字数。N=2でバイグラム、3でトリグラム） こうしてキーワードが連続しているかをチェックして、連続している物だけを返す検索方法をフレーズ検索と言う。一応形態素解析を使った検索で使われることもあるが、多くはN-gram検索で使われる。形態素解析を使う場合は、そもそもの形態素解析を使う目的から（インデックスのキーが単語になっているので）、単語で検索して問題ないことが殆ど。そして多くの人は単語で検索する。逆にN-gramの場合は、「いた」を含む文書とか基本的にノイズばっかりになるから、きちんと（二文字を越える）欲しい単語を含んでいるのかチェックしないと使い物にならない。
以上、英語での検索の場合の他に、日本語で頑張らないといけない処理。
余談。参加者の中に、Mroongaを使っていてMeCabの「too long sentence」といった内容のエラーに遭遇したという人がいた。これについても@ktou さんが解説してくれた。これはMeCabの制限に引っかかったために発生したエラーとのこと。MeCabでは入力された文書に対して、句読点などを見て文に分割しようとする。ところが、文を分割する目印を見付けられなくて一文が長くなりすぎるような文書があると、リソース不足でこのようなエラーになってしまう。
最近のGroongaではこれの対策も実装されているらしい。オプションを指定することで、「一文が長くなり過ぎたら強制的に途中で切ってMeCabに渡す」ということができるようになる。これまで全体がエラーになっていた所が、この部分だけちょっとおかしな検索結果になるというだけなので、全体としてはまあまあうまくいっているらしい。