Algoritmo de comparación de texto

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.

https://github.com/cubicdaiya/onp

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):

  • Tichy, Walter F., “El problema de la corrección de cadena a cadena con movimientos de bloque” (1983). Informes técnicos de informática. Documento 378.
  • Paul Heckel, “Una técnica para aislar las diferencias entre los archivos”, Comunicaciones de la ACM, abril de 1978, Volumen 21, Número 4

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:

  • ¿Hay algún algoritmo similar a un diff que maneje un bloque móvil de líneas? – Desbordamiento de stack

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