はじめに
とあるよく晴れた日、夢の中で 全文検索エンジンの裏側ってどうなっているの？ と不意に母に聞かれました。
「なんでそんな言葉知ってるんだ、、くそぉ(心の声)」
「えっとね、、うんとね、なんというか、その、、、笑」
5月から検索システムのリニューアルチームに配属されたにも関わらず、説明できないのは流石にまずいと思ったので、50代の母親にも理解してもらえるように、要点をまとめていきます。
こんな方には是非読んでいただきたいです。
- 検索システムの裏側を知りたい方
- 全文検索エンジンを使用したサービスの開発に従事している方
- 夢の中で母に質問された方
それでは検索システムの大枠から順に説明していきます。
(重要なキーワードは太文字にしているので、さらに詳細に知りたい方は検索してみてください。)
検索エンジンの概要
構造化されていないテキストから、テキストから特定のキーワードに合致する箇所を全て見つけ出すことを、全文検索といいます。
全文検索を実現する手段
全文検索を実現する手段は大きく分けて、「全文検索エンジン」 「逐次検索」 の2つがあります。
全文検索エンジン
事前に索引（インデックス）を構築しておくことで、全文検索を実現するソフトウェアのことを、全文検索エンジンと呼びます。代表的な全文検索エンジンには、Apache SolrやOpenSearchなどがあります。そして全文検索エンジンのデータ構造として転置インデックスが現在最も広く使われていいます。(この後詳しく説明します。)
逐次検索
テキストの先頭から末尾まで逐次スキャンし、与えられたキーワードまたはパターンに合致する箇所を全て洗い出すのが、逐次検索です。逐次検索方式の代表的なソフトウェアは、grepコマンドです。検索対象のテキストの集合 (テキストコーパス) が比較的小規模であれば高速に動作します。
ではなぜ現代の検索システムでは逐次検索だけではなく、全文検索エンジンを使っているのか。それは、検索システムを構築するにあたり、逐次検索では難しい次のような検索の要件の壁に、しばしばぶち当たるからです。
- 大規模テキストを高速に検索したい。数億単語以上からなるテキストコーパスを逐次検索するのは、あまり現実的ではない
- フレーズ検索を行いたい。(フレーズ検索とは、ある単語とある単語が隣り合っているか、または数単語以内の近くに出現するようなパターンを検索することを指します。)
- 検索結果にランキング等の付加価値をつけたい。検索にヒットした結果が多数ある場合、それらを人間が1つずつ確認して並び替えるのは非常に手間です。またランキング機能などをつける場合、検索したユーザーが求める結果ほど上位に並ぶようなに、適切に並び替える必要があります。
こうした「逐次検索方式では難しい検索の要件」を実現できる仕組みとして、転置インデックスがあります。
転置インデックスとは
先述しましたが、現在ほとんどの検索システムは転置インデックスという牽引構造を利用して、速い検索を実現しています。
転置インデックスは、検索システムにおいて効率的な単語検索を実現するためのデータ構造です。転置インデックスは、単語（またはトークン）とそれが出現する文書（または文書内の位置情報）の関連を逆転させて格納します。
転置インデックスの例
転置インデックを作成するにあたり、３つの手順が必要になります。
- ドキュメントを用意する
- 検索に使える単語として、単語毎に分割する
- 単語が出現したか否かを判定する
1. ドキュメントを用意する
下記の3つのドキュメントが検索エンジンの検索対象として存在していると定義します。
- Doc 1
私はWebの検索エンジンやアルゴリズムについて詳しく知りたい。 - Doc 2
検索エンジンには、Web検索、メール検索、ECサイトの商品検索など、様々な用途がある。 - Doc 3
高速に動作し、良いランキング結果を返すアルゴリズムが、検索エンジンにはとても重要である。
2. 検索に使える単語として、単語毎に分割する
先ほどのDoc1~3を、ユーザーが検索のためのキーワードに使える単語として、下記のように単語毎に分解します。これは本であれば 索引語です。
括弧内の数字は、その単語がドキュメント中で何番目に現れたかという、出現位置の情報です。
※ユーザーが尾文字と小文字の違いを意識せず検索できるように、英単語は小文字に統一することとします
- Doc 1
私(1)/は(2)/web(3)/の(4)/検索(5)/エンジン(6)/や(7)/アルゴリズム(8)/に(9)/ついて(10)/詳しく(11)/知り(12)/たい(13)。 - Doc 2
検索(1)/エンジン(2)/に(3)/は(4)/、(5)/web(6)/検索(7)/、(8)/メール(9)/検索(10)/、(11)/ec(12)/サイト(13)/の(14)/商品(15)/検索(16)/など(17)/、(18)/様々(19)/な(20)/用途(21)/が(22)/ある(23)/。(24) - Doc 3
高速(1)/に(2)/動作(3)/し(4)/、(5)/良い(6)/ランキング(7)/結果(8)/を(9)/返す(10)/アルゴリズム(11)/が(12)/、(13)/検索(14)/エンジン(15)/に(16)/は(17)/とても(18)/重要(19)/で(20)/ある(21)/。(22)
3. 単語が出現したかを判定する
単語がドキュメントに出現していれば1、出現していなければ0とする。
それぞれ要素とする下記の図のような行列が、転置インデックスのイメージです。
| Doc1 | Doc2 | Doc3 | |
|---|---|---|---|
| web | 1 | 1 | 0 |
| 検索 | 1 | 1 | 1 |
| アルゴリズム | 1 | 0 | 1 |
| エンジン | 1 | 1 | 1 |
図1(転置インデックスのイメージ)
転置インデックスを使った検索のイメージ
転置インデックスを参照することで、ある索引語がどのドキュメントに出現しているかがわかります。
たとえば先ほどの図1を見れば、索引語「web」が出現するドキュメントは、行列の1行めで要素が1になっている Doc 1、Doc 3 の2つであることがわかります。
つまり、図1のような「索引語 - ドキュメント行列」を使うことで、索引語に対する検索が可能になります。
複数の索引語を指定して、それら全部もしくは一部が出現するドキュメントを検索することも可能です。 (AND検索・OR検索・NOT検索)
実用的な転置インデックスの構造
より現実的な転置インデックスは、 ターム辞書と ポスティングリストと呼ばれる2つのデータ構造によって構成されています。
タームとは
タームとは、転置インデックスを検索するときの最小単位であり、先ほど索引語と呼んでいたものに相当します。このタームを並べたものがターム辞書です。
ポスティングリストとは
ポスティングリストとは、それぞれのタームから識別子(ドキュメントID)を下記の図2のように格納するリストです。
| ターム辞書 | ポスティングリスト |
|---|---|
| web | Doc1:[3]Doc2:[6] |
| 検索 | Doc1:[5],Doc2:[1,7,10,16] |
| アルゴリズム | Doc1:[8],Doc3:[11] |
| エンジン | Doc1:[6],Doc2:[2],Doc3:[15] |
図2(実用的な転置インデックスの構造)
実用的な転置インデックスの構造とは
上記の図２と、転置インデックスのイメージとして記載している図1との一番の違いは、「タームが出現しない」 という情報を保持しないで済むことです。
それにより効率の良いデータ構造となっています。
また図2ではポスティングリストの各要素を「ドキュメントID:ターム出現位置のリスト」で表現している点にも注目してください。
このようにポスティングリストには、ドキュメントID以外にも、タームの出現位置や、さらに文字位置(元のテキストの何文字目に出現したか)といった付加情報を保持させることがあります。
こららの付加情報は、主に フレーズ検索などで使われます。
フレーズ検索
フレーズ検索とは、ドキュメント中で複数のタームが隣り合った、または近接する位置に出現するパターンを検索することです。
たとえば、「web」「検索」という 2 つのタームが、ドキュメント中の離れた場所ではなく「全文検索」で連続して出現するドキュメントのみを検索したい場合に使用します。
例えば図2では「web」と「検索」はDoc1とDoc2両方に出現しますが、隣り合って出現しているのはDoc1のみです。
つまり「web検索」と検索してヒットするのはDoc1のみになります。
転置インデックスを使った検索の流れ
一般に転置インデックスを用いた検索は以下のような流れで実行されます。
- ユーザーが検索のために入力した文字列をタームに分解する (テキスト解析)
- ターム辞書を弾き、検索対象のポスティングリストを見つける (辞書引き)
- ポスティングリストを先頭から走査してマージ (ポスティングリスト走査)
- 見つかった検索結果をランキングして返す (ランキング)
1. テキスト解析
テキスト解析は、どのような言語で書かれたドキュメントを対象とするかによって異なる部分もありますが、大きな処理として考えると次のような流れになります。
- 文字の正規化
- トークン化
- トークン列に対する各種処理
文字の正規化
現在の多くのコンピューターシステムでは文字集合として Unicodeが利用でき、その文字符号化形式としては UTF-8 を用いています。Unicodeでは、互換性などの目的から、実質的に同じ文字を複数の表現で表せる仕組みが用意されています。これらの文字の等価性の定義および統一の手法はUnicode正規化としてUnicode標準で定義されています。
トークン化
転置インデックスの説明では、検索対象となる単語などを「ターム」と呼んでいました。転置インデックスにはタームが登録されていることからわかるように、ユーザーが検索クエリに入力した単語などは、タームとして一致しているかどうかを基準として検索が実行されます。
一方、ドキュメントや検索クエリに出現する単語などのことは、タームとは区別して 「トークン」 と呼びます。テキスト解析の対象となるのもタームではなく、トークンです。
日本語のテキスト解析
英語とは異なり、日本語にはスペースのようなわかりやすい単語の区切りはありません。日本語の文章のテキスト解析として用いられる手法には次の2つがあります。
- 形態素解析を用いたテキスト解析
- N-gramを用いたテキスト解析
形態素解析
形態素解析は、自然言語処理の一部であり、文や文書を形態素（言語の最小意味単位）に分割し、それぞれの形態素の品詞や意味情報などを特定するプロセスです。処理内容は下記の順で行われます。私はりんごを食べるを例に説明します。
-
形態素の分割
入力文: 私はりんごを食べる
形態素: [私] [は] [りんご] [を] [食べる] -
品詞の特定
形態素: [私] [は] [りんご] [を] [食べる]
品詞: [代名詞] [助詞] [名詞] [助詞] [動詞] -
活用形や語感の特定
形態素: [私] [は] [りんご] [を] [食べる]
活用形: [―] [―] [―] [―] [基本形]
形態素解析によって、入力文が形態素ごとに分割され、各形態素には品詞や活用形などの情報が付与されます。これにより、文の構造や意味を理解しやすくなります。形態素解析は、テキスト処理や自然言語処理の多くのタスクにおいて重要な前処理ステップとなります。
またこれら一連の処理を行うソフトウェアのことを指して 形態素解析器と呼びます。主な形態素解析器には下記のようなものが挙げられます。
- MeCab
- Kuromoji
- Sudachi
(本プロジェクトで使用しているkuromojiがどんな形態素解析をしているかを、すぐに確認できるこちらのサイトが非常に便利なので、興味がある方は使ってみてください)
N-gram解析
N-gram解析は、テキストをN個の連続した形態素や文字の組み合わせに分割する手法です。再び私はりんごを食べるを例にN-gram解析を説明します。
- 文字N-gram解析
文字N-gramでは、テキストを個々の文字の組み合わせに分割します。例えば、2文字N-gramを使う場合、入力文は以下のように分割されます。
：「私は」「はり」「りん」「んご」「ごを」「を食」「食べ」「べる」 - 単語N-gram解析
単語N-gramでは、テキストを個々の単語の組み合わせに分割します。例えば、2単語N-gramを使う場合、入力文は以下のように分割されます。
：「私は」「はりんご」「りんごを」「を食べる」
N-gram解析は、テキストデータ内のパターンや共起関係を把握するために使用されます。例えば、N-gram解析を用いることで、文章内の一連の単語の順序や特定のフレーズの出現頻度を把握することができます。
2. 辞書引き
入力された検索クエリに含まれるすべてのタームについてターム辞書を引き、そのタームに対応するポスティングリストのヒットした行をを見つけます。このヒットした行が、次のポスティングリストの走査における検索対象になります。
辞書引きの際の検索方法は大きく分けて2種類あります。
順次検索
順次検索は、辞書内の単語や用語を順番に比較しながら検索する方法です。
辞書内の単語がアルファベット順や他の基準に従って並んでいる場合、順次検索では最初の単語から順に比較して目的の単語を見つけるまで繰り返します。
順次検索は簡単で実装が容易ですが、辞書のサイズが大きくなると効率が低下する傾向があります。
二分検索
二分探索は、ソートされた辞書を対象に行われる検索方法です。
辞書の中央の単語を選択し、目的の単語と比較します。もし目的の単語が選択した単語よりも前にある場合、前半部分の単語に対して同様の操作を繰り返します。もし目的の単語が後ろにある場合、後半部分に対して同様の操作を繰り返します。これを繰り返すことで、効率的に目的の単語を見つけることができます。
二分探索は辞書が事前にソートされている必要がありますが、効率的な検索が可能です。
ポスティング走査
辞書引きが終わって検索対象のポスティングリストが得られたら、これを頭から走査することで、検索結果となるドキュメントのIDが得られます。一般には複数のタームに対応した複数のポスティングリストが得られるので、それらをANDやORでマージした結果を返す必要があります。
3. ランキング
全文検索の対象となるドキュメントが膨大になると、ポスティングリスト走査で得られた結果をそのまま返しても、ユーザーにとってあまり意味がない検索結果になることが多くなります。そこで、検索クエリとドキュメントの 類似度 を計算することにより、検索結果を適切な順番にソートする必要が生じます。このランキングには、タームが個々のドキュメントに出現する回数や、個々のタームが検索対象のドキュメント全体でどれくらいの出現頻度があるかといった情報を利用します。
計算方法としては、 コサイン類似度や TF-IDFなどがあります。
データを入手して検索できるようにするまで
一般に、データを入手してから検索エンジンに登録してユーザーが検索できるようになるまでの流れは、以下の3つのフェーズとして考えられます。
- データを入手
- 入手したデータを検索エンジンに合わせて加工
- 加工したデータを検索エンジンへ登録
上記の3つのフェーズは、各フェーズの頭文字をとって ETLと呼ばれています。
さいごに
以上が主に検索システムの大枠の流れになります。
検索のインターフェースの方の説明も書くつもりでしたが、長くなってしまうので、別の記事にして投稿しようかなと思います！(多分)
また今回の記事を書いたことで、ランキング結果に使用するコサイン類似度やTF-IDFについての知識がまだまだ足りないことにも気づきました。
さらに深ぼってアウトプットできたらと思います。
記事というより、備忘録的なものになってしまいましたが、最後まで読んでいただきありがとうございます！