Technosphere Mail.Ru-2年

こんにちは、Habr！ 2月、 Technosphereプロジェクトは2年を迎えます。 過去1年間、学習プロセスに影響を与えた3つの大きな変化がありました。 それらの最初のものは学生の選択に関するものでした-技術面接。 以前は、学生は技術面接に参加しましたが、解決するために提供されるタスクを知りませんでした。 現在、技術的な問題であるケースを生徒に送信していますが、事前にその場で解決し、教師に解決策を説明する必要があります。 ケースを追加した後、学業成績は劇的に向上しました。 Technosphereの2学期への編入は、40人の学生のうち27人でした。つまり、通常の40-50％の代わりに67％でした。



第二に、テクノスフィアに研究所が設立され、そこで学生はMail.Ruグループと外部顧客の実際的な問題の解決に取り組んでいます。 たとえば、彼らは広告キャンペーンのターゲットアルゴリズムを調査し、広告結果の品質を向上させることができるヒューリスティックを作成しようとします。 実際、研究室は企業でのインターンシップに代わるものです。 その中で、市場からのさまざまな実際的な問題の解決に取り組むことができますが、同時にオフィスへの道に時間を無駄にせず、あなたの学部ですべてを正しく行います。



3番目の重要なステップは、2年間の教育に切り替えることでした。 今年、私たちは毎年恒例のプログラムの下で勉強した子供たちの最後のグループをリリースしました。 彼らが1年間に習得した主題は、大量のデータの知的処理のためのアルゴリズム、C / C ++でのマルチスレッドプログラミング、DBMS、Hadoop、大量のデータの処理方法および情報検索です。



ここで、「情報検索」をテーマにした卒業プロジェクトの1つを紹介することにより、年次トレーニングプログラムを終了させたいと思います。 学期中、子供たちに宿題が与えられ、最終的に大規模な最終プロジェクトになりました。 ルールは次のとおりです。

• 男たちは2-3人のチームに分けられました。
• 目的：提案されたサイトの1つで完全な検索を行うこと。 計画どおり、検索は、結合された宿題+フロントエンド+スペルチェッカーなどのある種のパンで構成する必要があります。

スヴィアトスラフ・フェルドシェロフ



私たちの検索エンジンはpovarenok.ruサイトで機能しました 。 私たちのプロジェクトでは、すべてのコンポーネントをまとめて収集し、Webを作成しました。 当初、コースのすべてのタスクはPython 2.7で行われていましたが、どういうわけか慣性によってプロジェクトを実行し始めました。 したがって、Webアプリケーションを作成するために、Djangoを使用しました。 今ではそれが多すぎるという感覚があり、もっと単純なものでそれを行うことができましたが、それについては後で詳しく説明します。



当初、非常にシンプルなアイデアがありました。すでに書かれた宿題を取り、それらを接着して、ほぼ完成したプロジェクトを取得します。 そこで、私たちはドラフトと呼ばれるプロジェクトで最初の検索エンジンを得ました。 その瞬間、すべてが非常に便利になりました。飛行中のDjangoアプリケーションがあり、検索結果を返す機能が適切な場所に返され、勝利しました。 しかし、完全なインデックスで人気のある単語をクエリすると、構築全体が大幅に遅くなり始めました。 Pythonを高速化するために2、3の試みがありましたが、良い結果は得られませんでした。 次に、DenisはC ++で検索部分全体を取り、書き直しました。 さて、私の側では次のように見えました。高速な検索エンジンで検索してみてください。ある場合は、ゆっくりではありますがPython検索に進みますが、何もないよりはましです。



別の叙事詩は、スニペットと直接インデックスで発生しました。 私の最初のアイデアは、単にレシピの要約を取り、スニペットとして表示することでした。 最初はかなりうまくいったようでした。 しかし、このサイトを詳しく調べると、次のようなものを見つけることができます。「このレシピは、作者である才能豊かなシェフ、オレチカ・サロチカによって「最もおいしいティラミス」と宣言されました。」 そして、私は名前を変えませんでした。 回避するかのように... "。 このようなユーザーの工夫は、単純なスニペットに対する私の期待をすべて破壊しました。 この時点のどこかで、ダニエルはスニペットビルダーを展開しましたが、ここでもある程度の安全性が得られました。スニペットビルダーが落ちた場合は概要を探し、そうでない場合は悲しいかな。 ちなみに、これは、ページで突然エンコードが壊れたときにPython 2.7が特に優れている場所です。



次に対処しなければならないのはスペルチェッカーでしたが、そこにはあまり冒険はありませんでした。 そして、私の最後の作成は、これらすべてのフロントエンドであり、私たちにとっては大きくて骨の折れる作品ですが、それについて語ることはまったくありません:)。 私の自転車ができる人は興味がありませんし、そうでない人はトレーニングの最良の例ではありません。



デニス・クプリャコフ



