Clever Geek Handbook

1つのリクエストの履歴

画像






新しい仕事であなたの最初の日を想像してください。 オフィスは、まったく知られていないクルスカヤ地下鉄駅のエリアにあります。 昼食が近づいています。 検索アプリケーションを開き、 「Kurskで食べる」と書いて、食事ができるオプションを選択します。



「クルスクで食べる」リクエストの背後にあるものと、必要なものを正確に見つけるための処理方法 記事では、2GIS Searchチームが都市での生活をユーザーにとってより便利で快適にするために可能な限りのことを行う方法を説明します。



検索クエリのテキストは氷山の一角にすぎず、ユーザーが直接やり取りする内容のほんの一部にすぎないことを理解することが重要です。 検索クエリ自体には、テキストに加えて、他の多くのデータが含まれています。 これらには、ユーザーの位置、ユーザーが表示するマップの領域、お気に入りからのレコードのセット、および検索モードに関する情報に関するパーソナライズされた情報が含まれます。 たとえば、地図上や建物内の検索、または方向の検索などです。 データは、優れた検索機能を成功させるための鍵です。



データとその構造に細心の注意を払っています。 さらに、構造化データでの効率的かつ高速な検索によってシャープ化されるため、2GIS構造検索で検索アルゴリズムを呼び出します。 検索インデックスと、それが構築されるデータを特別な方法で準備します。 詳細は説明しませんが、データは処理が簡単になるように編成されているだけで、十分に圧縮されており、最も重要なことは、モバイルデバイス上でも迅速に処理できることです。



さらに、検索はオフラインで動作するため、検索インデックスの速度とボリュームに特別な要求があります。 この機能には細心の注意を払っています。検索インデックスを絶えず圧縮し、あらゆる種類のプラットフォームでパフォーマンスを評価し、特定の検索ケースが設定された制限時間を超える機能を高速化します。 ところで、モバイルデバイス上の2GISでの通常の検索クエリは、アプリケーションが結果に基づいてドロップダウンリストを描画するよりも高速であることを自慢できます。



以下に、検索の魔法をカバーする秘密のベールを明らかにします。 例として、 「クルスクで食べる」という上記のリクエストを取り上げます。 その処理の段階と、それぞれの段階で何が起こるかを検討してください。 さあ、行こう！











ステージ1.解析



入力パラメーター：リクエスト「クルスクで食べる」



まず、リクエストテキストを解析する必要があります。 これは重要です。解析後、リクエストテキストではなく、それを構成するトークンのセットで作業できるからです。 トークンは単一のリクエストワードです。 私たちの場合、3つのトークンのセットを受け取ります： "eat" 、 "on" 、 "Kursk" 。 すべてが単純であるように思えますが、悪魔は詳細にあります。 また、それほど明白ではない場合もあります。たとえば、「wi-fi」または「2番目」のクエリでは、このような組み合わせ全体を処理する必要があることを理解する必要があります。



トークン自体には、単語のテキストに関する情報、リクエスト内の位置に関する情報、単語に続くセパレータの存在および単語の何らかの特性に関する情報（文字のレジスタ、単語が数字、序数、電話番号、住所またはその他のデータであるかどうか）が含まれます。



ステージ2.辞書検索



入力パラメーター：トークン“ eat” 、 “ on” 、 “ Kursk”



画像






要求トークンの準備ができたリストを使用して、辞書検索の段階、つまり各トークンについてデータから単語形式のリストを見つける段階に進みます。 単語形式は、単語のルートとその末尾に関する情報をエンコードしたものです。



グラフ形式で提示される辞書を分析するためのアルゴリズムとして、辞書検索を提示します。 その中のノードは文字、またはむしろ記号です。 グラフは、シンボルノードとこれらのノード間の遷移で構成されます。 辞書グラフを調べた結果、前の段階から転送されたトークンに基づいて取得できる多くの単語形式が作成されました。 そのため、辞書から、リクエストの次のトークンに一致する一連の文字を見つけようとします。 同時に、ご存じのとおり、ユーザーはタイプミスをしたり、文字を見逃したり、キーボードのレイアウトを間違えたりします。 したがって、辞書を回るときは、考えられるヒューマンファクターを考慮したり、現在何が得られているのかを推測したりするために、いくつかの操作を適用します。 文字チェーンのさまざまな変換が使用されます：挿入、置換、文字の追加など。



その結果、グラフの各リクエストトークンについて、単語のルートと末尾に関する情報、単語形式の文字数に関する情報、および検出された推定値を含む単語形式のセットを抽出します。 発見の推定-発見された一連のキャラクターの語彙の距離を、望ましいシーケンスに特徴付ける評価。 評価では、見つかった文字列がリクエストトークンとどの程度異なるかを特徴付けます。



