Algoritmo de comparação de texto

Temos uma exigência no projeto de comparar dois textos (update1, update2) e criar um algoritmo para definir quantas palavras e quantas sentenças foram alteradas.

Existe algum algoritmo que eu possa usar? Eu nem estou procurando código. Se eu conheço o algoritmo, posso codificá-lo em java. Obrigado.

Normalmente, isso é feito encontrando-se a Subsequência Comum Mais Longa (comumente chamada de problema LCS). É assim que ferramentas como o diff funcionam. Claro, diff é uma ferramenta orientada a linhas, e parece que suas necessidades são um pouco diferentes. No entanto, estou assumindo que você já construiu alguma maneira de comparar palavras e sentenças.

Um Algoritmo de Comparação de Sequência O (NP) é usado pelo mecanismo de diferenças do subversion.

Para sua informação, existem implementações com várias linguagens de programação por mim na seguinte página do github.

https://github.com/cubicdaiya/onp

Algum tipo de variante diff pode ser útil, por exemplo, wdiff

Se você decidir criar seu próprio algoritmo, precisará resolver a situação em que uma sentença foi inserida. Por exemplo, para os dois documentos a seguir:

The men are bad. I hate the men

e

The men are bad. John likes the men. I hate the men

Sua ferramenta deve ser capaz de olhar em frente para reconhecer que, no segundo, I hate the men não tenham sido substituídos por John likes the men mas, em vez disso, esteja intocado e uma nova sentença inserida antes dele. isto é, deve reportar a inserção de uma frase, não a mudança de quatro palavras seguida de uma nova sentença.

O algoritmo específico usado pelo diff e a maioria dos outros utilitários de comparação é o Algoritmo de Diferença (ND) e Suas Variações de Eugene Myer. Existe uma implementação Java disponível no pacote java-diff-utils .

Aqui estão dois artigos que descrevem outros algoritmos de comparação de texto que geralmente devem produzir diferenças “melhores” (por exemplo, menores, mais significativas):

  • Tichy, Walter F., “O Problema de Correção String-to-String com Movimentos de Bloco” (1983). Informática Relatórios Técnicos. Artigo 378.
  • Paul Heckel, “Uma técnica para isolar diferenças entre arquivos”, Comunicações da ACM, abril de 1978, volume 21, número 4

O primeiro artigo cita o segundo e menciona isso sobre seu algoritmo:

Heckel [3] apontou problemas semelhantes com as técnicas de LCS e propôs um algoritmo de cal linear para detectar movimentos de blocos. O algoritmo tem um desempenho adequado se houver poucos símbolos duplicados nas cadeias. No entanto, o algoritmo dá resultados ruins de outra forma. Por exemplo, dadas as duas strings aabb e bbaa , o algoritmo de Heckel falha em descobrir qualquer substring comum.

O primeiro artigo foi mencionado nesta resposta e o segundo nesta resposta , tanto para a pergunta SO similar:

  • Existe um algoritmo semelhante ao diff que lida com o bloco em movimento de linhas? – estouro de pilha

A dificuldade surge quando se comparam arquivos grandes de forma eficiente e com bom desempenho. Portanto, implementei uma variação do algoritmo de diferenciação Myers O (ND) – que tem um desempenho muito bom e preciso (e suporta filtragem baseada na expressão regular):

Algoritmo pode ser testado aqui: becke.ch compara aplicação web da ferramenta

E um pouco mais de informação na home page: becke.ch compare tool