algoritmo de diferença texto

StackOverflow https://stackoverflow.com/questions/145607

  •  02-07-2019
  •  | 
  •  

Pergunta

Eu preciso de um algoritmo que pode comparar dois arquivos de texto e destacar a sua diferença e (ainda melhor!) Pode calcular a sua diferença de uma forma significativa (como dois arquivos semelhantes devem ter uma pontuação maior similaridade de dois arquivos diferentes, com a palavra "semelhante" definido nas condições normais). Parece fácil de implementar, mas não é.

A aplicação pode ser em C # ou python.

Graças.

Foi útil?

Solução

Em Python, há difflib , como também já foi sugerido.

ofertas difflib SequenceMatcher classe, que pode ser usado para dar-lhe um proporção similaridade. Exemplo função: 

def text_compare(text1, text2, isjunk=None):
    return difflib.SequenceMatcher(isjunk, text1, text2).ratio()

Outras dicas

Eu posso recomendo dar uma olhada código e artigos de Neil Fraser:

google-diff-match-patch

Atualmente disponível em Java, JavaScript, C ++ e Python. Independentemente da linguagem, cada biblioteca possui o mesma API e a mesma funcionalidade. Todas as versões têm também abrangente equipamentos de teste.

Neil Fraser: Diff Estratégias - para a teoria e implementação notas

difflib . (Python)

Isso irá calcular os diffs em vários formatos. Você poderia, então, usar o tamanho do diff contexto como uma medida de quão diferente dois documentos são?

Bazaar contém um algoritmo alternativo diferença, chamada paciência diff (há mais informações nos comentários nessa página), que é reivindicada a ser melhor do que o algoritmo diff tradicional. O arquivo 'patiencediff.py' na distribuição bazar é um simples front-end linha de comando.

O meu entendimento atual é que a melhor solução para o problema Shortest Editar Script (SES) é Myers método de "cobra média" com o Hirschberg linear refinamento espaço.

O algoritmo de Myers é descrito em:

E. Myers, `` Um O (ND) Diferença Algoritmo e suas variações, ''
Algorithmica 1, 2 (1986), 251-266.

O diff GNU usa o algoritmo de Myers.

O "score semelhança" de que fala é chamado de "editar distância" na literatura que é o número de inserções ou exclusões necessárias para transformar uma seqüência para o outro.

Note-se que um número de pessoas citaram o algoritmo distância Levenshtein, mas que é, ainda que fácil de implementar, não é a solução ideal, pois é ineficiente (requer o uso de um possivelmente enorme n * m matriz) e não fornece a "script de editar" que é a sequência de edições que poderiam ser usados ??para transformar uma seqüência para o outro e vice-versa.

Para uma boa Myers / Hirschberg olhar implementação em:

http://www.ioplex.com/~miallen /libmba/dl/src/diff.c

A biblioteca particular, que está contido dentro já não é mantida, mas a meu conhecimento o módulo diff.c em si ainda está correto.

Mike

Se você precisar de uma granularidade mais fina do que as linhas, você pode usar Levenshtein distância. Levenshtein distância é uma medida simples e direta sobre a forma de dois textos semelhantes são.
Você também pode usá-lo para extrair os logs de edição e pode muito diff, semelhante ao das páginas de edição de história de SO de grão fino. Lembre que Levenshtein distância pode ser bastante CPU e muita memória para calcular, portanto, usando difflib, como Douglas Leder sugerido, é mais provável vai ser mais rápido.

Cf. Também esta resposta .

Há uma série de métricas de distância, como paradoja mencionados há a distância Levenshtein, mas há também NYSIIS e Soundex . Em termos de implementações Python, tenho usado py-editdist e Advas antes. Ambos são bons no sentido de que você recebe um número único de volta como uma pontuação. Confira Advas primeiro, ele implementa um monte de algoritmos.

Como foi dito, o uso difflib. Uma vez que você tem a saída diffed, você pode encontrar o Levenshtein distância das cordas diferentes para dar um "valor" de como eles são diferentes.

Um método que eu empregado para uma funcionalidade diferente, para calcular a quantidade de dados era novo em um arquivo modificado, talvez pudesse trabalhar para você também.

Eu tenho um diff / patch implementação C # que me permite ter dois arquivos, presumivelmente versão antiga e nova do mesmo arquivo, e calcular a "diferença", mas não no sentido usual da palavra. Basicamente eu calcular um conjunto de operações que pode executar na versão antiga para atualizá-lo para ter o mesmo conteúdo que a nova versão.

Para usar este para a funcionalidade descrita inicialmente, para ver a quantidade de dados era novo, eu simples percorreu as operações, e para cada operação que copiado do arquivo antigo verbatim, que teve um fator 0, e cada operação que novo texto inserido (distribuído como parte do patch, uma vez que não ocorreu no arquivo de idade) teve um fator-1. Todos os personagens foi dada esta fábrica, que me deu, basicamente, uma longa lista de 0 e 1 do.

Tudo que eu então tinha que fazer era coaduna-se com os 0s e 1s. No seu caso, com a minha aplicação, um baixo número de 1s em comparação a 0 do significaria os arquivos são muito semelhantes.

Esta implementação seria também lidar com casos em que o arquivo modificado tinha inserido cópias do arquivo antigo fora de ordem, ou mesmo duplicatas (ie. Copiar uma parte do início do arquivo e colá-lo na parte inferior), uma vez que ambos seriam cópias da mesma peça original do arquivo antigo.

Eu experimentei com cópias de pesagem, de modo que a primeira cópia contado como 0, e cópias subsequentes do mesmo personagens tinham fatores progressivamente maiores, a fim de dar um copy / paste operação de alguns "novo factor", mas eu nunca acabada -lo como o projeto foi desmantelada.

Se você é, meu diff / código de correção interessado está disponível a partir de meu repositório Subversion.

Dê uma olhada na módulo fuzzy. Tem rápido (escrito em C) algoritmos baseados para soundex, NYSIIS e double-metaphone.

A introdução de bom pode ser encontrado em: http: //www.informit. com / artigos / article.aspx? p = 1848528

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top