盗作検索システム

まえがき

かつて私はあらゆる種類の奇妙な仕事に幸運でした。 たとえば、私はシナゴーグで管理者としての仕事に就きそうになりました。 土曜日に彼らが私をそこで働かせることを彼らが、最後の目的として、私を止めたのはほんの一握りだけでした。



別のオプションも興味がありました。 会社は、自分でスクラップを書くことになっているアメリカ人学生のためのエッセイと学期論文を作成しました。 後に、これはかなり広範で収益性の高いビジネスであり、「製紙工場」という独自の名前を思いついたことがわかりましたが、すぐにこのような生計を立てる方法は完全に偽物に思えました。 しかし、この仕事には多くの興味深い仕事があり、その中に-私がキャリアで行った仕事の中で最も難しくてcな仕事があり、子供たちに誇らしげに伝えることができることに注意する必要があります。



その表現は非常に簡単でした。 論文という用語の著者は、英語が母国ではないアラブ人や黒人であることが多く、学生自身と同じくらい怠け者でした。 多くの場合、彼らは最も抵抗の少ない道をたどり、オリジナルの作品を書く代わりに、インターネットから全体または一部を愚かに引き裂きました。 したがって、1つまたは複数のソースを見つけ、比較し、何らかの形で凝集の割合を決定し、収集された情報を送信して過失者を非難する必要がありました。



この問題は言語という用語によってある程度促進されました。それは、事例と複雑な活用形のない、もっぱら英語でした。 そして、この取り組みを一般的にどちらの側で行うべきかが明確ではなかったという事実により、非常に複雑になりました。



パールが実装言語として選ばれ、非常に成功したことが判明しました。 静的でコンパイルされた言語がなく、その厳格さとスロースタートにより、この問題をまったく解決することは不可能でした。 既製のソリューションを書き換えることは可能ですが、多数のテストを経て解決することは不可能です。 まあ、それに加えてたくさんの素晴らしい実行ライブラリがあります。

行き止まり

最初に、タスクの選択は、一部の学生に任せられました。 彼は長い間哲学をしませんでした。 インターネットを検索する必要がある場合は、検索エンジンが必要です。 そこでテキスト全体を詰め込んで、Googleはそれがどこから来たかを見つけます。 次に、見つかったソースを読み、ソーステキストの断片と比較します。



もちろん、これでは何も起こりませんでした。



まず、テキスト全体をGoogleに送信すると、検索が非常に悪くなります。 最終的に、それらにはインデックスが保存され、隣接する単語の数は必然的に制限されます。



第二に、同じアドレスから多くの検索を行うと、Googleがまったく気に入らないことがすぐに明らかになりました。 それ以前は、「Googleで禁止されたことがありますか？」というフレーズは単なる冗談だと思っていました。 そのようなことは何もありませんでした。 一定数のリクエストの後、Googleは本当に禁止され、かなり複雑なキャプチャを表示します。



HTMLを解析するというアイデア自体はあまり成功していません。これは、Googleが検索結果でページのレイアウトをわずかに調整することを決定すると、プログラムがいつでもクラッシュする可能性があるためです。



学生は、オープンプロキシを使用して暗号化して検索エンジンに乗り込むことを決定しました。インターネットでリストを見つけて、検索します。 実際、これらのプロキシの半分はまったく機能せず、残りの半分は恥知らずにスローダウンしたので、プロセスは良い結果で終わりませんでした。



そして第三に、文字ごとの比較を使用してテキストを見つけることは非現実的に遅く、完全に非実用的であることが判明しました。 さらに、ケニア人はテキストを逐語的にコピーするのではなく、あちこちで言葉遣いをわずかに変更するのに十分なトリックを持っていたので、それも役に立たない。



専門の文献を読むことから始めなければなりませんでした。 タスクはわずかなものであることが判明したため、教科書や堅実な本には記載されていませんでした。 私が見つけたのは、個人的な問題に関する多くの科学記事と、チェコのいくつかのレビュー論文だけでした。 悲しいかな、彼女は遅すぎて私のところに来ました-その時までに、私はすでにそこに記述されているすべての方法を知っていました。



トピックから注意をそらすため、有能なジャーナルに掲載されている科学論文のほとんどすべてが、a）アクセスが難しく、b）まったく役に立たないことに気づかざるを得ません。 それらが保存され、検索エンジンが最初のリンクを提供するサイトは、常に支払われ、非常に痛烈です-通常、出版のためにほぼ10ドル。 ただし、より豊かにすると、原則としてパブリックドメインで同じ記事を見つけることができます。 これが失敗した場合は、原則として親切にコピーを送信することを拒否しない著者に書き込もうとすることができます（著者自身は現在のシステムからほとんど受信せず、収益は他の誰かに送られます）。



