Algorytm Diff? [zamknięte]

Zacząłbym od spojrzenia na rzeczywisty kod źródłowy dla Diffa, który GNU udostępnia .

Dla zrozumienia Jak działa ten kod źródłowy, dokumenty w tym pakiecie odwołują się do dokumentów, które go zainspirowały:

Podstawowy algorytm jest opisany w" An O(ND) Difference Algorithm and its Variations", Eugene W. Myers, "Algorithmica" Vol. 1 Nr 2, 1986, s. 251-266; oraz w " pliku Comparison Program", Webb Miller i Eugene W. Myers, "Software--Practice and Experience" Vol. 15-11-1985, S. 1025-1040. Algorytm został niezależnie odkryty, jak opisano w "Algorithms for Approximate String Matching", E. Ukkonen, "Information and Control" Vol. 64, 1985, s. 100-118.

Przeczytanie dokumentów, a następnie spojrzenie na kod źródłowy implementacji powinno wystarczyć, aby zrozumieć, jak to działa.

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

" Biblioteki różnic i poprawek oferują solidne algorytmy do wykonywania operacje wymagane do synchronizacji zwykły tekst. ... Aktualnie dostępne w Javie, JavaScript, C++, C# i Python "

Zobacz też wikipedia.org strona Diff i - "Bram Cohen: problem diff został rozwiązany "

Przyszedłem tu w poszukiwaniu algorytmu diff, a potem zrobiłem własną implementację. Przepraszam, że nie wiem o vcdiff.

Wikipedia: z najdłuższej wspólnej sekwencji jest to tylko mały krok, aby uzyskać wynik podobny do Diffa: jeśli element jest nieobecny w subsequence, ale obecny w oryginale, musiał zostać usunięty. (Znaki"–", poniżej.), Jeśli nie występuje w dalszej kolejności, ale występuje w drugiej kolejności, musi być dodany w. (Znaki"+".)

Nice animacja algorytmu LCS tutaj .

Link do szybkiej implementacji LCS ruby tutaj .

Moja powolna i prosta adaptacja ruby jest poniżej.

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]

Bazując na linku podanym przez Emmelaich, na stronie internetowej Neila Frasera (jednego z autorów biblioteki) znajduje się również wiele różnych strategii.

Omawia podstawowe strategie i pod koniec artykułu przechodzi do algorytmu Myera i teorii grafów.