¿Se puede vencer a diff en su propio juego?

Question

Estoy buscando el algoritmo apropiado para comparar dos archivos. Creo que puedo hacerlo mejor que diff debido a algunas restricciones adicionales.

Lo que tengo son dos archivos de texto, cada uno con una lista de archivos. Son instantáneas de todos los archivos en un sistema tomadas en dos momentos diferentes. Quiero averiguar qué archivos se han agregado o eliminado entre las dos instantáneas.

Podría usar diff para comparar estos archivos, pero no quiero porque:

1. diff intenta agrupar los cambios, encontrando qué fragmentos en un archivo han cambiado. Solo estoy buscando una lista de líneas que han cambiado, y ese debería ser un problema mucho más simple que encontrar la subsecuencia común más larga o algo así.

2. Los algoritmos diff generalizados son O (mn) en tiempo de ejecución o espacio. Estoy buscando algo más como O (m + n) en el tiempo y O (1) en el espacio.

Aquí están las restricciones sobre el problema:

1. Los listados de archivos están en el mismo orden en ambos archivos. no están necesariamente en orden alfabético, pero están en el mismo orden relativo .

2. La mayoría de las veces no habrá diferencias entre las listas. Si hay diferencias, generalmente solo habrá un puñado de archivos nuevos / eliminados.

3. No necesito agrupar los resultados, como decir "se eliminó todo este directorio" o "las líneas 100-200 son nuevas". Puedo enumerar individualmente cada línea que es diferente.

Estoy pensando que esto es equivalente al problema de tener dos listas ordenadas y tratar de descubrir las diferencias entre las dos listas. El problema es que los elementos de la lista no están necesariamente ordenados alfabéticamente, por lo que no sabe si un elemento es '' mayor '' que otro Simplemente sabe que los archivos que están presentes en ambas listas estarán en el mismo orden.

Para lo que vale, publiqué previamente esta pregunta en < a href = "http://ask.metafilter.com/" rel = "noreferrer"> Pregunte a Metafilter hace varios años. Permítame responder a varias posibles respuestas por adelantado.

Respuesta: Este problema se llama Subsecuencia común más larga .

Respuesta: estoy tratando de evitar la subsecuencia común más larga porque los algoritmos simples se ejecutan en O (mn) tiempo / espacio y los mejores son complicados y más " heurístico " ;. Mi intuición me dice que hay un algoritmo de tiempo lineal debido a las restricciones añadidas.

Respuesta: Ordénelas alfabéticamente y luego compárelas.

Respuesta: Eso sería O (m log m + n log n) , que es peor que O (m + n) .

Answer 1

Esta no es la memoria O (1) , el requisito de memoria en el orden del número de cambios, pero es el tiempo de ejecución de O (m + n) .

Es esencialmente un algoritmo de transmisión en búfer que en cualquier línea sabe la diferencia de todas las líneas anteriores.

// Pseudo-code:
initialize HashMap<Line, SourceFile> changes = new empty HashMap
while (lines left in A and B) {
    read in lineA from file A
    read in lineB from file B

    if (lineA.equals(lineB)) continue

    if (changes.contains(lineA) && changes.get(lineA).SourceFile != A) {
         changes.remove(lineA)
    } else {
         changes.add(lineA, A)
    }

    if (changes.contains(lineB) && changes.get(lineB).SourceFile != B) {
         changes.remove(lineB)
    } else {
         changes.add(lineB, B)
    }
}

for each (line in longerFile) {
    if (changes.contains(line) && changes.get(line).SourceFile != longerFile) {
         changes.remove(line)
    } else {
         changes.add(line, longerFile)
    }
}

Lines in the HashMap from SourceFile == A have been removed
Lines in the HashMap from SourceFile == B have been added

Esto depende en gran medida del hecho de que los archivos se enumeran en el mismo orden relativo. De lo contrario, el requisito de memoria sería mucho mayor que el número de cambios. Sin embargo, debido a que ordenar este algoritmo no debería usar mucha más memoria que 2 * numChanges.