そのため、トークンには単語の形式があります。





次に、見つかった単語形式は、評価に応じてフィルタリングされます。 それらのベスト、つまり、クエリからの単語に可能な限り近いものは、用語のリストに含まれます。 この用語は、単語の形式と調査結果の推定を意味します。 さらに、見つかった単語の形式に加えて、形態の規則を使用して追加された用語がリストに追加されます。 形態学的処理の重要なステップは、形態学的評価の追加です。 実際には、検索では強力な形態学的処理メカニズムを使用しているため、辞書から類似の単語を見つけることができるだけでなく、自然言語のルールに従って、単語の類似性だけでなく、意味によってユーザーに正確に興味のあるものを見つける方がより正確です。



トークンの場合、用語が作成されます：





この段階で、辞書検索は終了します。 リクエストを処理し、トークンごとに、さらに処理する用語のリストがあります。 これらの用語には、それらが表す単語に関するすべての情報が含まれており、それぞれの用語がどのように見つかったかを評価しています。



ステップ3.データエントリの検索



入力：リクエストの各部分の用語のセット





前の段階からリクエストの各部分の用語のセットを受け取ったので、インデックスでそれらを検索します。 データ内の各ドキュメントには多くの見出しがあり、 逆インデックスで記述されているため、組織、住所などを表す特定のドキュメント内の目的の用語へのすべての参照を簡単に見つけることができます。



リクエストの各部分およびこれらの部分の各用語について、用語でエンコードされた単語を含むドキュメントを探しています。 したがって、リクエストの一部については、すべての用語でエントリが見つかります。





明らかに、前置詞「オン」は何度も発生するため、「コーヒーのテイクアウト」、「セットトップボックスでの再生」、「マシンの登録」など、ドキュメントの多くの見出しに分類されます。 「食べる」と「クルスク」も繰り返し使用されます。 2番目の単語とその用語は、最初の単語よりも頻繁にデータに含まれています。









ヒットすることにより、検索クエリの単語と特定のドキュメントの単語の一致を考慮します。 これらのヒットはリストに保存され、次のステップで分析されます。 ヒットを追加する場合、ドキュメント内の単語に関するデータを用語からコピーするだけでなく、単語がどのように見つかるかについての最適な推定値を計算します。 つまり、どの評価がリクエストトークンに近いかに応じて、用語の形態学的評価、または用語が辞書でどのように見つかったかの評価を選択します。



この段階は、検索自体の開始の前置きです。 特定のドキュメントに一連のヒットを準備しました。これに基づいて、次のアルゴリズムが結果としてユーザーに提供する必要があるものを選択して評価します。



ステージ4.検索の中心



入り口：ヒットリスト





実際、実装のヒットリストは非常に扱いにくいコンテナです。 ヒットを追加すると、ヒット自体が記録される特別なノードが作成され、これらのヒットが含まれるドキュメントへのリンクが作成されることを理解することが重要です。



したがって、次のように入力データを表示する方がより正確です。

入り口：ドキュメントノードのコンテナ





まず、検索はドキュメントツリーのバイパスを開始し、各ノードはそれをアナライザーに送信します。アナライザーは、このノードからのドキュメントが出力に入るための結果に適しているかどうかを評価します。 アナライザーがどのボリュームを処理する必要があるかを理解するために、最初はコンテナーに3000以上のノードが含まれていると言います。 ただし、クロールプロセス中にノードを追加できるため、実際にはさらに処理されます。 分析は検索の最も高価な部分であると同時に、プロジェクトの最も複雑で大きな機能の1つであると言っても過言ではありません。 それでも、モバイルデバイス上でも非常に高速に動作します。



ステージ5.分析



入力： ドキュメントノード：{hits、...}









分析は、ノードからタイトルのリストを取得することから始まります。 タイトルは、ドキュメントのこのタイトルに該当するタイトルとヒットのリストです。 これらの見出しは、最初の段階で評価されます。 各タイトルの有用性を知ることは重要です。 有用性は、良い、弱い、ジャンクになります。



各タイトルについて、ヒットチェーンの最高のものが選択されます-ヒットの類似性で構成される長さと語彙スコアが最高です。 最高のチェーンに基づいて、タイトルの有用性が評価されます。 チェーンの有用性を判断するために、ドキュメント内の単語の頻度に基づいたメカニズムも使用します。 大まかに言えば、ドキュメントに単語が現れる頻度が高いほど、その単語の重要度は高くなります（ TF-IDF ）。 したがって、連鎖に、優れた数字や性別など、形態上の大きな違いのないドキュメントのタイトルからの重要な単語が含まれている場合、タイトルが役立つと考えます。 タイトルは、そのヒットがドキュメントのタイトルの単語を完全にカバーしている場合にも役立ちます。