コース作業の私の部分は、ロードされたページの特定のデータベースでのブール検索ランキングの実装で構成されていました。つまり、テキストリクエストが着信し、出力は関連性の高い順にページのURLになります。 私は本当に検索が迅速に機能することを望みます。要求に対する応答は1秒以内です。



ソケットを使用して要求を送信するために、複数の処理スレッドを備えた別個のプロセスとして検索を実装することにしました。 メインのプログラミング言語としてC ++を選択しました。 これにより、高速で効率的なメモリ管理が可能になりました。 その結果、次のアーキテクチャが開発されました。







ソースデータは、povarenok.ruサイトのロードされたページです。 合計でzipで圧縮され、 Base64に記録された約20万の異なるURLがありました。 多数のページを正常に検索するには、それらに逆インデックスを作成する必要があります。各単語は、それが表示されているページのリストと一致します。 ページ内の単語の出現位置のリストも必要です-それらはランキング段階で使用されます。 それらを十分に速く構築するために、Hadoopを使用したトレーニングクラスターが使用されました。 処理は、ストリーミングモードのPythonで行われました。 以下は一般的な処理スキームです。







Webページのコンテンツを操作するために、 Beautiful Soupライブラリが使用されました。これにより、CSS、ページからスクリプト、およびテキストの選択が簡単になりました。 pymorphy2を使用して単語を通常に戻します。



マップ操作の後、出力はページの長さ（単語数）および単語位置のリストに関する記録です。 エンコードの問題を回避するために、単語はBase64でエンコードされ、リストはsimple-9アルゴリズムを使用して圧縮され、Base64にも書き込まれます。



MapReduceは、最初の2つのフィールドでソートするように構成され（2番目のフィールドは数値として扱われます）、Reduceステージで長さレコードが保存され、単語のリストがグループ化され、単語自体が1回書き込まれ、次に特別なPREV行が使用されます（前の単語を使用します）。 このトリックにより、インデックスが20パーセント削減されました。 LENGTH、DOC_LIST、およびPREVは、Base64で使用されていない文字を含む特別な文字列です。



ネットワークは、libeventライブラリを使用して実装されました。 スレッドを作成するために、C ++ 11のstd :: threadを使用しました。 着信リクエストはキューに入れられ、そこからワーカーによって取り出されます。 並列使用の場合、キューはstd :: mutexによって「保護」されます。



ブール検索。 着信要求は単語に分割され、それらの場合、ページのリストがインデックスからロードされます。 リストはソートされ、すぐに交差します。 C ++のpymorphy2の類似物を探しないために、ユーザー自身がリクエスト内の単語を正規化します（リクエストコードはPythonを使用します）。 その結果、すべての単語を含むページのリストを取得します。



ドラフトランキング：BM25。 結果のページをランク付けする必要がありますが、すべての人に対して効率的にこれを行うには、すぐに計算コストが高くなるため、時間がかかります。 このため、Okapi BM25アルゴリズムは最初に大まかなランキングを実行します。 詳細については、 Wikipediaをご覧ください 。 標準パラメーターを使用しました：k1 = 2.0、b = 0.75。 この段階のインデックスから、エントリのリストの長さを取得するペア（単語、ページ）が必要です。



最終ランキング：乗客。 このランキングは、大まかなランキングの後の最も関連性の高いページ（最初の300ページなど）にのみ適用されます。 アルゴリズムの考え方：検索語を含むウィンドウはページのテキストで強調表示され、各ウィンドウに対して次の特性が計算されます。

• ページの上部へのウィンドウの近接。
• ウィンドウ内の単語の総数に対するクエリからの単語の比率。
• ウィンドウ内の単語の概要TF-IDF 。
• ウィンドウ内の語順とリクエスト内の語順の類似度。

これらの特性は同じスケールに縮小され、線形結合で加算されます。すべてのウィンドウでの最大の特性がドキュメントのランクになります。 最良の結果を得るために係数を選択するのが正しいでしょうが、私は等しい係数を使用しました。 この段階のインデックスから、ペア（単語、ページ）のエントリリスト自体をロードする必要があります。



サイト構造に基づいて係数を下げる。 明らかな考慮事項：コメント、ジョーク（はい、これは 「クック」にあります）を含むページは、レシピほどユーザーにとって必要ではありません。 サイトの構造を強調するために、アドレス内の特定のセグメントの出現に基づいて、各URLを特定の属性セットに関連付けました。 それから彼は群がった。 その結果、URLがグループ、ブログ、レシピ、アルバムなどに分類されました。それらのいくつかについて、経験的に選択された削減係数を導入しました-BM25によって発行されたランクと乗客アルゴリズムによって乗算されます。 これにより、モバイルバージョンページ、コメントページ、ブログなどを下げることができました。



検索のボトルネックは、ハードドライブへのアクセスです。 すべてを迅速に機能させるには、その数を減らす必要があります。 これを行うために、できるだけ多くの情報をメモリに格納しようとしました。 サーバーのメモリはすべてを保存するのに十分ではありませんでした。さらに、ランダムアクセス（ポインタなど）を整理するには多くの追加メモリが必要であることを考慮する必要があります。



