Diff Algorithm

Question

Szukałem jak szalony na wyjaśnienie algorytmu diff, który działa i jest wydajny.

Najbliżej mam to this link to RFC 3284 (od kilku Eric Sink blogi), który opisuje w kategoriach doskonale zrozumiałym formacie dane w których wyniki są przechowywane diff. Nie ma jednak żadnej wzmianki o tym, w jaki sposób program osiągnąłby te wyniki, robiąc różnicę.

Próbuję zbadać to z osobistej ciekawości, ponieważ jestem pewny, że muszą istnieć kompromisy przy wdrażaniu algorytmu diff, które są całkiem jasne, czasami gdy patrzysz na różnice i zastanawiasz się "dlaczego program diff wybrał to jako zmiana zamiast tego? "...

Czy ktoś wie, gdzie mogę znaleźć opis skutecznego algorytmu, który zakończyłby się wyprowadzaniem VCDIFF?
Nawiasem mówiąc, jeśli znajdziesz opis rzeczywistego algorytmu używanego przez DiffMerge SourceGear, będzie 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ą.

Dzięki!

Answer 1

An O(ND) Difference Algorithm and its Variations to fantastyczna gazeta i możesz tam zacząć. Zawiera pseudokod kodu i ładną wizualizację wykresów przechwytujących zaangażowanych w robienie różnic.

Sekcja 4 dokumentu wprowadza pewne udoskonalenia algorytmu, które czynią go bardzo skutecznym.

Pomyślnie zaimplementowanie tego spowoduje, że otrzymasz bardzo przydatne narzędzie w zestawie narzędzi (i zapewne wspaniałe wrażenia).

Generowanie formatu wyjściowego, którego potrzebujesz, czasami może być trudne, ale jeśli masz wiedzę na temat wewnętrznych algorytmów, powinieneś być w stanie wyprowadzić wszystko, czego potrzebujesz. Możesz także wprowadzić heurystykę, aby wpłynąć na wydajność i dokonać pewnych kompromisów.

Here is a page który zawiera trochę dokumentacji, full source code, oraz przykłady algorytmu diff za pomocą technik we wspomnianym algorytmie.

Wydaje się, że source code ściśle przestrzega zasadniczego algorytmu i jest łatwy do odczytania.

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

Powodzenia!

Answer 2

Zacznę od przyjrzenia się rzeczywistemu kodowi źródłowemu dla diff, który GNU tworzy available.

Dla zrozumienie jak że kod źródłowy faktycznie działa, docs w tym pakiecie odwoływać dokumenty, które go zainspirowały:

Algorytm podstawowy jest opisany w rozdziale „O (ND) Różnica algorytmu i jego Wariacje ", Eugene W. Myers," Algorithmica "Vol. 1 No. 2, 1986, str. 251-266; oraz w "Programie porównywania plików", Webb Miller i Eugene W. Myers, "Software - Practice and Experience", tom. 15 nr 11, 1985, str. 1025-1040. Algorytmy zostały niezależnie odkryte, jak opisano w "Algorithms for Approximate String Matching", E. Ukkonen, "Information and Control" obj. 64, 1985, str. 100-118.

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

Answer 3

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

„diff Mecz i biblioteki krosowe oferta solidne algorytmy do wykonywania operacje wymagane do synchronizacji zwykły tekst. ... Obecnie dostępne w języku Java, JavaScript, C++, C# i Python”

zobacz także wikipedia.org Diff page i - "Bram Cohen: The diff problem has been solved"

Answer 4

W oparciu o link, który podała Emmelaich, można również z dużym wyprzedzeniem zastosować strategie Diff na Neil Fraser's website (one of the authors of the library).

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

Answer 5

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

Wikipedia: Od najdłuższego wspólnego podciągu jest to tylko mały krok, aby uzyskać wyjście typu diff: jeśli element jest nieobecny w podciągu, ale występuje w oryginale, musi zostać usunięty. (Znaczniki "-" poniżej). Jeśli jest nieobecny w podciągu, ale występuje w drugiej sekwencji, musi zostać dodany. (Znaczniki "+".)

Ładna animacja z LCS algorithm here.

Link do szybkiego LCS ruby implementation here.

Moja powolna i prosta adaptacja ruby ​​znajduje się 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]