Алгоритм Рабина – Карпа для реализации плагиата с использованием скользящего хэша

Question

Я использую алгоритм Рабина – Карпа для проверки плагиата для любых двух файлов исходного кода, поэтому сначала я просто реализую его алгоритм на C #, здесь его код, но его среднее и лучшее время выполнения O (n + m) в пространстве O(p), но его наихудшее время - O (нм).

 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");
        }

    }

, поэтому как сделать его более эффективным, используя скользящую хэш-функцию, потому что это лучше, чем эта ..

Answer 1

Статья в Википедии содержит достаточно хорошее описание алгоритма и даже упоминает, как можно реализовать скользящую хеш-функцию (см. «Использование хеширования для поиска смещения подстроки»).В нем также рассматривается, как повысить скорость выполнения с помощью хеш-таблицы или фильтра Блума.

Вам также нужно понимать, что наихудший случай - довольно надуманный пример.Пример, приведенный в статье в Википедии: «поиск строки из 10000« a », за которой следует« b »в строке из 10 миллионов» a ». '

Вы должны быть в состоянии реализоватьпереходящий хэш с использованием методов, описанных в этой записи в Википедии.Если у вас возникли проблемы с его реализацией, оставьте более конкретный вопрос о том, как это делается, и покажите, что вы пробовали.

Маловероятно, что вы встретите что-либо, приближающееся к худшему случаю в реальных документах.Даже если вы столкнетесь с наихудшим случаем, переходящий хеш не уменьшит сложность.Реализация скользящего хэша дает линейное улучшение времени выполнения, которое будет подавлено сложностью n*m.Если вы обнаружите, что наихудший случай случается часто, тогда вам, вероятно, нужен другой алгоритм.

Еще одна вещь, на которую стоит обратить внимание, это то, что, в то время как O(m*n) может быть проблемой, вы должны посмотреть на масштаб.Насколько большие документы вы изучаете?Вы говорите, что работаете с файлами исходного кода.Если вы смотрите на типичные проекты классов, то вы, вероятно, говорите, может быть, 2000 строк кода.Эти документы не собираются показывать худший случай.Даже если они это сделают, n*m не будет очень большим числом.

Однако, если у вас есть 100 документов, и вы хотите знать, является ли один из них существенным дубликатом другого, ваш размер больше.проблема в O (n ^ 2), потому что вы должны сверять каждый документ со всеми остальными.Количество сравнений документов равно (n*(n-1))/2.Если вы хотите оптимизировать свой процесс, вам нужен другой алгоритм.В идеале, то, что даст вам «отпечаток» документа.Таким образом, вы можете вычислить отпечаток пальца для каждого документа один раз, а затем сравнить отпечатки пальцев на предмет сходства.

Отпечатки документов - это хорошо известная проблема.Тем не менее, создание отпечатка пальца, который полезен для целей сравнения, немного проще.Вы хотели бы изучить технику под названием shingling.Я также видел некоторые исследования об использовании небольшого фильтра Блума (256 байтов или около того) для представления документа и возможности делать быстрые сравнения, используя это.

Все это говорит, я подозреваю, что если вы говоритеиз ста или двух файлов исходного кода, каждый из которых может быть длиной 1000 или 2000 строк, наивный метод сравнения O (n ^ 2) с использованием хорошей реализации Рабина-Карпа будет делать то, что вы хотите.Это займет некоторое время (вы проведете 5000 отдельных сравнений документов), но я не думаю, что скорость внедрения РК будет вашим ограничивающим фактором.