Diff एल्गोरिथ्म

Question

मैं एक diff एल्गोरिथ्म है कि काम करता है और कुशल है की एक विवरण के लिए पागल हो की तरह लग रही किया गया है।

निकटतम मुझे मिल गया जो पूरी तरह से समझा जा सकता शर्तों डेटा स्वरूप जिसमें diff परिणाम जमा हो जाती है में वर्णन करता है (कई एरिक सिंक ब्लॉग पोस्ट से) this link to RFC 3284 है। हालांकि, इसमें कोई उल्लेख नहीं है कि एक कार्यक्रम करने के दौरान एक कार्यक्रम इन परिणामों तक कैसे पहुंचेगा।

मैं व्यक्तिगत जिज्ञासा से इसे शोध करने की कोशिश कर रहा हूं, क्योंकि मुझे यकीन है कि एक diff एल्गोरिदम लागू करते समय ट्रेडऑफ होना चाहिए, जो कभी-कभी स्पष्ट होते हैं जब आप diffs को देखते हैं और आश्चर्य करते हैं "diff प्रोग्राम ने क्यों चुना इस बजाय कि? "का एक परिवर्तन ...

किसी को भी पता है, जहां मैं एक कुशल एल्गोरिथ्म कि VCDIFF outputting पहुंचते हैं का एक विवरण प्राप्त कर सकते हैं के रूप में?
वैसे, यदि आपको SourceGear's DiffMerge द्वारा उपयोग किए गए वास्तविक एल्गोरिदम का विवरण मिलना है, तो यह भी बेहतर होगा।

नोट: सबसे लंबे समय तक आम subsequence VCDIFF द्वारा प्रयोग किया जाता एल्गोरिथ्म होना प्रतीत नहीं होता है, ऐसा लगता है कि वे कुछ होशियार कर रहे हैं, वे का उपयोग डेटा स्वरूप को देखते हुए लग रहा है।

धन्यवाद!

Answer 1

An O(ND) Difference Algorithm and its Variations एक शानदार पेपर है और आप वहीं से शुरू कर सकते हैं। इसमें छद्म कोड शामिल है और अंतर करने में शामिल ग्राफ ट्रैवर्सल का एक अच्छा दृश्यता शामिल है।

पेपर के सेक्शन 4 एल्गोरिदम के लिए कुछ परिशोधन प्रस्तुत करता है जो इसे बहुत प्रभावी बनाता है।

सफलतापूर्वक लागू करने यह आप अपने पिटारे में एक बहुत ही उपयोगी उपकरण के साथ (और शायद कुछ उत्कृष्ट रूप में अच्छी तरह का अनुभव) छोड़ देंगे।

उत्पादन प्रारूप आप की जरूरत कभी कभी मुश्किल हो सकता है जनरेट कर रहा है, लेकिन आप एल्गोरिथ्म internals की समझ है, तो आप कुछ भी उत्पादन की जरूरत के लिए सक्षम होना चाहिए। आप आउटपुट को प्रभावित करने और कुछ ट्रेडऑफ बनाने के लिए हेरिस्टिक भी पेश कर सकते हैं।

Here is a page जिसमें कुछ दस्तावेज, full source code, और उपरोक्त एल्गोरिदम में तकनीकों का उपयोग करके एक diff एल्गोरिदम के उदाहरण शामिल हैं।

source code बारीकी से बुनियादी एल्गोरिथ्म का पालन करने के लिए प्रकट होता है और पढ़ने में आसान है।

वहाँ भी इनपुट है, जो आपके लिए उपयोगी हो सकता है की तैयारी पर एक सा है। जब आप चरित्र या टोकन (शब्द) से भिन्न होते हैं तो आउटपुट में एक बड़ा अंतर होता है।

गुड लक!

Answer 2

मैं diff के लिए वास्तविक स्रोत कोड पर देखकर शुरू करूंगा, जो जीएनयू available बनाता है।

एक कैसे है कि स्रोत कोड वास्तव में काम करता है की को समझने के लिए, कि पैकेज में डॉक्स कागजात है कि यह प्रेरित संदर्भ:

बुनियादी एल्गोरिथ्म "एक हे (एनडी) अंतर एल्गोरिथ्म में वर्णन किया गया और इसके बदलाव ", यूजीन डब्ल्यू मायर्स, 'एल्गोरिदमिका' वॉल्यूम। 1 नंबर 2, 1 9 86, पीपी 251-266; और "ए फाइल तुलना कार्यक्रम", वेबब मिलर और यूजीन डब्ल्यू मायर्स, 'सॉफ्टवेयर - प्रैक्टिस एंड एक्सपीरियंस' वॉल्यूम में। 15 नंबर 11, 1 9 85, पीपी 1025-1040। एल्गोरिदम को "लगभग स्ट्रिंग मिलान के लिए एल्गोरिदम", ई। Ukkonen, 'सूचना और नियंत्रण' वॉल्यूम में वर्णित के रूप में स्वतंत्र रूप से खोजा गया था। 64, 1 9 85, पीपी 100-118।

कागजात पढ़ना, फिर कार्यान्वयन के लिए स्रोत कोड को देखते हुए यह समझने के लिए पर्याप्त होना चाहिए कि यह कैसे काम करता है।

Answer 3

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

"Diff मैच और पैच पुस्तकालयों प्रस्ताव मजबूत एल्गोरिदम सादा पाठ सिंक्रनाइज़ करने के लिए आवश्यक कार्रवाई करने देखें। ... जावा, जावास्क्रिप्ट, सी ++, C# और में वर्तमान में उपलब्ध अजगर "

इसके अलावा wikipedia.org Diff page देख सकते हैं और -" Bram Cohen: The diff problem has been solved "

Answer 4

एमेलेच ने दिए गए लिंक के आधार पर, Neil Fraser's website (one of the authors of the library) पर डिफ रणनीतियों का एक बड़ा प्रदर्शन भी किया है।

वह बुनियादी रणनीतियों को शामिल किया गया और लेख के अंत में Myer एल्गोरिथ्म और कुछ ग्राफ सिद्धांत की प्रगति।

Answer 5

मैं यहाँ diff एल्गोरिथ्म की तलाश में आया था और बाद में अपने ही कार्यान्वयन कर दिया। क्षमा करें मुझे vcdiff के बारे में पता नहीं है।

Wikipedia: सबसे लंबे समय तक आम होने के बाद यह अलग-अलग आउटपुट प्राप्त करने के लिए केवल एक छोटा कदम है: यदि कोई आइटम बाद में अनुपस्थित है लेकिन मूल में मौजूद है, तो इसे हटा दिया जाना चाहिए। ('-' अंक, नीचे।) यदि यह अनुक्रम में अनुपस्थित है लेकिन दूसरे अनुक्रम में मौजूद है, तो इसे जोड़ा जाना चाहिए। ('+' अंक।)

LCS algorithm here की अच्छी एनीमेशन।

एक तेजी से LCS ruby implementation here से लिंक करें।

मेरा धीमा और सरल रूबी अनुकूलन नीचे है।

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]