बड़े डेटासेट पर हैमिंग दूरी की गणना

यह लेख HEngine एल्गोरिथ्म और बड़ी मात्रा में डेटा पर हेमिंग की दूरी की गणना की समस्या के समाधान के कार्यान्वयन पर चर्चा करेगा।

परिचय

हामिंग दूरी समान लंबाई वाली लाइनों के लिए विभिन्न पदों की संख्या है। उदाहरण के लिए, एचडी ( 1 0 0 , 0 0 1 ) = 2।

पहली बार, हैमिंग दूरी की गणना करने की समस्या 1969 [1] में मिन्स्की और पैपर्ट द्वारा पेश की गई थी, जहाँ कार्य डेटाबेस से उन सभी पंक्तियों की खोज करना था जो कि अनुरोध किए गए हैमिंग दूरी के भीतर हैं।

ऐसा कार्य असामान्य रूप से सरल है, लेकिन इसके प्रभावी समाधान की खोज अभी भी एजेंडे में है।

हैमिंग की दूरी पहले से ही व्यापक रूप से विभिन्न कार्यों के लिए उपयोग की जाती है, जैसे नज़दीकी डुप्लिकेट, पैटर्न मान्यता, दस्तावेज़ वर्गीकरण, त्रुटि सुधार, वायरस का पता लगाना, आदि।

उदाहरण के लिए, मांकू और सहयोगियों ने हेमिंग दूरी गणना [2] के आधार पर वेब दस्तावेज़ों को अनुक्रमित करते समय डुप्लिकेट को क्लस्टर करने की समस्या के समाधान का प्रस्ताव दिया।
मिलर और दोस्तों ने एक दिए गए ऑडियो टुकड़े [3], [4] द्वारा गाने की खोज करने की अवधारणा का भी प्रस्ताव रखा।
इसी तरह के समाधान छवि खोज और रेटिना मान्यता [5], [6], आदि के कार्य के लिए उपयोग किए गए थे।

समस्या का वर्णन

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

कार्य उन सभी रेखाओं की खोज करना है जो दूरी k के भीतर हैं।

एल्गोरिथ्म की मूल अवधारणा में, समस्या के दो संस्करणों पर विचार किया जाता है: स्थिर और गतिशील।

- एक स्थैतिक समस्या में, दूरी k अग्रिम में पूर्व निर्धारित है।
- गतिशील में, इसके विपरीत, आवश्यक दूरी अग्रिम में ज्ञात नहीं है।

लेख केवल एक स्थिर समस्या के समाधान का वर्णन करता है।

स्थिर कार्य के लिए HEngine एल्गोरिथ्म का विवरण

यह कार्यान्वयन कश्मीर <= 10 के भीतर तार खोजने पर केंद्रित है।

स्थैतिक समस्या के तीन समाधान हैं: रैखिक स्कैन, क्वेरी विस्तार और डेटाबेस विस्तार।

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

HEngine [8] स्मृति और क्रम के बीच प्रभावी ढंग से संतुलन बनाने के लिए इन तीन तरीकों के संयोजन का उपयोग करता है।

सिद्धांत की बिट

एल्गोरिथ्म एक छोटे प्रमेय पर आधारित है जो निम्नलिखित बताता है:

यदि दो रेखाओं के लिए a और b की दूरी HD ( a , b ) <= k है , तो यदि हम विभाजन विधि का उपयोग करके rcut विधि द्वारा लाइनों को a और b में विभाजित करते हैं
r > = ⌊ k / 2⌋ + 1
जब उनकी दूरी एकता, HD (i, b i) <= 1 से अधिक नहीं होगी तो कम से कम q = r - ⌋ k / 2ings सबस्ट्रिंग अवश्य होंगे।

आधार विधि से आधार स्ट्रिंग से सबस्ट्रिंग का चयन निम्नलिखित सिद्धांतों के अनुसार किया जाता है:
एक विभाजन कारक नामक एक मूल्य का चयन किया जाता है जो स्थिति को संतुष्ट करता है
r > = ⌊ k / 2⌋ + 1

पहले r - ( m mod r ) सबस्ट्रिंग की लंबाई लंबाई / m / r r होगी, और अंतिम m mod r substrings ⌈ m / r r । जहां मीटर स्ट्रिंग की लंबाई है, ⌊ निकटतम तल पर गोलाई में है, और निकटतम शीर्ष पर of राउंडिंग है।

अब एक ही बात, केवल एक उदाहरण के साथ:

लंबाई m = 8 बिट्स के दो बाइनरी स्ट्रिंग्स दिए गए हैं: A = 11110000 और B = 11010001, उनके बीच की दूरी k = 2 है।
हम विभाजन कारक आर = 2/2 + 1 = 2 का चयन करते हैं, अर्थात, लंबाई m / r = 4 बिट्स के कुल 2 सब्सट्रिंग होंगे।

