👌🏾 👨🏽‍🔬 🕖 मिनहाश - समान सेट की पहचान करें 👴🏽 🐁 🌵

जोरदार स्वागत! पिछली बार मैंने यह निर्धारित करने के लिए एक संभाव्य एल्गोरिथ्म के बारे में लिखा था कि क्या कोई तत्व एक सेट से संबंधित है, इस बार यह समानता के संभाव्य मूल्यांकन के बारे में होगा। आपको दो सेट A और B की समानता के निम्न संकेतक के बारे में सोचने के लिए एक महान दिमाग की आवश्यकता नहीं है:

जैक्वार्ड गुणांक

यही है, संघ में तत्वों की संख्या से विभाजित चौराहे में तत्वों की संख्या। इस अनुमान को जैककार्ड गुणांक कहा जाता है (इसलिए, "J"), गुणांक शून्य है जब सेट में सामान्य तत्व नहीं होते हैं, और एक जब सेट बराबर होते हैं, अन्यथा मूल्य कहीं न कहीं बीच में होता है।

इसे कैसे गिना जाए?

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

आमतौर पर, पिछले दो ऑपरेशनों को प्रभावी ढंग से करने के लिए, सेट को हैश टेबल के रूप में कुंजी से जुड़े मूल्यों के बिना प्रस्तुत किया जाता है, ऐसी संरचना बहुत जल्दी काम करती है। तालिका का निर्माण O (n) है, उन्हें दो की आवश्यकता है, चौराहे की गणना O (n) है और संघ की गणना भी O (n) है, जहां n पाठ में शब्दों की संख्या है। सब कुछ ठीक लग रहा है, लेकिन चलो कार्य को जटिल करते हैं।

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

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

कुंजी मिनहाश विचार

मान लीजिए हमारे पास: दो सेट ए, बी और एक हैश फ़ंक्शन एच है जो इन सेटों के तत्वों के लिए हैश की गणना कर सकता है। अगला, हम फ़ंक्शन एच _मिन (एस) को परिभाषित करते हैं, जो सेट एस के सभी सदस्यों के लिए फ़ंक्शन एच की गणना करता है और इसका सबसे छोटा मान लौटाता है। अब, विभिन्न सेटों के लिए एच _मिनट (ए) और एच _मिनट (बी) की गणना शुरू करते हैं, सवाल यह है: एच (ए) = एच _मिनट (बी) की संभावना क्या है?

यदि आप इसके बारे में सोचते हैं, तो यह संभावना सेट के प्रतिच्छेदन के आकार के समानुपाती होनी चाहिए - सामान्य शब्दों के अभाव में, यह शून्य हो जाता है, और एकता के लिए, जब सेट समान होते हैं, मध्यवर्ती मामलों में यह कहीं बीच में होता है। क्या कुछ भी समान नहीं है? हाँ, यह सही है, यह J (A, B) है - जैक्वार्ड गुणांक!

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

कार्यों की संख्या

जहां ε वांछित सबसे बड़ी त्रुटि है। तो, जम्मू (ए, बी) की गणना करने के लिए 0.1 से अधिक की त्रुटि के साथ, 100 हैश फ़ंक्शन की आवश्यकता है - कुछ नहीं। प्लसस क्या हैं?

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

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

खिलौना कार्यान्वयन

हमेशा की तरह, हमें हैश फ़ंक्शन के परिवार की आवश्यकता है:

function Hash(size) { var seed = Math.floor(Math.random() * size) + 32; return function (string) { var result = 1; for (var i = 0; i < string.length; ++i) result = (seed * result + string.charCodeAt(i)) & 0xFFFFFFFF; return result; }; }

मिनहाश ही:

 function MinHash(max_error) { var function_count = Math.round(1 / (max_error * max_error)); var functions = []; for (var i = 0; i < function_count; ++i) functions[i] = Hash(function_count); function find_min(set, function_) { var min = 0xFFFFFFFF; for (var i = 0; i < set.length; ++i) { var hash = function_(set[i]); if (hash < min) min = hash; } return min; } function signature(set) { var result = []; for (var i = 0; i < function_count; ++i) result[i] = find_min(set, functions[i]); return result; } function similarity(sig_a, sig_b) { var equal_count = 0; for (var i = 0; i < function_count; ++i) if (sig_a[i] == sig_b[i]) ++equal_count; return equal_count / function_count; } return {signature: signature, similarity: similarity}; }

उपयोग उदाहरण:

 var set_a = ['apple', 'orange']; var set_b = ['apple', 'peach']; var min_hash = MinHash(0.05); var sig_a = min_hash.signature(set_a); var sig_b = min_hash.signature(set_b); alert(min_hash.similarity(sig_a, sig_b));

सूक्ष्म क्षण

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

किसी कारण से, यह कहीं भी उल्लेख नहीं किया गया है कि फ़ंक्शन द्वारा उत्पादित बिट्स की संख्या कितनी होनी चाहिए। सिद्धांत रूप में, यह मात्रा इनपुट मूल्यों के सभी संभावित वेरिएंट का प्रतिनिधित्व करने के लिए ऐसी होनी चाहिए। उदाहरण के लिए, अंग्रेजी भाषा में लगभग 250 000 शब्द हैं, इसलिए, लगभग 18 बिट्स पर्याप्त हैं। लेकिन यह बेहतर है, फिर से, इसे सुरक्षित खेलने और अतिरिक्त बिट्स के एक जोड़े को जोड़ने के लिए।

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

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

चित्र या केवल मुझे लोड करते समय PS HabraStorage एक त्रुटि देता है?

मिनहाश - समान सेट की पहचान करें

इसे कैसे गिना जाए?

कुंजी मिनहाश विचार

खिलौना कार्यान्वयन

सूक्ष्म क्षण

More articles: