बाइनरी डेटा समानता की गणना

Question

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

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

जिस समस्या पर मैं काम कर रहा हूं वह वीडियो गेम रोम छवियों के लिए क्लोन डिटेक्शन है। उन लोगों के लिए जिनके पास अनुकरण के साथ अनुभव नहीं है, रोम गेम कारतूस पर डेटा के डंप हैं। एक रॉम "क्लोन" आमतौर पर एक ही गेम का एक संशोधित संस्करण है, सबसे आम प्रकार एक अनुवादित संस्करण है। उदाहरण के लिए, मूल के जापानी और अंग्रेजी संस्करण एनईएस के लिए अंतिम काल्पनिक क्लोन हैं। गेम लगभग सभी संपत्तियों (sprites, संगीत, आदि) साझा करते हैं, लेकिन पाठ का अनुवाद किया गया है।

वर्तमान में कई समूह हैं जो विभिन्न प्रणालियों के लिए क्लोन की सूचियों को बनाए रखने पर काम करते हैं, लेकिन जहां तक ​​मैं कह सकता हूं, यह सब मैन्युअल रूप से किया जाता है। मैं जो करने का प्रयास कर रहा हूं वह समान रोम की छवियों को स्वचालित रूप से और निष्पक्ष रूप से पहचानने का तरीका ढूंढता है, "ये एक ही गेम की तरह लगते हैं" की बजाय डेटा समानता के आधार पर। क्लोन का पता लगाने के कई कारण हैं, लेकिन Solid compression के साथ प्रमुख प्रेरणा का उपयोग किया जाना है। यह सभी गेम क्लोनों को एक ही संग्रह में संपीड़ित करने की अनुमति देता है, पूरे संपीड़ित क्लोन सेट अक्सर व्यक्तिगत रोम में से एक की तुलना में केवल थोड़ी अधिक जगह लेते हैं।

कुछ चिंताएं विचार करने के लिए जब संभावित दृष्टिकोण के साथ आ:

• रोम सिस्टम के आधार पर, आकार में अत्यधिक भिन्नता है। कुछ छोटे होते हैं, लेकिन आधुनिक प्रणालियों में बड़े, 256 एमबी या अधिक हो सकते हैं। कुछ (सभी?) प्रणालियों में केवल 2 आकारों की शक्तियां होती हैं, इन प्रणालियों में से एक पर 130 एमबी गेम में 256 एमबी रोम होगा, जो काफी हद तक खाली होगा। ध्यान दें कि इसके कारण, कुछ क्लोनों में जंगली रूप से भिन्न आकार हो सकते हैं, यदि कोई गेम संस्करण थ्रेसहोल्ड को पार करता है और उसे एक कारतूस का उपयोग करना होता है जो आकार के दोगुना होता है।
• वर्तमान में कई प्रणालियों पर हजारों ज्ञात रोम हैं, जिनमें अधिकांश सिस्टम अभी भी लगातार जारी किए जाते हैं। यहां तक ​​कि पुराने सिस्टम के लिए, एक प्रमुख रोम-हैकिंग समुदाय है जो अक्सर संशोधित रोम उत्पन्न करता है।
• रोम की हर संभव जोड़ी के लिए समानता डेटा संग्रहीत करने के परिणामस्वरूप किसी भी लोकप्रिय प्रणाली के लिए डेटा की लाखों पंक्तियां होंगी। 5000 रोम वाले सिस्टम को समानता डेटा की 25 मिलियन पंक्तियों की आवश्यकता होगी, जिसमें एक नया गेम 5000 पंक्तियों को जोड़ देगा।
• प्रसंस्करण का राज्य पुनर्प्राप्त करने योग्य होना चाहिए, ताकि यदि यह बाधित हो तो यह इसे छोड़कर उठा सकता है। किसी भी विधि के साथ, बहुत सारी प्रोसेसिंग की आवश्यकता होगी, और यह मानते हुए कि एक चीज में पूरी चीज चलनी सुरक्षित नहीं है।
• किसी भी समय नए रोम जोड़े जा सकते हैं, इसलिए विधि को यह नहीं मानना ​​चाहिए कि इसमें पहले से ही "पूर्ण" सेट है।यही है, यहां तक ​​कि जब आप पहले से ही सभी मौजूदा रोम के लिए समानता का पता लगा चुके हैं, तो एक नया जोड़ा गया है (और यह भी पिछली प्रसंस्करण पूरी तरह से समाप्त होने से पहले भी हो सकता है) यह निर्धारित करने के लिए सभी पिछले लोगों की तुलना करने के लिए एक विधि होनी चाहिए जो (अगर कोई है) यह एक क्लोन है।
• उच्च प्रसंस्करण गति सटीकता (एक बिंदु पर) पर प्राथमिकता दी जानी चाहिए। यह जानकर कि क्या दो रोम 94% या 96% समान हैं, विशेष रूप से महत्वपूर्ण नहीं है, लेकिन अगर किसी नए रोम की तुलना करने के लिए प्रसंस्करण का दिन पिछले सभी लोगों के लिए होता है, तो प्रोग्राम संभवतः कभी पूरा नहीं होगा।