ただし、通常、特定の記事ごとに実際的な利点はほとんどありません。 それらには、まれな例外を除き、座ってすぐにアルゴリズムの概要を説明できる情報はありません。 それらを実装する方法を示すことのない抽象的なアイデアがあります。 または、同じことを2行と人間の言語で書くことができることを理解するための方法を作成する数式の束。 または著者が行った実験の結果と同じコメント：「すべてが明確というわけではないので、さらに続行する必要があります。」 これらの記事がショーのために書かれているのか、それとも何らかの内部の科学的な儀式のために書かれているのか、またはヒキガエルが自分のスタートアップで非常にうまく使用できる本当のアイデアを共有するように迫っているのかはわかりません。 いずれにせよ、科学の侵食は明らかです。



ところで、最大かつ最も有名な盗作検索サイトはターニチンと呼ばれています。 この分野では実用的な独占者です。 彼の内部の仕事は軍事基地よりも悪く分類されていません-少なくとも非常に一般的な方法でどのアルゴリズムがそこで使用されているかを伝える単一の記事、短いメモさえ見つけませんでした。 完全なミステリー。



しかし、歌詞から行き止まりまで、今回は私自身のものです。



文書フィンガープリンティングのアイデアは実現しませんでした。 理論的には、インターネットからダウンロードされたすべてのドキュメントについて、その指紋が考慮されて、かなり良いように見えました-何らかの長い数字、何らかの形で内容を反映しています。 文書自体の代わりにurlと指紋が保存されるデータベースが確立され、その後、容疑者をすぐに見つけるために、ソーステキストを指紋データベースと比較するだけで十分であると想定されました。 これは機能しません。印刷が短ければ短いほど、比較は悪くなり、ソースの長さの半分に達したら、保存する意味がありません。 さらに、作者に適した変更が認識を欺くために。 それに、インターネットの膨大な量に加えて、データの巨大なサイズのために、短い印刷物であってもすぐに保存するのは面倒です。

解析および正規化

最初は、この段階は平凡で面白くないように思われます。入力に明らかにテキストファイルではなくMS Word形式のテキストが含まれることは明らかです。 分解し、文章と単語に分解する必要があります。 実際、検証の品質を改善する巨大なソースがあり、これはトリッキーなアルゴリズムよりもはるかに先です。 書籍の認識のようなものです-原稿が曲がってスキャンされ、インクで汚れた場合、それ以上のトリックはそれを修正しません。



ちなみに、ソーステキストだけでなく、インターネット上にあるすべてのリンクにも解析と正規化の両方が必要です。そのため、ここでは品質に加えて速度も必要です。



そこで、一般的な形式のいずれかでドキュメントを取得しました。 それらのほとんどは解析が容易です-たとえば、HTML :: Parserを使用してHTMLは完全に読み取り可能です。あらゆる種類のPDFおよびPSは、pstotextなどの外部プログラムを呼び出すことで処理できます。 OpenOfficeドキュメントの解析は楽しみです。倒錯を楽しむならXSLTをねじ込むことさえできます。 全体的な画像を台無しにするのはWordだけです-より粗末なテキスト形式を見つけることは不可能です。解析するのに非常に複雑で、内部の構造がありません。 詳細については、以前の記事を参照してください 。 私の意志があれば、私はそれを分解することはなかったでしょうが、他のすべての形式を組み合わせたよりもはるかに多く配布されます。 これはグレシャムの行動の法則、または世界の悪の陰謀のいずれかです。 神がすべて善良であるなら、誰もがWord形式で書いているのはなぜですか？



構文解析の過程で、通常の形式を取得した場合、テキストからあらゆる種類の有用なことを学ぶことができます。たとえば、ドキュメントの目次を見つけて比較プロセスから除外します（まだ有用なものはありません）。 テーブルでも同じことができます（テーブルセルの短い線は多くの誤検知を与えます）。 チャプターの見出しを計算したり、写真を捨てたり、インターネットアドレスをマークしたりできます。 Webページの場合、ファイルでマークされているサイド列とフッターを除外することは理にかなっています（html5で許可されています）。



はい、ところで、解凍する必要のあるアーカイブがあり、そこから各ファイルが抽出される場合があります。 主なことは、アーカイブをOOXMLのような複雑なパッケージ形式と混同しないことです。



