दस्तावेज diff एल्गोरिदम कैसे काम करते हैं?

Question

मैं शब्द दस्तावेज़ को लागू करना चाहता हूं, यह लागू करने के लिए क्या एल्गोरिदम की आवश्यकता है?

Answer 1

LCS में से अधिकांश का अनुकूलन समाधान O(ND) Myer 's algorithm है, और यहाँ एक एल्गोरिथम दृष्टिकोण है जो मैं अलग कार्यालय 2007 दस्तावेजों को लागू करने के लिए प्रयोग किया जाता था। Link to algorithm paper

Answer 2

एक अंतर अनिवार्य रूप से a solutionlongest common sub-sequence problem पर है।

इष्टतम समाधान के लिए dynamic programming का ज्ञान आवश्यक है, इसलिए यह हल करने के लिए एक काफी जटिल समस्या है।

हालांकि, यह प्रत्यय-पेड़ का निर्माण करके भी किया जा सकता है। दोनों एल्गोरिदम here रेखांकित हैं।

Answer 3

An O(ND) Difference Algorithm for C# देखें।

Answer 4

जैसा कि बेन एस इंगित करता है, आम तौर पर सबसे लंबी आम उप-अनुक्रम समस्या को हल करके differencing समस्या को संबोधित किया जा सकता है। अधिक विशेष रूप से, Hunt-McIlroy algorithm क्लासिक एल्गोरिदम में से एक है जो समस्या पर लागू किया गया है (उदाहरण के लिए यूनिक्स 'diff उपयोगिता के कार्यान्वयन में)।

Answer 5

ठीक है, आमतौर पर diff 'आईएनजी आमतौर पर Longest common subsequence problem द्वारा हल किया जाता है। इसके अलावा Diff पर "विकिपीडिया लेख के Algorithm" खंड देखें:।

diff के संचालन सबसे लंबे समय तक आम subsequence समस्या

इस समस्या में सुलझाने पर आधारित है, तो आप आइटम के दो दृश्यों है :

a b c d f g h j q z 

    a b c d e f g i j k r x y z 

और आप आइटम की सबसे लंबी अनुक्रम कि बॉट में मौजूद है पता लगाना चाहते हैं एच क्रम में एच मूल अनुक्रम। यही है, आप अनुक्रम प्राप्त करना चाहते हैं जिसे से आइटमों को हटाकर पहले अनुक्रम से प्राप्त किया जा सकता है, और दूसरे अनुक्रम से अन्य आइटमों को हटाकर प्राप्त किया जा सकता है। आप भी इस अनुक्रम को तक संभव बनाना चाहते हैं। इस मामले में यह

a b c d f g j z 

सबसे लंबे समय तक आम subsequence यह diff की तरह उत्पादन प्राप्त करने के लिए केवल एक छोटा सा कदम है से

है:

e h i q k r x y 
    + - + - + + + + 

जिसके अनुसार, यह सब आधारित पाठ के साथ ठीक काम करता है दस्तावेजों। चूंकि वर्ड डॉक्यूमेंट्स बाइनरी प्रारूप में प्रभावी ढंग से प्रभावी होते हैं, और इसमें कई प्रारूपण जानकारी और डेटा शामिल होते हैं, यह अधिक जटिल होगा। आदर्श रूप में, आप के रूप में यह क्षमता के लिए दस्तावेजों के बीच "अंतर" के रूप में यहाँ विस्तृत ही वचन को स्वचालित पर गौर कर सकता,:

Microsoft Word Tip: How to compare two documents for differences