検索エンジンはいかにして動くのか?

第6回 日本語における転置索引

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

はじめに

前回までの数回では,転置索引の論理的構造や実装のための具体的なデータ構造について見てきました。今まで特に触れてきませんでしたが,これらの説明はすべて英語の文書を対象としたものでした。

英語は単語の間に空白を置くため,文を空白で区切ることで単語を抽出することができます。しかし,日本語の文では各単語はつながっているため,日本語で転置索引を構築する場合は英語と同じように,文を単語や文字の並びに分けてあげる必要があります。今回は,その方法について説明します。

文を単語や文字の並びに分割する方法

日本語のように単語が空白で区切られていない文を単語に分割するには,大きく分けて以下の2つの方法があります※1)⁠

  • 形態素解析による分割
  • N-gram(q-gram)による分割

以下では,それぞれについて説明していきます。

※1
文を分割することを,英語では「segmentation」「tokenization」と言います。厳密には意味が異なりますが,転置索引の文脈ではあまり区別して使われていないようです。また,文を分割してできた各単語をターム(term)やトークン(token)と言います。

形態素解析による分割

形態素解析(Morphological Analysis)とは,文を言語で意味を持つ最小単位の"形態素"の列に分割し,それぞれの品詞を判別することです。⁠全文検索エンジン」を形態素解析で分割した場合は,⁠全文」⁠検索」⁠エンジン」となります。しかし,日本語での文の書き方は何通りもあることから,形態素解析を正確に行うことは非常に難しい問題となります。

現在は,手作業により文を分割した(正解)データを使って学習し,未知の文に対して文の区切れ・品詞を予測するという機械学習による手法が主流となっています※2)⁠このような手法により,現在の形態素解析の精度は90%程度と言われています。つまり,ほぼ間違いなく区切りと品詞判定を行うことができるということです。しかし,ブログなどの話言葉での表現を多く含むような文に対しては,精度は大分下がってしまうと言われています。

※2
隠れマルコフモデル(Hidden Markov Model)や条件付き確率場(Conditional Random Field)といった確率モデルが使われています。日本語における形態素解析エンジンとしてはMeCabChasenが有名で,MeCabでは後者が,Chasenでは前者が使われています。これらモデルによる学習と形態素解析用の辞書を利用することで,文の区切れ・品詞を予測します。

N-gram(q-gram)よる分割

N-gramとは文字のN文字の部分列のことを指し,Nには2や3などの数値が入ります※3)⁠

N-gramによる分割とは,文を単語の境界とは関係なくN文字ずつに分割することを言います。⁠全文検索エンジン」を2-gram(bi-gram)で分割した場合は,⁠全文」⁠文検」⁠検索」⁠索エ」⁠エン」⁠ンジ」⁠ジン」となります。この方法は,言語に依存しない機械的な方法としてアジア圏の言語を中心に広く使われています。

※3
N=1の場合をuni-gram(ユニグラム)⁠N=2の場合をbi-bram(バイグラム), N=3の場合をtri-gram(トリグラム)と呼びます。

各分割方法の利点と欠点

各分割方法で分割されたタームにより構築された転置索引の利点と欠点についてまとめておきます。

形態素解析による転置索引の利点と欠点

利点は,文に対して辞書に登録するターム数が少なくなることから,N-gramに比べて辞書,転置リストのサイズが小さくなり,また構築処理,検索処理も速くなります。

欠点は,検索漏れが生じてしまうことになります。検索漏れとは,実際にクエリが文に含まれているにもかかわらず,見つけられないことを言います。つまり,検索クエリと形態素解析で区切られた単語が正確に一致していないことから起きてしまいます。

たとえば,⁠チョコレート」を形態素に分割するとそのまま「チョコレート」となりますが,⁠チョコ」では「チョコレート」が入った文章を検索することができません。形態素解析の辞書に含まれていないような新語や,口語で使われる単語においても同様の現象が起きます。

N-gramによる転置索引の利点と欠点

利点は,形態素解析の場合と異なり,検索漏れが発生しないことです。これは,N-gramではすべての文字部分列をタームとして登録するため,検索キーワードが文章に含まれていれば必ず見つけることができます。しかし,先ほどの「全文検索エンジン」の例からもわかるように,同じ文からでも生成されるタームの数は形態素解析の場合と比べて多くなります。

欠点としては,上記のことから,辞書のサイズ,転置リストのサイズが大きくなってしまい,構築処理・検索処理が形態素解析の場合と比べて少しだけ遅くなってしまいます。また,N-gramは単語境界を考慮しないことから,⁠東京都」を含む文に対して,⁠京都」で検索ができてしまうなどの問題もあります※4)⁠

※4
この問題は,単語境界を別に持つことで解決することができます。

日本語文書における転置索引の実装

現代の検索エンジンは,文の分割方法に依存しないように設計されることが多いです。これにより,文書の特性に応じて形態素解析とN-gramを使い分けられるからです。そのように実装するには,タームの位置(文書の先頭から何単語目かではなく,文字の位置のオフセット(文書の先頭から何文字目かでインデックスするようにすれば,転置索引の構築部分のコードは形態素解析やN-gramを意識せずに書けます。

まとめ

今回は,日本語の文書で転置索引を構築する場合に必要である,文をタームに分割する方法について説明しました。これには形態素解析とN-gramの2つの方法が存在し,それぞれの利点・欠点について簡単に紹介しました。これで,英語の場合と同じように日本語でも転置索引が構築できるようになりました。

参考文献
[1]
Introduction to Information Retrieval
C. D. Manning, P. Raghavan,H. Schutze , Cambridge University Press, 2008

著者プロフィール

山田浩之(やまだひろゆき)

日本IBM株式会社を経て,ヤフー株式会社等で検索エンジンの開発に従事。現在は大学院でデータベース・情報検索の研究を行う。また,オープンソースで全文検索エンジンLuxやデータベースマネージャLux IOの開発を行っている。

コメント

コメントの記入