एक स्ट्रिंग में खोजें। CPython कार्यान्वयन

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

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

स्ट्रिंग ऑब्जेक्ट का कार्यान्वयन यहां पाया जा सकता है - ऑब्जेक्ट / stringobject.c । फ़ंक्शंस की परिभाषा जो विभिन्न प्रकार की खोजों के लिए ज़िम्मेदार है ( ढूँढें , rfind , __contains__ ) ऑब्जेक्ट्स / stringlib / find.h है। ये सभी फ़ंक्शंस ( स्प्लिट , रिप्लेस , आदि के साथ) ऑब्जेक्ट्स / स्ट्रिंगलिब / फास्टसर्च.एच में लागू सर्च का उपयोग करते हैं। हम उनसे निपटेंगे।

एल्गोरिथ्म को लेखक ( फ्रेड्रिक लुंड ) द्वारा बॉयर-मूर और हॉर्सपूल एल्गोरिदम का मिश्रण कई सुधारों और सरलीकरणों के साथ कहा जाता है। एल्गोरिथ्म में ब्लूम फ़िल्टर का भी उपयोग किया जाता है ।

और इसलिए, चलो चलते हैं। हेडर

fastsearch(const STRINGLIB_CHAR* s, Py_ssize_t n, const STRINGLIB_CHAR* p, Py_ssize_t m, Py_ssize_t maxcount, int mode) /* s - ,   , n -  , p - ,   (  ), m -  , maxcount -    ,       , mode -  /  /    */ 

सब कुछ स्पष्ट होने लगता है। आइए परिभाषित कथनों को देखें:

 /*      mode */ #define FAST_COUNT 0 #define FAST_SEARCH 1 #define FAST_RSEARCH 2 /* STRINGLIB_BLOOM_WIDTH    \(   )    32, 64, 128 */ #define STRINGLIB_BLOOM_ADD(mask, ch) ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1))))) #define STRINGLIB_BLOOM(mask, ch) ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1))))) 

खिल फिल्टर के इस कार्यान्वयन कैसे काम करता है? इसके अंतिम लॉग (STRINGLIB_BLOOM_WIDTH) बिट्स के आधार पर प्रत्येक वर्ण को एक संख्या दी गई है। उदाहरण के लिए, यह 1 के लिए है :

 >>> ord('a') & 31 1 

Q - 17 के लिए :

 >>> ord('q') & 31 17 

तार्किक "OR" STRINGLIB_BLOOM_ADD का उपयोग करने से फ़िल्टर मास्क में देखे गए वर्णों के बारे में जानकारी एकत्रित होती है। बाद में, STRINGLIB_BLOOM का उपयोग करके, आप देख सकते हैं कि कोई वर्ण फ़िल्टर में जोड़ा गया था या नहीं। बेशक, इस चेक में गलत पॉज़िटिव हो सकते हैं ( STRINGLIB_BLOOM रिटर्न 0 नहीं है, लेकिन चरित्र वास्तव में स्ट्रिंग \ फ़िल्टर में नहीं है):

 >>> ord(']') & 31 29 >>> ord('}') & 31 29 

लेकिन यह काफी सस्ता है और तुलना की संख्या को कम करने में मदद करता है।

अब हम एल्गोरिथम पर आगे बढ़ सकते हैं। मामलों के लिए स्पष्ट तर्क m> n और m <= 1 :

  w = n - m; if (w < 0 || (mode == FAST_COUNT && maxcount == 0)) return -1; 

और कोड का एक हिस्सा छोड़ दिया जाता है ताकि लेख को फाड़ा न जाए):

  if (m <= 1) { if (m <= 0) return -1; if (mode == FAST_COUNT) { /* ... */ } else if (mode == FAST_SEARCH) { for (i = 0; i < n; i++) if (s[i] == p[0]) return i; } else { /* FAST_RSEARCH */ /* ... */ } return -1; } 

उसके बाद, कई नए चर दिखाई देते हैं और आवश्यक विकल्प के लिए मास्क भरा जाता है:

  mlast = m - 1; skip = mlast - 1; mask = 0; for (i = 0; i < mlast; i++) { STRINGLIB_BLOOM_ADD(mask, p[i]); if (p[i] == p[mlast]) skip = mlast - i - 1; } STRINGLIB_BLOOM_ADD(mask, p[mlast]); 

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

विकिपीडिया से मुख्य एल्गोरिथ्म विचार का विवरण:

बाएं से दाएं स्कैन करें, दाएं से बाएं की तुलना करें। पाठ की शुरुआत (रेखा) और टेम्पलेट संयुक्त है, चेक टेम्पलेट के अंतिम चरित्र से शुरू होता है। यदि वर्णों का मिलान होता है, तो पैटर्न के पारमार्थिक चरित्र की तुलना की जाती है, आदि। यदि पैटर्न के सभी अक्षर स्ट्रिंग के सुपरिंपल वर्णों से मेल खाते हैं, तो प्रतिस्थापन पाया जाता है और खोज समाप्त हो जाती है।

यदि पैटर्न का कुछ वर्ण स्ट्रिंग के संगत वर्ण के साथ मेल नहीं खाता है, तो पैटर्न को कई वर्णों को दाईं ओर स्थानांतरित किया जाता है, और अंतिम वर्ण के साथ चेक फिर से शुरू होता है।

वास्तव में इस विवरण का कार्यान्वयन (ऊपर w = n - m ):

  for (i = 0; i <= w; i++) { if (s[i+m-1] == p[m-1]) { /* ,      */ for (j = 0; j < mlast; j++) if (s[i+j] != p[j]) break; if (j == mlast) { /*  ! */ if (mode != FAST_COUNT) /*       - ,     */ return i; /*     */ count++; if (count == maxcount) return maxcount; i = i + mlast; continue; } /*         ,      */ /*      ,        */ if (!STRINGLIB_BLOOM(mask, s[i+m])) /*  ,           */ i = i + m; else /*  ,        'skip' */ i = i + skip; } else { /*     .      ,        */ if (!STRINGLIB_BLOOM(mask, s[i+m])) /*  ,           */ i = i + m; /*   , i++ */ } } 

थोड़ा सा दृश्य। आइए हम स्ट्रिंग "ड्रम" के साथ काम करें और विकल्प "अबा" की तलाश करें:

     skip = 1 i = 0: ______________ |||||||| | -  , i++ _______ |||| i = 1: ______________ |||||||| | -  ,   _______ |||| ______________ |||||||| | -  .    ""  ""   ,   skip,   for   i += 2 _______ |||| i = 3: ______________ |||||||| | -  ,   _______ |||| ______________ |||||||| | -  ,   _______ |||| ______________ |||||||| | -  ,   _______ |||| 

खैर, यह बात है।

यदि आप इसे पसंद करते हैं, तो अभी भी पायथन स्रोत में स्थानों का एक गुच्छा है जो खुदाई में दिलचस्प हैं। उदाहरण के लिए, ऑब्जेक्ट्स / listobject.c या dict.get का लिस्ट में लागू करना ।

शुभकामनाएँ! :)