テキストだけを受け取ったので、さらに作業を進めることができます。 大学が必ず必要とするタイトルページと公式情報（「学生の仕事など」、「T。Syakoy教授の確認」）を破棄することは有益です。 同時に、参照のリストを扱うことができます。 少なくとも12個のタイトル（「参照」、「参照リスト」、「引用文献」、「参考文献」など）があるため、見つけるのはそれほど簡単ではありません。 ただし、署名されていない場合があります。 リストは認識が非常に難しく、かなりの負荷がかかるため、テキストから単に破棄するのが最善です。



結果のテキストは正規化する必要があります。つまり、高貴で統一されたフォームを提供します。 まず、すべてのキリル文字とギリシャ文字を見つける必要があります。スペルは対応する英語に似ています。 Cな著者は、意図的にそれらをテキストに挿入して、盗作のチェックを欺きます。 しかし、それはそこにはありませんでした。同様のトリックは、100パーセントの証拠と、そのような著者を首にする機会です。



その後、すべての一般的な省略形を完全なものに置き換えることはできません 。



今度は、芸術性の高いすべてのUnicode文字を単純な文字に変更する必要があります-ヘリンボーン引用符、逆コンマ引用符、長い半角ダッシュ、アポストロフィ、楕円、および合字ff、ffi、stなど。 行内の2つのアポストロフィを通常の引用符で置き換え（何らかの理由でこれが頻繁に発生します）、2つのダッシュを1つで置き換えます。 空白文字のすべてのシーケンス（およびそれらの束もあります）は、1つの通常のスペースに置き換える必要があります。 その後、テキストから、ASCII文字の範囲に収まらないすべてのものを捨てます。 最後に、通常の改行を除くすべての制御文字を削除します。



これで、テキストを比較する準備ができました。



次に、それを文章に分割します。 一見すると単純ではありません。 自然言語処理の分野では、一般に、最初はすべて、そして外部からはすべてが簡単に思えます。 文はピリオド、省略記号、感嘆符、疑問符で終わる場合もあれば、まったく終わらない場合もあります（段落の最後）。



さらに、ポイントはカットの後に立つことができますが、これは文の最後ではありません。 完全なリストは半ページかかります- 博士 ミスター 夫人 さん Inc. vol。 et.al. pp 。 などなど。 さらに、インターネットリンク：プロトコルが最初にある場合は便利ですが、常にそこにあるとは限りません。 たとえば、記事では一般にさまざまなオンラインストアについて説明し、Amazon.comについて常に言及しています。 そのため、すべてのドメインを知る必要があります。国ごとに12個のコアと200個のドメインがあります。



また、プロセス全体が確率的になりつつあるため、同時に精度が失われます。 特定の各ポイントは、文の終わりである場合とそうでない場合があります。



テキストを文章に分割する最初のバージョンは額に書かれていました-正規表現の助けを借りて、すべての間違ったポイントが見つかり、他の文字に置き換えられ、テキストは残りの文章によってsentences打され、ポイント記号が返されました。



それから私は、現代科学によって開発された高度な方法を使用しなかったことを恥ずかしく思い、他のオプションの研究を始めました。 Javaで断片を見つけ、いくつかの地質時代（ああ、退屈、単調で冗長な言語）でそれを解体しました。 Python NLTKを見つけました。 しかし、何よりも、私は特定のDan Gillick（Dan Gillick、「Improved Sentence Boundary Detection」）の仕事が好きで、彼の方法は他のすべての方法よりも優れていると自慢しています。 この方法は、ベイジアン確率に基づいており、事前のトレーニングが必要でした。 私が彼を訓練するために使用したテキストでは、彼は優れていましたが、他のものでは...まあ、それは非常に悪いというわけではありませんが、略語のリストを持つその恥ずべきバージョンよりもはるかに優れていません。 私は最終的に彼女に戻った。

インターネット検索

だから、今、私たちはテキストを手に入れて、Googleを私たちのために働かせ、インターネット中に散らばっている作品を探す必要があります。 もちろん、通常の検索を使用することはできませんが、どのようにすればよいですか？ もちろん、Google APIを使用します。 ただのビジネス。 条件はより自由で、プログラムの便利で安定したインターフェースであり、HTML解析はありません。 1日あたりのリクエスト数は制限されていますが、実際にはGoogleはチェックしませんでした。 もちろん、厚かましくないなら、何百万人もの人にリクエストを送信します。



ここで別の質問は、テキストをどの部分に送信するかです。 Googleは、単語間の距離に関する情報を保存します。 経験的に、一連の8単語が最適な結果をもたらすことがわかりました。 最終的なアルゴリズムは次のとおりです。

