【ITニュース解説】Under the Hood of Fuzzy Search: Building a Search Engine 15 times fuzzier than Lucene

システムエンジニアが開発する情報システムにおいて、ユーザーが情報を探し出すための「検索機能」は非常に重要な要素だ。しかし、人間は完璧な情報を入力できるわけではない。少しの誤字脱字や、表記の揺れ、あるいは入力ミスのために、本当に探したい情報が見つからないという経験は誰にでもあるだろう。このような問題を解決するために生み出されたのが、「ファジー検索」、日本語では「あいまい検索」と呼ばれる技術である。

今回のニュース記事は、「Lucene（ルーセン）」という強力な既存の検索エンジンよりも、15倍も「あいまい」な検索エンジンを構築したという話だ。これはつまり、従来の検索エンジンでは見つけられなかったような、より多くの誤字や表記揺れに対応できる検索システムを作り上げたことを意味する。では、そもそもあいまい検索とは何で、どのようにして実現するのか、そして「15倍あいまい」とは具体的にどういうことなのかを詳しく見ていこう。

まず、あいまい検索の基本的な考え方から説明する。私たちが普段使っている検索機能の多くは、入力されたキーワードと完全に一致する情報を探す「完全一致検索」を基本としている。例えば、「アップル」と入力したら「アップル」という文字列が含まれる情報だけを探す。しかし、「アップル」を「あっぷる」と入力したり、「Apple」と入力したり、「アプル」と誤字を入力したりした場合、完全一致検索では求める情報にたどり着けない。あいまい検索は、このような入力の「ずれ」を許容し、それでも関連性の高い情報を探し出すことを目的とする。

この「ずれ」をどのように許容するか、そのために使われるのが、文字列間の「距離」を測る技術だ。代表的なものに「レーベンシュタイン距離（編集距離）」という概念がある。これは、ある文字列を別の文字列に変形させるために必要な、文字の挿入、削除、置換（変更）の最小回数を数値化したものだ。例えば、「apple」を「aple」（「p」を削除）に変えるレーベンシュタイン距離は1。「apple」を「apply」（「e」を「y」に置換）に変える距離も1。「apple」を「apples」（「s」を挿入）に変える距離も1だ。この距離が小さいほど、二つの文字列は似ていると判断できる。あいまい検索では、入力されたキーワードとデータベースに登録されている文字列とのレーベンシュタイン距離を計算し、ある一定の距離範囲内であれば、一致する情報として扱う。

レーベンシュタイン距離のような編集距離は強力だが、文字数が長い文字列全体に対して計算すると、処理に時間がかかるという課題がある。そこで、あいまい検索の効率を高めるために、「N-gram（エヌグラム）」という手法がよく用いられる。N-gramは、文字列をN個の文字のまとまりに分割する技術だ。例えば、「システムエンジニア」という文字列をバイグラム（2-gram）で分割すると、「シス」「ステ」「テム」「ムエ」「エン」「ンジ」「ジニ」「ニア」といった具合に、2文字ずつの連続した部分文字列に分解される。このN-gramに分解された部分文字列を使ってインデックス（索引）を作成することで、検索の際に、部分的な一致や文字の並び順のずれにも対応しやすくなる。例えば、「システムエンジニア」と「しすてむえんじにあ」では、全体としてのレーベンシュタイン距離は大きくなるが、共通のN-gramが多く含まれるため、関連性の高い情報として検出できる可能性が高まる。

検索エンジンが膨大なデータの中から瞬時に情報を探し出せるのは、この「インデックス」のおかげだ。インデックスは、図書館の蔵書目録のようなもので、どの情報がどこにあるかを素早く見つけるための地図の役割を果たす。特に検索エンジンで重要なのは「転置インデックス」という仕組みだ。これは、一般的な本の巻末にある索引と似ている。通常のインデックスが「文書Aには単語X、Y、Zが含まれる」という形であるのに対し、転置インデックスは「単語Xは文書A、B、Dに含まれる」といったように、「単語」をキーにして、その単語が含まれる「文書」を効率的に探し出すことができる。あいまい検索では、レーベンシュタイン距離やN-gramを使って、入力されたキーワードから関連性の高いキーワード候補を生成し、これらの候補を使って転置インデックスを検索することで、あいまいな入力にも対応できるのだ。

今回のニュース記事が取り上げているのは、既存の検索エンジンであるLuceneを上回る「15倍あいまい」な検索エンジンだという点だ。Luceneはオープンソースの強力な検索ライブラリで、多くの商用・非商用システムで利用されており、もちろんあいまい検索の機能も持っている。しかし、本記事で開発されたエンジンは、Luceneがあいまいさを許容する範囲をさらに広げたものだと言える。具体的に「15倍あいまい」が何を指すのかは、検索のアルゴリズムやパラメーター設定によるが、おそらく、より大きなレーベンシュタイン距離を許容したり、より多くのN-gramの組み合わせを考慮したりすることで、従来のLuceneでは見つけられなかったような、より広範囲の関連語句や、より多くの誤字脱字を含む入力を関連情報として拾い上げられるようにしたのだろう。

あいまい度を高めることには大きなメリットがある。ユーザーが少し間違った入力をしてしまっても、システムが賢く補正して正しい情報を見つけてくれるため、ユーザーエクスペリエンス（利用体験）が格段に向上する。これは、表記揺れが多い専門用語や、ユーザーによって入力方法が異なる可能性のある名前や地名などを検索する際に特に有効だ。しかし、あいまい度を高めることにはデメリットも存在する。最も懸念されるのは、検索のパフォーマンス、つまり速度の低下だ。あいまいなマッチングを増やすほど、システムはより多くの計算を行う必要があり、結果として検索に時間がかかるようになる。また、あいまい度が高すぎると、本来意図しない無関係な情報まで検索結果として表示されてしまう、「ノイズ」が増える可能性もある。

システムエンジニアは、このようなメリットとデメリット、つまりトレードオフを理解し、開発するシステムやターゲットとなるユーザーのニーズに合わせて、最適な「あいまいさのレベル」を設定する必要がある。厳密な検索が求められる場面ではあいまい度を抑え、ユーザーの入力ミスが多いことが想定される場面では積極的にあいまい度を高めるなど、状況に応じたチューニングが求められるのだ。今回の記事は、あいまい検索の限界に挑戦し、よりユーザーに寄り添った検索システムの可能性を示している。システムエンジニアを目指す皆さんにとって、このような技術の深掘りは、ユーザーの課題を解決するシステムを設計・開発するための貴重なヒントとなるだろう。