2010-04-18 17 views
13

मुझे एक साधारण स्रोत नियंत्रण प्रणाली लिखने की आवश्यकता है और आश्चर्य है कि मैं फ़ाइल अंतर के लिए क्या एल्गोरिदम उपयोग करूंगा?एल्गोरिदम?

मैं लाइसेंस चिंताओं के कारण मौजूदा स्रोत कोड में देखना नहीं चाहता हूं। मुझे इसे एमपीएल के तहत लाइसेंस प्राप्त करने की आवश्यकता है, इसलिए मैं सीवीएस या मर्कुरियल जैसे किसी भी मौजूदा सिस्टम को नहीं देख सकता क्योंकि वे सभी जीपीएल लाइसेंस प्राप्त हैं।

बस कुछ पृष्ठभूमि देने के लिए, मुझे बस कुछ वाकई सरल कार्यों की आवश्यकता है - एक फ़ोल्डर में बाइनरी फाइलें। कोई उपफोल्डर नहीं और प्रत्येक फ़ाइल अपने स्वयं के भंडार की तरह व्यवहार करती है। कुछ अनुमतियों को छोड़कर कोई मेटाडेटा नहीं।

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

उत्तर

5

सबसे लंबा आम उपक्रम एल्गोरिदम प्राथमिक तंत्र है जो विभिन्न प्रकार के उपकरणों द्वारा उपयोग किया जाता है, और इसे स्रोत कोड नियंत्रण प्रणाली द्वारा लीवरेज किया जा सकता है।

"रिवर्स डेल्टास" भंडारण के लिए एक आम दृष्टिकोण है, क्योंकि आपको मुख्य रूप से सबसे हालिया संशोधन से समय पर आगे बढ़ने की आवश्यकता है।

+1

हम्म, मुझे आपके उत्तर को बेहतर पसंद है। आप वास्तव में जानते हैं कि आप किस बारे में बात कर रहे हैं, ऐसा लगता है। :- पी – Jaxidian

1

मैं वास्तव में (ना अजीब?) दूसरे दिन इस के समान कुछ ... के बारे में सोच रहा था

मैं तुम्हारे लिए एक महान जवाब नहीं है, लेकिन मैं इस निष्कर्ष पर आया था कि अगर मैं थे कि एक फ़ाइल diff उपकरण लिखने के लिए, कि मैं एक एल्गोरिदम (diffs खोजने के लिए) के साथ ऐसा करता हूं जो कुछ हद तक कार्य करता है जैसे REGEXes अपनी लालची के साथ कैसे कार्य करता है।

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

5

Subversion के स्रोत कोड को देखने के बारे में कैसे? अपने अपाचे लाइसेंस के तहत लाइसेंस 2.0

+0

धन्यवाद। यह जांचना है कि अपाचे और एमपीएल संगत हैं या नहीं, लेकिन ऐसा लगता है। –

2

हालांकि जीवाश्म जीपीएल है, डेल्टा एल्गोरिथ्म rsync पर आधारित है और वर्णित here

6

Patience Diff दो फ़ाइलों है कि लोगों को समझ बनाने की संभावना है के बीच डेल्टा खोजने के लिए एक अच्छा एल्गोरिथ्म है। यह अक्सर बेवकूफ "सबसे आम आम अनुवर्ती" एल्गोरिदम की तुलना में बेहतर परिणाम देता है, लेकिन परिणाम व्यक्तिपरक होते हैं।

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

+0

यह बहुत अच्छा है। अभी भी एलसीएस एल्गोरिदम परिवार की एक भिन्नता है, लेकिन यह एक बहुत अच्छा परिष्करण है। – JasonTrue

+0

दिलचस्प! (पैड, पैड ...) –

3

जीन मायर्स ने एक अच्छा पेपर An O(ND) Difference Algorithm and its Variations लिखा है। जब अनुक्रमों की तुलना करने की बात आती है, तो मायर्स वह आदमी होता है। आपको शायद आरसीएस पर वाल्टर टिची का पेपर भी पढ़ना चाहिए; यह बताता है कि नवीनतम संस्करण और अंतर को संग्रहीत करके फ़ाइलों का एक सेट कैसे स्टोर किया जाए।

2

डेल्टा (आगे या पीछे) स्टोर करने का विचार संस्करण नियंत्रण के संबंध में क्लासिक है। मुद्दा हमेशा रहा है, "आप क्या डेल्टा स्टोर करते हैं?"

स्रोत नियंत्रण प्रणालियों के बहुत सारे" डिफ "द्वारा अनिवार्य रूप से गणना के रूप में डेल्टा को संग्रहीत करते हैं, उदाहरण के लिए, सबसे लंबे समय तक सामान्य-रेखाओं के अनुरूप-आधारित पूरक। लेकिन आप उन दस्तावेजों के विशिष्ट तरीके से विशिष्ट प्रकार के दस्तावेज़ों के लिए डेल्टा की गणना कर सकते हैं , छोटे (और अक्सर अधिक समझने योग्य) deltas प्राप्त करने के लिए।

प्रोग्रामिंग भाषा स्रोत कोड के लिए, कोई प्रोग्राम संरचनाओं पर लेवेनशेटिन दूरी की गणना कर सकता है। विभिन्न प्रकार के लोकप्रिय प्रोग्रामिंग लैंगुग के लिए अनिवार्य रूप से ऐसा करने के लिए टूल का एक सेट पाया जा सकता है Smart Differencer

यदि आप गैर-पाठ फ़ाइलों को संग्रहीत कर रहे हैं, तो आप उनकी संरचना का लाभ लेने में सक्षम हो सकते हैं मॉलर डेल्टास

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