काम करने के लिए यह एक दिलचस्प समस्या रही है, मैं यह देखने के लिए उत्सुक हूं कि अन्य लोग क्या कर सकते हैं। यदि आप कोई और विवरण चाहते हैं तो मुझे टिप्पणियों में बताएं, और मैं उन्हें आपूर्ति करने की कोशिश करूंगा।

Answer 1

ऐसा लगता है कि आप बाइनरी डेल्टा या शायद बाइनरी डेल्टा (जैसे आकार के) के अनुप्रयोग से प्राप्त एक इंडेक्स चाहते हैं। इसके बाद आप इस इंडेक्स की तुलना कुछ आधार रेखा से कर सकते हैं जिसे आप प्रयोग करने के लिए प्रयोग करते हैं कि यह "क्लोन" है या नहीं।

संपीड़न और डेल्टा निर्माण के बीच बहुत सारी समानताएं हैं, इसलिए मैं कहूंगा कि आप अपने वर्तमान कार्यान्वयन से बहुत दूर नहीं हैं।

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

सामान्य मामले के लिए उपयोगी हैश का निर्माण कई वर्षों से सीएस में सक्रिय रूप से अनुसंधान विषय रहा है। LSHKit सॉफ़्टवेयर लाइब्रेरी इस प्रकार के कुछ एल्गोरिदम लागू करता है। इंटरनेट एक्सेस करने योग्य पेपर FINDING SIMILAR FILES IN A LARGE FILE SYSTEM ऐसा लगता है कि इसे टेक्स्ट फ़ाइलों की तुलना करने पर अधिक लक्षित किया जा सकता है लेकिन यह आपके लिए उपयोगी हो सकता है। हालिया पेपर Multi-resolution similarity hashing एक अधिक शक्तिशाली एल्गोरिदम का वर्णन करता है। यह सदस्यता के बिना सुलभ प्रतीत नहीं होता है, हालांकि। आप शायद अन्य संसाधन ब्राउज़ करते समय विकिपीडिया लेख को Locality Sensitive Hashing पर आसान रखना चाहते हैं। वे सभी बहुत तकनीकी हो जाते हैं और विकिपीडिया प्रविष्टि स्वयं गणित भारी है। अधिक उपयोगकर्ता के अनुकूल विकल्प के रूप में आप Acoustic Fingerprinting के क्षेत्र से कुछ विचार (या यहां तक ​​कि निष्पादन योग्य) लागू करने में सक्षम हो सकते हैं।

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

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

Answer 2

आप bsdiff पर देख सकते हैं, जो एक बाइनरी diffing/पैचिंग सिस्टम है। बहुत सारे सिद्धांत के साथ एक थीसिस भी है।

Answer 3

