पुस्तक "परफेक्ट अल्गोरिथम। ग्राफ एल्गोरिदम और डेटा संरचनाएं "

हाय, हब्रोज़ितेली! एल्गोरिदम कंप्यूटर विज्ञान के दिल और आत्मा हैं। आप उनके बिना नहीं कर सकते, वे हर जगह हैं - नेटवर्क रूटिंग और जीनोमिक्स की गणना से लेकर क्रिप्टोग्राफी और मशीन लर्निंग तक। "परफेक्ट अल्गोरिथम" आपको एक वास्तविक समर्थक में बदल देगा, जो किसी भी आईटी कंपनी को काम पर रखने के दौरान कार्यों को निर्धारित करेगा और मास्टर इन दोनों को जीवन में और एक साक्षात्कार में हल करेगा।

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

यह पोस्ट ब्लूम फ़िल्टर्स: द बेसिक्स का एक अंश प्रस्तुत करता है।

यह किताब किस बारे में है

"परफेक्ट अल्गोरिथम" पुस्तक का दूसरा भाग निम्नलिखित तीन विषयों पर साक्षरता की मूल बातें पर एक परिचयात्मक पाठ्यक्रम है।

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

सबसे छोटा रास्ता । सबसे छोटी पथ समस्या में, लक्ष्य बिंदु A से बिंदु B तक नेटवर्क में सर्वश्रेष्ठ मार्ग की गणना करना है। इस कार्य में स्पष्ट अनुप्रयोग हैं, जैसे कि यातायात मार्गों की गणना, और कई अन्य सार्वभौमिक कार्यों में प्रच्छन्न रूप में भी होता है। हम अपने ग्राफ़ खोज एल्गोरिदम में से एक को सामान्यीकृत करेंगे और प्रसिद्ध दिक्जस्त्र लघु पथ खोज एल्गोरिदम में आएंगे।

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

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

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

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

12.5। ब्लूम फिल्टर: मूल बातें

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

12.5.1। समर्थित कार्य

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

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

ब्लैक फिल्टर: समर्थित संचालन

देखें: कुंजी k के साथ, "हाँ" लौटाएं यदि k को पहले ब्लूम फ़िल्टर में डाला गया था, और अन्यथा "नहीं"।
चिपकाएँ: ब्लूम फ़िल्टर में एक नई कुंजी k जोड़ें।

ब्लूम फ़िल्टर बहुत स्थानिक रूप से कुशल हैं; आम तौर पर, उन्हें प्रति इन्सर्ट केवल 8 बिट्स की आवश्यकता हो सकती है। यह काफी अविश्वसनीय है, क्योंकि 8 बिट एक वस्तु के लिए 32-बिट कुंजी या पॉइंटर को याद रखने के लिए पूरी तरह से अपर्याप्त है! इस कारण से, ब्लूम फ़िल्टर में व्यू ऑपरेशन केवल "हां" / "नहीं" का उत्तर देता है, जबकि हैश तालिका में, यह ऑपरेशन वांछित ऑब्जेक्ट (यदि यह पाया जाता है) के लिए एक पॉइंटर लौटाता है। यही कारण है कि इन्सर्ट ऑपरेशन अब केवल कुंजी को स्वीकार करता है, न कि ऑब्जेक्ट को (पॉइंटर को)।

हमारे द्वारा अध्ययन किए गए अन्य सभी डेटा संरचनाओं के विपरीत, ब्लूम फ़िल्टर गलत हो सकते हैं। दो प्रकार की त्रुटियां हैं: झूठी निगेटिव जब व्यू ऑपरेशन "गलत" लौटाता है, भले ही अनुरोधित कुंजी पहले ही डाली जा चुकी हो, और गलत कथन (या सकारात्मक) जब व्यू ऑपरेशन "सही" वापस आता है, हालांकि अनुरोधित कुंजी अभी तक अतीत में नहीं डाली गई है । खंड 12.5.3 में हम देखेंगे कि बेसिक ब्लूम फ़िल्टर कभी भी झूठे नकारात्मक से पीड़ित नहीं होते हैं, लेकिन उनके पास गलत बयान के रूप में "प्रेत तत्व" हो सकते हैं। धारा 12.6 से पता चलता है कि झूठे दावों की आवृत्ति को उचित रूप से अंतरिक्ष के उपयोग को समायोजित करके नियंत्रित किया जा सकता है। ब्लूम फ़िल्टर के विशिष्ट कार्यान्वयन में लगभग 1% या 0.1% की त्रुटि दर हो सकती है।

