N-Gramインデックス方式

最終更新: 2011年08月07日 22:53

N-Gramインデックス方式とは、決められた文字数の単位で文章を切り出し、「単語を含んだ文字列」としてインデックスする方式です。

N-Gramインデックス方式とは、決められた文字数の単位で文章を切り出し、「単語を含んだ文字列」としてインデックスする方式です。Web検索エンジンでは小数派ですが、サイト内検索ソフトの中にはこの方式を採用しているものもあります。

この方式では、文書の頭から長さＮの文字列を一文字ずらしながら順に切り出して、その文字列の全てと記載されるファイルや位置をインデックスに記録していきます（長さＮはかなや漢字など、文字の種類によって適切な値が選ばれる場合があります）。例えば、「検索エンジンの仕組み」をN=4として取得すると、

という文字列が取得できます。あとは検索時に、「検索」「エンジン」「仕組み」などの単語を含んだ文字列のある場所を探すことで、どのファイルのどこに、どのような単語が含まれているのかを正確に知ることができます。

N-Gramインデックス方式には、次のような利点があります。

アルゴリズムが単純: N-Gramインデックス方式には、インデックスおよび検索のアルゴリズムが単純であるという利点があります。高速に処理することができる上、単語インデックス方式のような複雑な文書解析を行わないので、どのような言語にも同じアルゴリズムで対応することができます。
検索漏れを生じない: N-Gramインデックス方式には、元の文書に含まれている文字であればどんな語句でも検索でき、検索漏れを生じないという利点があります。例えば、ストップワードを含んだ検索ワードは通常の単語インデックス方式では検索することができませんが、N-Gramインデックス方式では検索可能です。

N-Gramインデックス方式には、次のような欠点があります。

検索ノイズが大きい: N-Gramインデックス方式には、検索時に大きなノイズを発生するという欠点があります。検索ノイズとは検索者が意図しないWebページが検索結果に混ざってしまう状態のことです。これは、単語辞書に基づく単語インデックスと異なり、単語が文中でどのように扱われているのかを詳しくは知ることが出来ないため、文章の内容を考えたスコアリングを行えないからです。
データベース量（インデックスサイズ）が大きくなる: N-Gramインデックス方式には、データベース量が大きくなるという欠点があります。(全文字数×N)の量の文字情報を保持しなければならず、単語インデックス方式に比べて数倍のテータ量を扱う必要があります。

特にこのインデックスサイズが大きくなるという欠点から、ウェブ全体を対象とする検索エンジンでN-Gramインデックス方式が使用されることはなくなってしまいました。

この記事が役に立った（または役に立ちそうだ）と思っていただけたなら、下のボタンから共有をお願いします。