सी # में बाइनरी पैच-पीढ़ी

क्या किसी के पास सी # में बाइनरी पैच पीढ़ी एल्गोरिदम कार्यान्वयन है, या पता है?

असल में, दो फाइलों (नामित पुराना और नया ) की तुलना करें, और एक पैच फ़ाइल तैयार करें जिसका उपयोग पुरानी फ़ाइल को अपग्रेड करने के लिए किया जा सकता है नई फ़ाइल के समान सामग्री।

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

मेरे स्वयं के एल्गोरिदम या तो लुसी हो जाते हैं (तेज़ लेकिन बड़े पैच का उत्पादन करते हैं) या धीमे (छोटे पैच का उत्पादन करते हैं लेकिन ओ (एन ^ 2) रनटाइम होते हैं)।

कार्यान्वयन के लिए कोई सलाह, या पॉइंटर्स अच्छा होगा।

विशेष रूप से, कार्यान्वयन का उपयोग विभिन्न बड़े डेटाफाइलों के लिए सर्वर को सिंक में रखने के लिए किया जाएगा, जिनके लिए हमारे पास एक मास्टर सर्वर है। जब मास्टर सर्वर डेटाफाइल बदलते हैं, तो हमें कई ऑफ़-साइट सर्वर भी अपडेट करने की आवश्यकता होती है।

मैंने बनाया है कि सबसे बेवकूफ एल्गोरिदम, जो केवल उन फ़ाइलों के लिए काम करता है जिन्हें स्मृति में रखा जा सकता है, निम्नानुसार है:

  1. Grab the first four bytes from the old file, call this the key
  2. Add those bytes to a dictionary, where key -> position, where position is the position where I grabbed those 4 bytes, 0 to begin with
  3. Skip the first of these four bytes, grab another 4 (3 overlap, 1 one), and add to the dictionary the same way
  4. Repeat steps 1-3 for all 4-byte blocks in the old file
  5. From the start of the new file, grab 4 bytes, and attempt to look it up in the dictionary
  6. If found, find the longest match if there are several, by comparing bytes from the two files
  7. Encode a reference to that location in the old file, and skip the matched block in the new file
  8. If not found, encode 1 byte from the new file, and skip it
  9. Repeat steps 5-8 for the rest of the new file

यह खिड़की के बिना कुछ हद तक संपीड़न की तरह है, इसलिए यह बहुत सारी स्मृति का उपयोग करेगा। हालांकि, यह काफी तेजी से है, और जब तक मैं कोड आउटपुट को न्यूनतम बनाने की कोशिश करता हूं, तब तक काफी छोटे पैच पैदा करता है।

एक और मेमोरी-कुशल एल्गोरिदम खिड़की का उपयोग करता है, लेकिन बहुत बड़ी पैच फ़ाइलों का उत्पादन करता है।

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


Edit #1: Here is a more detailed description of the above algorithm.

सबसे पहले, दो फाइलों को गठबंधन करें, ताकि आपके पास एक बड़ी फ़ाइल हो। दो फाइलों के बीच कट-पॉइंट याद रखें।

दूसरा, ऐसा करें कि 4 बाइट्स लें और पूरी स्थिति में सबकुछ के लिए अपनी स्थिति को शब्दकोश में जोड़ें चरण।

तीसरा, जहां से नई फ़ाइल शुरू होती है, लूप को 4 बाइट्स के मौजूदा संयोजन को ढूँढने का प्रयास करने के साथ करें, और सबसे लंबा मिलान ढूंढें। सुनिश्चित करें कि हम केवल पुरानी फ़ाइल से या पहले से नई फ़ाइल में स्थितियों की तुलना में केवल की स्थिति पर विचार करें। यह सुनिश्चित करता है कि हम पैच एप्लिकेशन के दौरान पुरानी और नई फाइल दोनों में सामग्री का पुन: उपयोग कर सकते हैं।


Edit #2: Source code to the above algorithm

आपको कुछ समस्याएं होने वाले प्रमाण पत्र के बारे में चेतावनी मिल सकती है। मैं नहीं जानता कि इसे कैसे हल किया जाए ताकि समय केवल प्रमाणपत्र स्वीकार कर लिया जा सके।

स्रोत मेरी अधिकांश लाइब्रेरी से कई अन्य प्रकारों का उपयोग करता है ताकि फ़ाइल वह सब कुछ न हो, लेकिन यह एल्गोरिदम कार्यान्वयन है।


@lomaxx, मैंने xdelta नामक उपवर्तन में उपयोग किए गए एल्गोरिदम के लिए एक अच्छा प्रलेखन खोजने का प्रयास किया है, लेकिन जब तक कि आप पहले से ही नहीं जानते कि एल्गोरिदम कैसे काम करता है, मेरे द्वारा प्राप्त किए गए दस्तावेज़ मुझे यह बताने में असफल होते हैं कि मुझे क्या जानने की आवश्यकता है।

