Dificultad para entender el algorithm Diff de Paul Heckel

He estado buscando el algorithm Diff de Paul Heckel y parece que no lo entiendo del todo.

Copié los pasos 1-5 como se muestra en el código de Python, pero no puedo mostrar las diferencias usando el paso final del algorithm. Le agradecería si alguien explicara el paso final junto con el código de Python.

Además, no entiendo completamente por qué necesita una reference a las líneas de la tabla en el paso 4 y 5, por lo que una explicación de eso sería increíble también.

Muchas gracias

Aquí está mi código actual:

def find_diff(current_file_as_list, different_file_as_list): N = current_file_as_list O = different_file_as_list table = {} OA = [] NA = [] for i in O: OA.append(i) for i in N: NA.append(i) # First pass i = 0 for line in N: if not line in table: table[line] = {} table[line]["NC"] = 1 else: if table[line]["NC"] == 1: table[line]["NC"] = 2 else: table[line]["NC"] = "many" NA[i] = table[line] i += 1 # second pass j = 0 for line in O: if not line in table: table[line] = {} table[line]["OC"] = 1 else: if not "OC" in table[line]: table[line]["OC"] = 1 elif table[line]["OC"] == 1: table[line]["OC"] = 2 else: table[line]["OC"] = "many" table[line]["OLNO"] = j # Gets overwritten with multiple occurrences. # Check to see if this is the intended implementation. # Maybe only relevant for "OC" == "NC" == 1 OA[j] = table[line] j += 1 # third pass i = 0 for i in range(0, len(NA)): # Check if they appear in both files if "OC" in NA[i] and "NC" in NA[i]: # Check if they appear exactly once if NA[i]["OC"] == NA[i]["NC"] == 1: olno = NA[i]["OLNO"] NA[i], OA[olno] = olno, i i += 1 # fourth pass # ascending for i in range(0, len(NA)): for j in range(0 , len(OA)): if NA[i] == OA[j] and i + 1 < len(NA) and j + 1 < len(OA) and NA[i + 1] == OA[j + 1]: OA[j + 1] = table[O[i + 1]] NA[i + 1] = table[N[j + 1]] # fifth pass # descending for i in range(len(NA) - 1, 0, -1): for j in range(len(OA) - 1, 0, -1): if NA[i] == OA[j] and i - 1 > 0 and j - 1 > 0 and NA[i - 1] == OA[j - 1]: OA[j - 1] = table[O[i - 1]] NA[i - 1] = table[N[j - 1]] # final step implementation should go here but I'm not sure how to approach it but this is my current attempt (which I am certain is wrong): k = 0 array = [] for i in range(0, len(NA)): if isinstance(NA[i], int): array.append("= " + str(N[i])) k = NA[i] + 1 elif isinstance(NA[i], dict): array.append("+ " + N[i]) for j in range(k, len(OA)): k = j + 1 print("j - " + str(j)) if not isinstance(OA[j], int): array.append("- " + O[j]) else: break 

Puede pasar dos cadenas o una list de cadenas como input a la function, por ejemplo. find_diff ("hola", "infierno")

No estoy seguro de dónde encontraste esta explicación y código, pero tiene varios errores. Una de las páginas de Wikipedia para las references de comparación de datos era una reference al artículo de Paul , que resultó ser muy útil para comprender el algorithm.

En primer lugar, por lo que puedo ver, su implementación del último paso es correcta (suponiendo que los pasos anteriores se realizaron correctamente).

Comencemos con un problema de syntax / lenguaje: tal vez me falta algo, pero no entiendo por qué usted (y el código al que se vinculó) incrementan el índice de autoincrementación i en el tercer pase.

En cuanto a los contadores de las inputs de la tabla: en el código vinculado hay una pregunta comentada: ¿por qué necesitamos los 2 valores? La respuesta es – ¡no lo hacemos! En el documento en sí, Heckel escribe explícitamente que los únicos valores que deberían tener los contadores son 0, 1 y muchos. Puede ver que nunca usamos o consultamos los contadores para un valor 2. Adivino que este error proviene de la implementación del algorithm en un lenguaje que es más flexible que los que Heckel tenía en mente al escribir el algorithm, ya que la consulta de si existe un contador para una input de tabla específica es sinónimo de consulta si el contador el valor es 0.

Por último, y lo más importante, los pases cuarto y quinto en esta implementación son incorrectos. Aquí creo que la networkingacción de los pases en el papel puede ser confusa y que quien escribió el código vinculado se equivocó. Tu segunda pregunta ya lo revela. El cuarto pase está en order ascendente sobre NA y para cada position con su valor apuntando a una position en OA (lo que significa que es de tipo int en la implementación discutida) verificamos si los valores de las siguientes posiciones en ambas matrices apuntan a la misma input de tabla . Si lo hacen, reemplazamos esos pointers con la position de los demás (anulando los pointers con int . Así que su segunda pregunta fue sobre el punto – no usamos los pointers de input de tabla aquí en absoluto). De esta manera, tenemos nuestras líneas únicas, descubiertas en el tercer paso, como anclajes para encontrar líneas sin trazar que vienen inmediatamente después de ellas y son parte de su "bloque", pero no son únicas en los files. Lo mismo ocurre en el quinto pase, pero al revés, por lo que las líneas idénticas que preceden a las líneas únicas inalteradas también se clasificarían como inalteradas.

Este es el cuarto y quinto pases como los describí:

 # fourth pass # ascending for i in range(0, len(NA) - 1): if isinstance(NA[i], int) and (NA[i] + 1) < len(OA) and NA[i + 1] == OA[NA[i] + 1]: NA[i + 1] = NA[i] + 1 OA[NA[i] + 1] = i + 1 # fifth pass # descending for i in range(len(NA) - 1, 0, -1): if isinstance(NA[i], int) and (NA[i] - 1) >= 0 and NA[i - 1] == OA[NA[i] - 1]: NA[i - 1] = NA[i] - 1 OA[NA[i] - 1] = i - 1