K-इंडिपेंडेंट हैशिंग: Difference between revisions

From Vigyanwiki
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 28: Line 28:


== परिभाषाएँ ==
== परिभाषाएँ ==
सबसे दृढ परिभाषा, वेगमैन और कार्टर द्वारा प्रस्तुत की गई<ref name=WC81 />दृढ़ता से 'यूनिवर्सल नाम<math>_k</math>' के अनुसार हैश समूह, निम्नलिखित है। हैश फ़ंक्शंस का समूह <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> होता हैं, हमारे पास:
सबसे दृढ परिभाषा, वेगमैन और कार्टर द्वारा प्रस्तुत की गई<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>
यह परिभाषा निम्नलिखित दो स्थितियों के बराबर है:
यह परिभाषा निम्नलिखित दो स्थितियों के बराबर है:
Line 50: Line 50:


: <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>-स्वतंत्र परिवार, जो स्वतंत्रता संपत्तियों के ब्लैक-बॉक्स उपयोग की अनुमति देता है।
उस पर ध्यान दे, यद्यपि ही <math>\mu</math> 1 के निकट है, <math>h(x_i)</math> अब इंडिपेंडेंट रैंडम वेरिएबल्स नहीं हैं, जो प्रायः रैंडम एल्गोरिदम के विश्लेषण में समस्या है। इसलिए, राउंडिंग इश्यूज से निवारण का अधिक सामान्य विकल्प यह सिद्ध करना है कि हैश समूह [[सांख्यिकीय दूरी]] <math>k</math>-इंडिपेंडेंट समूह के निकट है, जो इंडिपेंडेंस गुणों के ब्लैक-बॉक्स उपयोग की अनुमति देता है।


==तकनीक==
==तकनीक==


===यादृच्छिक गुणांक वाले बहुपद===
===रैंडम गुणांक वाले बहुपद===
निर्माण की मूल तकनीक {{mvar|k}}-कार्टर और वेगमैन द्वारा दिए गए स्वतंत्र हैश फ़ंक्शन, एक बड़ी अभाज्य संख्या का चयन करना था {{mvar|p}}, चुनना {{mvar|k}} यादृच्छिक संख्या मॉड्यूलो {{mvar|p}}, और इन संख्याओं को डिग्री के [[बहुपद]] के गुणांक के रूप में उपयोग करें {{math|''k'' &minus; 1}} जिनके मान मॉड्यूलो हैं {{mvar|p}} का उपयोग हैश फ़ंक्शन के मान के रूप में किया जाता है। दी गई डिग्री मापांक के सभी बहुपद {{mvar|p}} समान रूप से संभावित हैं, और कोई भी बहुपद किसी के द्वारा विशिष्ट रूप से निर्धारित होता है {{mvar|k}}-अलग-अलग तर्कों के साथ तर्क-मूल्य जोड़े का समूह, जिससे यह किसी का अनुसरण करता है {{mvar|k}}-अलग-अलग तर्कों के समूह को किसी में भी मैप किए जाने की समान रूप से संभावना है {{mvar|k}}-हैश मानों का टुपल।<ref name=WC81/>
निर्माण की मूल तकनीक {{mvar|k}}-कार्टर और वेगमैन द्वारा दिए गए इंडिपेंडेंट हैश फ़ंक्शन, बड़ी अभाज्य संख्या {{mvar|p}} का चयन करना था, {{mvar|k}} रैंडम संख्या मॉड्यूलो {{mvar|p}} को चुनना होता हैं, और इन संख्याओं को डिग्री के [[बहुपद]] के गुणांक {{math|''k'' &minus; 1}} के रूप में उपयोग करें जिनके मान मॉड्यूलो {{mvar|p}} हैं उसका उपयोग हैश फ़ंक्शन के मान के रूप में किया जाता है। दी गई डिग्री मापांक के सभी बहुपद {{mvar|p}} समान रूप से संभावित हैं, और कोई भी बहुपद किसी के द्वारा विशिष्ट रूप से निर्धारित होता है {{mvar|k}}-ट्यूपल आर्गुमेंट के साथ आर्गुमेंट-मूल्य जोड़े का समूह, जिससे यह किसी {{mvar|k}}-ट्यूपल आर्गुमेंट के समूह को किसी में भी मैप किए जाने की समान रूप से संभावना {{mvar|k}}-हैश मानों का टुपल का अनुसरण करता है।<ref name=WC81/>


