डेवलपर टूल · पाठ तुलना
टेक्स्ट डिफ बदली हुई पंक्तियों को कैसे ढूंढता है: LCS और मायर्स एल्गोरिथम
· यह काम किस प्रकार करता है
पाठ-अंतर एल्गोरिदम डेवलपर-वर्कफ़्लो
लाइन-आधारित तुलना के पीछे सबसे लंबे समय तक सामान्य-अनुवर्ती विचार की व्याख्या करता है और क्यों मायर्स एल्गोरिदम ने इसे ब्राउज़र टैब के अंदर भी तुरंत चलाने के लिए पर्याप्त तेज़ बना दिया है।
दो फ़ाइलें, एक प्रश्न: कौन सी पंक्तियाँ बची रहीं? - पंक्ति संख्याओं के मिलान के बजाय दोनों संस्करणों के लिए समान लाइनों की सबसे लंबी अवधि खोजने के रूप में फ़्रेम तुलना
दो संशोधन यह बताने वाले लेबल के साथ नहीं आते हैं कि कौन सी पंक्तियाँ बची हुई हैं। ToolAcre पहले प्रत्येक पाठ को एक क्रमबद्ध सूची में विभाजित करता है, फिर एक ही क्रम में दोनों सूचियों में प्रदर्शित होने वाले लंबे अनुक्रम की खोज करता है। उस साझा रीढ़ के बाहर की रेखाएँ अनुमानित संशोधनों के बजाय जोड़ या निष्कासन बन जाती हैं।
परिणाम दोनों पक्षों के लिए मूल एक-आधारित स्थिति प्रदान करता है। एक अपरिवर्तित पंक्ति में प्रत्येक तरफ एक संख्या होती है, केवल बाईं ओर एक निष्कासन होता है, और केवल दाईं ओर एक जोड़ होता है। वह लेखांकन प्रदर्शित कहानी को तब भी समीक्षा योग्य बनाता है जब दोहराई गई पंक्तियाँ एक से अधिक प्रशंसनीय संरेखण देती हैं।
अंतर पंक्तियों पर क्यों काम करता है, वर्णों पर नहीं - कैसे नई पंक्तियों पर विभाजन एक पाठ को तुलनीय इकाइयों के अनुक्रम में बदल देता है और यह क्यों गद्य को कोड से अलग व्यवहार करता है
कार्यान्वयन एक पूरी पंक्ति को इसकी तुलना इकाई के रूप में मानता है। इसलिए नई पंक्ति की सीमाएँ परिणाम को आकार देती हैं: एक पंक्ति में संग्रहीत पैराग्राफ के अंदर एक-शब्द का संपादन उस पूरी पंक्ति को बदल देता है, जबकि वाक्य द्वारा व्यवस्थित एक ही गद्य एक बहुत छोटे क्षेत्र को अलग कर सकता है।
लाइन तुलना एक अलग डिस्प्ले के पीछे छिपा हुआ चरित्र विश्लेषण नहीं है। `splitLines` सरणी बनाता है, और LCS तालिका एक पंक्ति कुंजी की तुलना दूसरे से करती है। यह पूर्वानुमानित ग्रैन्युलैरिटी स्रोत और कॉन्फ़िगरेशन फ़ाइलों के लिए उपयुक्त है, लेकिन यह मिलान-दिखने वाले प्रतिस्थापन के अंदर बदले गए सटीक अक्षरों को उजागर नहीं कर सकता है।
स्पष्ट शब्दों में सबसे लंबा सामान्य अनुवर्ती - पांच-पंक्ति के उदाहरण पर LCS विचार के माध्यम से चलता है और दिखाता है कि अनुवर्ती के बाहर सब कुछ एक सम्मिलन या विलोपन कैसे बन जाता है
कल्पना करें कि बायीं रेखाएं A, B, C, D, E और दाहिनी रेखाएं A, C, E. A, C और E एक क्रमबद्ध सामान्य अनुवर्ती बनाते हैं। बी और डी इसके बाहर आते हैं, इसलिए परिणाम दो निष्कासन और तीन अपरिवर्तित पंक्तियों की रिपोर्ट करता है, जिनमें से किसी भी हटाई गई लाइन को प्रतिस्थापन के साथ जोड़ने की आवश्यकता नहीं होती है।
तालिका प्रत्येक शेष जोड़ी स्थिति के लिए, वहां से उपलब्ध सर्वोत्तम साझा लंबाई को रिकॉर्ड करती है। पुनर्निर्माण उन मूल्यों के माध्यम से आगे बढ़ता है। समान कुंजियाँ दोनों ओर आगे बढ़ती हैं; अन्यथा बड़ा पड़ोसी मूल्य यह तय करता है कि बाएं निष्कासन या दाएं जोड़ का उत्सर्जन करना है या नहीं।
मायर्स एल्गोरिदम और गति क्यों मायने रखती है - सूत्रों के बिना बताता है कि कैसे सबसे छोटी संपादन स्क्रिप्ट का पता लगाने से हजारों लाइनों वाली फाइलों पर तुलना तेज रहती है
कार्यपुस्तिका का नाम मायर्स है, लेकिन `diff.js` स्पष्ट रूप से सादे सबसे लंबे-सामान्य-अनुवर्ती गतिशील प्रोग्रामिंग को लागू करता है। इसकी टिप्पणी भिन्न मध्य के लिए O(n·m) समय और स्मृति बताती है। मायर्स का दावा करना या सबसे छोटा-संपादन-ग्राफ़ व्यवहार वास्तव में शिप किए जाने वाले कोड के लिए एक परिचित एल्गोरिदम का स्थान ले लेगा।
ToolAcre आवंटन से पहले उस लागत को सीमित करता है। समान उपसर्गों और प्रत्ययों को रैखिक पासों में हटा दिया जाता है, और किसी भी भिन्न मध्य में अधिकतम 2,000 पंक्तियाँ हो सकती हैं। मैट्रिक्स एक `Uint32Array` है; प्रलेखित सबसे खराब अनुमत वर्ग अनबाउंड बॉक्सिंग मानों के बजाय लगभग सोलह मेगाबाइट घेरता है।
ToolAcre एक LCS तालिका का उपयोग करता है, रूपरेखा में नामित मायर्स एल्गोरिदम का नहीं
"अतिरिक्त खोज", "निश्चित निर्यात", और "अद्यतित सहायता" वाले चेंजलॉग की तुलना एक संशोधन के साथ करें जो पहली और तीसरी प्रविष्टियाँ रखता है लेकिन अंतिम से पहले "जोड़े गए फ़िल्टर" सम्मिलित करता है। सामान्य प्रविष्टियाँ पथ को एंकर करती हैं, "निश्चित निर्यात" हटा दिया जाता है, और "जोड़ा गया फ़िल्टर" जोड़ा जाता है।
एल्गोरिथम उस युग्म को संशोधित रेखा नहीं कहता है। इसकी पंक्ति शब्दावली केवल समान है, जोड़ें और हटाएं, इसलिए एक पाठ्य प्रतिस्थापन एक निष्कासन के बाद एक जोड़ के रूप में प्रकट होता है। सारांश उन परिचालनों को अलग-अलग गिनता है और पाठों को केवल तभी समान रूप से चिह्नित करता है जब दोनों गिनती शून्य हों।
दो सही अंतर अलग-अलग क्यों दिख सकते हैं - दिखाता है कि कैसे समान रूप से संक्षिप्त संपादन स्क्रिप्ट के बीच संबंध बताते हैं कि क्यों एक टूल एक रिक्त रेखा को दोष देता है और दूसरा एक समापन ब्रैकेट को दोष देता है
दोहराई जाने वाली या विनिमेय रेखाएँ समान लंबाई के कई सामान्य अनुवर्ती उत्पन्न कर सकती हैं। ToolAcre दो पड़ोसी तालिका मान बराबर होने पर हटाने को प्राथमिकता देकर एक टाई को हल करता है। एक अन्य सही कार्यान्वयन पहले एक अतिरिक्त का चयन कर सकता है और समान संपादन लागत के साथ एक अलग दिखने वाला संरेखण प्रस्तुत कर सकता है।
यही कारण है कि एक रिक्त रेखा या समापन ब्रेस सभी टूलों में एक अलग हंक से जुड़ा हुआ दिखाई दे सकता है। विसंगति का मतलब स्वचालित रूप से खोई हुई सामग्री की तुलना नहीं है। प्रस्तुतिकरण के अंतर को प्रतिस्पर्धी तथ्यात्मक दावों के रूप में मानने से पहले मूल पंक्ति संख्याओं और आसपास की अपरिवर्तित पंक्तियों को पढ़ें।
इसमें क्या शामिल नहीं है - सिमेंटिक या संरचनात्मक तुलना, चाल का पता लगाना और शब्द-स्तरीय हाइलाइटिंग एक लाइन-आधारित अंतर की गणना से बाहर है
इस पथ में कुछ भी वाक्यविन्यास पेड़ों को पार्स नहीं करता है, नामांकित पहचानकर्ताओं को पहचानता है, लेबल किए गए ब्लॉक को लेबल करता है या गद्य अर्थ को समझता है। एक स्थानांतरित पैराग्राफ साझा-आदेश की आवश्यकता का उल्लंघन करता है और एक बार हटाए गए और एक बार जोड़े गए रूप में दिखाई दे सकता है। टूल पंक्तियों के अंदर वर्ण-या शब्द-स्तरीय हाइलाइट्स की गणना भी नहीं करता है।
वे चूक सीमाएँ हैं, छिपे हुए तरीके नहीं। सिमेंटिक दावों और मर्ज इतिहास के लिए संस्करण नियंत्रण के लिए भाषा-जागरूक समीक्षक का उपयोग करें। टेक्स्ट डिफ इस संक्षिप्त प्रश्न का उत्तर देता है कि दो क्रमित पंक्ति अनुक्रम कैसे भिन्न होते हैं, फिर मानव को यह व्याख्या करने देता है कि क्या वे पाठ्य संपादन महत्वपूर्ण हैं।
टेकअवे: हाइलाइट की गई पंक्तियों का वास्तव में क्या मतलब है - संक्षेप में बताया गया है कि संपादन की सबसे छोटी कहानी के रूप में एक पंक्ति को कैसे पढ़ा जाए और ToolAcre की टेक्स्ट तुलना इसे आपके टैब में बिना कुछ भी अपलोड किए कैसे चलाती है
हरी और लाल पंक्तियों को एक LCS-व्युत्पन्न स्पष्टीकरण के रूप में पढ़ें, लेखक के इरादे के प्रमाण के रूप में नहीं। उपसर्ग और प्रत्यय ट्रिमिंग से काम की मात्रा बदल जाती है लेकिन अंतिम पंक्ति लेखांकन में नहीं। मूल पाठ प्रत्येक पंक्ति में तब भी बना रहता है, जब केस या रिक्त स्थान विकल्प मिलान के लिए ढीली कुंजियाँ प्रदान करते हैं।
तुलना आयातित ब्राउज़र मॉड्यूल के माध्यम से निष्पादित होती है और DOM टेक्स्ट नोड्स के साथ प्रस्तुत होती है; टूल पथ में कोई रूपांतरण समापन बिंदु नहीं है. पाँच-पंक्ति का उदाहरण आज़माएँ, पक्षों की अदला-बदली करें, और पैच-आकार का आउटपुट डाउनलोड करके देखें कि दिशा कैसे शब्दार्थ का आविष्कार किए बिना परिवर्धन को निष्कासन में बदल देती है।