Algoritmo diff? [fechadas]

Question

Eu estive procurando como um louco para uma explicação de um algoritmo diff que funciona e é eficiente.

O mais próximo que eu tenho é este link para RFC 3284 (de vários Eric Sink blogue publicações), que descreve em termos perfeitamente compreensíveis a formato de dados em que os resultados diff são armazenados. No entanto, ele não tem qualquer menção de como um programa iria alcançar estes resultados ao fazer um diff.

Eu estou tentando esta investigação por curiosidade pessoal, porque eu tenho certeza que deve haver compensações ao implementar um algoritmo de diff, que são bastante claras, por vezes, quando você olha para diffs e maravilha "por que o programa diff escolheu este como uma mudança em vez disso?" ...

Onde posso encontrar uma descrição de um algoritmo eficiente que acabaria outputting VCDIFF
By the way, se acontecer de você encontrar uma descrição do algoritmo real utilizado pelo DiffMerge de SourceGear, isso seria ainda melhor.

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

Answer 1

An O (ND) Diferença Algoritmo e suas variações é um papel fantástico e você pode querer a começar por aí. Ele inclui pseudo-código e uma boa visualização dos percursos gráfico envolvidos em fazer o diff.

Seção 4 dos introduz papel alguns refinamentos para o algoritmo que o tornam muito eficaz.

A aplicação bem sucedida isso vai deixá-lo com uma ferramenta muito útil em sua caixa de ferramentas (e, provavelmente, alguns excelente experiência bem).

Gerando o formato de saída que você precisa às vezes pode ser complicado, mas se você tiver a compreensão dos internos algoritmo, então você deve ser capaz de saída de 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, completo código fonte , e exemplos de um algoritmo diff usando as técnicas no 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 na preparação da entrada, que você pode achar útil. Há uma enorme diferença na saída quando você está diffing pelo personagem ou símbolo (palavra).

Boa sorte!

Answer 2

Gostaria de começar por olhar para o real código-fonte para diff, que GNU faz disponível .

Para uma compreensão de como que o código fonte realmente funciona, os documentos em que a referência pacote de jornais que o inspirou:

O algoritmo básico é descrito em "An O (ND) Diferença Algoritmo e suas variações", Eugene W. Myers, Vol 'Algorithmica'. 1 No. 2, 1986, pp 251-266.; e em "Um arquivo Programa de Comparação", 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 conforme descrito em "Algoritmos para aproximado Matching String" , E. Ukkonen, `Vol Controlo' Informação e. 64, 1985, pp. 100-118.

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

Answer 3

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

bibliotecas

"O jogo Diff e patch oferecer algoritmos robustos para executar a operações necessárias para a sincronização texto simples. ... Disponível atualmente em Java, JavaScript, C ++, C # e Python "

Também ver a wikipedia.org Diff página - " Bram Cohen: O problema diff foi resolvido "

Answer 4

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

Wikipedia : A partir de uma maior subsequência comum é apenas um pequeno passo para obter diff- como saída: se um item está ausente na subsequência mas presente no original, que deve ter sido excluído. (A '-'. Marcas, abaixo). Se ele está ausente na subsequência mas presente na segunda sequência, isto deve ter sido adicionado no (. As marcas '+')

Nice animação do LCS algoritmo aqui .

Link para um LCS ruby ??implementação rápida aqui .

A minha adaptação rubi lento e simples é 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]

Answer 5

Com base no link Emmelaich deu, há também um grande baixo prazo de Diff Estratégias no site da Neil Fraser (um dos autores da biblioteca) .

Ele abrange estratégias básicas e para o final do artigo avanços para o algoritmo de Myer e alguns teoria dos grafos.