夜の部屋。 暗闇の中で何千もの神秘的な顔が、モニターの青みがかった輝きに照らされています。 100万個のキーの耳障りなパチパチ音。 Enterキーで機械のようなパンチを押します。 数十万匹のネズミの不吉な鳴き声…だから、確かに、負荷の高いシステムのすべての開発者の想像力が発揮されました。 そして、あなたが彼を時間内に止めなければ、スリラー映画やホラー映画全体が出てくるかもしれません。 しかし、この記事では地面にずっと近づきます。 検索ヒントの問題を解決するためのよく知られたアプローチ、それらを全文にする方法を学んだ方法を簡単にレビューし、またそれらにスピードを与えるために行ったいくつかのトリックについて話しますが、同時にリソースへの欲を教えません。 記事の最後で、ボーナスがあなたを待っています-小さな実例です。

「フードの下」にあるべきものは何ですか？

1. プロンプトの検索は全文である必要があります。つまり、プロンプトテキスト内の任意の順序でユーザークエリからすべての単語を検索できる必要があります。 たとえば、ユーザーがクエリ「watch」を入力した場合、データベースには次のプロンプトが表示されます。
   
   
   
   
   
   
   
   
   
   「ウォッチ」という単語がこれらのプロンプトの異なる場所にあるにもかかわらず、ユーザーは3つすべてを見る必要があります。
2. ユーザーの要求は、キーボードで入力中に完了しない場合があります。 したがって、単語ではなく接頭辞で検索する必要があります。 前の例では、「ウォッチ」という単語全体だけでなく、そのプレフィックス部分についても3つのヒントがすべて表示されます。 たとえば、「 watch 」。
3. Search Mail.Ruは汎用の検索エンジンです。つまり、可能なクエリの種類は多く、システムは数千万のヒントの中から検索できるはずです。
4. 反応の速度は非常に重要なので、数ミリ秒で答えを出したいと思います。
5. 最後に、サービスは24時間365日稼働する信頼性の高いシステムでなければなりません。 ロシア全土およびCIS諸国からのヒントは、毎秒数千のリクエストを処理します。 フォールトトレランスのために、したがって、実装とデバッグを容易にするために、非常にシンプルでエレガントな特定のアイデアをサービスの中心に持つことが非常に望ましいです。

既知のアプローチ

1.プレフィックスの自動補完



a。 重み付きのヒント（重み==人気）は、ヒントに従って辞書順にソートされます。

b。 ユーザーがクエリ（プレフィックス）を入力すると、バイナリ検索でヒントのサブセットが検索され、その先頭がこのプレフィックスを満たします。

c。 見つかったサブセットは重みの降順でソートされ、結果として「最も重い」ヒントのトップがユーザーに提供されます。











このアプローチの明らかな最適化は、 ツリーのノードに重みを持つパトリシアツリーです。 最も「重い」クエリを選択する場合、原則として、 優先度キュー 、または対数検索時間を提供するセグメントツリー が使用されます 。 必要に応じて、 RMQアルゴリズムを介してLCAを使用してサーバーのメモリを消費することができます。そうすると、 非常に迅速なプレフィックスヒントが得られます。 このアプローチには、速度、コンパクトさ、実装の容易さの3つの利点があります。 ただし、明白で最も不快な欠点は、プロンプトのテキスト内の単語の順列を検索できないことです。 つまり、このようなプロンプトはプレフィックスのみであり、フルテキストではありません。



2.全文自動補完



a。 ヘルプテキストとユーザーリクエストは一連の単語と見なされます。

b。 ユーザーがクエリを入力すると、データベースは、プロンプト内の位置に関係なく、ユーザーのすべての単語（またはプレフィックス）を含むプロンプトのサブセットを検索します。

c。 見つかったサブセットは、ヒントワードの降順でクエリワードにソートされ、次に重みの降順でソートされ、「最も重い」もののTOPがユーザーに返されます。











