Algorytm różnicowy? [Zamknięte]

Szukałem szalonego wyjaśnienia algorytmu różnicowania, który działa i jest wydajny.

Najbliższy mi jest ten link do RFC 3284 (z kilku postów na blogu Erica Sinka), który opisuje w zrozumiały sposób format danych, w których przechowywane są wyniki różnic. Jednak nie ma żadnej wzmianki o tym, jak program osiągnąłby te wyniki podczas wykonywania różnicy.

Próbuję to zbadać z osobistej ciekawości, ponieważ jestem pewien, że przy implementacji algorytmu różnicowania muszą istnieć kompromisy, które są dość jasne czasami, gdy patrzysz na różnice i zastanawiasz się "dlaczego program porównujący wybrał to jako zmianę zamiast tego?"...

Gdzie mogę znaleźć opis wydajnego algorytmu, który wyprowadziłby VCDIFF?
Nawiasem mówiąc, jeśli zdarzy ci się znaleźć opis rzeczywistego algorytmu używanego przez SourceGear's DiffMerge, byłoby jeszcze lepiej.

UWAGA: najdłuższy wspólny podciąg nie wydaje się być algorytmem używanym przez VCDIFF, wygląda na to, że robią coś mądrzejszego, biorąc pod uwagę format danych, którego używają.

Algorytm różnicy O (ND) i jego wariacje to fantastyczny artykuł i możesz zacząć od tego. Zawiera pseudokod i ładną wizualizację przechodzenia przez wykresy związane z wykonywaniem różnic.

Rozdział 4 artykułu wprowadza pewne udoskonalenia algorytmu, dzięki którym jest on bardzo skuteczny.

Pomyślne wdrożenie tego zapewni Ci bardzo przydatne narzędzie w zestawie narzędzi (i prawdopodobnie również doskonałe doświadczenie).

Wygenerowanie potrzebnego formatu wyjściowego może czasami być trudne, ale jeśli rozumiesz funkcje wewnętrzne algorytmu, powinieneś być w stanie wydrukować wszystko, czego potrzebujesz. Możesz także wprowadzić heurystykę, aby wpłynąć na wynik i dokonać pewnych kompromisów.

Oto strona, która zawiera trochę dokumentacji, pełny kod źródłowy i przykłady algorytmu diff przy użyciu technik z wyżej wymienionego algorytmu.

Wydaje się, że kod źródłowy jest zgodny z podstawowym algorytmem i jest łatwy do odczytania.

Jest też trochę na temat przygotowania danych wejściowych, które mogą okazać się przydatne. Istnieje ogromna różnica w wynikach, gdy porównujesz znak lub znacznik (słowo).

Powodzenia!

Chciałbym zacząć od spojrzenia na rzeczywisty kod źródłowy dla GNU diff, co sprawia, że dostępne .

Aby zrozumieć, jak faktycznie działa ten kod źródłowy, dokumenty w tym pakiecie odnoszą się do artykułó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, str. 251-266; oraz w „Program do porównywania plików”, Webb Miller i Eugene W. Myers, „Software - Practice and Experience” Vol. 15 nr 11, 1985, str. 1025-1040. Algorytm został niezależnie odkryty zgodnie z opisem w „Algorithms for Approximate String Matching”, E. Ukkonen, „Information and Control 'Vol. 64, 1985, str. 100-118.

Przeczytanie artykułów, a następnie przyjrzenie się kodowi źródłowemu implementacji powinno wystarczyć, aby zrozumieć, jak to działa.

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

„Biblioteki Diff Match i Patch oferują niezawodne algorytmy do wykonywania operacji wymaganych do synchronizacji zwykłego tekstu. ... Obecnie dostępne w językach Java, JavaScript, C ++, C # i Python”

Zobacz także stronę różnic w wikipedia.org i - „ Bram Cohen: Problem z różnicami został rozwiązany ”

Przyjechałem tutaj, szukając algorytmu diff, a następnie wykonałem własną implementację. Przepraszam, nie wiem o vcdiff.

Wikipedia : Z najdłuższego wspólnego podciągu wystarczy mały krok, aby uzyskać wynik podobny do diff: jeśli element jest nieobecny w podciągu, ale występuje w oryginale, musiał zostać usunięty. (Znaki „-” poniżej.) Jeśli nie ma go w podciągu, ale występuje w drugiej sekwencji, musi zostać dodany. (Znaki „+”).

Ładna animacja algorytmu LCS tutaj .

Link do szybkiej implementacji LCS w języku Ruby tutaj .

Moja powolna i prosta adaptacja rubinowa 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]

Opierając się na linku podanym przez Emmelaicha, na stronie Neila Frasera (jednego z autorów biblioteki) znajduje się również obszerny przegląd Diff Strategies .

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