Tenemos un requisito en el proyecto que tenemos que comparar dos textos (actualización1, actualización2) y crear un algoritmo para definir cuántas palabras y cuántas oraciones han cambiado.
¿Hay algún algoritmo que pueda usarlo? Ni siquiera estoy buscando código. Si conozco el algoritmo, puedo codificarlo en java. Gracias.
Por lo general, esto se logra al encontrar la subsecuencia común más larga (comúnmente llamada 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.
Un algoritmo de comparación de secuencias O (NP) es utilizado por el motor de diferencias de subversión.
Para su información, hay implementaciones con varios lenguajes de progtwigción por mi cuenta en la siguiente página de github.
Algún tipo de variante de diferencia podría ser útil, por ejemplo, wdiff
Si decide diseñar su propio algoritmo, tendrá que abordar la situación en la que se insertó una oración. Por ejemplo, para los siguientes dos documentos:
The men are bad. I hate the men
y
The men are bad. John likes the men. I hate the men
Su herramienta debería ser capaz de mirar hacia adelante para reconocer que en el segundo, I hate the men no hayan sido reemplazados por John likes the men sino que queden intactos, y que se inserte una nueva oración antes. 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 el algoritmo de diferencia An O (ND) de Eugene Myer y sus variaciones . Hay una implementación de Java disponible en el paquete java-diff-utils .
Aquí hay dos documentos que describen otros algoritmos de comparación de texto que generalmente deberían producir “mejores” diferencias (por ejemplo, más pequeñas, más significativas):
El primer documento cita el segundo y menciona esto sobre su algoritmo:
Heckel [3] señaló problemas similares 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 documento se mencionó en esta respuesta y el segundo en esta respuesta , ambos para la pregunta SO similar:
La dificultad surge cuando se comparan archivos grandes de manera eficiente y con un buen rendimiento. Por lo tanto, implementé una variación del algoritmo diff Myers O (ND), que funciona bastante bien y es precisa (y admite el filtrado basado en la expresión regular):
El algoritmo se puede probar aquí: becke.ch compare herramienta de aplicación web
Y un poco más de información en la página de inicio: becke.ch compare tool