ユーティリティを使用すると、すべてのタイトルがノードのユーティリティマスクを形成します。 このマスクは、分析されたノードによってカバーされるリクエストトークンのアイデアを提供します。 そして、その助けを借りて、ノードをさらに分析するかどうかの大部分を決定します。



その結果、インデックスから1つのドキュメントだけでなく、潜在的な結果を表す構造データのセットがあり、それがどのように見つかるかについての情報を持っています。



ステップ6.評価



入力： ドキュメントノード：{hits、...}









ユーティリティマスクに応じて、ノードを処理するか、すぐに次のノードに進みます。 処理された多くのノードのうち、全体についてのさまざまな情報を蓄積します。 たとえば、多くのノードタイトル、ノード間の関係、およびその他のデータ。



次に、相互接続されたノードのタイトルの分析が開始されます。 実際、多くのノードがノードグラフに結合され、評価されます。



グラフノードのノードから、ランク付けされたタイトルのリストを取得します。 簡単に言えば、さまざまなノードから、タイトルの単一リストを作成します。各リストには、すべての参加ノードのタイトルのヒットからの推定値と要因の組み合わせも追加されます。



評価は、クエリからのタイトルに含まれる単語の数に関する情報と、単語がどのように検出および処理されたかに関する他の多くの要因に関する情報を持つ構造です-辞書検索段階から始まります。 ランク付けされたタイトルのこれらの成績が、最高の成績の選択に参加することが重要です。 それらの一部は選択済みとしてマークされ、ユーザーに表示される結果の最終評価に貢献します。



全体的な評価では、出力全体を並べ替えるのに重要な結果情報が提供されます。 これには、たとえば、クエリの単語の欠落などの要因が含まれます。 この測定は、構造情報を含むノードでカバーされなかった単語の数を特徴付けます。



タイトルの有用性に関する情報に基づいて、結果の明確さが決定されます。 明瞭さは、良い、弱い、悪いことがあります。 そして、処理されたノードの選択されたすべてのタイトルの参加で計算されます。 これらすべてのデータは、結果の運命とそれらが発行される順序に劇的な影響を及ぼします。



徐々に、ノードの分析の終わりに近づいています。 ノードが最終的にアナライザーを離れて潜在的な結果になる前に、さらにいくつかの指定操作を実行します。 たとえば、選択したドキュメントタイトルの互換性。



アナライザーのすべての円を通過したノードは、選択したヘッダーおよびドキュメントに関する情報を含む結果を形成します。 検索クエリを適切にカバーする結果は、後処理に送信されます。



ステップ7.後処理



入力：ノードから構築された結果









アナライザは、結果になる前にインデックスから多くのレコードを除外します。 ただし、分析中に、多くの潜在的な結果を評価し、処理のために送信できます。 関連性の高い順に最も有用なもののみをユーザーに表示するには、アナライザーで検出された最悪のオプションをカットする必要があります。



前のステップで、結果の一般的な評価が言及されました。 一般的な評価により、後処理段階で最悪の結果を切り捨てることができます。 グラデーションは次のとおりです。 要求トークンをカバーしない結果は、ユーザーの要求を完全にカバーする結果よりも明らかに悪い結果になります。 明快さが悪い結果は、明快が良い結果よりも明らかに望ましくありません。 ポストプロセッサは受信結果に関する情報を蓄積し、明らかに悪い結果を排除します。 残りはリストに追加されます。



空腹のユーザーにカフェに関する情報を提供する前に、最終処理を実行します-関連性で並べ替えます。 ソートには、検索のさまざまな段階で計算および集計された多くの要素が含まれます。 そして最終的に、 「Kurskで食べる」の検索結果は500を超える結果です。 それらの多くは同じ方法で発見されたため、同じ評価を持っています。 ユーザーの人気順にソートされます。











おわりに



私たちは多くのカフェやレストランで戻り、嬉しいことに夕食に行きました。 一瞬ですべての結果が得られました。 インターネット接続も必要ありません。



アプリケーションは検索インデックスをデバイスに保存します。 このようなスキームは、データ圧縮と処理速度を最適化するという重要なタスクを提供します。これは、さまざまなモバイルデバイスで検索が迅速に機能するためです。 ただし、これはまったく別の話です。



今日、私は検索エンジンのフードを開き、ユーザーが都市で必要なものを見つけるのにどのように役立つかを示し、迅速かつ便利にそれを実行しようとしました。 有益だったことを願っています。


More articles:


All Articles