検索エンジンを作る

第5回 N-gramのしくみ

この記事を読むのに必要な時間:およそ 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では文字列の出現位置情報を利用して,さらに曖昧検索というしくみを実現しています。この内部ロジックについては,別の機会に紹介する予定です。

著者プロフィール

工藤智行(くどうともゆき)

有限会社サイパック取締役社長。システム構築・管理のコンサルティング,ローカライゼーション,文書処理や障害者向けソフトウェアを中心とするプログラミングを長年手がける。 近著『UNIXプログラミングの道具箱』『システム管理現場の鉄則FreeBSD編』等

URLhttp://www.cypac.co.jp/

著書

コメント

コメントの記入