Алгоритм быстрого поиска строк для больших строк

Question

Я пытаюсь реализовать программное обеспечение для обнаружения плагиата, используя алгоритмы сопоставления с образцом. Здесь я наткнулся на алгоритм KMP и опробовал реализацию C#. Я вижу, что это не так быстро для реальных документов (не для строк, я загрузил два PDF-документа с помощью iText и получил реализацию для проверки на плагиат в этих двух статьях. Около 50 страниц).

Это очень медленно, и я понятия не имею, как это сделать. Я также посмотрел на Бойера Мура и Рабина Карпа.

Сейчас я беру каждое предложение в документе (разделенное на ".") И сканирую весь справочный документ (2-й документ) на предмет соответствия. Затем, взяв следующее предложение и так далее... Я полностью осознаю, что это может быть очень дорого. Но я понятия не имею, как еще реализовать сопоставление строк (шаблонов) без использования этого подхода. Это для моего последнего года проекта, и мне дали тему, поэтому я должен использовать сопоставление строк. (Не разрешается делать плагиат на основе цитирования, семантику или векторное пространство.)

Чем больше текст и шаблон, тем медленнее становится алгоритм (чрезвычайно медленно, даже не слишком медленно). Есть ли другой способ сделать это, которого я не знаю? Или есть более быстрые алгоритмы для меня, чтобы использовать с этим моим подходом?

РЕДАКТИРОВАТЬ

Мой код ниже:`

public class MatchChecker
{
    public void KMPSearch(string pattern, string text, int page)
    {
        if (pattern.Trim() != "")
        {
            int M = pattern.Length;
            int N = text.Length;

            // create lps[] that will hold the longest
            // prefix suffix values for pattern
            int[] lps = new int[M];
            int j = 0;  // index for pat[]

            // Preprocess the pattern (calculate lps[]
            // array)
            computeLPSArray(pattern, M, lps);

            int i = 0;  //index for text[]
            while (i < N)
            {
                if (pattern[j] == text[i])
                {
                    j++;
                    i++;
                }
                if (j == M)
                {
                    Console.WriteLine("Found pattern " + pattern + " at page " + page);
                    j = lps[j - 1];
                }
                //mismatch after j matches 
                else if (i < N && pattern[j] != text[i])
                {
                    //Do not match lps[0..lps[j-1]] characters,
                    //they will match anyway
                    if (j != 0)
                        j = lps[j - 1];
                    else
                        i = i + 1;
                }
            }
        }
    }

    private void computeLPSArray(string pattern, int M, int[] lps)
    {

        //length of the previous longest prefix suffix
        int length = 0;
        int i = 1;
        lps[0] = 0;     //lps[0]is always 0

        //the loop calculates lps[i] for i = 1 to M - 1
        while (i < M)
        {
            if (pattern[i] == pattern[length])
            {
                length++;
                lps[i] = length;
                i++;
            }
            else  // (pat[i] != pat[len])
            {
                // This is tricky. Consider the example.
                // AAACAAAA and i = 7. The idea is similar 
                // to search step.
                if (length != 0)
                {
                    length = lps[length - 1];

                    // Also, note that we do not increment
                    // i here
                }
                else  // if (len == 0)
                {
                    lps[i] = length;
                    i++;
                }
            }
        }
    }

    public string ReadDocPDF()
    {
        List<string> pages = new List<string>();
        PdfReader reader2 = new PdfReader(@"C:\Users\obn\Desktop\project\chapter1.pdf");
        string strText = string.Empty;

        for (int page = 1; page <= reader2.NumberOfPages; page++)
        {
            ITextExtractionStrategy its = new SimpleTextExtractionStrategy();
            PdfReader reader = new PdfReader(@"C:\Users\obn\Desktop\project\chapter1.pdf");
            String s = PdfTextExtractor.GetTextFromPage(reader, page, its);

            s = Regex.Replace(Encoding.UTF8.GetString(ASCIIEncoding.Convert(Encoding.Default, Encoding.UTF8, Encoding.Default.GetBytes(s))).Replace(",", ""), "[0-9]", "").ToLower();
            pages.Add(s);
            strText = strText + s;
            reader.Close();
        }
        return strText;
    }

    public void CheckForPlag()
    {
        string document = ReadDocPDF().Trim();
        string[] sentences = document.Split(new string[] { "\n", "\t\n\r", ". ", "." }, StringSplitOptions.RemoveEmptyEntries);

        foreach(string sentence in sentences) {
            PdfReader reader2 = new PdfReader(@"C:\Users\obn\Documents\visual studio 2015\Projects\PlagDetector\PlagDetector\bin\Debug\test3.pdf");
            for (int page = 1; page <= reader2.NumberOfPages; page++)
            {
                ITextExtractionStrategy its = new SimpleTextExtractionStrategy();
                PdfReader reader = new PdfReader(@"C:\Users\obn\Documents\visual studio 2015\Projects\PlagDetector\PlagDetector\bin\Debug\test3.pdf");
                String s = PdfTextExtractor.GetTextFromPage(reader, page, its);

                s = Regex.Replace(Encoding.UTF8.GetString(ASCIIEncoding.Convert(Encoding.Default, Encoding.UTF8, Encoding.Default.GetBytes(s))).Trim().Replace(".","").Replace(",","").Replace("\n", ""), "[0-9]", "").ToLower();
                KMPSearch(sentence, s, page);
                reader.Close();
            }
        }


    }
}`

Answer 1

Ваш алгоритм делает много повторных поисков чисто грубой силой. Некоторые из особенностей проблемы могут быть рассмотрены для ее оптимизации. Как вы определяете "плагиат"? content-1 и content-2 почти одинаковы. Допустим,>80% одинаковы. т. е. содержание-1 взято на 20% и произведено содержание-2.

Теперь давайте попробуем решить: сколько будет стоить (без изменений) конвертация контента-1 в контент-2? Это хорошо известная проблема в DP(мире динамического программирования) как проблема EDIT Distance. Стандартная проблема говорит о расстоянии между строками, но вы можете легко изменить его для слов вместо символов.

Теперь вышеуказанная проблема даст вам наименьшее количество изменений для преобразования контента-1 в контент-2. С общей длиной контента-1, мы можем легко вычислить% изменений, чтобы перейти к контенту-2 от контента-1. Если оно ниже установленного порога (скажем, 20%), тогда объявите плагиат.