検索エンジンを作る

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

この記事を読むのに必要な時間:およそ 3 分

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

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

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

著者プロフィール

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

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

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

著書

コメント

コメントの記入