इन्सर्ट और व्यू ऑपरेशंस का निष्पादन समय हैश तालिका में उतना ही तेज़ है। और इससे भी बेहतर, ब्लूम फ़िल्टर और डेटा सेट 1 के कार्यान्वयन की परवाह किए बिना, इन कार्यों को निरंतर समय में प्रदर्शन करने की गारंटी है। हालाँकि, कार्यान्वयन और डेटा सेट फ़िल्टर त्रुटि दर को प्रभावित करते हैं।

हैश टेबल पर ब्लूम फिल्टर के फायदे और नुकसान को संक्षेप में प्रस्तुत करना:

ब्लैक फिल्टर के बाद से फिल्टर

1. पेशेवरों: अधिक स्थानिक रूप से प्रभावी।

2. पेशेवरों: प्रत्येक डेटा सेट के लिए स्थायी-समय के संचालन की गारंटी।

3. विपक्ष: ऑब्जेक्ट्स को पॉइंटर्स स्टोर नहीं कर सकता।

4. विपक्ष: क्लच के साथ हैश तालिका की तुलना में अधिक जटिल विलोपन।

5. विपक्ष: एक गलत बयान की गैर-शून्य संभावना।

बुनियादी ब्लूम फिल्टर के लिए संकेतक की सूची इस प्रकार है।

तालिका 12.4। बेसिक ब्लूम फिल्टर: समर्थित संचालन और उनके निष्पादन का समय। डैगर साइन (†) इंगित करता है कि व्यू ऑपरेशन में झूठे दावों की एक नियंत्रणीय लेकिन गैर-अक्षीय संभावना है


उन अनुप्रयोगों में हैश टेबल के बजाय ब्लूम फ़िल्टर का उपयोग किया जाना चाहिए जिनमें उनके फायदे मायने रखते हैं और उनके नुकसान लेन-देन में बाधा नहीं हैं।

जब ब्लू फिल्म का उपयोग करने के लिए

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

12.5.2। अनुप्रयोगों

अगला, बार-बार स्कैन के साथ तीन उपयोग हैं, जहां बचत स्थान महत्वपूर्ण हो सकता है, और झूठे बयान लेनदेन के लिए बाधा नहीं हैं।

वर्तनी-जांचकर्ता। 1970 के दशक में, ब्लूम फ़िल्टर का उपयोग वर्तनी जांचकों - वर्तनी जांचकर्ताओं को लागू करने के लिए किया गया था। पूर्व-प्रसंस्करण चरण में, शब्दकोश में प्रत्येक शब्द ब्लूम फ़िल्टर में डाला जाता है। एक दस्तावेज़ की वर्तनी एक ऑपरेशन के लिए नीचे आती है। किसी दस्तावेज़ में एक शब्द देखें, किसी भी शब्द को चिह्नित करना जिसके लिए यह ऑपरेशन "नहीं" देता है।

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

निषिद्ध पासवर्ड । एक पुराना एप्लिकेशन जो आज तक मान्य है, निषिद्ध पासवर्डों को ट्रैक करता है - ऐसे पासवर्ड जो अनुमान लगाने में बहुत सामान्य या बहुत आसान हैं। प्रारंभ में, सभी निषिद्ध पासवर्ड ब्लूम फ़िल्टर में डाले गए हैं; अतिरिक्त निषिद्ध पासवर्ड बाद में डाले जा सकते हैं, आवश्यकतानुसार। जब कोई उपयोगकर्ता अपना पासवर्ड सेट या रीसेट करने की कोशिश करता है, तो सिस्टम ब्लूम फ़िल्टर में प्रस्तावित पासवर्ड की खोज करता है। यदि खोज "हाँ" देता है, तो उपयोगकर्ता को एक अलग पासवर्ड के साथ फिर से प्रयास करने के लिए प्रेरित किया जाता है। यहां, एक गलत कथन को एक मजबूत पासवर्ड में अनुवादित किया जाता है, जिसे सिस्टम अस्वीकार करता है।