• テキストを単語に分割します
• いわゆるストップワード（最も頻繁に遭遇するサービスワード-a、onなど）を破棄します。mysqlから取得したリストを使用しました）
• 重複する8つの単語のクエリを形成します（つまり、最初のクエリは単語1〜8、2番目の2〜9などです。2単語の重複でもクエリを保存できますが、品質はわずかに低下します）
• テキストが大きい（> 40 kb）場合、3回ごとにリクエストをスローできます。非常に大きい（> 200 kb）場合、1秒ごとにさえもスローできます。 盗作者は通常、単一のフレーズではなく段落全体を貼り付けるため、これは検索に害を及ぼしますが、それほどではありません
• その後、同時にすべてのリクエストをGoogleに送信します。
• そして最後に、答えを得て、それを整理し、一般的なリストを作成し、それから重複を捨てます。 また、受信したアドレスのリストを受信した重複の数でソートし、それらを示すものではなく、特に影響がないことを考慮して、後者を切り捨てることもできます。 残念ながら、ここでいわゆる盗作と呼ばれるものがあります。これは盗作を検索するときにあらゆる角度から見えます。 これは、非常に長く鈍い尾が無限に伸びる、逆さまの出展者です。 テールを完全に処理することは不可能ですが、どこでカットするかは明確ではありません。 どこを開けても、品質は低下します。 したがって、そのようなアドレス一覧を使用します。 そのため、テキストの長さに依存する経験式に基づいて切り取りました。 これは、いずれにしても、文字数の関数として安定した処理時間を保証しました

このアルゴリズムは、Googleがラフをカバーしてカバーするまで完全に機能しました。 APIはそのままで、さらには改善されましたが、会社はそのためのお金を求め始めました。 私は選択肢を検討しなければなりませんでしたが、そのうち2つだけがありました-BingとYahuです。 Bingは無料でしたが、そこで彼の美徳は終わりました。 彼はグーグルよりも著しく悪いように見えた。 後者は新しいEvil Corporationかもしれませんが、彼らの検索エンジンは依然として世界最高です。 しかし、Bingは自分よりもさらにひどく見えていました。APIを通じて、ユーザーインターフェイスからのリンクよりも1.5倍少ないリンクを見つけました。 また、リクエストの一部がエラーで終了し、再度繰り返す必要があるという嫌な習慣もありました。 明らかに、これがMicrosoftがヒットの流れを規制した方法です。 さらに、検索バーの単語数を5つに減らす必要があり、ストップワードを残し、1つのワードのみでオーバーラップを行う必要があります。



Yahuは、価格と検索品質の両方で、GoogleとBingの中間に位置していました。



その過程で、別の小さなアイデアが生まれました。 部門の長は、毎日インターネット全体のコンテンツを収集し、それをAmazonのどこかに置くプロジェクトを発見しました。 そこからデータを取得し、フルテキストデータベースでインデックスを作成してから、必要なものを探すだけでした。 さて、実際にはクモを使わずに独自のGoogleを作成してください。 ご想像のとおり、完全に非現実的でした。

ローカルデータベースで検索

Turnitinの強みの1つは、その人気です。 多くの作品がそこに送られます。生徒-自分自身、教師-生徒のもの、そして彼らの検索ベースは絶えず成長しています。 その結果、盗まれた商品をインターネットからだけでなく、昨年の授業からも見つけることができます。



同じ方法で、ローカルデータベースを作成しました。既製の注文と、ユーザーがアプリケーションに適用した資料を使用しました（「エッセイを書く必要のあるテーマに関する記事」）。 結局のところ、作家は以前の作品を書き直すのが大好きです。



これらはすべてフルテキストのKinoSearchデータベース（現在はLucyに名前が変更されています）にありました。 インデクサーは別のマシンで動作しました。 Kinopoiskは優れていることが判明しました-数十万人がドキュメントにアクセスしましたが、私はすばやく慎重に検索しました。 唯一の欠点は、インデックスにフィールドを追加したり、ライブラリバージョンを変更したりするときに、すべてのインデックスを再作成する必要があり、それが数週間続いたことです。

比較

さて、今最も活発な-それなしでは、他の誰も他のものを必要としません。 2つのチェックが必要です-最初に、2つのテキストを比較し、一方のテキストが他方のテキストを含むことを確認します。 そのような部分がない場合、続行できなくなり、計算能力を節約できなくなります。 そして、もしあれば、より複雑で重いアルゴリズムが働き、同様の提案を探します。



