Zenn
⌨️

Query Autocompletion(クエリサジェスト)のデータ構造とアルゴリズム

2022/11/26に公開
Elastic
#
検索
#
solr
tech

この記事について

この記事では、Query Autocompletion(クエリサジェスト)で用いられることが多いデータ構造とアルゴリズムついてに解説します。

システム全体を把握するには、Query Autocompletionの概要と歴史的経緯を最初に読むと理解できます。

Query Autocompletionを担当することになった（ニッチな）エンジニアの方に参考になればうれしいです

Query Autocompletionとは

Query Autocompletionとは、ユーザーがクエリを入力している途中で、入力内容に基づいてクエリの候補を自動的に提示する機能のことです。
例えば、Googleの検索エンジンで「ラーメン」と入力すると、「ラーメン屋」「ラーメンレシピ」「ラーメン博物館」などの候補が表示されるようになっています。

データ構造とアルゴリズム

Query Autocompletionシステムは、高スループットかつ低レイテンシーが要求されるため、検索システムとは異なるデータ構造を持つシステムを構築することが一般的です。Query Autocompletionの主なデータ構造とアルゴリズムは以下の表にまとめられています。

データ構造とアルゴリズム 概要
二分探索 二分探索(binary search)は、ソートされた配列やリストの中から特定の値を探索するアルゴリズムです。配列やリストを半分に分割して、探索する値が前半部分にあるか後半部分にあるかを判断し、探索範囲を狭めていくことで効率的に探索を行います。
N-gram N-Gramは任意の文字数(N)で先頭から1文字ずつずらしたものをトークン分割するデータ構造。検索クエリも N-Gramに分割し一致度が高い候補クエリを検索する
Edge N-gram Edge N-gramは、文字列のプレフィックスから始まるNが可変のN-gramに分割したトークンを転置インデックスにすることで、前方一致検索を高速化するためのデータ構造です。
Trie木 Trie木は、文字列などの先頭部分の共通する部分を共有することによって、データ量を削減したデータ構造です。
FST(Finite State Transducers) FSTは有限オートマトンに出力がついた形式で、Trie木と同じく先頭部分を共有し、末尾も共有することでデータ量を削減しています。

Query Autocompletionシステムを構築するにあたっては、これらのデータ構造とアルゴリズムを適切に組み合わせることが重要です。また、実際にシステムを構築する際には、データ量やクエリの種類に応じて最適な方法を選択する必要があります。

二分探索

「二分探索」は、リスト内のクエリ候補を高速に検索するアルゴリズムです。
クエリ候補を並べ替えたリスト形式のデータ構造を用意して、リスト内を二分探索して検索クエリと前方一致するクエリ候補を探索します。
このため、二分探索法はリストのクエリ候補を半分ずつしぼりこみながら探索するため、計算量はO(log n)となります。
二分探索は、リスト内のデータを高速に検索できるアルゴリズムで、Query Autocompletionなどでよく利用されます。ただし、実際のサービスではデータの更新に伴い、リストを再生成する必要という課題があります。またより高速なデータ構造やアルゴリズムもあるため実サービスではそれらを利用する場合が多いです。

N-gram

「N-Gram」は、クエリ候補を任意の文字数(N)で分割したトークンから構成される転置インデックスと呼ばれるデータ構造です。
この手法は、入力された検索クエリをトークンに分割し、トークンごとに転置インデックスから完全一致するクエリ候補を取得し、その一致度を評価することで、高速に検索ができるようになります。

たとえば、N=2の場合、"ラーメン"は"ラー"、"ーメ"、"メン"の3つのトークンに分割されます。一方、"博多ラーメン"は"博多"、"多ラ"、"ラー"、"ーメ"、"メン"の5つのトークンに分割されます。

この手法は、前方一致以外の検索や誤字にも強く、Solr/Elasticなどの検索エンジンでも採用されるデータ構造です。
ただし、日本語の場合は漢字が約6,400文字あるため、N=4であっても、組み合わせが約1,600兆にもなります。そのため、日本語のQuery Autocompletionでは、候補クエリが大きくなるとパフォーマンスが出にくい問題があります。

Edge N-Gram

