जिसका कुंजी मैचों सबस्ट्रिंग

Question

मैं एक बड़ी शब्दकोश इतनी तरह का निर्माण किया है शब्दकोश आइटम खोजें:

programs['New York'] = 'some values...' 
programs['Port Authority of New York'] = 'some values...' 
programs['New York City'] = 'some values...' 
... 

मैं कैसे लौट सकते हैं सभी programs जिसका कुंजी का उल्लेख है "न्यू यॉर्क" (केस असंवेदी) - जो ऊपर के उदाहरण में , सभी तीन वस्तुओं को वापस कर देगा।

संपादित करें: शब्दकोश काफी बड़ा है और समय के साथ बड़ा होने की उम्मीद है।

Answer 1

[value for key, value in programs.items() if 'new york' in key.lower()] 

Answer 2

एक iteritems और एक जनरेटर अभिव्यक्ति ऐसा करेंगे:

d={'New York':'some values', 
    'Port Authority of New York':'some more values', 
    'New York City':'lots more values'} 

print list(v for k,v in d.iteritems() if 'new york' in k.lower())  

आउटपुट:

['lots more values', 'some more values', 'some values'] 

Answer 3

आप सभी सबस्ट्रिंग समय से आगे उत्पन्न कर सकता है, और उन्हें अपने-अपने चाबियाँ करने के लिए नक्शे।

#generates all substrings of s. 
def genSubstrings(s): 
    #yield all substrings that contain the first character of the string 
    for i in range(1, len(s)+1): 
     yield s[:i] 
    #yield all substrings that don't contain the first character 
    if len(s) > 1: 
     for j in genSubstrings(s[1:]): 
      yield j 

keys = ["New York", "Port Authority of New York", "New York City"] 
substrings = {} 
for key in keys: 
    for substring in genSubstrings(key): 
     if substring not in substrings: 
      substrings[substring] = [] 
     substrings[substring].append(key) 

तो फिर तुम substrings क्वेरी कर सकता है कुंजी है कि स्ट्रिंग शामिल पाने के लिए:

>>>substrings["New York"] 
['New York', 'Port Authority of New York', 'New York City'] 
>>> substrings["of New York"] 
['Port Authority of New York'] 

सकारात्मक:

-स्ट्रिंग द्वारा

• हो रही कुंजी एक शब्दकोश तक पहुँचने के रूप में के रूप में तेजी से होता है।

विपक्ष:

• substrings जनरेट कर रहा है अपने कार्यक्रम की शुरुआत में एक बार की लागत आती, programs में समय कुंजियों की संख्या के अनुपात में ले रही है।
• substringsprograms में कुंजियों की संख्या के साथ लगभग रैखिक रूप से बढ़ेगा, जिससे आपकी स्क्रिप्ट का स्मृति उपयोग बढ़ जाएगा।
• genSubstrings में आपकी कुंजी के आकार के संबंध में ओ (एन^2) प्रदर्शन है। उदाहरण के लिए, "पोर्ट अथॉरिटी ऑफ न्यूयॉर्क" 351 सबस्ट्रिंग उत्पन्न करता है।

Answer 4

आपको mensi द्वारा दी गई ब्रूट फोर्स विधि का उपयोग करना चाहिए जब तक कि यह बहुत धीमा न हो जाए।

यहां कुछ ऐसा है जो डेटा को एक तेज लुकअप देने के लिए डुप्लिकेट करता है। यह केवल तभी काम करता है जब आपकी खोज केवल पूरे शब्दों के लिए है - यानी आपको "न्यूयॉर्क के सर्वश्रेष्ठ बैगल्स" से मेल खाने की आवश्यकता नहीं होगी क्योंकि "यॉर्क" और "यॉर्क" अलग-अलग शब्द हैं।

words = {} 
for key in programs.keys(): 
    for w in key.split(): 
     w = w.lower() 
     if w not in words: 
      words[w] = set() 
     words[w].add(key) 


def lookup(search_string, words, programs): 
    result_keys = None 
    for w in search_string.split(): 
     w = w.lower() 
     if w not in words: 
      return [] 
     result_keys = words[w] if result_keys is None else result_keys.intersection(words[w]) 
    return [programs[k] for k in result_keys] 

शब्द अनुक्रम में होना है, तो (अर्थात "न्यूयॉर्क" से मेल नहीं होना चाहिए) आप result_keys की संक्षिप्त सूची के लिए जानवर बल विधि लागू कर सकते हैं।

Answer 5

इसे आमतौर पर एक आराम से शब्दकोश कहा जाता है और इसे प्रत्यय पेड़ का उपयोग करके कुशलतापूर्वक कार्यान्वित किया जा सकता है।

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

मुझे इस पुस्तकालय को अजगर में मिला है जो इसे लागू करता है।

https://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/