सामान्य तौर पर बहुपद किसी भी [[परिमित क्षेत्र]] में [[बहुपद मूल्यांकन]] हो सकता है।
सामान्य तौर पर बहुपद किसी भी [[परिमित क्षेत्र]] में [[बहुपद मूल्यांकन]] हो सकता है।
मॉड्यूलो प्राइम फ़ील्ड के अलावा, एक लोकप्रिय विकल्प आकार का फ़ील्ड है <math>2^n</math>, जो आधुनिक कंप्यूटरों पर तेज़ [[परिमित क्षेत्र अंकगणित]] का समर्थन करता है।
मॉड्यूलो प्राइम फ़ील्ड के अतिरिक्त, प्रसिद्ध विकल्प आकार <math>2^n</math> का फ़ील्ड है, जो आधुनिक कंप्यूटरों पर तेज़ [[परिमित क्षेत्र अंकगणित|परिमित क्षेत्र अरिथमेटिक]] का समर्थन करता है।
यह CLHash के लिए [[डेनियल लेमायर]] और [[ओवेन कैसर]] द्वारा अपनाया गया दृष्टिकोण था।<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>
यह सीएल हैश के लिए [[डेनियल लेमायर]] और [[ओवेन कैसर]] द्वारा अपनाया गया कार्य था।<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|Tabulation hashing}}
{{main|टैब्युलेशन हैशिंग }}
[[सारणीकरण हैशिंग]] प्रत्येक कुंजी को [[बाइट]]्स में विभाजित करके, प्रत्येक बाइट को सूचकांक के रूप में यादृच्छिक संख्याओं की तालिका में (प्रत्येक बाइट स्थिति के लिए एक अलग तालिका के साथ) उपयोग करके, और इन तालिका लुकअप के परिणामों को जोड़कर हैश मानों की मैपिंग की एक तकनीक है। एक बिटवाइज़ [[एकमात्र]] ऑपरेशन। इस प्रकार, इसके आरंभीकरण में बहुपद विधि की तुलना में अधिक यादृच्छिकता की आवश्यकता होती है, लेकिन संभावित रूप से धीमी गुणन संक्रियाओं से बचा जाता है। यह 3-स्वतंत्र है लेकिन 4-स्वतंत्र नहीं है।<ref>{{citation
[[सारणीकरण हैशिंग]] प्रत्येक कुंजी को [[बाइट]] में विभाजित करके, प्रत्येक बाइट को सूचकांक के रूप में रैंडम संख्याओं की तालिका में (प्रत्येक बाइट स्थिति के लिए एक अलग तालिका के साथ) उपयोग करके, और इन तालिका लुकअप एक बिटवाइज़ एक्सक्लूसिव ऑपरेशन के परिणामों को जोड़कर हैश मानों की मैपिंग की तकनीक है। इस प्रकार, इसके आरंभीकरण में बहुपद विधि की तुलना में अधिक रैंडम की आवश्यकता होती है, लेकिन संभावित रूप से धीमी गुणन संक्रियाओं से बचा जाता है। यह 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> सारणीबद्ध हैशिंग की विविधताएं इनपुट कुंजी से बिट्स के ओवरलैपिंग संयोजनों के आधार पर तालिका लुकअप निष्पादित करके, या सरल सारणीबद्ध हैशिंग को पुनरावृत्त रूप से लागू करके स्वतंत्रता की उच्च डिग्री प्राप्त कर सकती हैं।<ref>{{citation
  | 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
प्रति ऑपरेशन निरंतर अपेक्षित समय की गारंटी के लिए आवश्यक स्वतंत्रता के स्तर के अनुसार, k-स्वतंत्रता की धारणा का उपयोग हैशटेबल्स में विभिन्न Hash_table#Collision_resolution के बीच अंतर करने के लिए किया जा सकता है।
 
उदाहरण के लिए, हैश_टेबल#सेपरेट_चेनिंग हैश फ़ंक्शंस के '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
 
दूसरी ओर,[[ रैखिक जांच | रैखिक जांच]], ओपन एड्रेसिंग का सरल रूप जहां चरण का आकार हमेशा एक होता है, 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-स्वतंत्र हैश फ़ंक्शंस मौजूद हैं जिनके लिए प्रति ऑपरेशन लॉगरिदमिक समय लगता है।<ref>{{citation
  | 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-स्वतंत्रता 2021 तक ज्ञात नहीं है।
 
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-स्वतंत्रता की आवश्यकता है।
[[कोयल हैशिंग|कुक्कू हैशिंग]] के लिए आवश्यक k-इंडिपेंडेंस 2021 तक ज्ञात नहीं है।
एक अन्य दृष्टिकोण टेब्यूलेशन हैशिंग का उपयोग करना है, जो 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> कोयल हैशिंग के लिए पर्याप्त अन्य गुण होना।
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 से तीसरा दृष्टिकोण<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-स्वतंत्र हैश फ़ंक्शंस से अधिक कुछ भी उपयोग करना संभव नहीं बनाता है।
एक अन्य दृष्टिकोण टेब्यूलेशन हैशिंग का उपयोग करना है, जो 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>
केन (गणितज्ञ), [[ स्पष्टीकरण नेल्सन |नेल्सन]] और डेविड वुड्रफ ने 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>-स्वतंत्र हैश फ़ंक्शन।
एक <math>\varepsilon</math> सही उत्तर के अप्प्रोक्सिमशन के लिए, उन्हें एक <math>\tfrac{\log1/\varepsilon}{\log\log1/\varepsilon}</math> '''इंडिपेंडेंट''' हैश फ़ंक्शन देने की आवश्यकता है।


[[आयामीता में कमी]] के लिए [[ गिनती रेखाचित्र ]] एल्गोरिदम को दो हैश फ़ंक्शन की आवश्यकता होती है, एक 2-स्वतंत्र और एक 4-स्वतंत्र।
[[आयामीता में कमी|डाइमेंसनलिटी में कमी]] के लिए [[ गिनती रेखाचित्र |काउंट स्केच]] एल्गोरिदम को दो हैश फ़ंक्शन '''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>
[[मिनहैश]] एल्गोरिदम का <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: एल्गोरिदम खोजें]] [[Category: त्रुटि का पता लगाना और सुधार करना]]


[[Category: Machine Translated Page]]
[[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-इंडिपेंडेंट समूहों का प्रस्ताव किया गया है।

पृष्ठभूमि

See also: हैश फंक्शन

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

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

परिभाषाएँ

सबसे दृढ परिभाषा, वेगमैन और कार्टर द्वारा प्रस्तुत की गई[2]दृढ़ता से 'यूनिवर्सल' के अनुसार हैश समूह'', निम्नलिखित है। हैश फ़ंक्शंस का समूह है -इंडिपेंडेंट यदि किसी के लिए विशिष्ट कुंजियाँ और कोई भी हैश कोड (आवश्यक नहीं कि अलग हो) होता हैं, हमारे पास:

यह परिभाषा निम्नलिखित दो स्थितियों के बराबर है:

  1. किसी भी निश्चित के लिए , जैसा से रैंडम रूप से , से निर्वासित किया जाता है जो समान रूप से से वितरित किया जाता है।
  2. किसी भी निश्चित, विशिष्ट कुंजी के लिए, जैसा से रैंडम रूप से , निर्वासित किया जाता है इंडिपेंडेंट रैंडम वेरिएबल्स हैं।

प्रायः राउंडिंग इश्यूज के कारण सही संयुक्त संभावना प्राप्त करना असुविधाजनक होता है। निम्न,[3] कोई से इंडिपेंडेंट समुह को संतुष्ट करने के लिए परिभाषित कर सकता है:

अलग और ,

उस पर ध्यान दे, यद्यपि ही 1 के निकट है, अब इंडिपेंडेंट रैंडम वेरिएबल्स नहीं हैं, जो प्रायः रैंडम एल्गोरिदम के विश्लेषण में समस्या है। इसलिए, राउंडिंग इश्यूज से निवारण का अधिक सामान्य विकल्प यह सिद्ध करना है कि हैश समूह सांख्यिकीय दूरी -इंडिपेंडेंट समूह के निकट है, जो इंडिपेंडेंस गुणों के ब्लैक-बॉक्स उपयोग की अनुमति देता है।

तकनीक

रैंडम गुणांक वाले बहुपद

निर्माण की मूल तकनीक k-कार्टर और वेगमैन द्वारा दिए गए इंडिपेंडेंट हैश फ़ंक्शन, बड़ी अभाज्य संख्या p का चयन करना था, k रैंडम संख्या मॉड्यूलो p को चुनना होता हैं, और इन संख्याओं को डिग्री के बहुपद के गुणांक k − 1 के रूप में उपयोग करें जिनके मान मॉड्यूलो p हैं उसका उपयोग हैश फ़ंक्शन के मान के रूप में किया जाता है। दी गई डिग्री मापांक के सभी बहुपद p समान रूप से संभावित हैं, और कोई भी बहुपद किसी के द्वारा विशिष्ट रूप से निर्धारित होता है k-ट्यूपल आर्गुमेंट के साथ आर्गुमेंट-मूल्य जोड़े का समूह, जिससे यह किसी k-ट्यूपल आर्गुमेंट के समूह को किसी में भी मैप किए जाने की समान रूप से संभावना k-हैश मानों का टुपल का अनुसरण करता है।[2]

सामान्य तौर पर बहुपद किसी भी परिमित क्षेत्र में बहुपद मूल्यांकन हो सकता है। मॉड्यूलो प्राइम फ़ील्ड के अतिरिक्त, प्रसिद्ध विकल्प आकार का फ़ील्ड है, जो आधुनिक कंप्यूटरों पर तेज़ परिमित क्षेत्र अरिथमेटिक का समर्थन करता है। यह सीएल हैश के लिए डेनियल लेमायर और ओवेन कैसर द्वारा अपनाया गया कार्य था।[4]


टैब्युलेशन हैशिंग

Main article: टैब्युलेशन हैशिंग

सारणीकरण हैशिंग प्रत्येक कुंजी को बाइट में विभाजित करके, प्रत्येक बाइट को सूचकांक के रूप में रैंडम संख्याओं की तालिका में (प्रत्येक बाइट स्थिति के लिए एक अलग तालिका के साथ) उपयोग करके, और इन तालिका लुकअप एक बिटवाइज़ एक्सक्लूसिव ऑपरेशन के परिणामों को जोड़कर हैश मानों की मैपिंग की तकनीक है। इस प्रकार, इसके आरंभीकरण में बहुपद विधि की तुलना में अधिक रैंडम की आवश्यकता होती है, लेकिन संभावित रूप से धीमी गुणन संक्रियाओं से बचा जाता है। यह 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]


संदर्भ

  1. ↑ 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. ↑ 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.
  3. ↑ 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.
  4. ↑ Lemire, Daniel, and Owen Kaser. "Faster 64-bit universal hashing using carry-less multiplications." Journal of Cryptographic Engineering 6.3 (2016): 171-185.
  5. ↑ 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
  6. ↑ 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
  7. ↑ 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
  8. ↑ 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
  9. ↑ 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
  10. ↑ 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)
  11. ↑ Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on Algorithms (2009).
  12. ↑ Pǎtraşcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.
  13. ↑ 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.
  14. ↑ 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.
  15. ↑ Indyk, Piotr. "A small approximately min-wise independent family of hash functions." Journal of Algorithms 38.1 (2001): 84-90.


अग्रिम पठन

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=K-इंडिपेंडेंट_हैशिंग&oldid=229091’