या शायद मैं सिर्फ घना हूँ ... :)

मैंने आपके द्वारा दी गई साइट से एल्गोरिदम पर एक त्वरित झलक लिया, और दुर्भाग्य से यह उपयोग करने योग्य नहीं है। द्विआधारी diff फ़ाइल से एक टिप्पणी कहती है:

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

हालांकि मेरी जरूरतें इष्टतम नहीं हैं, इसलिए मैं एक और व्यावहारिक समाधान की तलाश में हूं।

हालांकि उत्तर के लिए धन्यवाद, अगर मुझे कभी उनकी ज़रूरत है तो उनकी उपयोगिताओं के लिए एक बुकमार्क जोड़ा गया।

Edit #1: Note, I will look at his code to see if I can find some ideas, and I'll also send him an email later with questions, but I've read that book he references and though the solution is good for finding optimal solutions, it is impractical in use due to the time requirements.

Edit #2: I'll definitely hunt down the python xdelta implementation.

0
कोड का वह विशेष भाग पोस्ट है, यहां मेरा वर्तमान संस्करण है, हालांकि मैंने उम्र में लाइब्रेरी को बनाए रखा नहीं है: lassevk.kilnhg.com/Code/LVK-for-NET/net-40/trunk/Files/…
जोड़ा लेखक Lasse Vågsæther Karl, स्रोत
स्रोत कोड लिंक मर चुका है। क्या आप इसे अपडेट कर सकते हैं?
जोड़ा लेखक lasseschou, स्रोत

6 उत्तर

अगर यह स्थापना या वितरण के लिए है, तो क्या आपने विंडोज इंस्टालर एसडीके का उपयोग करने पर विचार किया है? इसमें बाइनरी फाइलों को पैच करने की क्षमता है।

http://msdn.microsoft.com/en-us /library/aa370578(VS.85).aspx

0
जोड़ा

यह पता लगाने लायक हो सकता है कि कुछ अन्य लोग इस जगह में क्या कर रहे हैं और जरूरी नहीं कि सी # क्षेत्र में भी।

यह सी # में लिखी गई एक लाइब्रेरी है

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

0
जोड़ा
एसवीएन xdelta एल्गोरिदम का उपयोग करता है (कम से कम स्रोत पर एक नज़र से)
जोड़ा लेखक Simon Buchan, स्रोत

क्षमा करें मैं और मदद नहीं कर सका। मैं निश्चित रूप से xdelta को देखता रहूंगा क्योंकि मैंने 600 एमबी + आईएसओ फाइलों पर गुणवत्ता वाले डिस्प्ले बनाने के लिए कई बार इसका इस्तेमाल किया है जो हमने अपने उत्पादों को वितरित करने के लिए उत्पन्न किया है और यह बहुत अच्छा प्रदर्शन करता है।

0
जोड़ा
हाँ, xdelta अच्छा है। हालांकि, यह अपेक्षाकृत छोटी खिड़कियों पर काम करता है (100kb अगर मुझे गलत नहीं है), लेकिन इसके कामकाजी कार्यान्वयन के साथ मैं आसानी से हमारे डेटा के लिए इसे ट्विक कर सकता हूं। अगर मुझे गलत नहीं लगता है तो विंडो आकार को उपversण के लिए गति के लिए चुना गया था, लेकिन हमारा कोड आसानी से थोड़ी देर तक चला सकता है, जब तक कि उसे पूरी रात लेने की आवश्यकता नहीं है (जो मेरा वर्तमान कार्यान्वयन करता है)।
जोड़ा लेखक Lasse Vågsæther Karl, स्रोत

bsdiff was designed to create very small patches for binary files. As stated on its page, it requires max(17*n,9*n+m)+O(1) bytes of memory and runs in O((n+m) log n) time (where n is the size of the old file and m is the size of the new file).

मूल कार्यान्वयन सी में है, लेकिन एक सी # पोर्ट का वर्णन यहां है और यहां उपलब्ध है।

0
जोड़ा

क्या आपने VCDiff देखा है? यह एक विविध पुस्तकालय का हिस्सा है जो काफी सक्रिय प्रतीत होता है (अंतिम रिलीज आर 25 9, 23 अप्रैल 2008)। मैंने इसका इस्तेमाल नहीं किया है, लेकिन सोचा कि यह उल्लेखनीय था।

0
जोड़ा

यह एक मोटा दिशानिर्देश है, लेकिन निम्नलिखित rsync एल्गोरिदम के लिए है जिसका उपयोग आपके द्विआधारी पैच बनाने के लिए किया जा सकता है।

http://rsync.samba.org/tech_report/tech_report.html

0
जोड़ा