Tenemos un requisito en el proyecto que tenemos que comparar dos textos (update1, update2) y proponer un algoritmo para definir cuántas palabras y cuántas oraciones han cambiado.Algoritmo de comparación de texto
¿Hay algún algoritmo que pueda usarlo? Ni siquiera estoy buscando código. Si conozco el algoritmo, puedo codificarlo en java. Gracias.
Normalmente esto se logra al encontrar el Longest Common Subsequence (comúnmente llamado el problema LCS). Así es como funcionan las herramientas como diff. Por supuesto, diff es una herramienta orientada a la línea, y parece que sus necesidades son algo diferentes. Sin embargo, asumo que ya has construido una forma de comparar palabras y oraciones.
Una especie de variante de diff puede ser útil, por ejemplo wdiff
Si decide diseñar su propio algoritmo, vas a tener que hacer frente a la situación en la que se ha insertado una frase. Por ejemplo, para los dos documentos siguientes:
The men are bad. I hate the men
y
The men are bad. John likes the men. I hate the men
Su herramienta debe ser capaz de mirar hacia adelante a reconocer que en el segundo, I hate the men no ha sido sustituido por John likes the men pero en cambio, no se toca, y se le inserta una nueva oración. es decir, debe informar la inserción de una oración, no el cambio de cuatro palabras seguido de una nueva oración.
El algoritmo específico utilizado por diff y la mayoría de otras utilidades de comparación es An O(ND) Difference Algorithm and Its Variations de Eugene Myer. Hay una implementación de Java disponible en el paquete java-diff-utils.
An O(NP) Sequence Comparison Algorithm es utilizado por el motor diff de subversion.
Para su información, hay implementaciones con varios lenguajes de programación en la siguiente página de github.
La dificultad viene cuando la comparación de archivos de gran tamaño de manera eficiente y con un buen rendimiento. Por lo tanto, he implementado una variación de Myers O (ND) algoritmo diff - que lleva a cabo bastante bien y preciso (y compatible con el filtrado basado en la expresión regular):
algoritmo se puede probar aquí: becke.ch compare tool web application
Y un poco más información en la página de inicio: becke.ch compare tool
Aquí hay dos documentos que describen otros algoritmos de comparación de texto que generalmente deberían dar como resultado 'mejor' (por ej.más pequeños, más significativos) diferencias:
El primer documento cita el segundo y menciona esto sobre su algoritmo:
Heckel [3] señalaron similares problemas con las técnicas LCS y propuso un algoritmo de cal lineal para detectar movimientos de bloque. El algoritmo funciona adecuadamente si hay pocos símbolos duplicados en las cadenas. Sin embargo, el algoritmo da resultados pobres de lo contrario. Por ejemplo, dadas las dos cadenas aabb y bbaa, El algoritmo de Heckel no puede descubrir ninguna subcadena común.
El primer papel fue mencionado en this answer y la segunda en this answer, tanto a la similares SO pregunta:
http://stackoverflow.com/questions/65199/ c-sharp-compare-algorithms –
http://neil.fraser.name/software/diff_match_patch/myers.pdf –