🦔

TF-IDFを使った簡単な検索システムを作ってみた

2023/07/22に公開

全文検索

tech

はじめに

初心者が全文検索エンジンに興味を持って独学し、簡単な検索エンジンを実装するまでをまとめてみました。検索エンジンのこと全然知らないけど興味はある、簡単な成果物を作成したいと思っている方々の一助になれば幸いです。

何をやったの

全文検索の技術書を読んだ内容をまとめてみました。
実践編として簡単な検索システムを作成しました。ポケモンのタイプを入力すると該当するポケモンが表示されます。

検索システム本

検索システム実務者のための開発改善ガイドブックを検索エンジニアの方から勧められました。
二部構成で第一部は初心者向けの検索エンジンの基礎的な内容、第二部は中級者向けの検索エンジンをより良くするためのエッセンス。第1~7章はとっつきやすいのですが、第8章はPJ立ち上げの話、第9章以降は検索エンジンの質を上げるための検討事項を具体的な数式や機械学習を交えて解説しています。特に第9章以降は初心者が詳細まで理解するのは難しい部分も多く、筆者も中級者以上向けと記載しているので、頭の片隅に置いて置いて必要になったら再度読み直せばいいかと思います。
今回は検索エンジンの仕組みの基礎である第1~5章のみを解説していきます。

検索エンジンの役割

HCIR（Human-computer information retrieval）という研究分野において検索エンジンに要求するものが定義されており、いい内容だと思うので載せておきます。

ドキュメントだけではなく、「意味のある情報」も提供しなければならない
人間の知的努力を必要とし、それに報いるべきである
検索者の進化に合わせて検索エンジンも進化すべきだ
スタンドアローンのサービスではなく、協働ツールとしての情報生態系の一部を目指すべき
情報のライフサイクル全体をサポートするべき
エンドユーザ、特に専門家のチューニングをサポートするべきである
魅力的で楽しく使えるものであるべき

良い検索とは

ユーザの情報要求を効率良く満たすことができるのが良い検索である。
ではどうすればいいかというと、ユーザの情報要求の種類とモチベーションについて理解する必要がある。情報要求の種類は大きく分けて、探したいものが明確になっている、なっていないの状態がある。明確になっている場合の検索はルックアップベースの検索と呼ばれ、なっていない場合は探索的検索と呼ばれ検索の過程でユーザ自身が学習や目的を具体化していく行動をとる。モチベーションは能動的に解決したいユーザもいれば、受動的に解決したいユーザもいる。
ユーザの状況によって検索エンジンに対して要求するものが常に変化することを覚えておく必要がある。

第１章　イントロダクション

若手エンジニアが検索システムを導入するストーリーが描かれている。
検索の方法には「逐次検索」と「索引検索」があり、検索エンジンは索引検索を利用して高速に目的地にたどり着くことができる。検索エンジン転置インデックスを利用して実現している。ユーザの目的を見定めてカスタマイズすることが重要。検索エンジンの歴史にも触れている。東芝が1961年に日本に初めて落札し導入した。
検索システムのコンポーネント郡。

インデクサ
テキスト処理をして同義語や表記揺れなどを補正して、ドキュメント用のデータベースに登録する。
クエリプリプロセッサ
検索クエリを加工する。例えばブーストと呼ばれる特定のワードでの検索スコアを上げたり、結果を絞り込むフィルターなどの機能を有する。
クエリポストプロセッサ
検索エンジンの結果を加工する。クエリプリプロセッサとの違いは検索クエリを加工するのか、検索結果を加工するのか。
データ活用基盤と適合性コントローラ
データ活用基盤を使ってユーザが検索した結果を収集・分析する。適合性コントローラは結果が情報要求にどれだけ適合しているのかを評価する。

第2章　検索エンジンのしくみ

検索エンジンが逐次検索で難しい問題の問題の解決のために開発された。

大規模テキストの高速検索
数十億の単語を逐次検索するのは厳しい
フレーズ検索
関連する単語を含む結果も表示したい
ランキング
ヒット率が上位のドキュメントは検索結果の上位に表示したい

転置インデックスはターム辞書とポスティングリストという２つの要素から構成されている。
ターム辞書は検索クエリの最小単位、ポスティングリストはドキュメントIDなどを含む。
ターム辞書は辞書順にソートされたり、ハッシュテーブルで管理されたりする。ハッシュテーブルは高速に検索できるが、「田中*」などの曖昧検索ができない問題がある。辞書順で並べれば2分探索も可能だし、曖昧検索も対応可能。登録時はハッシュテーブル、検索時は辞書順でソートした結果を使うことが多い。
ポスティングリストは巨大なのでメモリに乗らない問題がある。溢れた情報をストレージに保存して、定期的にインデックス郡をマージしてあげる。

転置インデックスを使った検索の流れ

テキスト解析でタームに分割
タームからポスティングリストを見つけて走査する
検索結果からランキングを作成
テキストデータ以外にもカテゴリ、数値や日時、位置情報などのインデックスも存在する。

検索エンジンとして有名なもの

Apache Lucene
一番の有名どころ。ElasticsearchやApache Solrにも使われている。
Vespa
Yahoo! JAPANで利用されている。更新処理のパフォーマンスの高さが特徴。
Groonga
日本発進の検索エンジン。MySQLやPostgresSQLの拡張モジュールが用意されている。