a1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

यदि हम अब संगत सबस्ट्रिंग के बीच की दूरी की गणना करते हैं, तो कम से कम ( q = 2 - 2/2 = 1) एक स्थानापन्न संयोग होगा या उनकी दूरी एक से अधिक नहीं होगी।

हम क्या देखते हैं:
एचडी (ए 1, बी 1) = एचडी (1111, 1101) = 1
और
HD (a2, b2) = HD (0000, 0001) = 1

बेस स्ट्रिंग के सबस्ट्रिंग को सिग्नेचर कहा जाता था।
हस्ताक्षर या सबस्ट्रिंग ए 1 और बी 1 (ए 2 और बी 2, ए 3 और बी 3 ..., एक आर और बी आर ) को एक दूसरे के साथ संगत कहा जाता है, और यदि उनके विभिन्न बिट्स की संख्या एक से अधिक नहीं है, तो इन हस्ताक्षरों को मिलान कहा जाता है।

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

डेटाबेस प्रीप्रोसेसिंग

हम पहले से ही जानते हैं कि यदि आप स्ट्रिंग को सब्सट्रिंग्स में सही ढंग से विभाजित करते हैं, तो कम से कम एक सबस्ट्रिंग संबंधित सबस्ट्रिंग के साथ मेल खाएगा या विभिन्न बिट्स की संख्या एक से अधिक नहीं होगी (हस्ताक्षर मेल खाएंगे)।

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

लेकिन सबस्ट्रिंग द्वारा कैसे खोजें?

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

एल्गोरिथ्म का मूल संस्करण सबस्ट्रिंग के क्रमांकन का भी वर्णन करता है ताकि चयनित सब्सट्रिंग पहले स्थान पर हो। यह कार्यान्वयन में आसानी के लिए और एल्गोरिथ्म के आगे अनुकूलन के लिए अधिक किया जाता है:

एक लाइन A है, जिसे 3 सबस्ट्रिंग में विभाजित किया गया है, a1, a2, a3, क्रमपरिवर्तन की पूरी सूची क्रमशः होगी:
ए 1, ए 2, ए 3
ए 2, ए 1, ए 3
ए 3, ए 1, ए 2

फिर ये सिग्नेचर टेबल छांटे जाते हैं।

कार्यान्वयन खोजें

इस स्तर पर, डेटाबेस को प्रीप्रोसेस करने के बाद, हमारे पास सॉर्ट किए गए तालिकाओं की कई प्रतियां हैं, प्रत्येक अपने स्वयं के विकल्प के लिए।

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

हम यह भी जानते हैं कि आवश्यक पदार्थ अधिकतम एक तत्व से भिन्न होते हैं। और उन्हें खोजने के लिए, आपको क्वेरी विस्तार विधि का उपयोग करने की आवश्यकता है।

दूसरे शब्दों में, इस सबस्ट्रिंग सहित सभी संयोजनों को उत्पन्न करने के लिए चयनित सबस्ट्रिंग की आवश्यकता होती है, जिसमें अंतर अधिकतम एक तत्व होगा। ऐसे संयोजनों की संख्या सबस्ट्रिंग + 1 की लंबाई के बराबर होगी।

और फिर एक पूर्ण मैच के लिए इसी हस्ताक्षर तालिका में एक द्विआधारी खोज करते हैं।

इस तरह के कार्यों को सभी सबस्ट्रिंग और सभी तालिकाओं के लिए किया जाना चाहिए।

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

ब्लूम फ़िल्टर

लेखकों ने बाइनरी फ़िल्टर की संख्या को कम करने के लिए ब्लूम फ़िल्टर [7] का उपयोग करने का प्रस्ताव किया है।
एक ब्लूम फ़िल्टर जल्दी से यह निर्धारित कर सकता है कि क्या एक विकल्प एक तालिका में गलत सकारात्मकता के एक छोटे प्रतिशत के साथ है। जो टेबल हैश की तुलना में तेज है।

यदि किसी तालिका में एक विकल्प के लिए एक द्विआधारी खोज से पहले, फ़िल्टर रिटर्न करता है कि यह प्रतिस्थापन इस तालिका में नहीं है, तो यह खोज करने के लिए कोई मतलब नहीं है।

तदनुसार, आपको प्रत्येक हस्ताक्षर तालिका के लिए एक फ़िल्टर बनाने की आवश्यकता है।

लेखकों ने यह भी ध्यान दिया कि ब्लूम फ़िल्टर का उपयोग इस तरह से क्वेरी प्रसंस्करण समय को 57.8% की औसत से कम करता है।

अब एक ही बात, केवल एक उदाहरण के साथ