最初は、ドキュメントの比較のために、帯状疱疹のアルゴリズムが使用されました-重複する正規化されたテキストの断片。 各ピースについて、特定のチェックサムが考慮され、比較に使用されます。 このアルゴリズムは最初のバージョンでも実装され、機能していましたが、ベクトル空間での検索アルゴリズムよりも悪いことが判明しました。 ただし、検索時に帯状疱疹のアイデアが思いがけず役に立ちましたが、これについてはすでに書きました。



そのため、ドキュメント間の特定の一致係数を考慮します。 アルゴリズムは検索エンジンと同じです。 私はそれを単純な集団農場の方法で提示します。科学的な説明は科学の本にあります（ Manning K.、Raghavan P.、SchützeH. Introduction to information search。-Williams、2011 ）。 私は何も混乱させないことを望みますが、それはかなり可能です-これはシステムの最も難しい部分であり、絶えず変化しています。



したがって、両方の記事からすべての単語を取り出し、単語の基礎を選択し、倍精度数を捨てて巨大なマトリックスを作成します。 列に彼女はまさに基礎を持ち、最初のテキストと2番目のテキストの2行しかない。 交差点では、このテキストで特定の単語が何回出現したかを数値で示します。



このモデルは非常に単純で、テキスト内の単語の順序を考慮しないため、「単語の袋」と呼ばれます。 しかし、私たちにとっては、盗作者はテキストを書き直したり、帳消しにされているものを書き直したりするときに言葉を頻繁に変更するためです。



言語の専門用語で単語の基本を強調することは、ステミングと呼ばれます。 Snowballライブラリーを使用して実行しました-迅速かつ問題ありません。 盗作は盗作の認識を改善するために必要です-unningな作者は単に他人のテキストを書き換えるだけでなく、見た目を変えて、しばしばスピーチの一部を別の部分に変えるからです。



それで、基本からいくつかのマトリックスを得ました。それは巨大なマルチベクトル空間を記述しています。 ここで、テキストはこの空間の2つのベクトルであると考え、それらの間の角度のコサインを計算します（スカラー積により）。 これは、テキスト間の類似性の尺度になります。



シンプルでエレガント、ほとんどの場合に当てはまります。 一方のテキストがもう一方のテキストよりもはるかに大きい場合にのみ、うまく機能しません。



<0.4の類似度係数を持つテキストは考慮できないことが実験的に判明しました。 しかし、その後、サポートサービスからのいくつかの提案についての苦情が見つからなかったため、しきい値を0.2に下げる必要があり、かなり役に立たなくなりました（そして、ここではいまいましいZipf）。



さて、実装に関するいくつかの言葉。 常に同じテキストを比較する必要があるため、その基本とエントリの数のリストを事前に取得することは理にかなっています。 したがって、マトリックスの4分の1が準備できます。



ベクトルを乗算するために、私は最初にPDLを使用しました（そして他に何を使用しましたか？）が、その後、速度を追求して、ベクトルがひどくまばらであることに気付き、Perlovハッシュに基づいて独自の実装を作成しました。



次に、文間の類似性係数を見つける必要があります。 ここには2つのオプションがあり、どちらも同じテーマのベクトル空間のバリエーションです。



あなたは非常に簡単に行うことができます-両方の文から単語を取り、それらからベクトル空間を作り、角度を計算します。 唯一のこと-各単語の出現回数を考慮する必要さえありません-すべて同じで、1つの文の単語が非常にまれに繰り返されます。



しかし、あなたはもっと巧妙にそれを行うことができます-文書のコレクションの代わりに、本の古典的なtf / idfアルゴリズムを適用します 両方のテキスト（2つのテキスト間の類似度を計算したときに既に得られている）の共通ベクトル空間を取得し、ベクトルを構築し、ベクトル内の出現回数をlnで置き換えます（出現回数/文数） 。 その後、結果はより良くなります-根本的にではなく、顕著に。



2つの文の類似性のしきい値が特定の値を超える場合、見つかった文をデータベースに記録し、盗作者の類似性を突き止めます。



そしてまだ-文に単語が1つしかない場合、それを何と比較することさえしません-それは役に立たず、アルゴリズムはそのようなビットでは動作しません。



類似度係数が0.6を超える場合、占い師に行かないでください。これは言い換えコピーです。 0.4未満の場合、類似性はランダムであるか、まったくありません。 しかし、グレーゾーンが形成されるギャップでは、盗作、または単なる偶然であり、人の目には、テキストに共通点はありません。



