前回は形態素解析を使う検索エンジンのしくみについて説明しました。今回は、FINDSPOTで使用しているN-gramという検索エンジンのしくみについて説明します。

N-gramによる見出し語の切り出し

前回は、形態素解析による検索エンジンでは、検索可能な最小単位が分かち書きの切り分け単位となる点を説明しました。

一方、N-gramを使った検索エンジンでは、単純に文字の並びを見出し語としてインデックスを作成します。1文字を元にインデックスを作成する方法をユニグラム、2文字の並びを元にインデックスを作成する方法をバイグラム、3文字の並びを元にインデックスを作成する方法をトリグラムと呼んでいます。

1文字：ユニグラム

2文字：バイグラム

3文字：トリグラム

N-gramによる見出し語の切り出しは、形態素解析のための文法解析を伴わないため、特定の自然言語に依存しないという特徴があります。

FINDSPOTでは、1文字の文字列を見出し語として用いるユニグラムと、2文字の文字列を見出し語として用いるバイグラムの手法を併用して、インデックスを作成しています。このうち、ユニグラムは専ら1文字の文字列検索に使用しており、2文字以上の文字列についてはバイグラムを用いて検索を行っています。

具体例を用いて説明しましょう。「今日は良い天気です。」という文字列をバイグラムのインデックスを作成してみます。この文書のIDを1番とすると、次のような索引情報が生成できます。

今日    1
日は    1
は良    1
良い    1
い天    1
天気    1
気で    1
です    1
す。    1
。　    1

別の「今日は大雨です。」という文書ID 2番の文書をバイグラム情報は、次のようになります。

今日    2
日は    2
は大    2
大雨    2
雨で    2
です    2
す。    2
。　    2

文書ID 1番と2番の文書を合算した索引情報は、次のようになります。

今日    1, 2
日は    1, 2
は良    1
良い    1
い天    1
天気    1
気で    1
です    1, 2
す。    1, 2
。　    1, 2
は大    2
大雨    2
雨で    2

これがバイグラムによる転置インデックスです。

このようにして作られた索引情報を使って、「⁠天気」という文字列を検索すると、文書IDが1番の文書が該当することがわかります。また、「⁠今日」という文字列を検索すると文書IDが1番と2番の中に見つかります。そして、「⁠今日」と「大雨」という2つの文字列を含む文書を探す場合には、「⁠今日」の検索結果と「大雨」の検索結果をAND条件で合成すると、文書IDが2番という結果が得られます。

では、バイグラムの単位より長い文字列の検索についてはどうでしょうか。長い文字列をバイグラムで検索するには、検索文字列をバイグラムの単位に分解します。そして、それぞれの2文字の文字列片による検索を行い、結果を合成します。

「⁠良い天気」という文字列を検索するには、「⁠良い」と「天気」という文字列に検索文字列を分解します。次にそれぞれの文字列片で検索を行います。「⁠良い」という文字列が含まれる文書IDは1、「⁠天気」という文字列が含まれる文書IDは1なので、結果をANDで演算して文書ID 1が検索結果となります。

では「今日は大雨」という文書についてはどうでしょうか。こちらは5文字の奇数長の文字列なので、文字列の終わりの1文字を重複させ、「今日」「⁠は大」「⁠大雨」という文字列に分解します。それぞれの文字列片で検索を行うと、「⁠今日」は文書IDが1と2、「⁠は大」は文書IDが2、「⁠大雨」は文書IDが2となります。結果をANDで演算すると文書ID 2が検索結果となります。

文字列の出現位置情報

