抄袭检测 - 风选算法 - 指纹冲突

Question

我在大文本文件中编写抄袭检测应用程序.在阅读了很多关于它的文章后,我决定使用Winnowing算法(使用Karp-Rabin滚动哈希函数),但我遇到了一些问题.

数据:

我有两个简单的文本文件 - 第一个是较大的文件,第二个是第一个的一个段落.

使用的算法:

这是我用来从所有哈希中选择我的指纹的算法.

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运行| t ^他我的检查你的.

Text2:我的责备了他的我的dasd鸡.

要获得具有相同值的正确哈希值(这也意味着我们具有相同的文本),算法应该从我指向"|"的位置获取指纹 或'^'(我假设我们用5个字符来计算哈希值,没有空格).它不能从'|'获取哈希值 在文本1和文本2中的'^',因为这两个哈希值将不同,并且不会检测到抄袭.

问题:

要检测此段落是否从文本编号1复制,我必须在两个文本中的某处都有两个相同的指纹.问题是算法选择那些不适合彼此的指纹,我的意思是他们只是错过了,即使是在更大的文本中.

题:

您是否有任何想法如何改进此算法(实际上归结为羚牛指纹的正确算法),它会更有可能找到抄袭？

我的想法:

我想过运行箕功能几次,对于不同的窗口大小(这将导致不同的散列将采取),但对在本方案将不得不工作(如2MB只是文本)大文本,这将花费太多时间.

Answer 1

如果您有正在计算哈希值的运行窗口，则可以在窗口移动时在恒定时间内更新哈希值。该方法称为拉宾指纹（另请参阅）。这应该允许您在 O(n) 运行时间内计算大小为 X 的所有指纹（n 是输入文档的大小）。我想您引用的论文是该方法的一些高级扩展，如果正确实现，它也应该为您提供类似的运行时间。关键是更新哈希而不是重新计算它。