आप hash trees जैसे कुछ संग्रहीत करके शुरू कर सकते हैं। प्रत्येक रोम के लिए इस तरह के एक हैंश को स्टोर करने की आवश्यकता होती है, और आवश्यक स्टोरेज स्पेस केवल रोम के आकार (लेकिन बहुत कम) के अनुपात के समान आनुपातिक होता है, जो निरंतर ब्लॉक आकार मानता है। चयनित ब्लॉक आकार को सटीकता सुनिश्चित करने के लिए पर्याप्त ग्रैन्युलरिटी देना चाहिए, उदाहरण के लिए: 128 एमआईबी के न्यूनतम आकार के लिए, 1% और Tiger-128 hash की शुद्धता बाधा (डायरेक्टकनेक्ट के माध्यम से स्थानांतरित फ़ाइलों की जांच के लिए वे क्या उपयोग करते हैं), 1 एमआईबी का ब्लॉक आकार ठीक है और आप 128 * 128/8 = 2048 बाइट्स में सभी हैंश स्टोर कर सकते हैं! तो 10,000 रोम के लिए इसे करने के लिए केवल 20 एमआईबी स्पेस की आवश्यकता होगी। इसके अलावा, आप कम सुरक्षित, लेकिन तेज़ और/या छोटे हैश चुन सकते हैं। समानता जोड़ने/जांचने के लिए एक नया रोम कुछ ऐसा होगा:

1. ब्लॉक में नए रोम को विभाजित करें और उनमें से प्रत्येक को हैश करें।
2. पहले से ही डेटाबेस में प्रत्येक रोम के लिए, नए रोम के हैंश के साथ अपने हैंश की तुलना करें (नीचे देखें)।

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

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

Answer 4

मुझे लगता है कि कुछ तकनीकों डेटा संपीड़न से उधार यहां दिलचस्प हो सकता है:

मान लें आप व्यक्तिगत रूप से दो फ़ाइलों, ए और बी

कम्प्रेस प्रत्येक फ़ाइल है और संकुचित आकार एक साथ जोड़ें। फिर दो फ़ाइलों को एक एकल, बड़ी फ़ाइल में संयोजित करें और इसे भी संपीड़ित करें।

आकारों में अंतर आपको अनुमान लगाएगा कि फाइलें कितनी समान हैं।

मेरा सुझाव है कि आप संपीड़न करने के लिए बरो व्हीलर ट्रांसफ़ॉर्मेशन (bzip2) आज़माएं। अधिकांश अन्य संपीड़न एल्गोरिदम में केवल सीमित इतिहास होता है। बीडब्ल्यूटी एल्गोरिदम otoh डेटा के बहुत बड़े हिस्सों पर काम कर सकता है। एल्गोरिदम एक ही समय में दोनों फाइलों को "देखता है" और किसी भी समानता के परिणामस्वरूप उच्च संपीड़न अनुपात होगा।

Answer 5

दो विचार:

• एक डाटा प्रवाह ग्राफ के रूप में फ़ाइल के आयोजन और कि represention पर कुछ कैनॉनिकलाइज़ेशन कर पर विचार करें। चूंकि आप निर्देश सेट को जानते हैं, यह संभव हो सकता है, शायद एक डिस्सेबलर को दबाकर और कुछ टेक्स्ट प्रोसेसिंग कर रहा हो।
• CRM114 जैसे एक प्रशिक्षक वर्गीकरण आपको एक कॉम्पैक्ट प्रतिनिधित्व देने के लिए आसान हो सकता है जो आपको कुछ विचार देता है कि क्या द्विआधारी में काफी आम है या नहीं।

Answer 6

हालांकि यह "कुछ दिनों" से बहुत अधिक रहा है, मुझे लगा कि मुझे शायद यहां अपना वर्तमान समाधान जोड़ना चाहिए।

निल्स पाइपेनब्रिनक मेरी वर्तमान विधि के समान दिशा में जा रहा था। चूंकि क्लोन ढूंढने के मुख्य परिणामों में से एक ठोस संग्रहण से बड़ी बचत है, मुझे लगा कि मैं किसी भी दो रोम को एक साथ संपीड़ित करने और यह देखने के लिए कि कितनी जगह बचाई गई थी। मैं इसके लिए 7zip में LZMA एल्गोरिदम का उपयोग कर रहा हूं।

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

अब, यह आवश्यक संपीड़न प्रयास की एक बड़ी संख्या है, इसलिए मैं अब तक अनुकूलन की एक जोड़ी है (और अधिक जानने के लिए चाहते हैं):

