Algoritmo de Diferença?

Eu tenho parecido louco por uma explicação de um algoritmo de diff que funciona e é eficiente.

O mais próximo que eu tenho é este link para o RFC 3284 (de vários posts do blog Eric Sink), que descreve em termos perfeitamente compreensíveis o formato de dados no qual os resultados do diff são armazenados. No entanto, não tem qualquer menção sobre como um programa alcançaria esses resultados enquanto fazia um diff.

Eu estou tentando pesquisar isso por curiosidade pessoal, porque tenho certeza que deve haver tradeoffs ao implementar um algoritmo diff, que são bem claros algumas vezes quando você olha para diffs e se pergunta “por que o programa diff escolheu isso como uma mudança ao invés disso?”…

Onde posso encontrar uma descrição de um algoritmo eficiente que acabaria produzindo VCDIFF?
A propósito, se você encontrar uma descrição do algoritmo real usado pelo DiffMerge do SourceGear, isso seria ainda melhor.

NOTA: a subseqüência comum mais longa não parece ser o algoritmo usado pelo VCDIFF, parece que eles estão fazendo algo mais inteligente, dado o formato de dados que eles usam.

Um Algoritmo de Diferença O (ND) e suas Variações é um artigo fantástico e você pode querer começar por aí. Inclui pseudocódigo e uma boa visualização dos trajetos de gráfico envolvidos na realização do diff.

A seção 4 do artigo introduz alguns refinamentos no algoritmo que o tornam muito eficaz.

Implementar com sucesso isso vai deixar você com uma ferramenta muito útil em sua checkbox de ferramentas (e provavelmente também uma excelente experiência).

Gerar o formato de saída que você precisa às vezes pode ser complicado, mas se você tem conhecimento dos componentes internos do algoritmo, então você deve ser capaz de produzir qualquer coisa que você precisa. Você também pode introduzir heurísticas para afetar a saída e fazer certas compensações.

Aqui está uma página que inclui um pouco de documentação, código-fonte completo e exemplos de um algoritmo diff usando as técnicas do algoritmo acima mencionado.

O código fonte parece seguir o algoritmo básico de perto e é fácil de ler.

Há também um pouco sobre a preparação da input, que você pode achar útil. Há uma enorme diferença na saída quando você está se diferenciando por caractere ou token (palavra).

Boa sorte!

Eu começaria olhando o código fonte para diff, que o GNU disponibiliza .

Para entender como esse código-fonte realmente funciona, os documentos desse pacote fazem referência aos artigos que o inspiraram:

O algoritmo básico é descrito em “Um Algoritmo de Diferença (ND) e suas Variações”, Eugene W. Myers, “Algorithmica” Vol. 1 No. 2, 1986, pp. 251-266; e em “Um programa de comparação de arquivos”, Webb Miller e Eugene W. Myers, “Software – Prática e Experiência” vol. 15 No. 11, 1985, pp. 1025-1040. O algoritmo foi descoberto independentemente como descrito em “Algoritmos para Correspondência de Cadeias Aproximadas”, E. Ukkonen, “Information and Control” Vol. 64, 1985, págs. 100-118.

Lendo os documentos, em seguida, olhando para o código-fonte para uma implementação deve ser mais que suficiente para entender como funciona.

Veja http://code.google.com/p/google-diff-match-patch/

“As bibliotecas Diff Match e Patch oferecem algoritmos robustos para executar as operações necessárias para sincronizar texto simples. … Atualmente disponível em Java, JavaScript, C ++, C # e Python”

Veja também a página de diferenças do wikipedia.org e – ” Bram Cohen: O problema do diff foi resolvido ”

Eu vim aqui procurando pelo algoritmo diff e depois fiz minha própria implementação. Desculpe eu não sei sobre vcdiff.

Wikipedia : A partir de uma subseqüência mais longa comum, é apenas um pequeno passo para se obter uma saída semelhante a um diff: se um item estiver ausente na subsequência, mas presente no original, ele deve ter sido excluído. (As marcas ‘-‘, abaixo.) Se estiver ausente na subsequência, mas presente na segunda sequência, deve ter sido adicionado. (As marcas ‘+’.)

Boa animação do algoritmo LCS aqui .

Link para uma implementação rápida do LCS ruby ​​aqui .

Minha lenta e simples adaptação ao ruby está abaixo.

 def lcs(xs, ys) if xs.count > 0 and ys.count > 0 xe, *xb = xs ye, *yb = ys if xe == ye return [xe] + lcs(xb, yb) end a = lcs(xs, yb) b = lcs(xb, ys) return (a.length > b.length) ? a : b end return [] end def find_diffs(original, modified, subsequence) result = [] while subsequence.length > 0 sfirst, *subsequence = subsequence while modified.length > 0 mfirst, *modified = modified break if mfirst == sfirst result << "+#{mfirst}" end while original.length > 0 ofirst, *original = original break if ofirst == sfirst result << "-#{ofirst}" end result << "#{sfirst}" end while modified.length > 0 mfirst, *modified = modified result << "+#{mfirst}" end while original.length > 0 ofirst, *original = original result << "-#{ofirst}" end return result end def pretty_diff(original, modified) subsequence = lcs(modified, original) diffs = find_diffs(original, modified, subsequence) puts 'ORIG [' + original.join(', ') + ']' puts 'MODIFIED [' + modified.join(', ') + ']' puts 'LCS [' + subsequence.join(', ') + ']' puts 'DIFFS [' + diffs.join(', ') + ']' end pretty_diff("human".scan(/./), "chimpanzee".scan(/./)) # ORIG [h, u, m, a, n] # MODIFIED [c, h, i, m, p, a, n, z, e, e] # LCS [h, m, a, n] # DIFFS [+c, h, +i, -u, m, +p, a, n, +z, +e, +e] 

Com base no link que Emmelaich deu, há também uma grande queda de Diff Strategies no site de Neil Fraser (um dos autores da biblioteca) .

Ele aborda estratégias básicas e, no final do artigo, avança para o algoritmo de Myer e alguma teoria dos grafos.