बाइनरी स्ट्रिंग्स का एक डेटाबेस है 8 बिट लंबा:
11111111
10000001
00111110

कार्य सभी लाइनों को खोजना है जहां विभिन्न बिट्स की संख्या लक्ष्य रेखा 10111111 से 2 से अधिक नहीं है।
तो आवश्यक दूरी k = 2 है।

1. एक विभाजन कारक चुनें।
सूत्र के आधार पर, हम विभाजन कारक r = 2 को चुनते हैं, जिसका अर्थ है कि एक स्ट्रिंग से केवल दो सब्सट्रिंग्स होंगे।

2. हस्ताक्षर का एक सेट बनाएँ।
चूंकि सबस्ट्रिंग की संख्या 2 है, केवल 2 टेबल बनाने की आवश्यकता है:
टी 1 और टी 2

3. हम स्रोत के लिंक को बनाए रखते हुए संगत तालिकाओं में सहेजते हैं।

टी 1 टी 2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. तालिकाओं को क्रमबद्ध करें। प्रत्येक व्यक्तिगत रूप से।
टी 1
0011 => 00111110
1000 => 10000001
1111 => 11111111

टी 2
0001 => 10000001
1110 => 00111110
1111 => 11111111

यह प्रीप्रोसेसिंग पूरा हो गया है। और खोज के लिए आगे बढ़ें।

1. अनुरोधित स्ट्रिंग के हस्ताक्षर प्राप्त करें।
खोज स्ट्रिंग 10111110 को हस्ताक्षरों में तोड़ा गया है। यह क्रमशः 1011 और 1100 निकला, पहली तालिका के लिए पहला, और दूसरे के लिए दूसरा।

2. हम एक-एक करके सभी संयोजन उत्पन्न करते हैं।
विकल्पों की संख्या 5 होगी।

2.1 पहले प्रतिस्थापन के लिए 1011:
1011
0 011
१ १ ११
१० ० १
101 ०

2.2 दूसरे विकल्प के लिए 1100:
1100
0 100
१ ० ००
११ १ ०
११० १

3. बाइनरी सर्च।

3.1 पहले प्रतिस्थापन 1011 के सभी उत्पन्न वेरिएंट के लिए, हम एक पूर्ण मैच के लिए पहली तालिका में एक द्विआधारी खोज करते हैं।

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

दो सबस्ट्रिंग मिले।

3.2 अब, दूसरे विकल्प 1100 के सभी प्रकारों के लिए, हम दूसरी तालिका में एक द्विआधारी खोज करते हैं।

1100
0100
1000
1110 == 1110 => 00111110
1101

एक सबस्ट्रिंग मिला।

4. परिणामों को एक सूची में जोड़कर:
00111110
11111111

5. अनुपालन के लिए रेखीय रूप से जाँच करें और अनुपयुक्त परिस्थितियों को फ़िल्टर करें <= 2:

एचडी (10111110, 00111110) = 1
एचडी (10111110, 11111111) = 2

दोनों रेखाएं दो से अधिक तत्वों के अंतर की स्थिति को संतुष्ट करती हैं।

हालांकि इस स्तर पर एक रेखीय खोज की जा रही है, यह उम्मीद की जाती है कि उम्मीदवारों की सूची बिल्कुल भी बड़ी नहीं होगी।
शर्तों के तहत जब उम्मीदवारों की संख्या बड़ी होगी, तो यह HEngine के एक पुनरावर्ती संस्करण का उपयोग करने का प्रस्ताव है।

रेखांकन

चित्र 1 खोज एल्गोरिथ्म का एक उदाहरण दिखाता है।
64 की एक स्ट्रिंग लंबाई और 4 की दूरी सीमा के लिए, विभाजन कारक 3 है, क्रमशः प्रति पंक्ति केवल 3 सब्सट्रिंग्स।
जहां T1, T2 और T3 हस्ताक्षर तालिकाएँ हैं जिनमें केवल बी 1, बी 2, बी 3, 21, 21 और 22 बिट्स हैं।

अनुरोधित स्ट्रिंग को सब्सट्रिंग में विभाजित किया गया है। अगला, संबंधित सबस्ट्रिंग के लिए एक हस्ताक्षर रेंज उत्पन्न होती है। पहले और दूसरे हस्ताक्षर के लिए, संयोजनों की संख्या 22 होगी। और अंतिम हस्ताक्षर 23 विकल्प देता है। और अंत में, एक द्विआधारी खोज किया जाता है।


चित्र 1. हस्ताक्षर तालिका के लिए प्रश्नों के प्रसंस्करण का एक सरलीकृत संस्करण।

परिणाम

