फ़ाइल संस्करण दृष्टिकोण के बारे में

जो लोग स्रोत नियंत्रण संस्करण नियंत्रण प्रणाली (SVN, Mercurial, Git, आदि) का उपयोग करते हैं, वे सबसे अधिक संभावना उपयोगकर्ता द्वारा किए गए परिवर्तनों को देखने के लिए फ़ाइल संस्करणों की तुलना करने की क्षमता का लाभ उठाएंगे। कई स्वतंत्र संस्करण तुलना कार्यक्रम ( WinMerge , BeyondCompare , आदि) हैं। संस्करणों की तुलना करते समय, एक नियम के रूप में, एक फ़ाइल के दो संस्करणों को एक दूसरे के बगल में दिखाया जाता है ताकि दस्तावेजों के समान (अपरिवर्तित) हिस्से एक दूसरे के विपरीत स्थित हों, और बदले (जोड़ा और हटाए गए) को संबंधित रंग में हाइलाइट किया जाता है।
मुझे यकीन है कि कई लोगों को यह जानने में दिलचस्पी होगी कि इस तरह की तुलना को लागू करने के लिए कौन से एल्गोरिदम का उपयोग किया जा सकता है।

एक साधारण मामले के रूप में, सादे पाठ फ़ाइलों की तुलना करने पर विचार करें।
एक पाठ फ़ाइल पाठ की पंक्तियों (या बल्कि पैराग्राफ) का एक संग्रह है। एक पैरा वर्णों की एक पंक्ति है जो लाइन-एंड और कैरिज रिटर्न कैरेक्टर (विंडोज पर) या सिर्फ एक लाइन-एंड कैरेक्टर (यूनिक्स / लिनक्स पर) के साथ समाप्त होती है। हम इस तथ्य से विचलित नहीं होंगे कि पात्रों को विभिन्न एन्कोडिंग द्वारा दर्शाया जा सकता है और हम मान लेंगे कि हम एकल-बाइट ASCII के साथ काम कर रहे हैं। ऐसी फ़ाइल के संस्करणों की तुलना करने का कार्य यह निर्धारित करना है कि कौन से पैराग्राफ नहीं बदले हैं और कौन से पैराग्राफ बदल गए हैं, हटाए गए या जोड़े गए हैं।

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

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

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

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