静的キャッシュ。 検索の開始時に、インデックス全体が読み取られ、メモリにロードされます。

• 単語ごとに、インデックスファイル内のページのリストのオフセット。
• すべてのページの長さ。
• すべてのペア（単語、ページ）の位置のリストの長さ。
• すべてのペア（単語、ページ）について、インデックスファイル内のこのリストのオフセット。

最初の方法では、ブール検索段階でハードドライブからリストをすばやく読み込むことができます。 2番目と3番目では、ハードドライブにアクセスせずにBM25を計算できます。 4番目は1番目と似ていますが、パッセンジャーアルゴリズムを高速化します。



動的キャッシュ。 検索は料理サイトのページで機能するため、「レシピ」、「パイ」などの一部の単語は非常に一般的です。 すぐに、ハードドライブへのアクセスをキャッシュするというアイデアが生まれます。 これを行うには、boost :: shared_lockおよびC ++テンプレートを使用して、さまざまなスレッドから使​​用できるキャッシュを実装しました。 レコードの存続期間は時間によって制限され、クラウドアウト戦略はLRUです。



検索品質評価。 評価のために、1000組のクエリとマーカーページのセットが与えられました。これらは互いに最も関連性が高いと見なされます。 品質は、結果の中のマーカーの平均位置によって判断できます。



テストを自動化するために、複数のスレッドでリクエストを送信し、グラフ付きのレポートを生成するPythonスクリプトが作成されました。 これにより、バグの外観と修正の有効性を迅速に追跡することができました。 以下は、プロジェクトの防衛のために提示した検索バージョンの統計です。







上のグラフは、出力内の位置ごとのマーカー数の分布を示しています。 ご覧のとおり、ほとんどのマーカーは上位20に入っています。



下のグラフは、実行時間ごとのリクエストの分布を示しています。 平均リクエスト時間は58ミリ秒でした。これは、プロジェクトの他のコンポーネントと組み合わせて、リクエストを1秒以内に維持することを可能にしました。



ダニエル・ポリコフスキー



プロジェクトの3つのコンポーネント（スペルチェッカー、直接インデックス、スニペット）を開発するのは私の責任でした。



店員は確率論（ベイズの公式）に基づいていました。 エラーを修正するには、2つの単語の「類似性」を比較する必要がありました。 このために、修正されたダメラウ-レーベンシュタイン距離が使用されました。 ロシア語の特徴は、特定の文字の2倍に関連するエラーです。 このようなエラーは、たとえば、文字を紛失するよりも可能性が高いと考えられ、文字nを2倍にすると、文字eを 2倍にするよりも大幅に少なく罰せられます。 保護者はレジスターを復元することもできたため、視覚的な要素が改善されました。 開発の興味深い部分は、単語統計の収集でした。 最初は、povarenok.ruサイトに構築された辞書が使用されましたが、後にロシア語の周波数辞書が追加されました（O. N. Lyashevskaya、S. A. Sharov、2009）。 その結果、単語の接着と貼り付けを含む最大2つのエラーを非常に迅速に修正できる非常に正確なシステムが実現しました。 プロジェクトが防御されるまでに、保護者に1つの間違いを見つけることができました。「主な肝臓」というフレーズは「王室の肝臓」に置き換えられました。



2番目の部分は、テキストを文章に分割し、スニペットを作成することです（ページの要約）。 パーティショニングには、機械学習が使用されました。 記号の選択は非常に興味深い問題であることが判明しました。その結果、それらは約20になりました。結果は非常に高く、いくつかの正規表現を追加することで改善できました。 トレーニングはOpenCorporaデータセットで実行されたため、料理のテーマに固有の単語に関連するエラーがありました。たとえば、小さじの減少です。 （ティースプーン）は2つの文に分割されました。 サイトpovarenok.ruの多くのページで、記事の要約がマークされていましたが、それを使用せざるを得ませんでした。 クエリのすべての単語がページタイトルでのみ見つかった場合、スニペットとして表示されました。



***

おそらく、今後も卒業プロジェクトを公開し続け、ブログの更新にご期待ください！



テクノスフィアMail.Ruは、 IT.Mail.Ruプラットフォームに統合された、Mail.Ru Groupの多くの教育プロジェクトの1つであり、ITに興味があり、この分野で専門的な開発に努めている人向けに作成されています。 また、MSTUのテクノパークの教育プロジェクトであるロシアのAiカップ、ロシアのコードカップ、ロシアのデベロッパーカップのチャンピオンシップも紹介しています。 MIPTのバウマンとテクノトレック。 さらに、IT.Mail.Ruでは、テストを使用して、人気のあるプログラミング言語の知識をテストしたり、ITの世界から重要なニュースを学習したり、ITトピックに関する関連イベントや講義の放送を見たり見たりできます。