1. घर
  2. सवाल और जवाब
  3. लिनक्स सी या सी ++ पुस्तकालय diff और पैच तारों के लिए?

लिनक्स सी या सी ++ पुस्तकालय diff और पैच तारों के लिए?

2012-11-18 9 views
8

संभव डुप्लिकेट:
Is there a way to diff files from C++?लिनक्स सी या सी ++ पुस्तकालय diff और पैच तारों के लिए?

मैं लंबे समय पाठ स्ट्रिंग्स है कि मैं यदि अंतर और पैच करना चाहते हैं।

string a = ...; 
string b = ...; 

string a_diff_b = create_patch(a,b); 
string a2 = apply_patch(a_diff_b, b); 

assert(a == a2);

तो a_diff_b मानव पठनीय है कि एक बोनस होता था: यह तार ए और बी दिया जाता है। इस लागू करने के लिए

एक तरह से system(3) उपयोग करने के लिए diffutils और पाइप उन्हें तार से diff और patch खोल आदेशों कॉल करने के लिए किया जाएगा। एक और तरीका स्वयं कार्यों को कार्यान्वित करना होगा (मैं सोच रहा था कि प्रत्येक पंक्ति परमाणु रूप से इलाज किया जाए और बैकट्रैकिंग के साथ मानक संपादन दूरी एन^3 एल्गोरिदम लाइनवाइज़ का उपयोग करें)।

मैं सोच रहा था कि क्या कोई अच्छी लिनक्स सी या सी ++ लाइब्रेरी के बारे में जानता है जो काम में काम करेगा?

स्रोत

2012-11-18 Andrew Tomazos

+0

यह लिंक उपयोगी होगा? http://www.codeproject.com/Articles/3666/Diff-tool – billz

+1

यदि आप अपने आवेदन में पायथन एम्बेड कर सकते हैं, [यह] (http://docs.python.org/2/library/difflib.html) सहायक बनें। – user4815162342

उत्तर

6

आप माइर्स डिफ एल्गोरिदम के कार्यान्वयन को Google बना सकते हैं। ("एक ओ (एनडी) अंतर एल्गोरिदम और इसकी विविधता") या पुस्तकालय जो "सबसे आम आम अनुक्रम" समस्या को हल करते हैं।

जहाँ तक मुझे पता है, सी ++ में diff/पैच के साथ स्थिति अच्छी नहीं है - (diff match patch, libmba सहित) कई पुस्तकालयों देखते हैं, लेकिन मेरे अनुभव के अनुसार वे या तो कर रहे हैं कुछ हद तक खराब दस्तावेज या भारी बाहरी है निर्भरता (diff match पैच को उदाहरण के लिए क्यूटी 4 की आवश्यकता होती है) या उस प्रकार पर विशेषीकृत किया गया है जिसकी आपको आवश्यकता नहीं है (std :: स्ट्रिंग जब आपको यूनिकोड की आवश्यकता होती है, उदाहरण के लिए), या पर्याप्त सामान्य नहीं हैं, या जेनेरिक एल्गोरिदम का उपयोग करें उच्च स्मृति आवश्यकताओं ((एम + एन)^2 जहां एम और एन इनपुट अनुक्रमों की लंबाई हैं)।

आप मायर्स एल्गोरिदम ((एन + एम) मेमोरी आवश्यकताएं स्वयं को लागू करने का प्रयास भी कर सकते हैं, लेकिन समस्या का समाधान समझना बेहद मुश्किल है - कम से कम एक हफ्ते पढ़ने के दस्तावेज को बर्बाद करने की उम्मीद है। मायर्स एल्गोरिदम के कुछ हद तक मानव-पठनीय स्पष्टीकरण here उपलब्ध है।

स्रोत

2012-11-18 20:42:52 SigTerm

+0

मैंने कल रात मूल पत्र पढ़ा: http://www.xmailserver.org/diff2.pdf। यदि आप संपादन दूरी एल्गोरिदम पहले जानते हैं तो यह काफी सरल है।असल में संपूर्ण संपादन ग्राफ की खोज करने के बजाय यह पहले न्यूनतम परिवर्तनों के साथ पथ की खोज करता है, और अगले पुनरावृत्ति के परिणामों को याद करता है, जिससे उन्हें हर बार एक बदलाव से बढ़ाया जाता है। इस प्रकार जब यह एंडपॉइंट पाता है तो यह न्यूनतम परिवर्तनों वाला समाधान होगा, और इससे पहले केवल बेहतर संभावित समाधान खोजे जाएंगे। यह सबसे अच्छा पहला खोज एल्गोरिदम ('ए *') का एक विशिष्ट मामला है। –

+0

@ एंड्रयू टोमाज़ोस-फाथोमलिंग: यह सीधा नहीं है। उदाहरण के लिए, यह कहना बेहद मुश्किल है कि वास्तव में "मध्य सांप" कहलाता है। बेशक, यह गणितीय पृष्ठभूमि वाले लोगों के लिए सीधा हो सकता है। – SigTerm

+0

"मध्य सांप" परिष्करण मूल एल्गोरिदम का विस्तार है। इसका मतलब यह है कि साथ-साथ शीर्ष-बाएं से नीचे-दाएं, और वीज़ा-विपरीत से एक खोज आयोजित करना। जब दो खोज मिलती हैं तो आपके पास समाधान होता है। आप बैकट्रैकिंग पथ की जानकारी को त्याग सकते हैं और इस दोहरी एल्गोरिदम को बार-बार "द्विआधारी खोज" विभाजित कर सकते हैं और पुनरावृत्ति जीत सकते हैं ताकि यद्यपि यह लॉगरिदमिक रूप से अधिक समय लगेगा, आपको केवल रैखिक स्थान की आवश्यकता है (यदि स्थान प्रीमियम पर है)। –

2

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

Diff मैच और पैच पुस्तकालयों की पेशकश सादा पाठ सिंक्रनाइज़ करने के लिए आवश्यक कार्रवाई करने मजबूत एल्गोरिदम ।

वर्तमान में जावा, जावास्क्रिप्ट, डार्ट, सी ++, सी #, उद्देश्य सी, लुआ और पायथन में उपलब्ध है। भाषा के बावजूद, प्रत्येक पुस्तकालय में एक ही एपीआई और समान कार्यक्षमता होती है। सभी संस्करणों में व्यापक परीक्षण harnesses भी है।

स्रोत

2012-11-18 20:25:41

संबंधित मुद्दे

 संबंधित मुद्दे