बशर्ते कि त्रुटि दर बहुत अधिक न हो, 1% या 0.1% से अधिक न हो, यह बहुत मायने नहीं रखता है। समय-समय पर, कुछ उपयोगकर्ताओं को सिस्टम को स्वीकार्य पासवर्ड खोजने के लिए एक अतिरिक्त प्रयास की आवश्यकता होगी।

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

12.5.3। कार्यान्वयन

ब्लूम फ़िल्टर के अंदर देखते हुए, आप एक सुरुचिपूर्ण कार्यान्वयन देख सकते हैं। डेटा संरचना एन-बिट स्ट्रिंग का समर्थन करती है या इसी तरह, लंबाई ए की एक सरणी जिसमें प्रत्येक तत्व 0 या 1. है (सभी तत्वों को शून्य से आरंभीकृत किया गया है।) यह संरचना m हैश फ़ंक्शन h1, h2, ..., h , जबकि प्रत्येक ने सरणी में पदों के {0, 1, 2, ..., n - 1} के सभी संभावित कुंजियों के ब्रह्मांड यू को मैप किया। पैरामीटर एम प्रविष्टि के लिए ब्लूम फ़िल्टर द्वारा उपयोग किए जाने वाले बिट्स की संख्या के लिए आनुपातिक है, और, एक नियम के रूप में, एक छोटा सा स्थिरांक है (उदाहरण के लिए, 5)।

जब भी एक कुंजी को ब्लूम फ़िल्टर में डाला जाता है, तो प्रत्येक हैश फ़ंक्शन फ्लैग सेट करता है, जिससे ए से 1 तक की समान बिट सेट होती है।

ब्लो फिल्टर: इन्सर्ट (चालू)

for i = 1 to m do A[hi(k)] := 1 

उदाहरण के लिए, यदि m = 3 और h1 (k) = 23, h2 (k) = 17 और h3 (k) = 5, k डालने से सरणी के 5 वें, 17 वें और 23 वें बिट्स के बराबर सेट होने का कारण बनता है 1 (छवि 12.5)।


व्यू ऑपरेशन में, ब्लूम फ़िल्टर उस फ़िंगरप्रिंट की खोज करता है जो संभवत: इन्सर्ट k पर रहता है।

ब्लो फिल्टर: व्यू (प्रमुख कुंजी)

 for i = 1 to m do if A [hi (k)] = 0 then return «» return «» 

अब हम देख सकते हैं कि ब्लूम फ़िल्टर झूठे नकारात्मक से पीड़ित क्यों नहीं हो सकते हैं। जब कुंजी कश्मीर डाला जाता है, तो संबंधित m बिट्स 1 पर सेट होते हैं। ब्लूम फ़िल्टर के जीवनकाल के दौरान, बिट्स 0 से 1 तक अपना मान बदल सकते हैं, लेकिन इसके विपरीत नहीं। इस प्रकार, ये m बिट्स हमेशा के लिए 1 रह जाते हैं। प्रत्येक बाद के दृश्य k ऑपरेशन को सही हाँ उत्तर देने की गारंटी दी जाती है।

हम यह भी देख सकते हैं कि गलत बयान कैसे सामने आते हैं। मान लीजिए कि m = 3 और चार कुंजी k1, k2, k3, k4 में निम्नलिखित हैश मान हैं:


मान लीजिए कि हम ब्लूम फ़िल्टर (चित्र 12.6) में k1, k2, k3 और k4 सम्मिलित करते हैं। ये तीन आवेषण कुल नौ बिट्स को 1 पर सेट करते हैं, जिनमें कुंजी k1 (5, 17 और 23) के फिंगरप्रिंट में तीन बिट्स शामिल हैं। इस बिंदु पर, ब्लूम फ़िल्टर अब यह भेद नहीं कर सकता है कि कुंजी k1 डाला गया था या नहीं। यहां तक ​​कि अगर k1 को फ़िल्टर में नहीं डाला गया था, तो खोज "हां" लौटा देगी, जो कि एक गलत कथन है।

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



»पुस्तक की अधिक जानकारी प्रकाशक की वेबसाइट पर पाई जा सकती है
» सामग्री
» अंश

ख़ारोज़ज़ाइटी के लिए कूपन पर 20% की छूट - एलगोरिदम
पुस्तक के पेपर संस्करण के भुगतान पर, एक इलेक्ट्रॉनिक पुस्तक ई-मेल द्वारा भेजी जाती है।