実際、これはフルテキストアプローチであり、これについてはさらに説明します。 このテーマに関しては、国内外の著者による膨大な数の出版物がインターネットで入手できます。 例：

• ファジー検索の実装-著者は、誤字訂正と組み合わせて、バー、レストラン、その他の施設の名前の検索ヒントを実装しました。 ヒントは約2.5千個しかなかったため、ワードプレフィックスによる検索用に変更されたWagner-Fisherアルゴリズムを使用して、すべてのヒントで検索するのに十分であることが判明しました。 この方法は高品質ですが、速度が遅いために適していません。
• TASTIERアプローチ -記事のライブ検索は、完全に一致するだけでなく、関連する出版物も検索します。 ユーザーのコンテキストをRAMに保存し、ユーザーの要求に応じて適応できるようにします。これは、メモリが非常に高価で、速度に悪影響を及ぼします。
• Sphinxシンプルなオートコンプリートと修正の提案 -有名なオープン検索エンジンSphinxに基づくオートコンプリート。 自動補完の基本的な考え方は、MySQLクエリ言語でのワイルドカードの使用です：“ the wor * ”。 タイプミス補正-n-gramアプローチに基づいています。 もちろん、そのような検索は私たちが必要とするものではありません。結局、ユーザーは必ずしも最後の単語を入力するとは限りません。 そして、実践が示すように、ユーザーはクエリ語を好きなように、任意の順序で入力できます。 さらに、n-gramアプローチでは、リアルタイムプロンプトに適用するために多くのリソースが必要になります。

ここで考慮されていない上記およびその他のアプローチは、収益性+速度+シンプルさの組み合わせでは満足できませんでした。 そのため、ニーズを満たす独自のアルゴリズムを開発しました。

問題の正式な声明

アルゴリズムを説明する前に、問題をより正式な方法で定式化します。 だから、与えられた：

• ヒントテキストのセットS = {s ₁ 、s ₂ 、...、s _N }。各ワードは、単語W（s _i ）= {w _i1 、w _i2 、...、w _iK }で構成されます。 ユーザーが検索エンジンに問い合わせるクエリログから取得するヘルプテキスト。
• ヒントの人気の重みのセットF = {f ₁ 、f ₂ 、...、f _N }。 ここでの人気とは、特定のリクエストの使用頻度、つまり、ユーザーが特定のリクエストに対して検索エンジンで何かを検索する頻度を意味します。
• プレフィックスQ = {p ₁ 、p ₂ 、...、p _M }の順序付けられたシーケンスで構成される不完全なユーザー要求。 前述のように、リクエストは不完全な場合があるため、ユーザーのリクエストは一連のプレフィックスと見なされます。

必須です：

• Sからのすべてのヒントs _iのセットRを見つけて、Qからの各接頭辞p _{j に対して} 、Wからの1つの一意の単語w _k （s _i ）に対応します。
• 2つの基準に従って、見つかったヒントのセットRをソートします。
  
  
  • W（s _i ）の語順w _kの降順、ユーザークエリQの接頭辞p _i
  • Fからの人気重みf _lの降順Rからのs _i
  
  
  

索引

ヒントによる全文検索が必要なため、インデックスの基礎は、一般的な全文検索の実装への古典的なアプローチであり、最新のWeb検索エンジンはこれに基づいています。 全文検索は通常、いわゆるドキュメント間で実行されます。つまり、ユーザーのリクエストから単語を検索するテキストです。 アルゴリズムの本質は、フォワードインデックスとリバースインデックスの2つの単純なデータ構造に縮小されます。

• 直接インデックス -このドキュメントをそのIDで検索できるドキュメントのリスト。 つまり、直接インデックスは文字列の配列（ドキュメントのベクトル）であり、ドキュメントのIDはインデックスです。
  
  
  
  
  
  
  
  
  
  
• 逆索引 -すべての文書から「中傷」した単語のリスト。 各単語には、この単語が出現するソート済みIDドキュメントのリスト（投稿リスト）が割り当てられます。
  
  
  
  
  
  
  
  