1. कैसे समान संकुचित के आधार पर प्राथमिकता तुलना आकार हैं। यदि रोम ए में 10 एमबी का संपीड़ित आकार होता है और रोम बी में 2 एमबी का संकुचित आकार होता है, तो उनके लिए 20% से अधिक समान होना असंभव है, इसलिए वास्तविक परिणाम प्राप्त करने के लिए उन्हें तुलना करना बाद में छोड़ा जा सकता है। अत्यधिक समान फाइलों पर एक ही संपीड़न एल्गोरिदम को चलाने के परिणामस्वरूप समान आकार के परिणाम होते हैं, इसलिए यह बहुत सारे क्लोन बहुत तेज़ी से पाता है।

2. उपरोक्त के साथ संयुक्त, रोम की किसी भी जोड़ी के बीच संभावित समानता पर ऊपरी और निचले "सीमाएं" दोनों रखें। यह आगे प्राथमिकता की अनुमति देता है। यदि रोम ए और बी 95% समान हैं, और रोम बी और सी केवल 2% समान हैं, तो आप पहले ही जानते हैं कि ए और सी 0% और 7% के बीच हैं। यह क्लोन होने के लिए बहुत कम है, इसलिए इस तुलना को सुरक्षित रूप से स्थगित कर दिया जा सकता है या यहां तक ​​कि पूरी तरह से अनदेखा किया जा सकता है, जब तक कि मैं वास्तव में सबकुछ की सटीक समानताओं को जानना नहीं चाहता।

Answer 7

Plagiarism Detection एल्गोरिदम से कुछ विचारों का उपयोग करें।

मेरा विचार:

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

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

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

आप शायद प्रत्येक के उच्च आवृत्तियों के साथ कम हैश मान चाहते हैं, लेकिन बहुत दूर मत जाओ या आपका ग्राफ बहुत सपाट होगा, जिसके परिणामस्वरूप उनकी तुलना में कठिनाई होगी। इसी प्रकार बहुत व्यापक मत जाओ, या आपके पास बहुत कम आवृत्तियों की आवश्यकता होगी, जिससे तुलना फिर से कठिन हो जाएगी।

प्रति ग्राफ़ इस ग्राफ को स्टोर करें। प्रत्येक हैश मान के आवृत्तियों में अंतर के वर्गों के योग की गणना करके दो अलग-अलग रोमों के लिए आवृत्ति ग्राफ की तुलना करें। यदि वह शून्य पर रकम करता है तो रोम समान होने की संभावना है। शून्य से आगे यह है कि रोम की तरह ही कम होगा।

Answer 8

जैसा कि वायलॉन फ्लिन ने कहा, आपको बाइनरी डेल्टा एल्गोरिदम की आवश्यकता हो सकती है। rsync algorithm एक अच्छा है। यह तेज़ और भरोसेमंद है। utility's documentation भी देखें।

Answer 9

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

difflib (या समकक्ष डब्ल्यू/आपकी पसंदीदा भाषा) के साथ एक समाधान को हैक करने के लिए एक त्वरित और गंदे समाधान होगा, क्योंकि यह आपको एक स्लाइडिंग तुलना प्राप्त करता है जो डेटा जोड़ या हटाने से निपट सकता है। ROM को निष्पादन योग्य और डेटा अनुभागों में विभाजित करें (यदि संभव हो)। डेटा सेक्शन की तुलना सीधे और similarity ratio calculated की तुलना की जा सकती है, हालांकि आपको अभी भी समस्याएं/पते या ऑफसेट की समस्या होगी।

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

दुर्भाग्यपूर्ण हिस्सा यह है कि यह अभी भी आपके द्वारा ट्रैक किए जाने वाले रोम की संख्या पर एक ओ (एन^2) ऑपरेशन है, लेकिन इसे (वृद्धिशील) क्लस्टरिंग या आवृत्ति-आधारित तुलना आदेश के साथ कम किया जा सकता है ताकि राशि कम हो सके तुलना की जरूरत है।

Answer 10

xdelta सभ्य द्विआधारी diffs प्राप्त करने के लिए बहुत उपयोगी है: http://xdelta.org