Algorytm różnicowy? [Zamknięte]


164

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ą.


Nic na Wikipedii? Możesz spróbować znaleźć inną implementację w języku wyższego poziomu, np. Python, która może być łatwiejsza do zrozumienia niż implementacja w C. Python słynie z tego, że jest czytelny? W Pythonie jest różnica. Oto adres URL źródła. Źródło zawiera mnóstwo komentarzy na temat algorytmów diff. svn.python.org/view/python/trunk/Lib/…
bsergean

4
RFC nie mają na celu opisywania algorytmów. Mają opisywać interfejsy (/ protokoły).

2
W rzeczywistości rdzeń algorytmu diff, najdłuższy wspólny problem z sekwencjami, można znaleźć na Wikipedii. Ta strona zawiera przegląd algorytmu i przykładowy kod, który okazał się pomocny, gdy musiałem napisać niestandardowy plik różnicowy: en.wikipedia.org/wiki/Longest_common_subsequence_problem
Corwin Joy

3
Być może to pomoże: paulbutler.org/archives/a-simple-diff-algorithm-in-php To z pewnością jest niesamowite i jest tak małe (w sumie tylko 29 wierszy ; ma 2 funkcje). Jest podobny do porównania edycji wersji Stack Overflow.
Nathan

VCDIFF nie jest przeznaczony dla różnic czytelnych dla człowieka. Wykorzystuje instrukcje dodawania, kopiowania i uruchamiania w przeciwieństwie do bardziej czytelnych dla człowieka instrukcji usuwania i wstawiania, emitowanych przez większość algorytmów porównywania zwykłego tekstu. Dla VCDIFF potrzebujesz czegoś takiego jak xdelta algortihm opisana tutaj xmailserver.org/xdfs.pdf
asgerhallas

Odpowiedzi:


175

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!


1
Na wypadek zepsutego łącza jest to Myers 1986; patrz np. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927 - dalej zawiera odsyłacz do diffpublikacji uniksowej autorstwa Hunta i McIlroya.
tripleee

34

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.


80
Hmmm, w skrócie, czasami ustalanie podstawowego algorytmu na podstawie rzeczywistego kodu źródłowego (zwłaszcza jeśli jest zoptymalizowany pod kątem wydajności) może być dość złożone. Będę w stanie zrozumieć krok po kroku, co robi program, ale nie dokładnie „dlaczego”, ani ogólne omówienie tego ... Przykład: Nigdy nie zrozumiesz, jak działają wyrażenia regularne (ani czym one są) przyglądając się implementacji Regexes Perla. A jeśli mógłbyś to zrobić, to przechylam kapelusz, zdecydowanie potrzebuję bardziej wyjaśnionego, wyższego poziomu przeglądu, aby dowiedzieć się, co się dzieje.
Daniel Magliola

3
Nigdy nie rozumiem, jak działa ogromna większość Perla :-), ale w dokumentacji pakietu (patrz aktualizacja) znajduje się odsyłacz, który wskaże opisującą go literaturę (jest to algorytm diff, a nie Perl).
paxdiablo

32
Nie czytaj kodu. Przeczytaj artykuł.
Ira Baxter

31

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


2
Chciałem tylko wspomnieć, że algorytm Cohena również wydaje się być znany jako Patience Diff. Jest to (domyślny?) Algorytm diff na bazarze i opcjonalny w git.
Dale Hagglund

13

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]

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.