Обнаружение скопированных или похожих текстовых блоков

Question

У меня есть куча текстов о программировании в формате Markdown. Существует процесс сборки, который способен преобразовывать эти тексты в Word/HTML, а также выполнять простые правила проверки, такие как проверка орфографии или проверка наличия требуемой структуры заголовка. Я хотел бы расширить этот код сборки, чтобы также проверять скопированные или похожие фрагменты во всех текстах.

Есть ли какая-либо существующая библиотека Java/Groovy, которая может помочь мне в этом анализе?

Моя первая идея заключалась в использовании PMP CopyPasteDetector, но она слишком ориентирована на анализ реального кода. Я не вижу, как я могу использовать его для анализа обычного текста.

Answer 1

В конце концов, я использовал CPD и Groovy. Вот код, если его интересует:

import net.sourceforge.pmd.cpd.Tokens 
import net.sourceforge.pmd.cpd.TokenEntry 
import net.sourceforge.pmd.cpd.Tokenizer 
import net.sourceforge.pmd.cpd.CPDNullListener 
import net.sourceforge.pmd.cpd.MatchAlgorithm 
import net.sourceforge.pmd.cpd.SourceCode 
import net.sourceforge.pmd.cpd.SourceCode.StringCodeLoader 
import net.sourceforge.pmd.cpd.SimpleRenderer 

// Prepare empty token data. 
TokenEntry.clearImages() 
def tokens = new Tokens() 

// List all source files with text. 
def source = new TreeMap<String, SourceCode>() 
new File('.').eachFile { file -> 
    if (file.isFile() && file.name.endsWith('.txt')) { 
    def analyzedText = file.text 
    def sourceCode = new SourceCode(new StringCodeLoader(analyzedText, file.name)) 
    source.put(sourceCode.fileName, sourceCode) 
    analyzedText.eachLine { line, lineNumber -> 
     line.split('[\\W\\s\\t\\f]+').each { token -> 
     token = token.trim() 
     if (token) { 
      tokens.add(new TokenEntry(token, sourceCode.fileName, lineNumber + 1)) 
     } 
     } 
    } 
    tokens.add(TokenEntry.getEOF()) 
    } 
} 

// Run matching algorithm. 
def maxTokenChain = 15 
def matchAlgorithm = new MatchAlgorithm(source, tokens, maxTokenChain, new CPDNullListener()) 
matchAlgorithm.findMatches() 

// Produce report. 
matchAlgorithm.matches().each { match -> 
    println " ========================================" 
    match.iterator().each { mark -> 
    println " DUPLICATION ERROR: <${mark.tokenSrcID}:${mark.beginLine}> [DUPLICATION] Found a ${match.lineCount} line (${match.tokenCount} tokens) duplication!" 
    } 
    def indentedTextSlice = "" 
    match.sourceCodeSlice.eachLine { line -> 
    indentedTextSlice += " $line\n" 
    } 
    println " ----------------------------------------" 
    println indentedTextSlice 
    println " ========================================" 
} 

Answer 2

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

Answer 3

Вы можете начать с простой реализации алгоритма Longest Common Substring (LCS) для двух строк. См. Один Java implementation.

Далее вы можете увидеть Suffix Arrays и Genetics and string algorithms.

См. Также Longest Common Substring in a big text.