剽窃検出用のアプリケーションを大きなテキスト ファイルで作成します。それに関する多くの記事を読んだ後、Winnowing アルゴリズム(Karp-Rabin ローリング ハッシュ関数を使用) を使用することにしましたが、いくつかの問題があります。
データ：
私は 2 つの単純なテキスト ファイルを持っています。
使用されたアルゴリズム:
これは、すべてのハッシュから指紋を選択するために使用したアルゴリズムです。
void winnow(int w /*window size*/) {
// circular buffer implementing window of size w
hash_t h[w];
for (int i=0; i<w; ++i) h[i] = INT_MAX;
int r = 0; // window right end
int min = 0; // index of minimum hash
// At the end of each iteration, min holds the
// position of the rightmost minimal hash in the
// current window. record(x) is called only the
// first time an instance of x is selected as the
// rightmost minimal hash of a window.
while (true) {
r = (r + 1) % w; // shift the window by one
h[r] = next_hash(); // and add one new hash, if hash = -1, then it's end of file
if(h[r] == -1)
break;
if (min == r) {
// The previous minimum is no longer in this
// window. Scan h leftward starting from r
// for the rightmost minimal hash. Note min
// starts with the index of the rightmost
// hash.
for(int i=(r-1)%w; i!=r; i=(i-1+w)%w)
if (h[i] < h[min]) min = i;
record(h[min], global_pos(min, r, w));
} else {
// Otherwise, the previous minimum is still in
// this window. Compare against the new value
// and update min if necessary.
if (h[r] <= h[min]) { // (*)
min = r;
record(h[min], global_pos(min, r, w));
}
}
}
}
次に、両方のファイルに同じテキストがあるかどうかを検出するために、両方のテキストのフィンガープリントを比較して、一致するかどうかを確認します。したがって、盗作を検出するには、アルゴリズムは、テキスト内のまったく同じ場所から始まるハッシュを取得する必要があります。次に例を示します。
Text1: A do run |t^his my check your.
Text2: My bla lol |t^his my dasd Chicken.
同じ値を持つ正しいハッシュを取得するには (つまり、同じテキストがあることも意味します)、アルゴリズムは、'|' で指定した場所からフィンガープリントを取得する必要があります。または「^」（スペースなしで、ハッシュを計算するために5文字を取ると仮定します）。'|' からハッシュを取得することはできません これらの 2 つのハッシュは異なり、盗作は検出されないためです。
問題：
この段落がテキスト番号 1 からコピーされたかどうかを検出するには、両方のテキストのどこかに 2 つの同じフィンガープリントが必要です。問題は、アルゴリズムが互いに適合しない指紋を選択することです。つまり、はるかに大きなテキストであっても、それらは単に見逃されます。
質問：
剽窃を見つける可能性が高くなるというこのアルゴリズムを改善する方法（実際には、指紋を取得する正しいアルゴリズムにつながる）について何かアイデアはありますか？
私の考え：
winnow 関数を数回実行することを考えましたが、ウィンドウ サイズが異なる場合 (異なるハッシュが取得される原因となります) が、このプログラムが動作しなければならない大きなテキスト (2 MB のテキストのみなど) の場合、これには時間がかかりすぎます。