その後、私は良い記事から学んだ別のアルゴリズムが登場します（ Yuhua Li、Zuhair Bandar、David McLean、James O'Shea。「文の類似性の測定方法と会話エージェントへの応用」 ）。 重火器、言語的特徴がすでに関与しています。 このアルゴリズムでは、不規則な活用形、同義語や誇張語などの単語間の関係、および単語の希少性を考慮する必要があります。 これらはすべて機械可読情報が必要です。 幸いなことに、プリンストン大学の善良な人々は、長い間Wordnetと呼ばれる英語の特別な語彙に従事してきました。 CPANで読むための既製のモジュールもあります 。 私がやったのは、プリンストンに保存されているテキストファイルからMySQLテーブルに情報を転送し、それに応じてモジュールを書き換えることだけでした。 テキストファイルのヒープからの読み取りは便利でも速度でもないため、リンクをファイルにオフセットとして保存することは特にエレガントとは言えません。

第二版

うーん... 2番目。 そして、最初はどこですか？ まあ、最初のことについて話すことは何もありません。 彼女はテキストを取り、アルゴリズムのすべてのステップを順番に実行しました-正規化、検索、比較、結果を返しました。 したがって、彼女は並行して何もできず、遅かった。



したがって、最初のバージョン以降の残りの作業はすべて、同じこと、より速く、より速く、より速くすることを目指していました。



主にリンクの取得とインターネットからの情報の取得に費やしたため、ネットワークへのアクセスが最適化の最初の候補です。 シリアルアクセスは、パラレルダウンロード（ 非同期CurlへのLWP）に置き換えられました。 もちろん、仕事のスピードは素晴らしく成長しました。 モジュール内のグリッチでさえ、100のリクエストを受信し、99を実行し、最後のリクエストに無期限にハングしたとき、喜びを台無しにすることはできませんでした。



新しいシステムの一般的なアーキテクチャは、OSをモデルにしています。 子プロセスを起動し、「量子」時間（5分）でそれらを割り当てる制御モジュールがあります。この間、プロセスはデータベースから前回停止したものを読み取り、次のアクションを実行し、継続に関する情報をデータベースに書き込んで終了する必要があります。 5分で、リンクのダウンロードと比較以外の操作を実行できるため、このアクションは一度に100または200リンクに分割されました。 5分後、ディスパッチャは実行を中断します。時間がない？次回お試しください。



ただし、ワークフロー自体もタイマーの進行状況を監視する必要があります。これは、すべてをハングアップさせるWebサイトにアクセスするリスクが常に存在するためです（たとえば、1つのサイトに100,000語の英語がリストされ、他には何もありませんでした）。上記のアルゴリズムは3日間類似性を探し、おそらくいつか見つけることもあります）。



理論的には、動的にでも、ワークプロセスの数を変更できます。実際には、3つのプロセスが最適でした。



まあ、処理用のテキストと中間データが保存されたMySQLデータベースと最終結果もあったことは明らかです。そして、ユーザーがそこで何が処理され、どの段階で処理されているかを見ることができるWebインターフェイス。



より重要なタスクがより速く完了するように、タスクに優先順位が付けられました。優先度は、ファイルサイズ（大きいほど処理が遅くなる）および期限（近いほど、結果が必要になる速度）の関数と見なされました。ディスパッチャは、最高の優先度に従って次のタスクを選択しましたが、ランダムに修正しました。そうでない場合、優先度の高いタスクが存在する限り、優先度の低いタスクは順番を待ちませんでした。

第三版

3番目のバージョンは、処理アルゴリズムの観点からの進化的開発の成果であり、アーキテクチャの革命でした。失敗した日付の前に寒さの中で何とかしてゴドーを待っていたのを思い出し、最近読んだAmazonサービスの話を思い出しました。また、ファイルを保存し、仮想マシンを作成します。さらに、3文字のあらゆる種類のあいまいなサービスもあります。それから私は夜明けしました。セヴァストポリ水族館で一度見た巨大なエビを思い出しました。彼女は石の真ん中に立って、足を振って水をろ過します。それはあらゆる種類のおいしいものを彼女に運び、彼女はそれらを取り去り、さらに水を吐き出します。そして、あなたがたくさんのそのようなエビを一列に置くならば、それらはすべて20分でそこにフィルターをかけます。そして、これらの甲殻類や異なる種類のものでさえも、それぞれが自分自身を捕まえるのであれば、一般的にはどのような見通しが開かれますか？



比ur的な言葉から技術的な言葉への翻訳。 AmazonにはSQSキューサービスがあります-データを運ぶような連続したパイプライン。 1つのアクションのみを実行する複数のプログラムを作成します。コンテキスト切り替え、子プロセス、その他のオーバーヘッドコストはありません。 「朝から夜まで、クレーンは同じバケツに水を満たします。ガスストーブは、同じ鍋、やかん、鍋を加熱します。



