大字符串的快速字符串搜索算法

Question

我正在尝试使用模式匹配算法实现抄袭检测软件。我遇到了 KMP Algorithm Here 并尝试了 c# 实现。我可以看到它对于实际文档（不是字符串，我使用 iText 上传了两个 pdf 文档并获得了检查这两篇论文中是否存在抄袭的实现。大约 50 页）并不那么快。

它真的很慢，我不知道该怎么做。我也看过 Boyer Moore 和 Rabin Karp。

我目前正在做的是获取文档中的每个句子（拆分为“.”）并扫描整个参考文档（第二个文档）以进行匹配。然后取下一句等等…… 我完全知道这可能非常昂贵。但我不知道如果不使用这种方法，还有什么方法可以实现字符串（模式）匹配。这是我最后一年的项目，我得到了一个主题，所以我必须使用字符串匹配。（不允许进行基于引用的抄袭、语义或向量 Space。）

文本和图案越大，算法就越慢（非常慢，甚至不慢）。还有其他我不知道的方法吗？还是有更快的算法供我使用我的方法？

编辑

我的代码如下：`

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

您的算法进行大量重复搜索纯粹是一种蛮力。一些问题特征可以考虑对其进行优化。你如何定义'plagiarism'？ content-1 和 content-2 几乎相似。让我们说 >80% 是相同的。即 content-1 被 20% 更改为 content-2。

现在，让我们尝试解决：将 content-1 转换为 content-2 的成本（no.of 变化）是多少？这是 DP（动态规划世界）中众所周知的问题 EDIT Distance problem。标准问题讨论的是字符串距离，但您可以轻松地将其修改为单词而不是字符。

现在，上述问题将给您带来最少 no.of content-1 到 content-2 转换的变化。使用 content-1 的总长度，我们可以轻松计算出从 content-1 到 content-2 的更改百分比。如果它低于固定阈值（比如 20%），则宣布抄袭。

大字符串的快速字符串搜索算法

Fast String Searching Algorithm for large strings

algorithm

performance

string-matching

plagiarism-detection

knuth-morris-pratt

编辑