Answer 2

Lea un archivo, colocando cada nombre de archivo en un Estructura de datos tipo HashSet con O (1) add y O (1) contiene implementaciones.

Luego lea el archivo de segundos, verificando cada nombre de archivo contra el HashSet.

Algoritmo total si el archivo uno tiene longitud m y el segundo archivo tiene longitud n es O (m + n) según se requiera.

Nota: Este algoritmo supone que el conjunto de datos se ajusta cómodamente en la memoria física para ser rápido.

Si el conjunto de datos no cabe fácilmente en la memoria, la búsqueda podría implementarse usando alguna variación de un B-Tree con paginación de disco. La complejidad sería entonces O (mlog m) para configurar inicialmente y O (n log m) para cada comparación de archivos.

Answer 3

Desde un punto de vista teórico, la comparación de la distancia de edición entre dos cadenas (porque aquí tiene cadenas en un lenguaje divertido donde un 'carácter' es un nombre de archivo) no se puede hacer O (m + n). Pero aquí tenemos simplificaciones.

Una implementación de un algoritmo en su caso (debe contener errores):

# i[0], i[1] are undoable iterables; at the end they both return Null

while (a = i[0].next()) && (b = i[1].next()) :    # read one item from each stream
    if a != b:                 # skip if they are identical
        c = [[a],[b]]          # otherwise, prepare two fast arrays to store difference
        for (w = 1; ; w = 1-w) # and read from one stream at a time
             nxi = Null        
             if (nx = i[1-w].next()) in c[w]:  # if we read a new character that matches
                  nxi = c[w].index(nx)          
             if nx is Null: nxi = -1           # or if we read end of stream
             if nxi is not Null:               # then output that we found some diff
                 for cc in c[1-w]: yield cc              # the ones stored 
                 for cc in c[w][0:nxi-1]: yield cc       # and the ones stored before nx
                 for cc in c[w][nxi+1:]: i[w].undo(cc)   # about the remainder - put it back
                 break                         # and return back to normal cycle
 # one of them finished
 if a: yield a
 if b: yield b
 for ci in i: 
     while (cc = ci.next()): yield cc

Hay estructuras de datos que llamo matrices rápidas, probablemente son HashSet , pero son las que recuerdan haber ordenado. La adición y búsqueda en ellos debe ser O (log N) , pero la memoria usa O (N) .

Esto no usa ninguna memoria o ciclos más allá de O (m + n) fuera de encontrar diferencias. Para cada 'bloque de diferencia', la operación que se puede describir como quitar M elementos consecutivos y agregar N, esto requiere O (M + N) memoria y O (MN) O (Mlog N + Nlog M) instrucciones. La memoria se libera después de que se realiza un bloqueo, por lo que esto no es gran cosa si de hecho solo tiene pequeños cambios. Por supuesto, el peor de los casos es tan malo como con el método genérico.

Answer 4

En la práctica, una diferencia de factor de registro en los tiempos de clasificación es probablemente insignificante: sort puede ordenar cientos de miles de líneas en unos pocos segundos. Por lo tanto, no necesita escribir ningún código:

sort filelist1 > filelist1.sorted
sort filelist2 > filelist2.sorted
comm -3 filelist1.sorted filelist2.sorted > changes

No estoy afirmando que esta sea necesariamente la solución más rápida, creo que La respuesta aceptada de Ben S será, al menos por encima de algún valor de N. Pero definitivamente es el más simple, escalará a cualquier número de archivos y (a menos que usted sea el responsable) de la operación de copia de seguridad de Google) será más que suficientemente rápido para la cantidad de archivos que tiene.

Answer 5

Si acepta que los diccionarios (mapas hash) son O (n) espacio y O (1) inserción / búsqueda, esta solución debería ser O (m + n) tanto en tiempo como en espacio.