これら2つのデータ構造を使用すると、ユーザーの要求を満たすすべてのドキュメントを簡単に見つけることができます。 これを行うには、次のものが必要です。

1. 逆インデックス：クエリの単語に従って、これらの単語が見つかったドキュメントのIDリストを見つけます。 これらのリストの共通部分は、クエリからのすべての単語が見つかったidドキュメントの結果リストです。
2. 直接インデックス：受信したIDでソースドキュメントを見つけ、ユーザーに「渡します」。

この記事では説明が十分であるため、検索の詳細については、スタンフォード大学の本「 情報検索の概要 」に送ります。



古典的なアルゴリズムは単純で優れていますが、クエリの単語は一般に「未完成」であるため、純粋な形式ではヒントには適用されません。 または、上で述べたように、リクエストは単語ではなくプレフィックスで構成されます。 この問題を解決するために、逆インデックスを完成させました。これが得られたものです。











注 ：以下の図では、簡潔にするために、ツリーのいくつかのノードが複数の文字の1つの遷移に「マージ」されています。



例を使用してインデックス検索を分析しましょう。

1. 上記のインデックスを自由に使用でき、ユーザーがすでにリクエストの一部を入力しているとします。 次の文字がキーボードに入力されましたが、不完全なリクエスト「 omn​​ia v 」を受け取りました。
2. クエリをプレフィックスワードに分割します。「 omn​​ia 」と「 v 」を取得します。
3. 検索エンジンとの類推により、最初に、与えられた接頭語が与えられると、逆インデックスでid idリストを見つけます。 逆インデックスは2つの部分で構成されていることに注意してください。
   
   a。 プロンプトのテキストから「切断」した単語を含むプレフィックスツリー （「トライ」、「ボロン」）。
   
   b。 ツールチップIDのリスト-直接インデックス内のツールチップテキストのインデックス。これについては以下で説明します。 リストはidの昇順でソートされ、単語が終わる頂点に配置されます。
   
   私はトライが私たちにとって2つの理由で良いと言わなければなりません：
   
   
   • 時間O（log（n））で任意の単語接頭辞を見つけるために使用できます。ここで、 nは接頭辞の長さです。
   • 特定のプレフィックスについて、その継続のすべてのオプションを簡単に決定できます。
   
   
   そのため、各接頭辞について、ツリーを下って行き、中間ノードで自分自身を見つけます。 次に、 正しい ID IDリストを取得する必要があります。
4. すべての子ノードのリストをマージします。 何のために？ 通常の検索エンジンと同様に、各プレフィックスのIDリストを横断する必要がありますが、2つの「BUT」があります。
   
   a。 まず、すべてのノードにidヒントのリストが含まれているわけではなく、単語全体がダウンロードされるノードのみが含まれています。
   
   b。 第二に、葉ノードを除き、各ツリーノードには特定の継続があります。 つまり、1つのプレフィックスに対して非常に多くの拡張子が存在する可能性があり、これらの拡張子を考慮する必要があります。
   
   したがって、抑制を見つける前に、個々のプレフィックスごとにIDヒントのリストを「合計」する必要があります。 したがって、各接頭辞について、この接頭辞に従ってツリー内で停止したノードから開始して、ツリーを再帰的に深く巡回し、マージアルゴリズムによってその子ノードのすべてのリストの結合を構築します。 この図では、プレフィックスで停止したノードには赤い丸が付けられ、 マージ操作には 「 U 」 が付けられています。
