Algoritmo de diferencia de texto

Question

Necesito un algoritmo que pueda comparar dos archivos de texto y resaltar su diferencia y (¡incluso mejor!) que pueda calcular su diferencia de manera significativa (como dos archivos similares deberían tener un puntaje de similitud más alto que dos archivos diferentes, con la palabra `` similar '' definido en los términos normales). Parece fácil de implementar, pero no lo es.

La implementación puede ser en C # o Python.

Gracias.

Answer 1

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

difflib ofrece la clase SequenceMatcher , que se puede usar 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()

Answer 2

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. Sin importar   de lenguaje, cada biblioteca presenta el   misma API y la misma funcionalidad.   Todas las versiones también tienen una completa   arneses de prueba.

Neil Fraser: Diff Strategies - para notas de teoría e implementación

Answer 3

Mire difflib . (Python)

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?

Answer 4

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

Answer 5

Mi comprensión actual es que la mejor solución para el problema de la secuencia de comandos de edición más corta es Myers " middle-snake " método con el refinamiento del espacio lineal de Hirschberg.

El algoritmo Myers se describe en:

  

E. Myers, `` Una diferencia O (ND)   Algoritmo y sus variaciones ''
  Algorithmica 1, 2 (1986), 251-266.

La utilidad GNU diff utiliza el algoritmo Myers.

El " puntaje de similitud " del que hablas se llama " editar distancia " en la literatura, que es el número de inserciones o eliminaciones necesarias para transformar una secuencia en la otra.

Tenga en cuenta que varias personas han citado el algoritmo de distancia de Levenshtein pero que, aunque es fácil de implementar, no es la solución óptima, ya que es ineficiente (requiere el uso de una matriz de n * m posiblemente enorme) y no proporciona el " editar guión " cuál es la secuencia de ediciones que podrían usarse para transformar una secuencia en la otra y viceversa.

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

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 módulo diff.c sigue siendo correcto.

Mike

Answer 6

Si necesita una granularidad más fina que las líneas, puede usar la distancia de Levenshtein. La distancia de Levenshtein es una medida directa de cómo son similares dos textos.
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 del historial de edición de SO. Sin embargo, tenga en cuenta que la distancia de Levenshtein puede ser bastante intensiva para calcular la CPU y la memoria, por lo que utilizar difflib, como sugirió Douglas Leder, probablemente sea más rápido.

Cf. también esta respuesta .

Answer 7

Hay varias métricas de distancia, ya que paradoja mencionó que 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 buenos en el sentido de que obtienes un solo número como puntaje. Echa un vistazo a ADVAS primero, implementa un montón de algoritmos.

Answer 8

Como se indicó, use difflib. Una vez que tenga la salida diferida, puede encontrar la distancia de Levenshtein de las diferentes cadenas como para dar un " valor " de lo diferentes que son.

Answer 9

Puede usar la solución al problema de la subsecuencia común más larga (LCS) . Consulte también la discusión sobre las posibles formas de optimizar esta solución.

Answer 10

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

Tengo una implementación diff / patch C # que me permite tomar dos archivos, presumiblemente una versión antigua y una nueva del mismo archivo, 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 actualizarlo y tener el mismo contenido que la nueva versión.

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

Todo lo que tenía que hacer era contar los 0 y 1. En su caso, con mi implementación, un número bajo de 1 en comparación 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 antiguo fuera de servicio, o incluso duplicados (es decir, copia una parte desde el inicio del archivo y la pega cerca de la parte inferior), ya que ambos serían copias de la misma parte original del archivo anterior.

Experimenté pesando copias, de modo que la primera copia contaba como 0, y las copias posteriores de los mismos caracteres tenían factores progresivamente más altos, a fin de dar a la operación de copiar / pegar algo de "factor nuevo", pero nunca lo terminé cuando el proyecto fue descartado.

Si está interesado, mi código de diferencias / parches está disponible en mi repositorio de Subversion.

Answer 11

Eche un vistazo al módulo Fuzzy . Tiene algoritmos rápidos (escritos en C) basados ??en soundex, NYSIIS y doble metafonía.

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