Algoritmo Diff? [fechadas]

Estou parecendo louco por uma explicação de um algoritmo diff que funciona e é eficiente.

O mais próximo que cheguei foi desse link para o RFC 3284 (de várias postagens no 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 há menção alguma sobre como um programa alcançaria esses resultados ao fazer uma comparação.

Estou tentando pesquisar isso por curiosidade pessoal, porque tenho certeza de que deve haver vantagens e desvantagens ao implementar um algoritmo diff, que às vezes é bastante claro quando você olha para diffs e se pergunta "por que o programa diff escolheu isso como uma alteração ao invés disso?"...

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

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

Um algoritmo de diferença O (ND) e suas variações é um artigo fantástico e você pode começar por aí. Inclui pseudo-código e uma boa visualização dos percursos gráficos envolvidos na execução do diff.

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

A implementação bem-sucedida disso deixará uma ferramenta muito útil na sua caixa de ferramentas (e provavelmente também uma excelente experiência).

Às vezes, a geração do formato de saída necessário pode ser complicada, mas se você entender os detalhes internos do algoritmo, poderá produzir o que precisar. Você também pode introduzir heurísticas para afetar a saída e fazer certas trocas.

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 mencionado acima.

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

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

Boa sorte!

Eu começaria examinando o código fonte real do diff, que o GNU disponibiliza .

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

O algoritmo básico é descrito em "Um algoritmo de diferença O (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 - Practice and Experience' vol. 15 No. 11, 1985, pp. 1025-1040. O algoritmo foi descoberto independentemente, conforme descrito em "Algoritmos para correspondência aproximada de cadeias", E. Ukkonen, `Information and Control 'Vol. 64, 1985, pp. 100-118.

Ler os documentos e examinar o código fonte de uma implementação deve ser mais do que suficiente para entender como ele funciona.

Consulte https://github.com/google/diff-match-patch

"As bibliotecas Diff Match e Patch oferecem algoritmos robustos para executar as operações necessárias para sincronizar texto sem formatação. ... Atualmente disponível em Java, JavaScript, C ++, C # e Python"

Veja também a página Diff do wikipedia.org e - " Bram Cohen: O problema do diff foi resolvido "

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

Wikipedia : De uma subsequência comum mais longa, é apenas um pequeno passo para obter uma saída do tipo diff: se um item estiver ausente na subsequência, mas presente no original, ele deverá 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 a rubi 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, também há uma grande quantidade 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.