📖

Query Autocompletion(クエリサジェスト)概要

2022/06/05に公開

この記事について

クエリサジェストはユーザの検索体験を改善するために広く導入されています。

しかし、効果的に提供するにはシステム要件を正しく理解する必要があります。本記事では、クエリサジェストの概要と歴史的経緯を説明したうえで、一般的なシステム構成について解説します。
クエリサジェストを担当することになった（ニッチな）エンジニアの方々に参考になれば幸いです。

クエリサジェストの概要

クエリサジェストとは、ユーザが入力したクエリの入力補完を行う機能の一つです。
Query Autocompletionの例
クエリサジェストの例

クエリサジェスト、検索ボックスでユーザの検索したいクエリを予測し提示することで、少ないキーストロークで検索行動を完了させることを目的としています。
Query Autocompletionは、GoogleのようなWeb検索、Amazonのようなeコマース、TwitterのようなSNSアプリなど、さまざまな分野でPC/モバイル問わず提供されています。
また、クエリサジェストは「サジェスト」「QAC」「QuerySuggest」などと呼ばれることもあります。

クエリサジェストシステムに要求されること

一般的にクエリサジェストシステムには高スループットかつ低レイテンシーが要求されます

要求	要求される性能
スループット	検索ボックスの検索数の数倍のリクエストを処理できること
レイテンシー	キーワード入力から100ミリ秒以内に表示が完了することが望ましい
大規模なデータセットの処理	膨大な量のデータを処理する必要があります。

これらの要求を満たすために、適切なアルゴリズムやデータ構造の選択が必要となります。

スループット

クエリサジェストシステムでは、検索ボックスの入力が変更されるたびに検知し、検索を実行します。つまり、1文字増えるごとに検索が実行され、1回の検索行動で複数回のシステムへの呼び出しが発生します。

例えば、"ラーメン"と検索する場合、Query Autocompletionでは "ラ"、"ラー"、"ラーメ"、"ラーメン" という順で呼び出しが行われます。
また、ローマ字入力の場合は、"R"、"RA" などより多くの検索が実行される場合があります。

そのため、多数のユーザから同時に大量のリクエストが送信され、システムが高いスループットを維持する必要があります。スループットが低い場合、ユーザが入力するたびに検索結果の表示に時間がかかり、ユーザ体験が低下する可能性があります。

低レイテンシー

クエリサジェストシステムは、PC・モバイルに搭載されている日本語入力用のIMEと同様の応答をユーザに期待されています
人間は、応答速度が50ミリ秒以内であればリアルタイムで処理されていると感じます。しかし、100ミリ秒を超えるとユーザの行動とは関係ないアクションだと感じてしまいます。
そのため、ネットワーク通信の処理コストを考慮すると、サーバーサイドで50ミリ秒以内の応答が望ましいとされています。

大規模なデータセットの処理

クエリサジェストシステムは、ユーザーが入力する文字列に対してリアルタイムに候補を生成する必要があります。
そのためには、検索エンジンのインデックスではなく、専用のデータ構造やアルゴリズムを用いることが必要です。
また、クエリサジェストは検索ログやクエリの人気度などの大規模なデータセットから学習することで、より適切な候補を提供することができます。

これらの理由から、クエリサジェスト大規模なデータセットの処理を必要とします。

クエリサジェストの歴史

Autocompletionの歴史

クエリサジェストの歴史は1960年代まで遡り、コマンド入力支援として継続的に研究対象となっています。
当時は「インクリメントサーチ」と呼ばれ、検索クエリの予測ではなく、事前に登録されていた「単語」や「コマンド」といったコンテンツ予測が主なタスクでした。

「クエリの予測」とは、利用者が入力しようとしている検索クエリを予測し、その予測結果を補完する機能のことです。例えば、利用者が「ら」と入力した時点で、「らーめん」というキーワードが最も頻繁に検索されるキーワードだと判断された場合、検索欄の下に「らーめん」という単語が表示され、利用者は続けて入力をすることができます。

一方、「コンテンツ予測」とは、該当システムの内のコンテンツを予測する機能のことです。例えば、利用者がOSのコマンドラインで「cd」と入力した場合、「cd」の後に移動したいディレクトリの名前を入力することが予想されます。この時、利用者のディレクトリ名を候補を表示してくれる機能がコンテンツ予測です。

クエリサジェストとWeb検索

2000年代には、利用者の履歴をベースとしたクエリサジェストがOSやブラウザ、メールなどに組み込まれるようになりました。

利用者の履歴をベースとしたvが登場した背景には、利用者の検索クエリの傾向を把握することによって、より正確な予測を行い、利用者の利便性を向上させるという考え方があります。つまり、利用者が過去に検索したキーワードやフレーズを基に、その後の検索クエリを予測することで、より迅速で正確な検索を実現しようというものです。

Web検索への適用は2004年にラボ機能としてGoogle Suggestがリリースされました。
Google Suggestは2008年にGoogle検索に統合され、現在ではWeb検索の必須な補助機能となっています。

Query Autocompletionの効果

クエリサジェストは、ユーザ検索体験とシステムリソースの両方に効果があります。

ユーザ検索体験への効果

ユーザのクエリ入力時間を短縮することができる。
　- Yahoo!の英語PCユーザにおいて、キーストロークを50％以上削減することができることが報告されている（2014年）。
　- Googleのモバイルユーザーにおいて、最大46％以上の入力時間の削減が報告されている（2006年）。
スペルミスを回避することができる。
検索クエリには通常10%程度のスペルミスが含まれている
関連する検索用語を見つけることができる。

システムリソースへの効果

クエリサジェストによってスペルミスを回避し、適切なクエリを作成することができれば、ユーザが求めていた結果により早くたどり着くことができます。そのため、検索エンジンが処理する必要がある検索クエリの数が減り、リソース利用効率が改善されます。これにより、検索エンジンのレスポンス時間を短縮し、少ない台数で多くのユーザの検索を処理することができます。

クエリサジェストのフローについて

一般的なQuery Autocompletionのフローを説明します。

検索ボックスの入力が変更された文字「Prefix（プレフィックス）」をバックエンドシステムに問い合わせます。
「Prefix」からユーザの完成した検索クエリ候補を取得します。この処理は「検索処理」と呼ばれます。
検索結果候補から時間・位置情報・ユーザの行動履歴などを用いてランキングを行います。これを「ランキング」と呼びます。
検索クエリ候補を検索ボックスの下などに表示します。これを「表示」と呼びます。

「検索処理」「ランキング」「表示」の各処理において、様々な改善手法が提案されています。す

まとめ

「クエリサジェスト」は、ユーザが入力したクエリを予測し、提示することで検索行動を支援する機能です。
この機能は、GoogleやAmazon、Twitterなどの検索エンジンやSNSアプリで提供されており、利用者にとって非常に便利な機能と言えます。ユーザーは、クエリを入力する際の手間や時間を減らすことができます。

ただし、クエリサジェストシステムには、高スループットかつ低レイテンシーが要求されます。多数のユーザから同時に大量のリクエストを処理することが必要であるため、適切なアルゴリズムやデータ構造を使用する必要があります。

フィードバックのお願い

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

参考文献

以下のリンクでは、この記事で取り上げたトピックに関する詳細情報が提供されています。これらの資料を参考にして、クエリサジェストシステムついてさらに学びましょう。