【読書感想】『検索システム ― 実務者のための開発改善ガイドブック』メモ、感想
目次
はじめに
検索システムは、現代のアプリケーションやウェブサービスにおいて不可欠な要素です。SNSやECサイトをはじめ、大部分のwebサービスには検索システムが実装されており、効率的な検索体験を提供することは、ユーザーの満足度や利便性に直結します。
今回は、『検索システム ― 実務者のための開発改善ガイドブック』を読み、その内容をまとめ、私が感じたことを共有したいと思います。本書は実務に即したアプローチで、検索システムの設計や改善方法について解説しており、開発者目線でとても有益な内容が詰まっています。
読書時のメモ
第1章 イントロダクション
RDBへのクエリをそのまま検索システムとして使おうとすると生じる「キーワードの表記揺」、「ランキング」、「レイテンシ」、「フレーズ検索」について触れ、全文検索エンジンの導入となる章。
検索の方式
- 逐次方式: 検索対象から文字列のマッチングでキーワードを探し出す単純な手法。unixのgrepは逐次方式の検索。
- 牽引方式: データベースを構築する段階で「キーワードごとに対象となるドキュメントを並べた形式のデータ」を牽引として用意し、(この牽引を転置インデックスと呼ぶ)転置インデックスを利用して高速にドキュメントを探す手法
転置インデックスはデータ構造の一つ。転置インデックスを格納して、クエリで問い合わせるという性質上、検索エンジンはデータベースの一種と言える。
検索機能を作成するために考慮する必要があること
- データを検索エンジンにどのように格納するか(データモデリングやインデクシング)
- ユーザーに検索機能をどのように使ってもらうか(UI/UXや検索を支援するための機能)
- 検索機能に関係する多様な要素をどうやって管理していくか(プロジェクトマネジメント)
さらに、検索の歴史と検索システムの全体像と構成要素について前触れがある。
検索システムの構成要素として以下が紹介される。
- 検索エンジン
- インデクサ: 検索対象のデータの取得、適切な形式への加工、インデックスへの登録を担う
- クエリプロセッサ: ユーザーによって入力されたクエリの前処理を行う
- クエリポストプロセッサ: 検索結果の後加工を行う
- 「データ活用基盤」および「適合性コントローラー(Relevance Controller)」: より良い検索を実現するため、検索結果に対するユーザーのフィードバック、サービス提供側のニーズに基づいて検索システムを最適化する仕組み
(可能ならばここに図を置きたい)
2章から続くいくつかの章は「現代の検索エンジンがどのような課題を意識して実装されているか」を解説する章となる。
第2章 検索エンジンの仕組み
主題: 「そもそも全文検索エンジンがどのようなソフトウェアなのか、特に全文検索エンジンのデータ構造として最も広く使われている転置インデックスを利用した検索の大まかなフローを解説」
転置インデックスとは
前提として、逐次検索では実現の難しい要件を整理する
- 大規模テキストを高速に検索する
- フレーズ検索を行う(ある単語とある単語が隣り合うか、または近くに出現するかのようなパターン検索)
- 検索結果にランキングを付けたい
これらを実現する仕組みとして転置インデックス(inverted index)がある。
ドキュメントを牽引語に分割し、牽引語を行、ドキュメントIDを列として、「牽引語がドキュメントに出現すれば 1 、出現しない場合は 0」のような行列が最も簡単な転置インデックス。
「Webページのランキングアルゴリズム PageRank はラリー・ペイジらによって開発された」
↓ 牽引語に分割
「Web / ページ / の / ランキング / アルゴリズム / pagerank / は / ラリー / ・ / ペイジ/ ら / によって / 開発 / さ / れ / た」
(牽引後の分割方法は第3章を参照。形態素解析やN-Gramなどのアルゴリズムが用いられることが一般的。)
Doc1 | Doc2 | Doc3 | |
---|---|---|---|
web | 1 | 1 | 0 |
検索 | 1 | 1 | 1 |
アルゴリズム | 1 | 0 | 1 |
エンジン | 1 | 1 | 1 |
このような行列の転置インデックスを用いると、牽引語「web」が出現しつつ、牽引語「検索」も出現する AND検索や、どちらかが出現する OR検索、出現しないことを指定する NOT 検索が可能になる(検索処理を集合演算に落とし込めるということ。AND検索、OR検索、NOT検索はまとめてブール検索モデルという。)
上のような「牽引語-ドキュメント行列」の転置インデックスでは、大規模なテキストコーパスではほとんどの要素が 0 になってしまいメモリ効率が悪くなる。そのため、実用的な転置インデックスとして、**ターム辞書(term dictionary)とポスティングリスト(posting list)**を用いた転置インデックスがある。
- ターム辞書: は牽引語をkey、ポスティングリストをvalueとしたデータ構造。
- ポスティングリスト: その牽引語が出現しているドキュメントIDと出現位置のリスト。
{ "web" : [1:[3], 2:[1], 3:[6]], "検索" : [1:[4], 3:[1,7,10,16], 4:[14]] }
転置インデックスを用いた検索
- ユーザーが検索のために入力した文字列(検索クエリ)をターム(牽引語)に分割する(テキスト解析)
- ターム辞書を引き、検索対象のポスティングリストを見つける(辞書引き)
- ポスティングリストを先頭から走査してまーじ(ポスティングリスト走査) ポスティングリスト走査の詳細については第4章を参照
- 見つかった検索結果をランキングにして返す(ランキング)
この一連の流れはクエリ処理(query processing)と呼ぶ。
テキストデータ以外のインデックス
転置インデックスを利用すると、テキストデータの全文検索が行えることがわかりました。しかし、検索システムでは全文検索のみでは成り立たず、テキスト以外のデータの検索を組み合わせる必要があります。
e.g.) ECサイトの検索では、商品のカテゴリや価格による絞り込み(フィルタリング)やソート、ファセット機能(6章を参考)を組み合わせた検索が必須
e.g.) ホテルの空室検索では、予約したい日付による検索が必須
e.g.) レストランや店舗検索では、ユーザーの地理情報を考慮した検索を実現したい
無償で利用可能な検索エンジンの紹介
- Apache Lucene
単体ではサーバーとしての機能を持たないため、Apache Luceneをベースとした検索エンジンサーバーである、Apache SolrやElasticsearch を用いることが多い - Vespa
- Groonga
※ 転置インデックスの特徴
- インメモリでもディスクベースでも、そのハイブリットでも動作する
- 一台のマシーンで扱いきれない大規模なデータを扱う際に、水平分散によりスケールしやすい
第3章 テキスト解析
主題:「全文検索エンジンにおいてテキストがどのように扱われるか」を扱う
テキスト解説は大きな処理として考えると次のような流れになる
- 文字の正規化
- トークン化
- トークン列に対する各種処理
※ トークン(牽引語)はテキストを構成する基本的な単語や記号であり、タームは検索の目的でインデックスされる特定の単語やフレーズを指します。
対象となるドキュメントの言語によってトークンの決め方は異なり、それぞれに対して独自のアルゴリズムが発展している。
日本語のテキスト解析
日本語のテキスト解析には以下の二つの手法が用いられることが多い
- 形態素解析器を用いたテキスト解析
日本語の文章を人間が認識できる単語へと区切る手法。
OSS: MeCab
- 文字N-Gramを用いたテキスト解析
N-Gramでは入力された文章をN文字ずつ切り出して切り出してトークンとして出力する。
その他、Unicode正規化、ストップワード、類義語の展開など、検索エンジンの精度を高めるためのテキスト解析の工夫うが紹介されている。
第4章 ポスティングリストの走査とランキングのアルゴリズム
主題: 「転置インデックスからドキュメントを取得する際にどのようなアルゴリズムやロジックが使われているか」
これまでの章で全文検索エンジンの主な仕組みは、転置インデックス上でテキストをタームの集合として扱い、ターム集合から構築したポスティングリストを走査することで目的の検索結果を取得するというところまでわかりました。本章ではポスティングリスト走査とランキングのアルゴリズムについて解説されています。
ポスティングリストの走査
図での解説が必要なため、まとめられず。
ランキングを考慮したポスティングリストの走査
TF(term frequency)とIDF(inverse document frequency)を考慮しながらポスティングリストを走査することで、走査時の結果が重み付けされランキングを考慮した結果となる。
パフォーマンスの評価
検索システムにおいて重視されるのレイテンシ(Latency)とスループット(throughput)
クエリ処理時はレイテンシのみが重要視され、インデクシング時はレイテンシとスループットの両方が重視される。
また、大量のデータを扱う検索システムでは、ディスク I/O のレイテンシやスループットがパフォーマンスを下げる大きな要因になりうるため、注意が必要。
よって、検索システムのパフォーマンス試験を実施するに当たっては以下項目を見るのが良いとされる
- レイテンシ
- スループット
- CPUおよびメモリの使用量
- ディスク I/O の回数測定
- (Kubernetes環境では)ネットワークレイテンシやDNS名前解決などのTCP通信
キャッシュの利用
検索エンジン内に実装されるキャッシュの種類
- 検索結果のキャッシュ
- クエリ途中結果のキャッシュ
具体的には、ポスティングリストの積集合や絞り込み条件、ソート条件がキャッシュ対象。 - ドキュメントのキャッシュ
インデクシング元のテキストそのものをキャッシュし、ユーザーに返却するスニペットの生成を高速化するキャッシュ - etc…
検索結果のキャッシュは、キャッシュのヒット率が低いことが多く、不要なデータをキャッシュから追い出す処理(eviction)のオーバーヘッドがキャッシュ効率を上回ることが多い。クエリの特性に合わせて慎重にキャッシュ戦略を選ぶ必要がある。
また、リアルタイム性が重視されるシステムではそおそもキャッシュを導入しない方が良い場合もあるので注意。
キャッシュを導入する前に遅いクエリを分析するしてクエリそのものを改善できないかを検討することが重要。
インデックスの冗長化と分散検索
1台の検索エンジンでは扱いきれないほど大量のデータやトラフィックを捌く必要が出てきた場合、一部で障害が発生した場合でも処理を継続できるようシステムとデータを冗長化しておく必要が出てきます。インデックスのレプリケーション、シャーディングを検討できる。
第5章 検索エンジンへのデータ登録
主題: 「転置インデックスでの利用を前提として、そもそも検索エンジンに登録すべきデータをどのような手段で準備すればいいか」
ECの場合、検索結果で1件として扱いたいデータをどのように考えるか
- 1SKU(Stock Keeping Unit)で扱う: Tシャツのカラーが3パターンでサイズが3種類の合計9種類のTシャツをそれぞれ1つとして扱い、9件を検索結果にヒットさせる
- そのTシャツ商品を1件のデータとして扱う: 検索結果の件数はSKUの数ではなく、1件のみ。サイズ、カラーなどはその商品の属性として表示される
不要なものは登録しない
- 検索結果として十分な品質がないデータ
- 何年間も非アクティブなユーザーによるデータ
- 検索結果に一定期間表示されていないデータ
検索エンジンのデータを更新するタイミング
- リアルタイム: ECサイトで在庫の状況を反映する必要がある場合は必須
- バッチ更新
- 手動更新
データを更新する度に内部で小さな転置インデックスが作成されるため、リアルタイムよりバッチの方が検索効率がよくなる場合がある。また削除操作も、転置インデックス内に利用されないデータが蓄積されるため、検索効率への影響が出る可能性がある。
代表的なデータソース
- ファイルシステム:
- データベース: SQLを利用して収集。同期的 or 非同期的に検索エンジンにデータを反映させるかの判断が必要。また、非正規化データを扱う場合、一つのデータが更新された場合にそれに関連するすべてのデータを検索エンジンに反映させる際に注意が必要
- Web: クローラーによる収集など
ファイルシステムからのコンテンツ抽出にはApache Tikaが良さそう。PDF, PowerPoint, Word等のファイルからコンテンツとメタデータを構造化データとして抽出し、Apache Solar等の検索エンジンの転置インデックスとして登録する仕組みがすでに用意されている。
第6章 検索インターフェースと検索クエリの処理
検索システムへのユーザーからの入力は大きく分けて以下の二つ
- 検索クエリ: 検索したいキーワード、検索対象とするカテゴリなどのフィルタ条件、ソート指示など
- コンテキスト: ユーザーの行動履歴、性別、年齢、登録情報など
検索を「ユーザーが求める情報を得るための手段」と考えると、キーワードやフレーズでの全文検索は必ずしも最適な解決方法ではない。ECサービスでウィンドウショッピングする際は全文検索よりもカテゴリによるナビゲーションの方が検索行動をフォローする重要な機能である可能性がある。
ファセット
ファセットナビゲーションとは、ユーザーが検索クエリを明確にしたり絞り込みした入できるように、検索結果のドキュメントについているメタデータを集計して視覚的に選択肢を提示する仕組みです。
ファセットの役割の一つは、ユーザーの検索クエリの作成および修正をナビゲートすることです。ユーザーに対してファセットで簡単な絞り込みの手段を提供することで、少数のキーワードから検索を始め、少しずつ検索条件を絞っていくという検索体験を提供できる。
ファセットを再有する場合には、選択済みの項目をパンくずリストやチェックボックスとしてページに表示しておくことや、各ファセットのマッチする件数を表示することがとても重要。ユーザーが次の行動を判断する指標となる。
ファセットで集計するメタデータは、ユーザーの情報要求を明確にできるもの、検索効率を上げるようなものを慎重に選ぶ必要がある。メタデータの選択を誤るとユーザーに混乱を招くこととなる。
これから先は完全ネタバレ要約みたいになってしまうのでメモも公開しません。ぜひ以下でお買い求めください。
語彙
- テキストコーパス: 検索の対象となるテキストの集合
- 文章サロゲート: 検索結果のタイトル、要約、メタデータなどの情報の集合。検索結果が目的の文章であるかどうかをユーザーが判断するために使う情報。Google検索したときにタイトル周辺に出る情報。
- スラッシング(thrashing): スペルミスなど誤った検索クエリを解決しないまま検索を繰り返す行動。スラッシングの発生は検索システムにおけるアンチパターンであり、オートコンプリートはこれを防止する重要な役割がある
- クリックエントロピー: 同じ検索クエリを実行した異なる検索者が検索結果から選択したドキュメントの散らばり具合
- ストップワード: 頻繁に現れ、テキスト検索処理に関連する内容を もたないワードのこと。英語では "and", "or", "in" などで、日本語では ”て”, “に”, “を”, “は” などがストップワードにあたる。
感想
『検索システム ― 実務者のための開発改善ガイドブック』は、理論と実務の両方をバランスよくカバーしており、エンジニアとして検索システムを構築する際に非常に役立つ内容が満載でした。
本記事のメモでは言及していませんが、後半部分は検索システムのプロジェクト管理や、検索クエリの処理(機械学習のアプローチも含む)など検索体験向上の様々なアプローチが紹介されています。
より洗練された検索機能を提供できるよう、検索システムに関する理解を深めたい方には、ぜひ一読をお勧めします!
ちなみにQiitaで100いいね近くでバズっている以下記事も、出典明記されていませんが、構成や具体例が一致しているためこちらの本の要約になっているようです。