「Edge N-Gram」は、文字列のプレフィックスから始まるNグラムに分割したトークンをインデックスにしたデータ構造です。検索時は、入力クエリをそのままインデックスまたはKVSに引き当てるため、Nグラムより高速に検索できます。「ラーメン」のEdge N-Gramは「ラ」「ラー」「ラーメ」「ラーメン」の4つのトークンに分割されます。

データサイズは、文字列長に応じたトークンが生成されますが、検索時は、入力クエリと完全一致または部分一致するクエリを検索するため、情報検索（IR）の分野で転置インデックスと同じ高速な検索になるデータ構造です。Solr/Elasticなどの検索エンジンでも利用されており、日本語での実装事例も多数あります。

Nグラムよりもコンパクトですが、文字列長に応じたトークンを生成するため、データ容量が肥大化しやすく、前方一致にしか対応していないという欠点があります。

検索対象が完全一致する部分をKVSの仕組みが利用できるため、データ投入部分だけ実装することで分散型のKVSを利用すれば、比較的簡単に分散システムを構築することが可能です。

Trie木

「Trie木」は、文字列や単語などのプレフィックスの共通部分を共有するデータ構造です。
配列のキー（Prefix）を共有しているため、N-Gramと比較してデータ容量が大幅に少なくて済みます。
また、検索時には、検索クエリをもとにデータを探索することで候補クエリを引き当てることができるため、クエリ長をTとするとO(T)とクエリ長で引き当てが可能です。

ただし、Trie木は前方一致に特化しており、揺らぎに対応することが難しいアルゴリズムです。
そのため、Query Autocompletionのように前方一致に特化した処理が必要な場合には有用なデータ構造ですが、それ以外の用途には適していない場合があります。

シンプルな実装ができるため、Query Autocompletionのコーディングテストなどで良く利用されます。

FST(Finite State Transducers)

「FST」は、Trie木と文字列や単語などのプレフィックスを共有する加えてサフィックスも共有するデータ構造です
例えば、「さっぽろ一番みそラーメン」と「さっぽろ一番塩ラーメン」という候補クエリがある場合、`プレフィックスの「さっぽろ一番」もTrieと同じく共有していますが、サフィックスの「ラーメン」を共有するため、Trie木よりもよりコンパクトなデータ構造であり、検索時の効率性が向上します。

その他

Deep Learningを用いた様々な手法が存在します。
Query Autocompletionの論文レベルでは、例えばNeural Query Auto Completion(NQAC)やDeepAutocompleteなどの手法が提案されています。一方で、事例はまだ限られているようです

日本語システムでのデータ構造

日本語の Query Autocompletion のデータ構造について調べると、Edge N-Gram のデータ構造を選択するケースが多く見られます。
また、日本語の入力は PC ではローマ字入力によるアルファベット、スマートフォンではフリック・ガラケー入力によるひらがなを入力して変換するケースが多いため、これらの対策として、クエリ候補は元の検索ログとは別に、読みを生成しひらがなまたはローマ字に変換したインデックスを用意して、2つ以上のインデックスを同時に検索しているケースが多いようです。

まとめ

Query Autocompletion(クエリサジェスト)のデータ構造やアルゴリズムは複数提案されており、サイトの規模や検索支援の目的に合わせて選ぶ必要があります。

  1. 検索エンジンで標準的に採用されるN-GramがElasticやSolrと相性が良いが、前方一致以外の応答が含まれる問題があります。
  2. 前方一致に特化したQuery Autocompletion(クエリサジェスト)システムの場合は、Edge N-gramを利用しているケースが多く、比較的大きなインデックスサイズでも動作します。
  3. さらに大規模になる場合は、TrieやFSTなどの仕組みを導入しているケースがあります。
  4. 近年は、Deep Learningを利用したベクトル検索技術が注目されており、クエリ自動補完にも応用される可能性があります。

なお、以上の手法に加え、ユーザーが過去に検索したキーワードやアクセスしたページなどの情報を利用して、より個人化されたクエリサジェストを提供する取り組みも進んでいます。また、日本語においては、入力においてローマ字やひらがなの変換が行われることが多いため、その影響を受けたデータ構造の選定も重要になります。

フィードバックのお願い

記事について、皆様のご意見や指摘をお聞かせください。誤りや不足点があれば、修正いたしますので、お知らせいただければ幸いです。

参考文献

Discussion