Quais são algumas maneiras eficientes de encontrar as diferenças entre dois grandes grupos de texto que possuem conteúdo semelhante, mas diferentemente ordenado?

Eu tenho dois arquivos grandes que contêm parágrafos do texto em inglês:

1. O primeiro texto tem cerca de 200 páginas e 10 parágrafos por página (cada parágrafo tem 5 sentenças).
2. O segundo texto contém quase exatamente os mesmos parágrafos e texto que o primeiro. Também tem 200 páginas, com 10 parágrafos por página. No entanto, os parágrafos são randomizados e em uma ordem diferente quando comparados ao primeiro texto. Além disso, uma grande porcentagem dos parágrafos apresenta pequenas alterações na redação em comparação com parágrafos semelhantes. Por exemplo, um parágrafo no primeiro texto pode ter uma frase como Like Jimmy, I wanted to go to the palacea frase correspondente no parágrafo do segundo texto seria lida Like Jimmy, I really wanted to go to the castle.

Quero poder capturar as alterações aqui, como a adição reallye a exclusão de palacecom a substituição de castle. Se os parágrafos fossem mais ou menos alinhados, isso seria bastante trivial, pois existem várias maneiras de diferenciar o texto. No entanto, como os parágrafos não estão alinhados, esse não é o caso.

Se os arquivos fossem pequenos (poucos parágrafos), o Levenshtein Distance provavelmente funcionaria bem, mas como os arquivos são enormes, seria ineficiente comparar cada parágrafo do texto 1 com cada parágrafo do texto 2 para descobrir quais parágrafos correspondem.

Quais seriam algumas outras abordagens para esse problema para lidar com ele com eficiência?

A comparação de parágrafos de 2000 a parágrafos de 2000 é de apenas quatro milhões de comparações.

A chave do problema não é usar uma função que calcula a distância de Levenshtein, mas usar uma função que calcula a distância de Levenshtein se a distância for menor que um determinado limite e falhar (ou melhor, retornar + ∞) se a distância for maior que o limite.

Isso ocorre porque você está interessado apenas em parágrafos semelhantes. Você não tem nenhum interesse na distância precisa entre parágrafos que são diferentes o suficiente para não serem relacionados. Portanto, assim que a distância estiver alta o suficiente para ser desinteressante, a função poderá sair imediatamente; e isso geralmente ocorrerá muito cedo, durante a execução da função.

Quanto maior o limite, maior o tempo de execução, mas menor a proporção de falsos negativos.

Se você souber algo mais sobre os documentos (como que cada parágrafo corresponda a no máximo um parágrafo no outro documento), poderá fazer uma passagem com um limite baixo, excluir os parágrafos correspondentes de uma análise mais aprofundada, fazer uma passagem sobre o seu agora reduzido corpus com um limite mais alto, exclua os parágrafos reduzidos e assim por diante.

Detalhes da implementação: Presumivelmente, você calcularia uma distância de Levenshtein com palavras e não com caracteres. Se for esse o caso, primeiro atribua um número a cada palavra - por exemplo, classificando o corpus inteiro, chamando a primeira palavra '1', a segunda palavra '2' e assim por diante. Dessa forma, suas comparações de parágrafos seriam feitas comparando números em vez de palavras, o que é mais rápido.

Pode ser possível usar uma abordagem composta. Talvez alguém possa construir sobre isso ...

Misture o conteúdo do parágrafo de maneira que parágrafos com apenas pequenas diferenças possuam hashes semelhantes e, em seguida, ordene os hashes para determinar quais parágrafos comparar por meio de um método mais exato (diff ou algo semelhante).

Por exemplo, como um algoritmo de hash rudimentar, e se você somasse os valores ascii dos caracteres e modulasse a soma por um número grande, como 2.000.000.000? Isso faria com que dois parágrafos com apenas algumas palavras adicionadas ou subtraídas tivessem valores de hash que provavelmente estão mais próximos do que parágrafos com palavras muito diferentes e, portanto, eles estarão muito mais próximos na lista do que os parágrafos muito diferentes (você pode dizer hashes próximos, neste caso, são necessários, mas não suficientes para parágrafos semelhantes). Obviamente, você deve levar em consideração o envolvimento causado pelo módulo e considerar um parágrafo com o valor de hash 1.999.999.999 como sendo apenas uma distância de 1 de um com valor de 0, etc.

Como resultado, pode reduzir o número de comparações entre parágrafos que você precisa executar em uma quantidade substancial (você não precisaria comparar cada parágrafo em um texto com cada parágrafo no outro texto) - você poderia comparar um parágrafo com parágrafos no texto 2 em ordem de quão próximos são seus hashes (faça os mais próximos com valor de hash primeiro) e invoque um algoritmo mais caro aqui para determinar se eles são "suficientemente parecidos" para serem considerados iguais.