⌨️

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

2022/11/26に公開約4,200字

この記事について

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

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

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

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

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

| データ構造 |データ構造と検索の概要|
| ---- | ---- | ---- | ---- |
| 二分探索|文字列をソートし、配列に配置するデータ構造。検索時に二分探索が可能になる|
| N-gram| N-Gramは任意の文字数(N)で先頭から1文字ずつずらしたものをトークン分割するデータ構造。検索クエリも N-Gramに分割し一致度が高い候補クエリを検索する|
| Edge N-gram | 候補クエリを先頭から文字列長分のトークンに分割したデータ構造。検索クエリと完全一致するトークンを検索する|
| Trie木| Trie木は、文字列などの先頭部分の共通部分を共有することでデータ量を削減したデータ構造|
| FST(Finite State Transducers)| 有限オートマトンに出力がついた形式。Trie木と同じく先頭部分を共有し、かつ末尾も共有することでデータ量を削減してている |

二分探索

二分探索はリスト内のクエリ候補を高速に検索するアルゴリズムです
クエリ候補を並べ替えたリスト形式のデータ構造を用意して、リスト内を二分探索して検索クエリと前方一致するクエリ候補を探索します
二分探索法はリストのクエリ候補を半分ずつしぼりこみながら探索するため、計算量はO(log n) となります
二分探索はシンプルなデータ構造で高速で検索できる仕組みでQuery Autocompletionの説明でよく利用されていますが、実サービスではデータの更新にリストの再生成が必要なことや他に良いアルゴリズムがあるので実サービスで利用している事例は少ないと思われます

N-gram

N-Gramはクエリ候補を任意の文字数(N)で分割したトークンを転置インデックスにしたデータ構造です
検索アルゴリズムは検索クエリもトークンに分割し、トークンごとに転置インデックスから完全一致するクエリ候補があるかを取得し、一致度を評価する仕組みです

N=2のときの
ラーメンのN-Gramは  ラー、ーメ、メンの3つのトークンに分割されます
博多ラーメンのN-Gramは  博多、多ラ、ラー、ーメ、メンの6つのトークンに分割されます
検索時に、入力クエリをN-Gramに分割して、サジェスト候補のトークンの一致度が高い結果を応答します

比較的高速に検索できて、前方一致以外の応答や誤字などの揺らぎに強い手法で、Solr/Elasticでも採用されるデータ構造です
ただしアルファベットは24文字しかないのでのN=4でもの日本語だと漢字6400文字では1600兆の組み合わせがあるため、日本語でのQuery Augocompletionでは候補クエリ大きくなるとパフォーマンスが出にくい問題があります

Edge N-Gram

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

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

N-Gramよりはコンパクトですが、文字列長文のトークンを生成するためデータ容量が肥大化しやすいこと前方一致にしか対応していないのと揺らぎに弱いという欠点があります

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

Trie木

Trie木は、文字列などの先頭の共通部分を共有するデータ構造です。
配列のキー(Prefix)を共有しているためN-Gramと比較してデータ容量が大幅に少なくてすみます

検索時も、検索クエリをもとにデータを探索することで候補クエリを引き当てることができるため、クエリ長をTとするとO(T)とクエリ長で引き当てが可能です

前方一致に特化していて揺らぎに対応することが難しいアルゴリズムなのですが、シンプルな実装ができるためQuery Autocompletionのコーディングテストではベストな解法として紹介されるケースがあります

FST(Finite State Transducers)

FST(Finite State Transducers)。候補クエリ間をTrie木と同じくPrefixを共有している,またTrie木とは異なりSuffixも共有しているためデータ構造がよりコンパクトになっています

その他

その他の手法として、Deep Learningを利用したベクトル検索技術があります。Query Autocompletionの論文レベルでは様々な手法が提案されています。またGoogleのQuery Autocompletionでは既にベクトル検索技術を利用していると発表がありました
ただそれ以外だと、それほど事例がないようです。

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

日本語の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

ログインするとコメントできます