¿Cuáles son algunas formas eficientes de encontrar las diferencias entre dos grandes corpus de texto que tienen contenido similar pero ordenado de manera diferente?

Tengo dos archivos grandes que contienen párrafos de texto en inglés:

1. El primer texto tiene aproximadamente 200 páginas y tiene aproximadamente 10 párrafos por página (cada párrafo tiene 5 oraciones).
2. El segundo texto contiene casi exactamente los mismos párrafos y texto que el primero. También tiene 200 páginas con 10 párrafos por página. Sin embargo, los párrafos son aleatorios y en un orden diferente en comparación con el primer texto. Además, un gran porcentaje de los párrafos tienen pequeños cambios en la redacción en comparación con párrafos similares. Por ejemplo, un párrafo en el primer texto podría tener una oración similar a la Like Jimmy, I wanted to go to the palaceque se leería la oración correspondiente en el párrafo del segundo texto Like Jimmy, I really wanted to go to the castle.

Quiero poder capturar los cambios aquí, como la adición reallyy la eliminación de palacecon el reemplazo de castle. Si los párrafos estuvieran más o menos alineados, esto sería bastante trivial, ya que hay muchas maneras de diferenciar el texto. Sin embargo, dado que los párrafos no están alineados, ese no es el caso.

Si los archivos fueran pequeños (un puñado de párrafos), Levenshtein Distance probablemente funcionaría bien, pero debido a que los archivos son enormes, sería ineficiente comparar cada párrafo del texto 1 con cada párrafo del texto 2 para averiguar qué párrafos coinciden.

¿Cuáles serían algunos otros enfoques de este problema para manejarlo de manera eficiente?

Comparar 2000 párrafos con 2000 párrafos es solo cuatro millones de comparaciones.

La clave del problema no es usar una función que calcule la distancia de Levenshtein, sino usar una que calcule la distancia de Levenshtein si la distancia es menor que un cierto umbral y falla (o, más bien, devuelve + ∞) si la distancia es mayor que el umbral.

Esto se debe a que solo le interesan párrafos muy similares. No tiene ningún interés en la distancia precisa entre párrafos que son lo suficientemente diferentes como para no estar relacionados. Entonces, tan pronto como la distancia sea lo suficientemente alta como para no ser interesante, la función puede salir de inmediato; y esto sucederá principalmente muy pronto durante la ejecución de la función.

Cuanto mayor sea el umbral, mayor será el tiempo de ejecución pero menor será la proporción de falsos negativos.

Si sabe algo más sobre los documentos (como que cada párrafo coincide como máximo con un párrafo del otro documento), entonces podría hacer un pase con un umbral bajo, excluir los párrafos coincidentes de mayor consideración, hacer un pase sobre su ahora reducido corpus con un umbral más alto, excluya esos párrafos reducidos, etc.

Detalle de implementación: presumiblemente estaría calculando una distancia de Levenshtein en palabras en lugar de en caracteres. Si ese es el caso, primero debe asignar un número a cada palabra, por ejemplo, ordenando todo el corpus, llamando a la primera palabra '1', la segunda palabra '2', y así sucesivamente. De esa manera, las comparaciones de los párrafos se realizarían comparando números en lugar de palabras, lo que es más rápido.

Podría ser posible utilizar un enfoque compuesto. Quizás alguien pueda construir sobre esto ...

Hash el contenido del párrafo de tal manera que los párrafos con solo pequeñas diferencias tengan valores hash similares, luego ordene los valores hash para determinar qué párrafos comparar a través de un método más exacto (diff o algo similar).

Por ejemplo, como un algoritmo hash rudimentario, ¿qué pasa si suma los valores ascii de los caracteres y luego modula la suma en un gran número como 2,000,000,000? Esto provocaría que 2 párrafos con solo unas pocas palabras agregadas o restadas tengan valores hash que probablemente estén más juntos que los párrafos con palabras muy diferentes, y por lo tanto, estarán mucho más juntos en la lista que los párrafos muy diferentes (se podría decir los hashes cercanos en este caso son necesarios pero no suficientes para párrafos similares). Obviamente, debe tener en cuenta la envoltura causada por el módulo y considerar un párrafo con el valor hash 1,999,999,999 como solo una distancia de 1 de uno con un valor de 0, etc.

Como resultado, podría reducir la cantidad de comparaciones entre párrafos que debe realizar en una cantidad considerable (no tendría que comparar cada párrafo en un texto con cada párrafo en el otro texto); podría comparar un párrafo con párrafos del texto 2 en orden de cuán cerca están sus valores hash (haga primero los valores con valores hash más cercanos) e invoque aquí un algoritmo más costoso para determinar si son "lo suficientemente similares" para ser considerados iguales.