5. 次に、各プレフィックスの合成ユニオンリストを横断します。 ソートされたリストを横断するためのさまざまなアルゴリズムは単なる海であり、それぞれが異なるタイプのシーケンスにより適していると言わなければなりません。 最も効果的なものの1つは、Ricardo Baez-YatesおよびAlejandro Salingerアルゴリズムです。 戦闘のヒントでは、特定のタスクを解決するのに最適な独自のアルゴリズムを使用しますが、Baez-Yates-Salingerアルゴリズムはかつて私たちにインスピレーションを与えました。
6. 見つかったIDによって、ヒントテキストを探しています。 この場合の直接インデックスは、検索エンジンの直接インデックスと同じです。つまり、文字列の単純な配列（ベクトル）です。 ヘルプテキストに加えて、追加情報を含めることができます。 特に、ここでは人気の重みを保存します。

そのため、6番目のステージの終わりまでに、ユーザーリクエストからのすべてのプレフィックスがあるすべてのヒントが既にあります。 明らかに、この段階で得られるヒントの数は非常に多く、数千から数十万に及ぶ場合があり、ユーザーに「プロンプト」を出すために必要なのは最高のものだけです。 この問題は、別のアルゴリズムであるランキングアルゴリズムによって解決されます。



次に、絶対に何もせずにプロンプ​​トを「半分」ランク付けできるようにする1つの小さなトリックを見ていきます。 そして、2つの問題を検討する過程で、これについて以下で説明します。

スピードアップ

「時期尚早の最適化はすべての悪の根源です」-ドナルド・クヌートによって策定された人気のあるプログラミングの知恵は述べています。 しかし、上記のアルゴリズムを純粋な形で実装すると、2つのパフォーマンスの問題が発生します。 したがって、私たちにとって、スピードを求める闘争の欠如はさらに悪いことです。



最初の問題は、リストのマージが遅いことです 。 この問題をさらに詳しく考えてみましょう。

1. 私たちのツリー（トレイ）には、文字「 a 」で始まる1000個の単語が既に存在するとします（実際には、さらに多くの単語が存在します）。
   
   
   
   
   
   
   
   
2. 明らかに、1000ワードの場合、idヒントの最小平均数も約1000です。つまり、平均して、文字「a」で始まるワードがある最低1000のヒントがあります。
3. ここで、ユーザーがこの文字「 a 」で何かを検索することにしたと想像してください。 アルゴリズムによれば、プレフィックス「a」に対して、ノード「a」の下にあるすべての子ノードのリストを結合する操作が開始されます。 当然、この操作には適切なリソースが必要です。まず、新しいリストにメモリを割り当て、次に、この新しいリストにidをコピーします。

結合は、2つのトリックを使用して最適化できます。

• 新しい要求ごとにメモリを割り当てないように、最終リスト用にメモリを予約します。
• 「怠lazな」方法で、つまり必要に応じて団結する。

しかし、私たちの実験では、ユニオンを使用したトリックはキャッシングのために最適化と比較できないことが示されました。 はい、はい、リーフトップだけでなく、ツリーの各ノードにヒントのIDを追加し始めました。 合計：マージする必要はありません-各可能なプレフィックスの既製リストはツリーノードに直接あります。 そして、逆インデックスの形式は次のとおりです。











しかし、待ってください！ ツリーの各ノードにidのヒントを入れますか？！ とても無駄に見えますよね？ しかし、それはとても無駄ですか？ 推論：

• 新しいヒントごとに、テキストに含まれる文字数と同じ数のidを追加する必要があります。 これは最悪の場合のシナリオです。idはスペースと繰り返し単語（「くまのプーさんとすべてです 」）には必要ないため、idの追加も必要ありません。
• たとえば、平均ヒント長が25文字の場合、100万件の検索ヒントには2500万文字が含まれます。 また、ヒントIDが4バイト整数（標準int）の場合、最悪の場合、逆インデックス内のすべてのヒントIDリストがメモリで占有します： 4バイト* 25,000,000 = 100 MB 。 そして、そのようなボリュームは、明らかに、普通のpersonalkaにとってさえ、それほど無駄ではありません。 比例して、5000万のヒントに対して、インデックスは5 GBを占有します。これは、本格的な検索ヒントのサービスに非常に適しています。

