बाइनरी स्ट्रिंग खोज - न्यूनतम बिन चौड़ाई?

Question

मैं पाइथन में बाइनरी खोज का निर्माण करता हूं, लेकिन सवाल सामान्य रूप से बाइनरी खोज संरचना के साथ अधिक करना है।

मान लीजिए कि मेरे पास लगभग एक हजार योग्य उम्मीदवार हैं जो मैं बाइनरी खोज का उपयोग करके खोज रहा हूं, सॉर्ट किए गए डेटासेट को विभाजित करने के क्लासिक दृष्टिकोण कर रहा हूं और इस प्रक्रिया को दोहराने के लिए योग्य सेट को कम करने के लिए इस प्रक्रिया को दोहराना चाहता हूं।

hi = len(names) 
lo = 0 
while lo < hi: 
    mid = (lo+hi)//2 
    midval = names[mid].lower() 
    if midval < query.lower(): 
    lo = mid+1 
    elif midval > query.lower(): 
    hi=mid 
    else: 
    return midval 
return None 

यहां से अनुकूलित किया गया यह कोड: https://stackoverflow.com/a/212413/215608 उम्मीदवारों सिर्फ नाम के तार, (प्रथम पिछले प्रारूप, उदाहरण के लिए "पीटर जैक्सन") मैं शुरू में वर्णानुक्रम सेट को सॉर्ट और फिर कुछ इस तरह का उपयोग कर द्विभाजन के साथ आगे बढ़ना कर रहे हैं

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

मैं इतना नहीं पूछ रहा हूं कि इसे के रूप में कैसे पूरा किया जाए इस प्रकार की खोज कहलाती है ... "बिन आकार" के लिए सीमित मानदंड के साथ बाइनरी खोज क्या है? कुछ जो सशर्त रूप से डेटासेट को विभाजित करता है, और मानदंड पूरा होने के बाद, यह सुनिश्चित करने के लिए स्ट्रिंग मिलान के किसी अन्य रूप पर वापस आ जाता है ताकि यह सुनिश्चित किया जा सके कि क्वेरी पर प्रभावी वाइल्डकार्ड प्रभावी रूप से हो सकता है (इसलिए "पीटर" की खोज " पीटर जैक्सन "और" पीटर एडवर्ड्स ")

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

Answer 1

मैं दो चरणों खोज के इस प्रकार के पार से पहले नहीं आए हैं बजाय प्रयास पर गौर करना चाहिए, ताकि पता नहीं है चाहे यह एक प्रसिद्ध नाम है। हालांकि, मैं एक विधि का प्रस्ताव कर सकता हूं कि इसे कैसे किया जा सकता है।

मान लें कि आपने पहला चरण चलाया है और कोई मिलान नहीं मिला है।

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

अब तुलनित्र को। खोज कुंजी x की खोज कुंजी k के विरुद्ध तुलना करते समय, तुलनित्र केवल x[:len(k)] का उपयोग करेगा और शेष x को अनदेखा करेगा। इस प्रकार "पीटर" की खोज करते समय, सूची में सभी पीटर्स कुंजी के बराबर तुलना करेंगे। नतीजतन, bisect_left() से bisect_right() आपको सूची में सभी पीटर्स युक्त श्रेणी प्रदान करेगा।

यह सब O(log n) तुलना का उपयोग करके किया जा सकता है।

Answer 2

अपनी बाइनरी खोज में आप या तो एक सटीक मैच या एक क्षेत्र जहां मैच होगा।
तो आपके मामले में आपको ऊपरी और निचली सीमाएं (hilo जैसे ही आप उन्हें कॉल करते हैं) प्राप्त करने की आवश्यकता है, उस क्षेत्र के लिए जिसमें Peter शामिल होगा और सभी मध्यवर्ती तारों को वापस कर दें।

लेकिन यदि आप एक शब्द के शो अगले शब्द की तरह कुछ करने के लिए उद्देश्य आप BSTs