ここまで述べたような方法によるN-gramの検索システムも存在しますが、実は若干正確性に欠けています。バイグラムの場合、文書中に検索する文字列を2文字の長さで分解し、この文字列片がすべて含まれている文書を結果とします。ところが、1つの文書に、「⁠今日」「⁠は大」「⁠大雨」が含まれているという条件だけでは、正確に「今日は大雨」という文字列を含む文書を探したことにはなりません。例を挙げると、「今日の東海地方は大雨でしょう。」という文書も、「⁠今日」「⁠は大」「⁠大雨」という文字列片が含まれているので、このロジックを使うと誤検索されてしまいます。 「⁠今日は大雨」を「今日」「⁠日は」「⁠は大」「⁠大雨」と4つに分解して検索を行えば若干精度は上がりますが、これでも完全とはいえません。

完全一致の正確さを実現するために、FINDSPOTでは転置インデックスに文書IDに加えて、その文字列片の出現位置情報を含めています。転置インデックスに記録された出現位置情報を検索時に利用することで、完全一致の正確さを実現しています。

例を挙げて説明しましょう。文字列片の出現位置情報を、文書IDの後ろに「:文書の先頭からのオフセット」を加えて表現してみます。すると文書ID 1番「今日は良い天気です。」の索引情報は、次のようになります。

今日    1:0
日は    1:1
は良    1:2
良い    1:3
い天    1:4
天気    1:5
気で    1:6
です    1:7
す。    1:8
。　    1:9

「⁠今日は大雨です。」という文書ID 2番の文書の索引情報は、次のようになります。

今日    2:0
日は    2:1
は大    2:2
大雨    2:3
雨で    2:4
です    2:5
す。    2:6
。　    2:7

「⁠今日の東海地方は大雨でしょう。」という文書ID 3番の文書の索引情報は、次のようになります。

今日    3:0
日の    3:1
の東    3:2
東海    3:3
海地    3:4
地方    3:5
方は    3:6
は大    3:7
大雨    3:8
雨で    3:9
でし    3:10
しょ    3:11
ょう    3:12
う。    3:13
。　    3:14

文書ID 1, 2, 3番の索引情報を合算すると次のようになります。

今日    1:0, 2:0, 3:0
日は    1:1, 2:1 
は良    1:2
良い    1:3
い天    1:4
天気    1:5
気で    1:6
です    1:7, 2:5
す。    1:8, 2:6
。　    1:9, 2:7, 3:14
は大    2:2, 3:7
大雨    2:3, 3:8
雨で    2:4, 3:9
日の    3:1
の東    3:2
東海    3:3
海地    3:4
地方    3:5
方は    3:6
でし    3:10
しょ    3:11
ょう    3:12
う。    3:13

「良い天気」という文字列を検索するには、先ほどと同様に「良い」と「天気」という文字列に検索文字列を分解します。次にそれぞれの文字列片で検索を行い、「⁠良い」と「天気」を両方含む文書を求めます。

良い    1:3
天気    1:5

文書ID 1番が合致することは、前述の通りですが、ここで「良い」と「天気」の文字列の出現位置が2文字分ずれているかをチェックします。ここでは文書の先頭からのオフセットがそれぞれ3と5なので、2文字分ずれています。これで「良い天気」という文字列が確かに文書ID 1番の文中に存在したことが確認できます。

次に懸案の「今日は大雨」という文字列を含む文書を検索してみましょう。前述のように、検索文字列を「今日」「⁠は大」「⁠大雨」という文字列に分解します。それぞれについて、索引情報を調べてみると次のようになります。

今日    1:0, 2:0, 3:0
は大    2:2, 3:7
大雨    2:3, 3:8

文書ID 1番は、「⁠は大」「⁠大雨」にはエントリが無いので、すぐに対象外であることがわかります。次に、「⁠今日」「⁠は大」間の出現位置の差が2で、「⁠は大」「⁠大雨」間の出現位置の差が1である文書IDを探します。文書ID 2がこの条件に当てはまります。前述の単純な方法では文書ID 3がノイズとして紛れ込んでいましたが、出現位置情報を利用すれば、検索語と完全一致した文字列を含む文書を100%正確に検索できるのです。

FINDSPOTでは文字列の出現位置情報を利用して、さらに曖昧検索というしくみを実現しています。この内部ロジックについては、別の機会に紹介する予定です。