1つの入力ファイルと指定された数のファイルを一致させるアルゴリズム

Question

先週インタビューを受けました。私はアルゴリズムラウンドの質問の一つに立ち往生した。私はその質問に答えましたが、面接官は確信していませんでした。だから私は同じものを共有している。

この質問に最適化された方法を教えてください。今後のインタビューに役立ちます。

質問： -

10^9バイトより サイズ小さい持つ、すべてのファイルは、ASCIIテキストファイルで与えられた20件のテキストファイルがあります。 1つの入力もありますが、これは でも1つのASCIIファイル、例えばinput.txtです。

私たちの仕事は、この入力ファイルの内容と戦略的に一致するファイルを と一致させ、最も近いファイルの名前を出力することです。入力ファイルの の内容は、部分的にのみ一致する可能性があります。

ありがとうございます。あなたの親切な返事を探しています。

Answer 1

それらの差分

とトイレ-lを通過、またはCでLevenshtein distanceを実装++単一の文字（または対象のドメインをcondidering任意のより適切な単位）として、それぞれの行を処理する

Answer 2

あなたは、インデックスのいくつかの種類（例を作成することができます。 trie）を使用して入力ファイルを要約します。次に、ドキュメント間で一致するインデックスの数を確認できます。

例：長さ10の入力ファイルに対してトライを作成します。テキストファイルの長さが10（重複する）の文字列ごとに、トライで一致するトライの数を確認します。

Answer 3

文書の類似性のために本当にスケーラブルなシステムを設計するための提案として、私はMining Massive Datasetsの第3章を読むことをお勧めします。これはオンラインで自由に入手できます。そこに提示されている1つのアプローチは、ワードカウントをセットにベクトル化し、そのワードカウントをハッシュし、ハッシュ結果のファミリをJaccardの類似性と比較してすべてのドキュメント間でスコアを得ることによってデータセットをシングルすることです。これは正しく行われれば、精度が高いペタバイトのファイルで動作します。良い図での明示的な詳細はスタンフォードのCS246 Slides on Locality Sensitive Hashingから読み取ることができます。単語頻度のカウントのような簡単なアプローチは、本にも記載されています。