Algoritmo de diferencia de texto

Necesito un algoritmo que pueda comparar dos archivos de texto y resaltar su diferencia y (¡aún mejor!) Puede calcular su diferencia de manera significativa (como dos archivos similares deben tener una puntuación de similitud mayor que dos archivos diferentes, con la palabra “similar” definido en los términos normales). Suena fácil de implementar, pero no lo es.

La implementación puede ser en c # o python.

Gracias.

En Python, hay difflib , como también otros han sugerido.

difflib ofrece la clase SequenceMatcher , que puede usarse para darle una relación de similitud. Función de ejemplo:

 def text_compare(text1, text2, isjunk=None): return difflib.SequenceMatcher(isjunk, text1, text2).ratio() 

Puedo recomendar echar un vistazo al código y los artículos de Neil Fraser:

google-diff-match-patch

Actualmente disponible en Java, JavaScript, C ++ y Python. Independientemente del idioma, cada biblioteca presenta la misma API y la misma funcionalidad. Todas las versiones también tienen arneses de prueba integrales.

Neil Fraser: Diff Strategies – para notas teóricas y de implementación

Mira difflib . (Pitón)

Eso calculará las diferencias en varios formatos. Entonces, ¿podría usar el tamaño de la diferencia de contexto como una medida de cuán diferentes son dos documentos?

Bazaar contiene un algoritmo de diferencia alternativo, llamado paciencia de diferencia (hay más información en los comentarios en esa página) que se dice que es mejor que el algoritmo de diferenciación tradicional. El archivo ‘patiencediff.py’ en la distribución de bazar es un simple extremo de línea de comando.

Mi entendimiento actual es que la mejor solución para el problema del Script (Shortest Edit Script) es el método de “serpiente media” de Myers con el refinamiento del espacio lineal de Hirschberg.

El algoritmo de Myers se describe en:

E. Myers, “ Un algoritmo de diferencia de O (ND) y sus variaciones, ”
Algorithmica 1, 2 (1986), 251-266.

La utilidad de diferencia GNU usa el algoritmo de Myers.

La “puntuación de similitud” de la que habla se denomina “distancia de edición” en la literatura, que es el número de inserciones o eliminaciones necesarias para transformar una secuencia en otra.

Tenga en cuenta que varias personas han citado el algoritmo de distancia Levenshtein, pero esto es, aunque fácil de implementar, no es la solución óptima, ya que es ineficiente (requiere el uso de una gran matriz n * m) y no proporciona el “script de edición “que es la secuencia de ediciones que podrían utilizarse para transformar una secuencia en la otra y viceversa.

Para una buena implementación de Myers / Hirschberg, mira:

http://www.ioplex.com/~miallen/libmba/dl/src/diff.c

La biblioteca particular en la que está contenida ya no se mantiene, pero que yo sepa, el propio módulo diff.c sigue siendo correcto.

Micro

Si necesita una granularidad más fina que las líneas, puede usar la distancia Levenshtein. La distancia de Levenshtein es una medida directa de cómo son dos textos similares.
También puede usarlo para extraer los registros de edición y puede hacer una diferencia muy fina, similar a la de las páginas de historial de edición de SO. Sin embargo, tenga en cuenta que la distancia de Levenshtein puede ser bastante intensiva en el uso de memoria y CPU, por lo que el uso de difflib, como sugirió Douglas Leder, probablemente sea más rápido.

Cf. También esta respuesta .

Hay una serie de métricas de distancia, como paradoja mencionó, existe la distancia de Levenshtein, pero también hay NYSIIS y Soundex . En términos de implementaciones de Python, he usado py-editdist y ADVAS antes. Ambos son agradables en el sentido de que obtienes un solo número como puntaje. Echa un vistazo a ADVAS primero, implementa un montón de algoritmos.

Como se indica, utilice difflib. Una vez que tenga la salida diferida, puede encontrar la distancia Levenshtein de las diferentes cadenas para dar un “valor” de cuán diferentes son.

Podría usar la solución al problema de la Subsecuencia Común Más Larga (LCS) . Consulte también la discusión sobre posibles formas de optimizar esta solución.

Un método que he empleado para una funcionalidad diferente, para calcular la cantidad de datos nuevos en un archivo modificado, también podría funcionar para usted.

Tengo una implementación de D / parche C # que me permite tomar dos archivos, supuestamente antiguos y nuevos, y calcular la “diferencia”, pero no en el sentido habitual de la palabra. Básicamente calculo un conjunto de operaciones que puedo realizar en la versión anterior para actualizarla y tener el mismo contenido que la nueva versión.

Para usar esto para la funcionalidad inicialmente descrita, para ver cuántos datos eran nuevos, simplemente repasé las operaciones y para cada operación que copió literalmente el archivo antiguo, que tenía un factor 0, y cada operación que insertaba texto nuevo. (distribuido como parte del parche, ya que no ocurrió en el archivo anterior) tenía un factor 1. Todos los personajes recibieron esta fábrica, que me dio básicamente una larga lista de 0 y 1.

Todo lo que tenía que hacer era sumr los 0 y los 1. En su caso, con mi implementación, un número bajo de 1 comparado con 0 significaría que los archivos son muy similares.

Esta implementación también manejaría casos en los que el archivo modificado había insertado copias del archivo anterior fuera de orden o incluso duplicadas (es decir, si copia una parte desde el principio del archivo y la pega en la parte inferior), ya que ambas serían Copias de la misma pieza original del archivo anterior.

Experimenté pesando copias, de modo que la primera copia contó como 0, y las copias subsiguientes de los mismos caracteres tuvieron factores progresivamente más altos, para dar a una operación de copiar / pegar algo de “nuevo factor”, pero nunca la terminé como la proyecto fue desechado.

Si está interesado, mi código de diferencia / parche está disponible en mi repository de Subversion.

Echa un vistazo al módulo Fuzzy . Cuenta con algoritmos rápidos (escritos en C) para soundex, NYSIIS y doble metáfono.

Puede encontrar una buena introducción en: http://www.informit.com/articles/article.aspx?p=1848528