実装はシンプルで美しいことがわかりました。上記のアルゴリズムの各ステップは、個別のプログラムです。それぞれに独自の行があります。 XMLメッセージはキューで送信され、そこで何をどのように行うのかを伝えます。別の制御キューと、注文を監視し、作業の進行状況に関するデータを更新し、発生した問題についてユーザーに通知する別個のディスパッチャプログラムがあります。個々のプログラムは、ディスパッチャに回答を送信したり、直接および次のターンに便利なように送信したりできます。エラーが発生した場合、彼らはこのディスパッチャに関するメッセージを送信し、彼はすでに理解しています。



エラー修正は自動的に取得されます。プログラムがタスクの完了に失敗して、たとえばクラッシュした場合、再起動され、失敗したタスクはキューに残り、しばらくしてから再びポップアップします。何も失われませんでした。



Amazonの唯一の難点は、キューサービスが各メッセージが少なくとも1回配信されることを保証することです。つまり、何らかの方法で配信されますが、一度は配信されません。このために準備し、重複に適切に応答するようにプロセスを記述するか、処理しないでください（何らかのアカウンティングを保持する必要があるため、あまり便利ではありません）、またはthey等に処理されます。



もちろん、インターネットからダウンロードしたファイルはメッセージで送信されませんでした-不便にも、SQSにもサイズ制限があります。代わりに、S3に積み重ねられ、リンクのみがメッセージで送信されました。ディスパッチャは、タスクの完了後、これらすべての一時ストレージをクリアしました。



中間データ（たとえば、読み取る必要のあるリンクの数、すでに実行されたリンクの数）は、シンプルだが分散されたデータベースであるAmazon Simple Data Storageに保存されました。 SDSには、考慮する価値のある制限もありました。たとえば、即時更新を保証しませんでした。



そして最後に、完成した結果-盗作を示すテキスト、MySQLデータベースではなく、CouchDBに追加し始めました。とにかく、リレーショナルデータベースでは、それらは非リレーショナルに保存されました-Data :: Dumper（これはJSONのPerlovの類似物）の形式のテキストフィールドです。 CouchDBはShebaの女王と同じくらい良かったのですが、欠点が1つありましたが、致命的でした。任意のクエリでデータベースにアクセスすることは不可能です。クエリインデックスは事前に作成する必要があります。つまり、事前に予測する必要があります。水晶玉がない場合は、インデックス作成プロセスを開始する必要があります。大規模なデータベースの場合は数時間続きます（！）同時に、他のすべてのリクエストは実行されません。ここで、MongoDBを使用します-バックグラウンドインデックスがあります。



結果として得られた回路は、古い回路に比べて大きな利点がありました-それは自然にスケーリングしました。実際、彼女にはローカルデータはなく、すべてが配布され（結果のデータベースを除く）、ワークプロセスのすべてのインスタンスは完全に同じです。これらは重大度別にグループ化できます。1台のマシンですべての肺を実行し、リソースをほとんど必要とせず、テキストを比較するためのブレーキングプロセスとして別の仮想サーバーを選択します。足りない？引っ張っていない？もう1つ持つことができます。まだ処理できないプロセスはありますか？取り出して別の車に乗せます。原則として、これは自動的に行うこともできます。キューの1つが大量の生メッセージを蓄積していることがわかり、別のEC2サーバーを起動します。



しかし、過酷な叔母のライフは、いつものように、この牧歌を調整しました。技術的な側面からは、アーキテクチャは完璧でしたが、経済的な観点からは、SDS（およびS3）の使用は完全に不採算であることがわかりました。特にベースは非常に高価です。



中間データを古き良きMySQLに急いで転送し、ダウンロードしたドキュメントをNFS経由で共有されているハードドライブに保存する必要がありました。さて、同時にシームレスなスケーリングを忘れてください。

未実現計画

特に、マニングの網羅的な本から自然言語処理を研究していますが、そこに記載されているすべての方法は、アドホックなトリック、特定のタスクのためのトリックであり、一般的ではないという考えを取り除くことができませんでした。 2001年に、Lemはコンピューターサイエンスから離れました。コンピューターサイエンスは、40年にわたって人工知能を発明していませんでしたが、このテーマには多くの騒ぎがありました。それから彼は、予見可能な未来の状況は変わらないだろうと悲観的に予測した。マシンはポイントを理解していなかったので、理解できません。哲学者は正しかった。