第3章テキスト解析

検索クエリを抽出することをテキスト分析という。
転置インデックスに登録されるのはタームだが、検索クエリから抽出した文字は区別をするためにトークンと呼ぶ。
英語での表記揺れの対応として、大文字・小文字、複数形・現在進行形・三人称、記号などが検討されている。日本語の場合は英語のようにわかりやすい単語の区切りがないので難しいが代表的な２つの方法がある。

形態素解析
形態素解析器を通して最もそれらしい単語列を抽出する。有名なOSSとしてmecabがある。
文字N-Gram
検索クエリをN文字ごとにトークン化する。
形態素解析はトークンがうまく抽出されなかったり、長い単語で一部だけで検索したい場合に不向きであり、本方式が向いている。

第4章　ポストリスティングの捜査とランキングのアルゴリズム

ポスティングリスト走査のAND、OR検索の実例を簡単に紹介している。
一例として、検索クエリの類似度はコサイン類似度と、TF-IDFとアルゴリズムを使った重みづけで決定できる。実践編ではこれらの類似度計算を使っている。
パフォーマンス評価して重視されるのがレイテンシとスループットであり、これらを下げる要因としてCPU、メモリ、ディスクI/Oがある。負荷試験ではこれらの指標を計測して評価する。
ドキュメントは追加・更新・削除があるので、併せて転置インデックスも再構築が必要である。この方式を動的転置インデックスという。

高速化

キャッシュ
ヒット率が悪かったり最新の状態を保たなければならないなど燃費が悪いだけの場合もある。クエリが固定されている広告システムなんかでは有効な手段。
MaxScore
ポスティグリスト操作の一部をスキップして高速化するアルゴリズム
レプリケーション・シャーディング
分散スケーリングして可用性を担保しつつ高速化する

第5章　検索エンジンへのデータ登録

検索をいかに早くするかを考えて登録処理を実施することが重要。データを入手して登録するフェーズをETLフェーズという。Extractはデータ抽出、Tranceformはデータ加工、Loadはデータ登録。
更新するタイミングはシステム要件による。ECサイトなどの在庫管理があるシステムであればリアルタイムでの更新が必要。更新は既存のシステムに影響を及ぼす可能性もあるので慎重に。夜間のバッチで非同期に更新する方が効率がいいケースもある。

データの入手方法

ファイルシステム
特定のディレクトリを起点に逐次的に探索する。所有者名やグループ名などのメタデータも収集することで、公開範囲を設定可能。
Web
クローラを使ってHTMLなどを収集する。サイトによってはクローリングが禁止されていたり、負荷をかけないように注意しなければいけない。ヘッドレスCMSなどの場合はAPIで収集可能かもしれない。
データベース
同期・非同期の２つがあり、非同期の場合もキューイングして準リアルタイムにするのか、バッチなどで定期実行するのか。

HTMLから特定のメタデータを除去・抽出する方法はスクレイピングという。代表的なツールにbeautifulsoupがある。

実践編

ポケモンのタイプを入力すると該当するポケモンが検索できる検索システムを作成しました。
ポケモンのNo、名前、タイプを事前に転置インデックスに登録します。
形態素解析の機能は盛り込んでいないので、検索窓には直接トークンとして最小分解されたと仮定したポケモンのタイプのみを半角スペース区切りで入力します。また、スペース区切りはOR検索として機能するようにしております。
スコアの計算はTF-IDFの重みづけを利用しました。

TFIDF-Score = \sum_{\substack{t \in q}}(1+\log (tf_{t,d})) * \log(\frac N {df_t}) \\\\ N: ドキュメントの総数 \\\\ df_t: タームtが出現するドキュメントの総数 \\\\ f_{t,d}: ドキュメントd中のタームtの出現回数

事前にNo1~30までのポケモンを登録して、「くさどく」と検索してみました。
下記のように、くさ、どくの複数のタイプを持つポケモン（この場合ダネフシさん）はスコアが高いため上位に表示され、同一スコアの場合は図鑑Noで昇順で表示しております。

登録した転置インデックスの中身です。

Term: {<タイプ> <タームが出現するドキュメントの総数>}
PostingList: [{<図鑑No> <出現回数>} ...]

Term: {くさ 3}
PostingList: [{1 1} {2 1} {3 1}]
Term: {どく 8}
PostingList: [{1 1} {2 1} {3 1} {13 1} {14 1} {15 1} {23 1} {24 1}]
Term: {ほのお 3}
PostingList: [{4 1} {5 1} {6 1}]
Term: {ひこう 7}
PostingList: [{6 1} {12 1} {16 1} {17 1} {18 1} {21 1} {22 1}]
Term: {みず 3}
PostingList: [{7 1} {8 1} {9 1}]
Term: {むし 6}
PostingList: [{10 1} {11 1} {12 1} {13 1} {14 1} {15 1}]
Term: {ノーマル 7}
PostingList: [{16 1} {17 1} {18 1} {19 1} {20 1} {21 1} {22 1}]

最後に

検索エンジンは技術の塊みたいなもので、今まで経験していない分野を学べてとても楽しかったです、と同時にこれではまだまだ不十分だと思うので精進を続けたいと思います。
また、検索に対するユーザの要求水準はものすごく高いと思いますが、それだけに満たせた時にはえも言われぬ感動があると思うので、いつか仕事として携われればいいなと思いました。