6

私はRabin–Karpアルゴリズムを使用して、任意の2つのソースコードファイルの盗用をチェックしているので、最初にそのアルゴリズムをc＃ここでそのコードに実装しますが、その平均および最良の実行時間は空間O（p）でO（n + m）です。 、ただし、最悪の場合の時間はO（nm）です。

 public void plagiarism(string [] file1, string [] file2)
    {
        int percent = 0;

        for (int i = 0; i <(file1.Length - file2.Length +1); i++)
        {

            for (int j = 0; j < file1.Length; j++)
            {
                if (file1[i + j - 1] != file2[j])
                {


                }

                    percent++;
                Console.WriteLine(percent);
            }


            Console.WriteLine("not copied");
        }

    }

それで、これよりも優れているので、ローリングハッシュ関数を使用してそれをより効率的にするにはどうすればよいでしょうか。

4

1 に答える 1

5

ウィキペディアの記事には、アルゴリズムについてのかなり良い議論があり、ローリングハッシュ関数を実装する方法についても言及されています（「部分文字列検索をシフトするためのハッシュの使用」を参照）。また、ハッシュテーブルまたはブルームフィルターを使用して実行速度を向上させる方法についても説明します。

また、最悪のケースはかなり不自然な例であることを理解する必要があります。ウィキペディアの記事に示されている例は、「10,000個の「a」の文字列に続いて1,000万個の「a」の文字列で「b」を検索する」です。

そのウィキペディアのエントリで説明されている手法を使用して、ローリングハッシュを実装できるはずです。それを実装するのに問題がある場合は、それがどのように行われるかについてより具体的な質問を残し、何を試したかを示してください。

実際のドキュメントで最悪のケースに近づいているものに遭遇する可能性はほとんどありません。最悪のケースに遭遇したとしても、ローリングハッシュは複雑さを軽減しません。ローリングハッシュを実装すると、実行時間が直線的に改善されますが、これはn*m複雑さに圧倒されます。最悪のケースが頻繁に発生することがわかった場合は、おそらく別のアルゴリズムが必要です。

もう1つ注意すべき点はO(m*n)、問題になる可能性はありますが、スケールを確認する必要があるということです。調べているドキュメントの大きさはどれくらいですか？あなたはあなたがソースコードファイルで働いていると言います。典型的なクラスプロジェクトを見ているなら、おそらく2,000行のコードを話しているでしょう。これらのドキュメントは、最悪のケースを示すことはありません。たとえそうn*mだったとしても、それほど多くはないでしょう。

ただし、100個のドキュメントがあり、一方が他方と実質的に重複しているかどうかを知りたい場合は、すべてのドキュメントを他のすべてのドキュメントと照合する必要があるため、より大きな問題はO（n ^ 2）です。ドキュメント比較の数はに等しくなり(n*(n-1))/2ます。プロセスを最適化する場合は、別のアルゴリズムが必要です。理想的には、ドキュメントの「指紋」を提供するものです。このようにして、各ドキュメントのフィンガープリントを1回計算してから、フィンガープリントの類似性を比較できます。

ドキュメントのフィンガープリントはよく知られている問題です。ただし、比較の目的で役立つフィンガープリントを作成するのは少し簡単ではありません。あなたはshinglingと呼ばれるテクニックを調べたいと思うでしょう。また、ドキュメントを表すために小さなブルームフィルター（256バイト程度）を使用すること、およびそれを使用して高速比較を実行する機能についての調査もいくつか見ました。

とはいえ、それぞれ1,000行または2,000行の長さの100または2つのソースコードファイルを話している場合は、優れたRabin-Carp実装を使用した単純なO（n ^ 2）比較手法でうまくいくと思います。欲しいです。しばらく時間がかかりますが（5,000の個別のドキュメント比較を行う予定です）、RKの実装の速度が制限要因になるとは思いません。

于 2011-12-08T22:07:51.090 に答える