Обнаружение плагиата - алгоритм затихания - столкновение отпечатков пальцев

Question

Я пишу приложение для обнаружения плагиата в больших текстовых файлах. Прочитав много статей об этом, я решил использовать алгоритм Winnowing (с катящейся хэш-функцией Карпа-Рабина), но у меня есть некоторые проблемы с этим.

Данные:

У меня есть два простых текстовых файла - первый больше, второй - только один абзац от первого.

Используемый алгоритм:

Это алгоритм, который я использовал для выбора отпечатков пальцев из всех хэшей.

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: А беги | т ^ его мой проверить твой.

Text2: Мой бла лол | мой цыпленок.

Чтобы получить правильные хэши, которые будут иметь одинаковые значения (что также означает, что у нас один и тот же текст), алгоритм должен брать отпечатки пальцев с мест, которые я указал '|' или '^' (я предполагаю, что мы берем 5 символов для вычисления хэша без пробелов). Он не может взять хеш от '|' в тексте 1 и '^' в тексте 2, потому что эти два хэша будут отличаться, и плагиат не будет обнаружен.

Проблема:

Чтобы определить, был ли этот абзац скопирован из текста № 1, мне нужно иметь два одинаковых отпечатка, где-то в обоих текстах. Проблема в том, что алгоритм выбирает те отпечатки пальцев, которые не соответствуют друг другу, я имею в виду, что они просто пропускают даже в гораздо больших текстах.

Вопрос:

Есть ли у вас какие-либо идеи, как я могу улучшить этот алгоритм (который фактически сводит к правильному алгоритму снятия отпечатков пальцев), что у него будет больше вероятности обнаружения плагиата?

Мои мысли:

Я думал о запуске функции winnow пару раз, для разных размеров окна (что приведет к тому, что будут использоваться разные хэши), но для больших текстов, над которыми эта программа должна работать (например, 2 МБ просто текст), это займет слишком много времени.

Answer 1

Если у вас есть запущенное окно, для которого вы вычисляете хеш, вы можете обновлять значение хеша за постоянное время при перемещении окна. Этот метод называется отпечатком Рабина ( см. Также). Это должно позволить вам вычислить все отпечатки пальцев размера X за время O(n) (n - это размер входного документа). Я предполагаю, что статья, которую вы цитируете, является некоторым расширенным расширением этого метода, и при правильной реализации он также должен дать вам подобное время выполнения. Ключ заключается в том, чтобы обновить хэш, а не пересчитать его.