from collections import defaultdict
def diff(left, right):
    left_map, right_map = defaultdict(list), defaultdict(list)
    for index, object in enumerate(left): left_map[object] += [index]
    for index, object in enumerate(right): right_map[object] += [index]
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left_map[right[j]]:
            i2 = left_map[right[j]].pop(0)
            if i2 < i: continue
            del right_map[right[j]][0]
            for i in range(i, i2): print '<', left[i]
            print '=', left[i2], right[j]
            i, j = i2 + 1, j + 1
        elif right_map[left[i]]:
            j2 = right_map[left[i]].pop(0)
            if j2 < j: continue
            del left_map[left[i]][0]
            for j in range(j, j2): print '>', right[j]
            print '=', left[i], right[j2]
            i, j = i + 1, j2 + 1
        else:
            print '<', left[i]
            i = i + 1
    for j in range(j, len(right)): print '>', right[j]

>>> diff([1, 2, 1, 1, 3,    5, 2,    9],
...      [   2, 1,    3, 6, 5, 2, 8, 9])
< 1
= 2 2
= 1 1
< 1
= 3 3
> 6
= 5 5
= 2 2
> 8
= 9 9

Bien, un ligero engaño como list.append y list .__ delitem__ son solo O (1) si son listas enlazadas, lo cual no es realmente cierto. . Pero esa es la idea, de todos modos.

Answer 6

Un refinamiento de la respuesta de ephemient, esto solo usa memoria extra cuando hay cambios.

def diff(left, right):
    i, j = 0, 0

    while i < len(left) and j < len(right):
        if left[i] == right[j]:
            print '=', left[i], right[j]
            i, j = i+1, j+1
            continue

        old_i, old_j = i, j
        left_set, right_set = set(), set()

        while i < len(left) or j < len(right):
            if i < len(left) and left[i] in right_set:
                for i2 in range(old_i, i): print '<', left[i2]
                j = old_j
                break

            elif j < len(right) and right[j] in left_set:
                for j2 in range(old_j, j): print '>', right[j2]
                i = old_i
                break

            else:
                left_set .add(left [i])
                right_set.add(right[j])
                i, j = i+1, j+1

    while i < len(left):
        print '<', left[i]
        i = i+1

    while j < len(right):
        print '>', right[j]
        j = j+1

Comentarios? ¿Mejoras?

Answer 7

He estado buscando un programa para diferenciar archivos grandes sin quedarse sin memoria, pero no encontré nada que se ajustara a mis propósitos. No estoy interesado en usar los diffs para parchar (entonces probablemente usaría rdiff de librdiff), pero para inspeccionar visualmente los diffs, quizás convertirlos en word-diffs con dwdiff - -diff-input (que lee el formato diff unificado) y tal vez recolectando la palabra diff de alguna manera.

(Mi caso de uso típico: tengo alguna herramienta de PNL que utilizo para procesar un corpus de texto grande. Lo ejecuto una vez, obtengo un archivo que tiene 122760246 líneas de largo, hago un cambio en mi herramienta, lo ejecuto nuevamente, obtengo un archivo que difiere como cada millón de líneas, tal vez dos inserciones y una eliminación, o solo una línea difiere, ese tipo de cosas.)

Como no pude encontrar nada, acabo de hacer un pequeño script https: // github. com / unhammer / diff-large-files : funciona (dwdiff lo acepta como entrada), es lo suficientemente rápido (más rápido que el proceso xz que a menudo se ejecuta en la tubería), y lo más importante es que no quedarse sin memoria.

Answer 8

Leería las listas de archivos en dos conjuntos y buscaría los nombres de archivo que son únicos para cada lista.

En Python, algo así como:

files1 = set(line.strip() for line in open('list1.txt'))
files2 = set(line.strip() for line in open('list2.txt'))
print('\n'.join(files1.symmetric_difference(files2)))