そこで、可能なプレフィックスごとにすべてのリストをキャッシュすることで、リストを結合する問題を解決しました。



2番目の問題は、リストの交差が遅いことと、重量によるチップのランキング（ソート）です 。 アルゴリズムによると、結合後、2つの重要なステップが続き、それぞれにパフォーマンスの問題があります。

1. 結合リストの交差。 大規模なデータベースでは、特に短いプレフィックスの場合、実際のリストは長すぎます。 したがって、「 a b 」のような短いクエリのクロスリストは長すぎます。
2. まず、重量の降順でのランキングのヒント。 交差点後の最終リストも非常に大きくなる可能性があるため、クエリ「 a b 」のように数千のidをソートすることも採算が取れません。

結果を得るために必要なのは7〜10個の「最良の」ヒントだけであることを思い出して、2つのポイントで構成される非常に簡単なソリューションを見つけました。

1. IDヒントの正しい順序。 IDリストをコンパイルして、ウェイトが最大のツールチップのIDが最小になるようにします。 つまり、ヒントは重みの降順でインデックスに追加する必要があります。 したがって、交差点の結果のリストは、重みとID値を減らすことで既に同時にソートされます。 このアプローチを「 事前ランキング 」と呼びます。
2. 完全な交差点は必要ありません。 経験的に確立されました：交差点ではすべてを取ることはできませんが、最初のK個のチップ（K> Nであり、チップの目標数Nに比例する）を取るだけで十分であり、それらの中にはすでに重量によって適切なものを選択できるものがあります単語順で。 たとえば、TOP N = 10の最高のヒントが必要な場合、最初のK = 100についての結果の交差から選択する必要があります。これを行うには、交差するときに、結果リストにあるIDの数をカウントし、最初の100を入力するとすぐに停止します交差点。
   
   
   
   
   
   
   
   
   
   

したがって、重量によるランキングと「怠“な」K最初のヒントへの交差の両方を最適化しました。

実装

最初に約束したように、記事で説明されているアルゴリズムを実装するC ++の実用例を投稿します。 ソースデータベースとして任意のテキストファイルを使用できます。各行はヒントです。 たとえば、 ラテン語 （ source ）のことわざや翼のある表現でそれを埋めることができます。そうすれば、ロシア語への翻訳やその逆の翻訳をすばやく取得できます。







実装の機能については説明せず、読者に提供します。利点は非常に簡単です。

結論の代わりに：残されたもの

もちろん、ここで紹介するアルゴリズムは最も一般的な形式で説明されており、多くの質問はこの記事の範囲外です。 ツールチップ開発者を考えるのに役立つ他のものは何でしょう：

• 単語の位置に基づくヒントランキングアルゴリズム。
• キーボードの言語レイアウトを逆にする： "ghbdtn"-> "hello" ;
• ユーザー要求のタイプミスの修正。 ここでは、Microsoftの開発者による優れた記事をお送りします。S。Chaudhuri、R。Kaushik、エラーを許容するためのオートコンプリートの拡張 。
• 準備されたプロンプトのデータベースから何も伝えることができない場合のケースに対するユーザーのリクエストの終わりを設計する： 「Alla Pugachevaは80年代半ばに何を歌ったか」
• ユーザーの地理を考慮に入れる： 「映画」->サラトフのユーザーにとっては、モスクワとサンクトペテルブルクの映画館を促す価値はありません。
• 1億から2億から5億のヒントを追加して、メモリおよびプロセッサリソースを実行する場合、2、3、またはそれ以上のサーバーでアルゴリズムをスケーリングします。
• 等々、これは私たちの最愛のユーザーと私たちのニーズにのみ向けることができます。

それだけです ご清聴ありがとうございました。



アレクセイ・メドベチェク、

検索ヒント開発者 。