盗作の検索はまったく同じトリックでした。まあ、私はAIを引き起こしてテキストの人間の理解を待つことを望んでいませんでした、私はそれほど素朴ではありませんでしたが、私は長い間頭をさまよって、少なくとも同じ文を認識するために構文解析を添付し、異なるキー（アクティブとパッシブ）に立っています。しかし、私が見つけたすべての自然言語パーサーは非常に複雑で確率的であり、理解できない形で結果を出し、膨大な計算リソースを必要としました。一般に、科学の発展の現在の段階では、これは非現実的だと思います。

人的要因

このシステムは、完全自動モードで動作するように作成されたため、人々は何も持ち込めませんでした。さらに、非常に優秀なシステム管理者が私と協力しました。おかげで、すべてのサーバーが完全に構成され、さまざまな種類のダウンタイムが最小限に抑えられました。しかし、結局のところ、まだユーザーがいました-サポートサービス。まあ、そしてもちろん、当局。



彼らは長い間、盗作の調査に携わったのはコンピューターではなく、コンピューター内に座っていた小さな男（または群衆全体）であると確信していました。特に本物のようであり、特に、トピックに関する学期論文に書かれているすべてを完全に理解しており、インターネットのすべてのコンテンツを念頭に置いているため、盗作を見つけています。しかし、これらの小さな男性が台無しになったとき、彼らはすべての論理に反して、何らかの理由で彼らからではなく、私から尋ねました。一言-哲学者。



盗作はまだ何をしているのか全く理解していないコンピューターを探していることを説明するのに多くの仕事が必要でした。 1年のうちのどこかで当局に届きましたが、残りは完全ではないようです。



サポートには別の方法もありました。Googleにいくつかのオファーを紹介し、Googleが盗作を発見したことを喜んで知らせてくれましたが、私のシステムはそうではありませんでした。さて、私はそれに対して何と言えますか？ Zipfの配布について説明し、速度とメモリサイズのために妥協する必要があり、そのような妥協はそれぞれ品質の低下を意味することを伝えますか？絶望的に。幸いなことに、これらのケースのほとんどで、Googleが一部の有料サイトで素材を見つけたことが判明しましたが、システムは単にアクセスできませんでした。



トリックもありました-Turnitinが盗作を検出したが、私たちのシステムは検出しなかったことを報告する。そして、Turnitinが関連分野の卒業証書を持つ資格のある専門家のチーム全体によって書かれた可能性が高いことを説明することは不可能であり、サイト自体は何らかのクールな検索エンジンと密接な関係を持っています。繰り返しになりますが、幸いなことに、盗作の検出されていないケースのほとんどは、有料サイトまたは他の学生の作品からのものであり、一般に、何らかの方法でアクセスできません。



数か月間、私はディレクターの要件を一定の処理時間で満たそうとしました。各作品は1時間以上チェックされるべきではありません。私にはうまくいきませんでした。ある日、彼らは本質的に、彼らは私から永久運動機械を発明したいと言ったまで、夜眠りませんでした。そのようなことは、プログラムの世界でも、人生では起こりません。要件が再定式化されたとき-特定のボリューム（50ページ）以下の各作業は、キューに巨大な学位論文がなければ、1時間以内に検索する必要があります-物事はスムーズに進みました。条件は厳しいものでしたが、少なくとも原則としては実現可能です。



時には、顧客サービスは満足しています。私は彼らのロジックを説明するのに途方に暮れていますが、定期的に、検証キューの負荷が重いため、彼らはそれに作業の追加コピーを詰め込みました。まあ、つまり、渋滞の中に100台の車がある場合は、道路上でさらに100台を運転する必要があります。そうすれば、物事はスムーズに進みます。私は彼らに間違いを説明することができませんでした、そして、そのようなケースは純粋に管理手段によって禁止されました。

コメンテーターへの別れの言葉

私の悲しい経験は、Habréには多くの若者がいて、何らかの理由で、生まれた直後から人類が発明したすべての知識に完全に精通していると信じていることを示しています。チェーホフによると、「彼女は私の解放であり、彼女はすべて愚か者であり、彼女は賢い一人です。」あなたがそのような仲間に属し、私がばかである、私は何も理解していない、私は単純なことを理解していないなどと私に書くことにした場合、ほとんどダウンタイムなしで、顧客にいくつかのお金を節約しました。したがって、上記のタイプのコメントを書くときは、あなたが開発したシステムの同様の特性をすぐに示してください。さて、先導的な質問なしにあなたの天才がすぐに目立つように。