K-इंडिपेंडेंट हैशिंग: Difference between revisions
No edit summary |
No edit summary |
||
| (10 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Family of Hash functions}} | {{Short description|Family of Hash functions}} | ||
{{DISPLAYTITLE:''k''-independent hashing}} | {{DISPLAYTITLE:''k''-independent hashing}} | ||
[[कंप्यूटर विज्ञान]] में, [[हैश फ़ंक्शन]] के समूह को '''''k''-इंडिपेंडेंट, ''k''-वाइज इंडिपेंडेंट या ''k''-यूनिवर्सल''' कहा जाता है।<ref name=CLRS>{{Introduction to Algorithms|edition=3}}</ref> यदि समूह से | [[कंप्यूटर विज्ञान]] में, [[हैश फ़ंक्शन]] के समूह को '''''k''-इंडिपेंडेंट, ''k''-वाइज इंडिपेंडेंट या ''k''-यूनिवर्सल''' कहा जाता है।<ref name=CLRS>{{Introduction to Algorithms|edition=3}}</ref> यदि समूह से रैंडम रूप से किसी फ़ंक्शन का चयन करना निश्चितता प्रदान करता है कि किसी भी डेसिग्नेटेड k कुंजी के हैश कोड [[स्वतंत्रता (संभावना सिद्धांत)|इंडिपेंडेंट रैंडम वेरिएबल]] हैं (नीचे सही गणितीय परिभाषाये देखना हैं)। ऐसे समूह रैंडम एल्गोरिदम या डेटा संरचनाओं में अच्छे औसत स्थीतीओ के प्रदर्शन की अनुमति देते हैं, यद्यपि ही इनपुट डेटा किसी एडवेर्सरी द्वारा चुना गया हो। इंडिपेंडेंस की डिग्री और हैश फ़ंक्शन के मूल्यांकन की दक्षता के बीच ट्रेड-ऑफ का अच्छी तरह से अध्ययन किया गया है, और कई ''k''-इंडिपेंडेंट समूहों का प्रस्ताव किया गया है। | ||
== पृष्ठभूमि == | == पृष्ठभूमि == | ||
{{see also| | {{see also|हैश फंक्शन }} | ||
हैशिंग का लक्ष्य | हैशिंग का लक्ष्य साधारण तौर पर कुछ बड़े डोमेन (यूनिवर्स) <math>U</math> से छोटी रेंज में जैसे <math>m</math> बिन्स (लेबल्ड <math>[m] = \{0, \dots, m-1\}</math> कुंजियों को मैप करना होता है। रैंडम एल्गोरिदम और डेटा संरचनाओं के विश्लेषण में, विभिन्न कुंजियों के हैश कोड का यादृच्छिक रूप से व्यवहार करना प्रायः वांछनीय होता है। उदाहरण के लिए, यदि प्रत्येक कुंजी का हैश कोड इंडिपेंडेंस रैंडम विकल्प <math>[m]</math> था, [[चेर्नॉफ़ बाध्य|चेर्नॉफ़ बाउंड]] का उपयोग करके प्रति बिन कुंजियों की संख्या का विश्लेषण किया जा सकता है। नियतात्मक हैश फ़ंक्शन किसी एडवेर्सिअल सेटिंग में ऐसी कोई निश्चितता नहीं दे सकता है, क्योंकि प्रतिद्वंद्वी बिन की सही [[छवि (गणित)|प्रीइमेज]] के लिए कुंजियाँ चुन सकता है। इसके अतिरिक्त, नियतात्मक हैश फ़ंक्शन रीहैशिंग की अनुमति नहीं देता है: कभी-कभी इनपुट डेटा हैश फ़ंक्शन के लिए खराब हो जाता है (उदाहरण के लिए बहुत अधिक टकराव होते हैं), इसलिए कोई हैश फ़ंक्शन को परिवर्तित करना नहीं चाहता हैं। | ||
इन समस्याओं का समाधान हैश फ़ंक्शंस के | इन समस्याओं का समाधान हैश फ़ंक्शंस के बड़े समूह से रैंडम रूप से फ़ंक्शन चुनना है। हैश फ़ंक्शन को चुनने में रैंडम का उपयोग रुचि की किसी भी कुंजी के हैश कोड के कुछ डिजायर्ड रैंडम बिहैवियर की निश्चितता के लिए किया जा सकता है। इन पंक्तियों के साथ पहली परिभाषा [[सार्वभौमिक हैशिंग|यूनिवर्सल हैशिंग]] थी, जो किन्हीं दो निर्दिष्ट कुंजियों के लिए कम टकराव की संभावना की निश्चितता देती है। इसकी अवधारणा <math>k</math>-इंडिपेंडेंट हैशिंग, 1981 में वेगमैन और कार्टर द्वारा प्रारम्भ की गई,<ref name=WC81> | ||
{{cite journal | {{cite journal | ||
| last1 = Wegman | | last1 = Wegman | ||
| Line 25: | Line 25: | ||
| accessdate = 9 February 2011 | | accessdate = 9 February 2011 | ||
| doi-access = free | | doi-access = free | ||
}}</ref> | }}</ref> k- समूहों के लिए रैंडम बिहैवियर की निश्चितता को मजबूत करता है <math>k</math> निर्दिष्ट कुंजियाँ, और हैश कोड के समान वितरण पर निश्चितता जोड़ता है। | ||
== परिभाषाएँ == | == परिभाषाएँ == | ||
सबसे | सबसे दृढ परिभाषा, वेगमैन और कार्टर द्वारा प्रस्तुत की गई<ref name=WC81 />दृढ़ता से 'यूनिवर्सल<math>_k</math><nowiki>' के अनुसार हैश समूह''</nowiki>, निम्नलिखित है। हैश फ़ंक्शंस का समूह <math>H=\{ h:U \to [m] \}</math> है <math>k</math>-इंडिपेंडेंट यदि किसी के लिए <math>k</math> विशिष्ट कुंजियाँ <math>(x_1, \dots, x_k) \in U^k</math> और कोई भी <math>k</math> हैश कोड (आवश्यक नहीं कि अलग हो) <math>(y_1, \dots, y_k) \in [m]^k</math> होता हैं, हमारे पास: | ||
: <math>\Pr_{h \in H} \left[ h(x_1)=y_1 \land \cdots \land h(x_k)=y_k \right] = m^{-k}</math> | : <math>\Pr_{h \in H} \left[ h(x_1)=y_1 \land \cdots \land h(x_k)=y_k \right] = m^{-k}</math> | ||
यह परिभाषा निम्नलिखित दो स्थितियों के बराबर है: | यह परिभाषा निम्नलिखित दो स्थितियों के बराबर है: | ||
#किसी भी निश्चित के लिए <math>x\in U</math>, जैसा <math>h</math> से | #किसी भी निश्चित के लिए <math>x\in U</math>, जैसा <math>h</math> से रैंडम रूप से <math>H</math>, <math>h(x)</math> से निर्वासित किया जाता है जो समान रूप से <math>[m]</math> से वितरित किया जाता है। | ||
# किसी भी निश्चित, विशिष्ट कुंजी | # किसी भी निश्चित, विशिष्ट कुंजी <math>x_1, \dots, x_k \in U</math> के लिए, जैसा <math>h</math> से रैंडम रूप से <math>H</math>, <math>h(x_1), \dots, h(x_k)</math> निर्वासित किया जाता है इंडिपेंडेंट रैंडम वेरिएबल्स हैं। | ||
प्रायः राउंडिंग इश्यूज के कारण सही संयुक्त संभावना <math>m^{-k}</math> प्राप्त करना असुविधाजनक होता है। निम्न,<ref name=Siegel> | |||
{{cite journal | {{cite journal | ||
| last1 = Siegel | | last1 = Siegel | ||
| Line 47: | Line 47: | ||
| url = http://www.cs.nyu.edu/faculty/siegel/FASTH.pdf | | url = http://www.cs.nyu.edu/faculty/siegel/FASTH.pdf | ||
| doi=10.1137/S0097539701386216}} | | doi=10.1137/S0097539701386216}} | ||
</ref> कोई | </ref> कोई <math>(\mu, k)</math> से इंडिपेंडेंट समुह को संतुष्ट करने के लिए परिभाषित कर सकता है: | ||
: <math>\forall</math> अलग <math>(x_1, \dots, x_k) \in U^k</math> और <math>\forall (y_1, \dots, y_k) \in [m]^k</math>, <math>~~\Pr_{h \in H} \left[ h(x_1)=y_1 \land \cdots \land h(x_k)=y_k \right] \le \mu / m^k</math> | : <math>\forall</math> अलग <math>(x_1, \dots, x_k) \in U^k</math> और <math>\forall (y_1, \dots, y_k) \in [m]^k</math>, <math>~~\Pr_{h \in H} \left[ h(x_1)=y_1 \land \cdots \land h(x_k)=y_k \right] \le \mu / m^k</math> | ||
उस पर | उस पर ध्यान दे, यद्यपि ही <math>\mu</math> 1 के निकट है, <math>h(x_i)</math> अब इंडिपेंडेंट रैंडम वेरिएबल्स नहीं हैं, जो प्रायः रैंडम एल्गोरिदम के विश्लेषण में समस्या है। इसलिए, राउंडिंग इश्यूज से निवारण का अधिक सामान्य विकल्प यह सिद्ध करना है कि हैश समूह [[सांख्यिकीय दूरी]] <math>k</math>-इंडिपेंडेंट समूह के निकट है, जो इंडिपेंडेंस गुणों के ब्लैक-बॉक्स उपयोग की अनुमति देता है। | ||
==तकनीक== | ==तकनीक== | ||
=== | ===रैंडम गुणांक वाले बहुपद=== | ||
निर्माण की मूल तकनीक {{mvar|k}}-कार्टर और वेगमैन द्वारा दिए गए | निर्माण की मूल तकनीक {{mvar|k}}-कार्टर और वेगमैन द्वारा दिए गए इंडिपेंडेंट हैश फ़ंक्शन, बड़ी अभाज्य संख्या {{mvar|p}} का चयन करना था, {{mvar|k}} रैंडम संख्या मॉड्यूलो {{mvar|p}} को चुनना होता हैं, और इन संख्याओं को डिग्री के [[बहुपद]] के गुणांक {{math|''k'' − 1}} के रूप में उपयोग करें जिनके मान मॉड्यूलो {{mvar|p}} हैं उसका उपयोग हैश फ़ंक्शन के मान के रूप में किया जाता है। दी गई डिग्री मापांक के सभी बहुपद {{mvar|p}} समान रूप से संभावित हैं, और कोई भी बहुपद किसी के द्वारा विशिष्ट रूप से निर्धारित होता है {{mvar|k}}-ट्यूपल आर्गुमेंट के साथ आर्गुमेंट-मूल्य जोड़े का समूह, जिससे यह किसी {{mvar|k}}-ट्यूपल आर्गुमेंट के समूह को किसी में भी मैप किए जाने की समान रूप से संभावना {{mvar|k}}-हैश मानों का टुपल का अनुसरण करता है।<ref name=WC81/> | ||
सामान्य तौर पर बहुपद किसी भी [[परिमित क्षेत्र]] में [[बहुपद मूल्यांकन]] हो सकता है। | सामान्य तौर पर बहुपद किसी भी [[परिमित क्षेत्र]] में [[बहुपद मूल्यांकन]] हो सकता है। | ||
मॉड्यूलो प्राइम फ़ील्ड के | मॉड्यूलो प्राइम फ़ील्ड के अतिरिक्त, प्रसिद्ध विकल्प आकार <math>2^n</math> का फ़ील्ड है, जो आधुनिक कंप्यूटरों पर तेज़ [[परिमित क्षेत्र अंकगणित|परिमित क्षेत्र अरिथमेटिक]] का समर्थन करता है। | ||
यह | यह सीएल हैश के लिए [[डेनियल लेमायर]] और [[ओवेन कैसर]] द्वारा अपनाया गया कार्य था।<ref>Lemire, Daniel, and Owen Kaser. "Faster 64-bit universal hashing using carry-less multiplications." Journal of Cryptographic Engineering 6.3 (2016): 171-185.</ref> | ||
=== | ===टैब्युलेशन हैशिंग=== | ||
{{main| | {{main|टैब्युलेशन हैशिंग }} | ||
[[सारणीकरण हैशिंग]] प्रत्येक कुंजी को [[बाइट]] | [[सारणीकरण हैशिंग]] प्रत्येक कुंजी को [[बाइट]] में विभाजित करके, प्रत्येक बाइट को सूचकांक के रूप में रैंडम संख्याओं की तालिका में (प्रत्येक बाइट स्थिति के लिए एक अलग तालिका के साथ) उपयोग करके, और इन तालिका लुकअप एक बिटवाइज़ एक्सक्लूसिव ऑपरेशन के परिणामों को जोड़कर हैश मानों की मैपिंग की तकनीक है। इस प्रकार, इसके आरंभीकरण में बहुपद विधि की तुलना में अधिक रैंडम की आवश्यकता होती है, लेकिन संभावित रूप से धीमी गुणन संक्रियाओं से बचा जाता है। यह 3-इंडिपेंडेंस है लेकिन 4-इंडिपेंडेंस नहीं है।<ref>{{citation | ||
| last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist) | | last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist) | ||
| last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup | | last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup | ||
| Line 75: | Line 75: | ||
| title = The power of simple tabulation hashing | | title = The power of simple tabulation hashing | ||
| volume = 59 | | volume = 59 | ||
| year = 2012}}</ref> | | year = 2012}}</ref> टैब्युलेशन हैशिंग की विविधताएं इनपुट कुंजी से बिट्स के ओवरलैपिंग संयोजनों के आधार पर तालिका लुकअप निष्पादित करके, या सरल सारणीबद्ध हैशिंग को पुनरावृत्त रूप से क्रियान्वित करके स्वतंत्रता की उच्च डिग्री प्राप्त कर सकती हैं।<ref>{{citation | ||
| last = Siegel | first = Alan | | last = Siegel | first = Alan | ||
| doi = 10.1137/S0097539701386216 | | doi = 10.1137/S0097539701386216 | ||
| Line 92: | Line 92: | ||
| title = Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) | | title = Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) | ||
| year = 2013| arxiv = 1311.3121| title-link = Symposium on Foundations of Computer Science | isbn = 978-0-7695-5135-7 }}</ref> | | year = 2013| arxiv = 1311.3121| title-link = Symposium on Foundations of Computer Science | isbn = 978-0-7695-5135-7 }}</ref> | ||
==विभिन्न प्रकार के टकराव समाधान के लिए इंडिपेंडेंस की आवश्यकता== | |||
प्रति ऑपरेशन निरंतर अपेक्षित समय की निश्चितता के लिए आवश्यक इंडिपेंडेंस के स्तर के अनुसार, k-इंडिपेंडेंस की धारणा का उपयोग हैशटेबल्स में विभिन्न के बीच अंतर करने के लिए किया जा सकता है। | |||
उदाहरण के लिए, हैश चेनिंग हैश फ़ंक्शंस के '''<nowiki/>'2-इंडिपेंडेंट'''' समूहों के साथ भी निरंतर अपेक्षित समय लेती है, क्योंकि किसी दी गई कुंजी की खोज करने का अपेक्षित समय उन टकरावों की अपेक्षित संख्या से सीमित होता है जिनमें कुंजी सम्मलित होती है। अपेक्षा की रैखिकता, यह अपेक्षित संख्या हैश तालिका में अन्य सभी कुंजियों के योग के बराबर होती है, इस संभावना की दी गई कुंजी और दूसरी कुंजी टकराती है। क्योंकि इस योग की टर्म्स में केवल दो कुंजियों से जुड़ी संभाव्य घटनाएं सम्मलित हैं, 2-इंडिपेंडेंट यह सुनिश्चित करने के लिए पर्याप्त है कि इस योग का वही मूल्य है जो वास्तव में रैंडम हैश फ़ंक्शन के लिए होता हैं।<ref name=WC81/> | |||
[[डबल हैशिंग]], हैशिंग की एक और विधि है जिसके लिए कम स्तर की स्वतंत्रता की आवश्यकता होती है। यह ओपन एड्रेसिंग का एक रूप है जो दो हैश फ़ंक्शन का उपयोग करता है: एक प्रोब सीक्वेंस की प्रारम्भ निर्धारित करने के लिए, और दूसरा प्रोब सीक्वेंस में स्थितियों के बीच चरण आकार निर्धारित करने के लिए होता हैं। जब तक ये दोनों 2-इंडिपेंडेंट हैं, यह विधि प्रति ऑपरेशन निरंतर अपेक्षित समय देती है।<ref>{{citation | |||
[[डबल हैशिंग]], हैशिंग | |||
| last1 = Bradford | | last1 = Bradford | ||
| first1 = Phillip G. | | first1 = Phillip G. | ||
| Line 118: | Line 116: | ||
| url-status = dead | | url-status = dead | ||
}}</ref> | }}</ref> | ||
दूसरी ओर, [[ रैखिक जांच ]], ओपन एड्रेसिंग का | |||
दूसरी ओर,[[ रैखिक जांच | रैखिक जांच]], ओपन एड्रेसिंग का सरल रूप जहां चरण का आकार हमेशा एक होता है, 5-इंडिपेंडेंट हैश फ़ंक्शन के साथ प्रति ऑपरेशन निरंतर अपेक्षित समय में काम करने की निश्चितता दी जा सकती है,<ref>{{citation | |||
| last1 = Pagh | first1 = Anna | | last1 = Pagh | first1 = Anna | ||
| last2 = Pagh | first2 = Rasmus | author2-link = Rasmus Pagh | | last2 = Pagh | first2 = Rasmus | author2-link = Rasmus Pagh | ||
| Line 129: | Line 128: | ||
| title = Linear probing with constant independence | | title = Linear probing with constant independence | ||
| volume = 39 | | volume = 39 | ||
| year = 2009| arxiv = cs/0612055}}</ref> और 4- | | year = 2009| arxiv = cs/0612055}}</ref> और 4-इंडिपेंडेंट हैश फ़ंक्शंस उपस्थित हैं जिनके लिए प्रति ऑपरेशन लॉगरिदमिक समय लगता है।<ref>{{citation | ||
| last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist) | | last1 = Pătraşcu | first1 = Mihai | author1-link = Mihai Pătrașcu (computer scientist) | ||
| last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup | | last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup | ||
| Line 141: | Line 140: | ||
| volume = 6198 | | volume = 6198 | ||
| year = 2010| arxiv = 1302.5127| title-link = International Colloquium on Automata, Languages and Programming | isbn = 978-3-642-14164-5 }}</ref> | | year = 2010| arxiv = 1302.5127| title-link = International Colloquium on Automata, Languages and Programming | isbn = 978-3-642-14164-5 }}</ref> | ||
[[कोयल हैशिंग]] के लिए आवश्यक k- | |||
2009 में इसे दिखाया गया था<ref>Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).</ref> वह <math>O(\log n)</math>- | [[कोयल हैशिंग|कुक्कू हैशिंग]] के लिए आवश्यक k-इंडिपेंडेंस 2021 तक ज्ञात नहीं है। | ||
एक अन्य दृष्टिकोण टेब्यूलेशन हैशिंग का उपयोग करना है, जो 6- | 2009 में इसे दिखाया गया था<ref>Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).</ref> वह <math>O(\log n)</math>-इंडिपेंडेंस पर्याप्त है, और '''कम से कम 6-इंडिपेंडेंस''' की आवश्यकता है। | ||
2014 से तीसरा | एक अन्य दृष्टिकोण टेब्यूलेशन हैशिंग का उपयोग करना है, जो 6-इंडिपेंडेंट नहीं है, लेकिन 2012 में दिखाया गया था।<ref>Pǎtraşcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.</ref> कुक्कू हैशिंग के लिए पर्याप्त अन्य गुण होता हैं। | ||
2014 से तीसरा प्रयास<ref>Aumüller, Martin, Martin Dietzfelbinger, and Philipp Woelfel. "Explicit and efficient hash families suffice for cuckoo hashing with a stash." Algorithmica 70.3 (2014): 428-456.</ref> कुक्कू हैशटेबल को तथाकथित स्टैश के साथ थोड़ा संशोधित करना है, जो 2-इंडिपेंडेंट हैश फ़ंक्शंस से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है। | |||
== अन्य अनुप्रयोग == | == अन्य अनुप्रयोग == | ||
केन (गणितज्ञ), [[ स्पष्टीकरण नेल्सन |नेल्सन]] और डेविड वुड्रफ ने 2010 में विशिष्ट एलिमेंट्स समस्या के लिए फ्लैजोलेट-मार्टिन एल्गोरिदम में सुधार किया था।<ref>Kane, Daniel M., Jelani Nelson, and David P. Woodruff. "An optimal algorithm for the distinct elements problem." Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 2010.</ref> | |||
एक | एक <math>\varepsilon</math> सही उत्तर के अप्प्रोक्सिमशन के लिए, उन्हें एक <math>\tfrac{\log1/\varepsilon}{\log\log1/\varepsilon}</math> '''इंडिपेंडेंट''' हैश फ़ंक्शन देने की आवश्यकता है। | ||
[[आयामीता में कमी]] के लिए [[ गिनती रेखाचित्र ]] एल्गोरिदम को दो हैश फ़ंक्शन | [[आयामीता में कमी|डाइमेंसनलिटी में कमी]] के लिए [[ गिनती रेखाचित्र |काउंट स्केच]] एल्गोरिदम को दो हैश फ़ंक्शन '''2-इंडिपेंडेंट''' और '''4-इंडिपेंडेंट''' की आवश्यकता होती है। | ||
[[MAX-3SAT]] समस्या के लिए कार्लॉफ़-ज़्विक एल्गोरिदम को 3- | [[MAX-3SAT|एम्एएक्स-3एसएटी]] समस्या के लिए कार्लॉफ़-ज़्विक एल्गोरिदम को '''3-इंडिपेंडेंट''' रैंडम वेरिएबल्स के साथ कार्यान्वित किया जा सकता है। | ||
[[मिनहैश]] एल्गोरिदम का | [[मिनहैश]] एल्गोरिदम का <math>\log\tfrac{1}{\epsilon}</math>-'''इंडिपेंडेंट हैश फंक्शन्स''' उपयोग करके कार्यान्वित किया जा सकता है जैसा कि 1999 में [[पीटर इंडीक]] द्वारा सिद्ध किया गया था।<ref>Indyk, Piotr. "A small approximately min-wise independent family of hash functions." Journal of Algorithms 38.1 (2001): 84-90.</ref> | ||
| Line 176: | Line 176: | ||
| page = [https://archive.org/details/randomizedalgori00motw_066/page/n229 221] | | page = [https://archive.org/details/randomizedalgori00motw_066/page/n229 221] | ||
}} | }} | ||
[[Category: | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
[[Category:CS1 errors]] | |||
[[Category:Created On 10/07/2023]] | [[Category:Created On 10/07/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with ignored display titles]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:एल्गोरिदम खोजें]] | |||
[[Category:त्रुटि का पता लगाना और सुधार करना]] | |||
[[Category:हैश फ़ंक्शन]] | |||
Latest revision as of 12:26, 28 July 2023
कंप्यूटर विज्ञान में, हैश फ़ंक्शन के समूह को k-इंडिपेंडेंट, k-वाइज इंडिपेंडेंट या k-यूनिवर्सल कहा जाता है।[1] यदि समूह से रैंडम रूप से किसी फ़ंक्शन का चयन करना निश्चितता प्रदान करता है कि किसी भी डेसिग्नेटेड k कुंजी के हैश कोड इंडिपेंडेंट रैंडम वेरिएबल हैं (नीचे सही गणितीय परिभाषाये देखना हैं)। ऐसे समूह रैंडम एल्गोरिदम या डेटा संरचनाओं में अच्छे औसत स्थीतीओ के प्रदर्शन की अनुमति देते हैं, यद्यपि ही इनपुट डेटा किसी एडवेर्सरी द्वारा चुना गया हो। इंडिपेंडेंस की डिग्री और हैश फ़ंक्शन के मूल्यांकन की दक्षता के बीच ट्रेड-ऑफ का अच्छी तरह से अध्ययन किया गया है, और कई k-इंडिपेंडेंट समूहों का प्रस्ताव किया गया है।
पृष्ठभूमि
हैशिंग का लक्ष्य साधारण तौर पर कुछ बड़े डोमेन (यूनिवर्स) से छोटी रेंज में जैसे बिन्स (लेबल्ड कुंजियों को मैप करना होता है। रैंडम एल्गोरिदम और डेटा संरचनाओं के विश्लेषण में, विभिन्न कुंजियों के हैश कोड का यादृच्छिक रूप से व्यवहार करना प्रायः वांछनीय होता है। उदाहरण के लिए, यदि प्रत्येक कुंजी का हैश कोड इंडिपेंडेंस रैंडम विकल्प था, चेर्नॉफ़ बाउंड का उपयोग करके प्रति बिन कुंजियों की संख्या का विश्लेषण किया जा सकता है। नियतात्मक हैश फ़ंक्शन किसी एडवेर्सिअल सेटिंग में ऐसी कोई निश्चितता नहीं दे सकता है, क्योंकि प्रतिद्वंद्वी बिन की सही प्रीइमेज के लिए कुंजियाँ चुन सकता है। इसके अतिरिक्त, नियतात्मक हैश फ़ंक्शन रीहैशिंग की अनुमति नहीं देता है: कभी-कभी इनपुट डेटा हैश फ़ंक्शन के लिए खराब हो जाता है (उदाहरण के लिए बहुत अधिक टकराव होते हैं), इसलिए कोई हैश फ़ंक्शन को परिवर्तित करना नहीं चाहता हैं।
इन समस्याओं का समाधान हैश फ़ंक्शंस के बड़े समूह से रैंडम रूप से फ़ंक्शन चुनना है। हैश फ़ंक्शन को चुनने में रैंडम का उपयोग रुचि की किसी भी कुंजी के हैश कोड के कुछ डिजायर्ड रैंडम बिहैवियर की निश्चितता के लिए किया जा सकता है। इन पंक्तियों के साथ पहली परिभाषा यूनिवर्सल हैशिंग थी, जो किन्हीं दो निर्दिष्ट कुंजियों के लिए कम टकराव की संभावना की निश्चितता देती है। इसकी अवधारणा -इंडिपेंडेंट हैशिंग, 1981 में वेगमैन और कार्टर द्वारा प्रारम्भ की गई,[2] k- समूहों के लिए रैंडम बिहैवियर की निश्चितता को मजबूत करता है निर्दिष्ट कुंजियाँ, और हैश कोड के समान वितरण पर निश्चितता जोड़ता है।
परिभाषाएँ
सबसे दृढ परिभाषा, वेगमैन और कार्टर द्वारा प्रस्तुत की गई[2]दृढ़ता से 'यूनिवर्सल' के अनुसार हैश समूह'', निम्नलिखित है। हैश फ़ंक्शंस का समूह है -इंडिपेंडेंट यदि किसी के लिए विशिष्ट कुंजियाँ और कोई भी हैश कोड (आवश्यक नहीं कि अलग हो) होता हैं, हमारे पास:
यह परिभाषा निम्नलिखित दो स्थितियों के बराबर है:
- किसी भी निश्चित के लिए , जैसा से रैंडम रूप से , से निर्वासित किया जाता है जो समान रूप से से वितरित किया जाता है।
- किसी भी निश्चित, विशिष्ट कुंजी के लिए, जैसा से रैंडम रूप से , निर्वासित किया जाता है इंडिपेंडेंट रैंडम वेरिएबल्स हैं।
प्रायः राउंडिंग इश्यूज के कारण सही संयुक्त संभावना प्राप्त करना असुविधाजनक होता है। निम्न,[3] कोई से इंडिपेंडेंट समुह को संतुष्ट करने के लिए परिभाषित कर सकता है:
- अलग और ,
उस पर ध्यान दे, यद्यपि ही 1 के निकट है, अब इंडिपेंडेंट रैंडम वेरिएबल्स नहीं हैं, जो प्रायः रैंडम एल्गोरिदम के विश्लेषण में समस्या है। इसलिए, राउंडिंग इश्यूज से निवारण का अधिक सामान्य विकल्प यह सिद्ध करना है कि हैश समूह सांख्यिकीय दूरी -इंडिपेंडेंट समूह के निकट है, जो इंडिपेंडेंस गुणों के ब्लैक-बॉक्स उपयोग की अनुमति देता है।
तकनीक
रैंडम गुणांक वाले बहुपद
निर्माण की मूल तकनीक k-कार्टर और वेगमैन द्वारा दिए गए इंडिपेंडेंट हैश फ़ंक्शन, बड़ी अभाज्य संख्या p का चयन करना था, k रैंडम संख्या मॉड्यूलो p को चुनना होता हैं, और इन संख्याओं को डिग्री के बहुपद के गुणांक k − 1 के रूप में उपयोग करें जिनके मान मॉड्यूलो p हैं उसका उपयोग हैश फ़ंक्शन के मान के रूप में किया जाता है। दी गई डिग्री मापांक के सभी बहुपद p समान रूप से संभावित हैं, और कोई भी बहुपद किसी के द्वारा विशिष्ट रूप से निर्धारित होता है k-ट्यूपल आर्गुमेंट के साथ आर्गुमेंट-मूल्य जोड़े का समूह, जिससे यह किसी k-ट्यूपल आर्गुमेंट के समूह को किसी में भी मैप किए जाने की समान रूप से संभावना k-हैश मानों का टुपल का अनुसरण करता है।[2]
सामान्य तौर पर बहुपद किसी भी परिमित क्षेत्र में बहुपद मूल्यांकन हो सकता है। मॉड्यूलो प्राइम फ़ील्ड के अतिरिक्त, प्रसिद्ध विकल्प आकार का फ़ील्ड है, जो आधुनिक कंप्यूटरों पर तेज़ परिमित क्षेत्र अरिथमेटिक का समर्थन करता है। यह सीएल हैश के लिए डेनियल लेमायर और ओवेन कैसर द्वारा अपनाया गया कार्य था।[4]
टैब्युलेशन हैशिंग
सारणीकरण हैशिंग प्रत्येक कुंजी को बाइट में विभाजित करके, प्रत्येक बाइट को सूचकांक के रूप में रैंडम संख्याओं की तालिका में (प्रत्येक बाइट स्थिति के लिए एक अलग तालिका के साथ) उपयोग करके, और इन तालिका लुकअप एक बिटवाइज़ एक्सक्लूसिव ऑपरेशन के परिणामों को जोड़कर हैश मानों की मैपिंग की तकनीक है। इस प्रकार, इसके आरंभीकरण में बहुपद विधि की तुलना में अधिक रैंडम की आवश्यकता होती है, लेकिन संभावित रूप से धीमी गुणन संक्रियाओं से बचा जाता है। यह 3-इंडिपेंडेंस है लेकिन 4-इंडिपेंडेंस नहीं है।[5] टैब्युलेशन हैशिंग की विविधताएं इनपुट कुंजी से बिट्स के ओवरलैपिंग संयोजनों के आधार पर तालिका लुकअप निष्पादित करके, या सरल सारणीबद्ध हैशिंग को पुनरावृत्त रूप से क्रियान्वित करके स्वतंत्रता की उच्च डिग्री प्राप्त कर सकती हैं।[6][7]
विभिन्न प्रकार के टकराव समाधान के लिए इंडिपेंडेंस की आवश्यकता
प्रति ऑपरेशन निरंतर अपेक्षित समय की निश्चितता के लिए आवश्यक इंडिपेंडेंस के स्तर के अनुसार, k-इंडिपेंडेंस की धारणा का उपयोग हैशटेबल्स में विभिन्न के बीच अंतर करने के लिए किया जा सकता है।
उदाहरण के लिए, हैश चेनिंग हैश फ़ंक्शंस के '2-इंडिपेंडेंट' समूहों के साथ भी निरंतर अपेक्षित समय लेती है, क्योंकि किसी दी गई कुंजी की खोज करने का अपेक्षित समय उन टकरावों की अपेक्षित संख्या से सीमित होता है जिनमें कुंजी सम्मलित होती है। अपेक्षा की रैखिकता, यह अपेक्षित संख्या हैश तालिका में अन्य सभी कुंजियों के योग के बराबर होती है, इस संभावना की दी गई कुंजी और दूसरी कुंजी टकराती है। क्योंकि इस योग की टर्म्स में केवल दो कुंजियों से जुड़ी संभाव्य घटनाएं सम्मलित हैं, 2-इंडिपेंडेंट यह सुनिश्चित करने के लिए पर्याप्त है कि इस योग का वही मूल्य है जो वास्तव में रैंडम हैश फ़ंक्शन के लिए होता हैं।[2]
डबल हैशिंग, हैशिंग की एक और विधि है जिसके लिए कम स्तर की स्वतंत्रता की आवश्यकता होती है। यह ओपन एड्रेसिंग का एक रूप है जो दो हैश फ़ंक्शन का उपयोग करता है: एक प्रोब सीक्वेंस की प्रारम्भ निर्धारित करने के लिए, और दूसरा प्रोब सीक्वेंस में स्थितियों के बीच चरण आकार निर्धारित करने के लिए होता हैं। जब तक ये दोनों 2-इंडिपेंडेंट हैं, यह विधि प्रति ऑपरेशन निरंतर अपेक्षित समय देती है।[8]
दूसरी ओर, रैखिक जांच, ओपन एड्रेसिंग का सरल रूप जहां चरण का आकार हमेशा एक होता है, 5-इंडिपेंडेंट हैश फ़ंक्शन के साथ प्रति ऑपरेशन निरंतर अपेक्षित समय में काम करने की निश्चितता दी जा सकती है,[9] और 4-इंडिपेंडेंट हैश फ़ंक्शंस उपस्थित हैं जिनके लिए प्रति ऑपरेशन लॉगरिदमिक समय लगता है।[10]
कुक्कू हैशिंग के लिए आवश्यक k-इंडिपेंडेंस 2021 तक ज्ञात नहीं है। 2009 में इसे दिखाया गया था[11] वह -इंडिपेंडेंस पर्याप्त है, और कम से कम 6-इंडिपेंडेंस की आवश्यकता है। एक अन्य दृष्टिकोण टेब्यूलेशन हैशिंग का उपयोग करना है, जो 6-इंडिपेंडेंट नहीं है, लेकिन 2012 में दिखाया गया था।[12] कुक्कू हैशिंग के लिए पर्याप्त अन्य गुण होता हैं। 2014 से तीसरा प्रयास[13] कुक्कू हैशटेबल को तथाकथित स्टैश के साथ थोड़ा संशोधित करना है, जो 2-इंडिपेंडेंट हैश फ़ंक्शंस से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।
अन्य अनुप्रयोग
केन (गणितज्ञ), नेल्सन और डेविड वुड्रफ ने 2010 में विशिष्ट एलिमेंट्स समस्या के लिए फ्लैजोलेट-मार्टिन एल्गोरिदम में सुधार किया था।[14] एक सही उत्तर के अप्प्रोक्सिमशन के लिए, उन्हें एक इंडिपेंडेंट हैश फ़ंक्शन देने की आवश्यकता है।
डाइमेंसनलिटी में कमी के लिए काउंट स्केच एल्गोरिदम को दो हैश फ़ंक्शन 2-इंडिपेंडेंट और 4-इंडिपेंडेंट की आवश्यकता होती है।
एम्एएक्स-3एसएटी समस्या के लिए कार्लॉफ़-ज़्विक एल्गोरिदम को 3-इंडिपेंडेंट रैंडम वेरिएबल्स के साथ कार्यान्वित किया जा सकता है।
मिनहैश एल्गोरिदम का -इंडिपेंडेंट हैश फंक्शन्स उपयोग करके कार्यान्वित किया जा सकता है जैसा कि 1999 में पीटर इंडीक द्वारा सिद्ध किया गया था।[15]
संदर्भ
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
- ↑ 2.0 2.1 2.2 2.3 Wegman, Mark N.; Carter, J. Lawrence (1981). "New hash functions and their use in authentication and set equality" (PDF). Journal of Computer and System Sciences. 22 (3): 265–279. doi:10.1016/0022-0000(81)90033-7. Conference version in FOCS'79. Retrieved 9 February 2011.
- ↑ Siegel, Alan (2004). "On universal classes of extremely random constant-time hash functions and their time-space tradeoff" (PDF). SIAM Journal on Computing. 33 (3): 505–543. doi:10.1137/S0097539701386216. Conference version in FOCS'89.
- ↑ Lemire, Daniel, and Owen Kaser. "Faster 64-bit universal hashing using carry-less multiplications." Journal of Cryptographic Engineering 6.3 (2016): 171-185.
- ↑ Pătraşcu, Mihai; Thorup, Mikkel (2012), "The power of simple tabulation hashing", Journal of the ACM, 59 (3): Art. 14, arXiv:1011.5200, doi:10.1145/2220357.2220361, MR 2946218
- ↑ Siegel, Alan (2004), "On universal classes of extremely random constant-time hash functions" (PDF), SIAM Journal on Computing, 33 (3): 505–543, doi:10.1137/S0097539701386216, MR 2066640, archived from the original (PDF) on 2019-02-17
- ↑ Thorup, M. (2013), "Simple tabulation, fast expanders, double tabulation, and high independence", Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pp. 90–99, arXiv:1311.3121, doi:10.1109/FOCS.2013.18, ISBN 978-0-7695-5135-7, MR 3246210
- ↑ Bradford, Phillip G.; Katehakis, Michael N. (2007), "A probabilistic study on combinatorial expanders and hashing" (PDF), SIAM Journal on Computing, 37 (1): 83–111, doi:10.1137/S009753970444630X, MR 2306284, archived from the original (PDF) on 2016-01-25, retrieved 2016-01-19
- ↑ Pagh, Anna; Pagh, Rasmus; Ružić, Milan (2009), "Linear probing with constant independence", SIAM Journal on Computing, 39 (3): 1107–1120, arXiv:cs/0612055, doi:10.1137/070702278, MR 2538852
- ↑ Pătraşcu, Mihai; Thorup, Mikkel (2010), "On the k[[Category: Templates Vigyan Ready]]-independence required by linear probing and minwise independence" (PDF), Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6198, Springer, pp. 715–726, arXiv:1302.5127, doi:10.1007/978-3-642-14165-2_60, ISBN 978-3-642-14164-5
{{citation}}: URL–wikilink conflict (help) - ↑ Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).
- ↑ Pǎtraşcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.
- ↑ Aumüller, Martin, Martin Dietzfelbinger, and Philipp Woelfel. "Explicit and efficient hash families suffice for cuckoo hashing with a stash." Algorithmica 70.3 (2014): 428-456.
- ↑ Kane, Daniel M., Jelani Nelson, and David P. Woodruff. "An optimal algorithm for the distinct elements problem." Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. 2010.
- ↑ Indyk, Piotr. "A small approximately min-wise independent family of hash functions." Journal of Algorithms 38.1 (2001): 84-90.
अग्रिम पठन
- Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. p. 221. ISBN 978-0-521-47465-8.
