検索エンジンを作る

第6回N-gramと形態素解析との比較

これまでに、N-gram形態素解析の2つの検索エンジンの、見出し語の切り出し方法を説明しました。今回は、2つの見出し語の切り出し方法を比較し、それぞれの得意な点、不得意な点を明らかにしていきます。

2つの手法の概要

はじめに、2つの手法をおさらいしてみます。

形態素解析

  • 検索対象のテキストを形態素解析を行い分かち書きを行う
  • 分かち書きした単位を見出し語として転置インデックスを作成する
  • 転置インデックスを元に検索を行う

N-gram

  • 検索対象のテキストをN文字単位の文字列片に分解する
  • 分解した文字列片を見出し語として転置インデックスを作成する
  • 検索語をN文字単位の文字列片に分け検索を行う
  • 文字列の出現位置情報を利用すれば、漏れのない完全一致の検索が可能

大きな違いは、⁠転置インデックスの見出し語をどのように作るか」というプロセスが異なる点です。形態素解析は構文解析を行って分かち書きを行うのに対して、N-gramでは機械的にN文字の文字列片に分けるという処理となります。

次に、このような見出し語の切り方が、実際の検索性能に対してどのような影響を及ぼすかについて見ていきましょう。

完全一致の検索

まずは、完全一致の検索についてです。形態素解析では、対象のテキストを形態素解析を行って分かち書きを行い、分かち書きした単位の単語を見出し語として転置インデックスを作成します。このため、分かち書きされていない単位での検索が苦手です。このあたりの事情については前々回解説した通りです。

一方、N-gramでは、機械的に検索対象のテキストをN文字の長さの文字列に区切り、この文字列を見出し語として転置インデックスを作成します。こちらについては前回詳しく解説を行いました。N-gramは論理的に完全一致による検索結果が保証できる点が大きな特徴です。

特殊用語

形態素解析は、自然言語を構文解析して分かち書きを行う方法です。形態素解析が利用する辞書に存在しない言葉については、どのように分かち書きされるかは形態素解析のロジックに依存するため、結果が保証しにくいという事情があります。とくに人名、専門用語、新語、造語、略語などについては形態素解析の辞書に存在しないことが考えられます。このような特殊用語については、検索結果が保証できないという問題があります。

もちろん、辞書のメンテナンスを行い形態素解析辞書に問題の語を加えれば、検索は可能になります。しかしそのためには、転置インデックスを再度作り直さなければなりません。一般にインデックスの再作成は時間がかかる処理であるため、即座には対応できない点にも留意が必要です。

一方、N-gramでは、形態素解析で問題となる人名、専門用語、新語、造語、略語についても他のテキストとまったく同様にN文字の長さの文字列に区切り、この文字列を見出し語として転置インデックスを作成します。このため、人名、専門用語、新語、造語、略語などであっても確実に検索が行えるという特徴があります。

検索ノイズ

このように話を進めると、完全一致の検索や特殊用語の扱いではN-gramの方が優れているようにも思われますが意外な落とし穴があります。じつはN-gramの方式は厳密すぎて逆に検索ノイズを拾ってしまうという問題があるのです。たとえばN-gramの方式では「京都」という言葉で検索を行うと「東京都」という文字列を含む文書も検索されてしまいます。これは「東京都」の中に「京都」という文字列が含まれているためです。

一方、形態素解析の方式では、文中に「京都」という語が登場した場合には「京都」という見出し語で転置インデックスに登録され、⁠東京都」という語が登場した場合には「東京都」という見出し語で転置インデックスに登録されます。結果として「京都」という語で検索した場合には「東京都」を含まない文書が検索できるのです。

N-gramのロジックとしては「東京都」には「京都」という文字列が含まれているため正しい動作ですが、意味的には間違いと考えられます。このような例は、他にも「スパ」「フランスパン」⁠アスパラガス」⁠エキスパート」⁠スパゲッティー⁠⁠、⁠テリヤ」「テリヤキ⁠⁠、⁠ルパン」「ダブルパンチ⁠⁠、⁠ミント」「バドミントン」などがあります。

検索ノイズが現れる場合には、N-gramでは次の検索式(FINDSPOTの検索式)のように「京都」の検索結果に「東京都」を含めないという条件で絞り込むめば対応が可能ですが、絞り込みの手間が煩雑であるという欠点があります。

京都 NOT 東京都

活用語尾対応

⁠着物を着るという検索文字列で「着物を着たという文字列を含む文書を検索することを考えてみましょう。N-gramでは異なる表現であるために、このような活用語尾が変化したバリエーションに対する検索は苦手です。一方、形態素解析では分かち書きと同時に、文の構成要素の文法的な解析を行っているため、⁠着た」という語を「着る」と活用形を修正した上で転置インデックスを作成する処理は比較的容易です。このような処理を行えば、⁠着物を着る」という検索文字列で「着物を着た」という文字列を含む文書の検索が可能になります。

英語では名詞の単数形と複数形の違い、動詞の活用なども全文検索では対応が必須と考えられますが、活用形を統一した上で転置インデックスを作成することで、活用語尾が異なっていても検索が行えるようになります。

活用形を修正して転置インデックスを作成する方法は、活用語尾が異なっていても検索が行える一方で、正確な完全一致での検索が行えなくなるため、トレードオフの関係がある点に注意する必要があります。

複数言語対応

一般的に形態素解析処理は、日本語なら日本語用の形態素解析エンジンといった具合に特定の言語を対象としたものとなります。たとえば、日本語の形態素解析エンジンでは中国語や韓国語などの形態素解析を行うことはできません。形態素解析による方法では複数の言語で記載された文書を扱うのが苦手なのです。

一方、N-gramによる方法では、文字列を機械的にN文字の単位で切り出して見出し語を作るため、言語によって見出し語の作成がうまくいかないということがありません。つまり、N-gramの方法を用いると複数言語対応が可能なのです。

検索対象の文書が複数の言語を含む場合には、このあたりの事情を考慮する必要があります。

転置インデックスのデータサイズ

大量の文書を検索対象とする場合には、転置インデックスのサイズがハードウェアの面で問題となります。これまで何度も説明しているように、形態素解析の方法では、見出し語は単語単位となります。一方、N-gramではN文字の文字列素を機械的に作成して見出し語を作ります。この見出し語の数が転置インデックスのデータサイズを決める大きな要素となります。

「長時間の講演」という文字列を例として考えてみます。形態素解析を行って分かち書きをすると、⁠長時間」⁠の」⁠講演」3つの単語に分けられます。つまり3つの見出し語に転置インデックスの情報が記録されます。

一方N-gramの方式ではNを2として考えてみると、⁠長時」⁠時間」⁠間の」⁠の講」⁠講演」5つの文字列素となります。これを見出し語として転置インデックスに登録することになります。形態素解析での見出し語が3つであったのと比べると大きな転置インデックス情報が必要だということが解ります。

Nを3とした場合でも、⁠長時間」⁠時間の」⁠間の講」⁠の講演」4つの文字列素となります。これでも形態素解析の場合と比べると多くの転置インデックスの情報だということが判ります。Nを4にすると、⁠長時間の」⁠時間の講」⁠間の講演」と3つの文字列素となり、やっと形態素解析の見出し語数と並びました。

ただし、N-gramの処理ではNを大きくするとN文字未満の文字列の検索が行えなくなってしまうので、N文字より少ない長さの文字列素の見出しでも転置インデックスを作成したり、転置インデックスのデータ構造を工夫してN文字未満の文字列も検索できるようにするなどの対処が必要です。しかしいずれも転置インデックスのデータサイズがさらに大きくなることにつながります。

一般に、転置インデックスのデータサイズのコンパクトさの面では、軍配は形態素解析の手法に上がると考えられます。

転置インデックス作成時間

次に転置インデックスの作成時間について比較してみます。前述のように形態素解析の方が転置インデックスのデータサイズが小さいため、純粋な転置インデックスの作成時間の面では形態素解析の方が短い時間で済みます。しかし、形態素解析の方法では、転置インデックス作成の前処理として、比較的計算量の多い形態素解析という処理により、分かち書きを行わなければなりません。

つまり、形態素解析とN-gramの見出し語の数の差に相当する転置インデックスの格納時間を、形態素解析の処理時間が上回るようならば、形態素解析の方が、転置インデックスの作成に時間がかかってしまうことになります。どちらが処理時間が速いかは一概に比較できず、実装に依存するという結論となります。

まとめ

これまでのポイントを整理すると次のようになります。

ポイント形態素解析N-gram
完全一致の検索結果が保証できない確実に検索可能
特殊用語形態素解析辞書に用語追加が必要辞書のメンテナンスが不要
検索ノイズ発生しにくい検索ノイズがある
複数言語対応特定の言語に形態素解析が依存可能だが活用語尾対応ができない
転置インデックスサイズ小さい大きい
インデックス作成時間実装依存実装依存

たとえば、日々新たな新語や略語が生まれるようなニュースや新聞などのマスコミやブログなどでは、形態素解析辞書のメンテナンスのいらないN-gram方式が向いています。また、専門用語が多用され、完全一致での検索が必須とされるような化学、機械、医学、法律のような分野でもN-gram方式が向いていると考えられます。

一方、検索ノイズを避けて、手軽に検索したいという用途には形態素解析の方法が向いています。CD-ROMなどの容量の限られたメディアに転置インデックスを保存するような場合にも、データサイズの小さい形態素解析の方法が向いています。


このように、形態素解析とN-gramでは、それぞれ得意な面と不得意な面があるので、どちらが一方的に優れているというのではなく、目的や用途に応じて検索エンジンの方式を選択するのがお勧めです。さらに、多くの検索エンジンでは、それぞれの基本ロジックの持つ欠点を克服するために、独自の工夫を凝らしているものも多くなっています。たとえばFINDSPOTには、活用語尾の変化に対応した検索も行えるように、次回解説を行う予定の曖昧検索機能があります。このような、欠点を補完する機能も、検索エンジンの方式を選択する際の大きなポイントです。

おすすめ記事

記事・ニュース一覧