औसत मामले में इस तरह के एक एल्गोरिथ्म की जटिलता हे ( पी * (लॉग एन + 1)) है, जहां एन डेटाबेस में पंक्तियों की कुल संख्या है, लॉग एन + 1 एक द्विआधारी खोज है, और पी द्विआधारी खोजों की संख्या है: हमारे मामले में, यह माना जाता है तालिकाओं की संख्या प्रति तालिकाओं की संख्या से गुणा की गई: P = (64 / r + 1) * r

चरम मामलों में, जटिलता रैखिक से अधिक हो सकती है।

यह ध्यान दिया जाता है कि यह दृष्टिकोण 4.65 में कम मेमोरी का उपयोग करता है और [2] में वर्णित पिछले काम की तुलना में 16% तेज है। और यह एक ज्ञात सीमा में सभी लाइनों को खोजने के लिए ज्ञात सबसे तेज़ तरीका है।

कार्यान्वयन

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

tests$ ./matches 7 data/db/table.txt data/query/face2.txt Reading the dataset ........ done. 752420 db hashes and 343 query hashes. Building with 7 hamming distance bound ....... done. Building time: 12.964 seconds Searching HEngine matches ....... found 100 total matches. HEngine query time: 0.1 seconds Searching linear matches ....... found 100 total matches. Linear query time: 6.828 seconds 

परिणाम प्रसन्न थे, क्योंकि 752420 में डेटाबेस से 343 हैश की खोज में ~ 0.1 सेकंड लगते हैं, जो एक रैखिक खोज की तुलना में 60 गुना तेज है।

ऐसा लगता है कि कोई यहां रुक सकता है। लेकिन मैं वास्तव में इसे किसी वास्तविक परियोजना में उपयोग करने का प्रयास करना चाहता था।

वास्तविक उपयोग से पहले एक क्लिक करें

छवि हैश का एक डेटाबेस है, और PHP के लिए एक बैकएंड है।
कार्य किसी तरह HEngine और PHP की कार्यक्षमता को जोड़ना था।
FastCGI [10] का उपयोग करने का निर्णय लिया गया, पदों habrahabr.ru/post/154187 और habrahabr.ru/post/61532 ने इसमें मेरी बहुत मदद की।

PHP से, बस कॉल करें:

 $list = file_get_contents( 'http://fcgi.local/?' . $hashes ); 

क्या ~ 0.5 सेकंड परिणाम देता है। जब एक रैखिक खोज में 9 सेकंड लगते हैं, और MySQL के प्रश्नों के माध्यम से, कम से कम 20 सेकंड।

सभी के लिए धन्यवाद जिन्होंने महारत हासिल की।

संदर्भ

[१] एम। मिंस्की और एस। पैपर्ट। Perceptrons। MIT प्रेस, कैम्ब्रिज, MA, 1969।
[२] जीएस मंकू, ए। जैन, और एडी सरमा। वेब क्रॉलिंग के लिए निकटवर्ती लोगों का पता लगाना प्रोक में। 16Th WWW, मई 2007।
[३] एमएल मिलर, एमए रोड्रिगेज और आईजे कॉक्स। ऑडियो फिंगरप्रिंटिंग: उच्च-आयामी बाइनरी स्पेस में निकटतम पड़ोसी खोज। एमएमएसपी, 2002 में।
[४] एमएल मिलर, एमए रोड्रिगेज और आईजे कॉक्स। ऑडियो फिंगरप्रिंटिंग: उच्च आयामी बाइनरी स्पेस में निकटतम पड़ोसी खोज। वीएलएसआई सिग्नल प्रोसेसिंग, स्प्रिंगर, 41 (3) के जर्नल: 285–291, 2005।
[५] जे। लैंडर ande और एफ। ट्रुसेटेट। बाइनरी हैमिंग दूरी के साथ छवि पुनर्प्राप्ति। प्रोक में। 2 वीएएसएपीपी, 2007।
[६] एच। यांग और वाई। वांग। एक LBP- आधारित फेस रिकग्निशन मेथड विथ हैमिंग डिस्टेंस कंस्ट्रक्शन प्रोक में। चौथा आईसीआईजी, 2007।
[Bloom] बी। ब्लूम। स्वीकार्य त्रुटियों के साथ हैश कोडिंग में स्पेस / टाइम ट्रेड-ऑफ। एसीएम, 13 (7) के संचार: 422-426, 1970।
[[] एलेक्स एक्स। लियू, के शेन, एरिक टॉर्नेग। बड़े पैमाने पर हैमिंग दूरी क्वेरी प्रसंस्करण। ICDE सम्मेलन, पृष्ठ 553 - 564, 2011।
[९] github.com/valbok/HEngine C ++ में HEngine का मेरा कार्यान्वयन
[१०] github.com/valbok/HEngine/blob/master/bin/fastcgi.cpp FastCGI के माध्यम से हैश खोजने के लिए एक रैपर प्रोग्राम का एक उदाहरण।