वाइल्डकार्ड के साथ शब्द लुकअप के लिए कुशल डेटा संरचना

Question

मुझे शब्दों के एक बड़े शब्दकोष के खिलाफ उपयोगकर्ता इनपुट शब्दों की एक श्रृंखला से मिलान करने की आवश्यकता है (दर्ज मूल्य सुनिश्चित करने के लिए)।

तो अगर उपयोगकर्ता दर्ज किया गया:

"orange" it should match an entry "orange' in the dictionary. 

अब पकड़ कहना तरह

"or__ge" which would also match "orange" 

महत्वपूर्ण आवश्यकताओं हैं कि उपयोगकर्ता भी एक वाइल्डकार्ड या वाइल्डकार्ड वर्णों की श्रृंखला में प्रवेश कर सकते है:

* this should be as fast as possible. 

* use the smallest amount of memory to achieve it. 

यदि शब्द सूची का आकार छोटा था तो मैं सभी स्ट्रिंग वाले स्ट्रिंग का उपयोग कर सकता था ई शब्द और नियमित अभिव्यक्तियों का उपयोग करें।

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

तो क्या किसी प्रकार का 'पेड़' इस के लिए जाने का तरीका है ...?

इस पर किसी भी विचार या सुझाव की पूरी सराहना की जाएगी!

अग्रिम धन्यवाद, मैट

Answer 1

Appel and Jacobsen's paper on the World's Fastest Scrabble Program (कोलंबिया में free copy) में वर्णित अनुसार अपनी शब्द सूची को डीएडब्ल्यूजी (निर्देशित विश्वकोश शब्द ग्राफ) में रखें। आपकी खोज के लिए आप पॉइंटर्स के सेट को बनाए रखने वाले इस ग्राफ को पार करेंगे: एक पत्र पर, आप उस पत्र के साथ बच्चों को एक निर्धारिक संक्रमण करते हैं; वाइल्डकार्ड पर, आप सभी बच्चों को सेट में जोड़ते हैं।

दक्षता मोटे तौर पर जेआरपी के लिए थॉम्पसन की एनएफए व्याख्या के समान ही होगी (वे एक ही एल्गोरिदम हैं)। DAWG संरचना अत्यंत अंतरिक्ष-कुशल — केवल शब्दों को संग्रहीत करने से कहीं अधिक है। और इसे लागू करना आसान है।

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

वाइल्डकार्ड के मनमाना अनुक्रम से मिलान करना, उदाहरण के लिए, ______ हमेशा महंगी होने जा रहा है क्योंकि संयोजक रूप से कई समाधान हैं। दाग सभी समाधानों को बहुत जल्दी बताएगा।

Answer 2

मैं पहली बार regex समाधान का परीक्षण और देखें कि क्या यह पर्याप्त रूप से तेज़ होगा - आप हैरान हो सकता है! :-)

हालांकि अगर यह पर्याप्त नहीं था तो शायद मैं इसके लिए एक उपसर्ग पेड़ का उपयोग करूंगा।

• शीर्ष स्तर पर नोड्स के लिए सभी संभव पहले अक्षर (a-z संभालने आप एक पूर्ण शब्दकोश का उपयोग कर रहे हैं ... से अर्थात शायद 26 नोड्स) हैं:

  बुनियादी संरचना एक पेड़ जहां है।

• अगले स्तर नीचे प्रत्येक दिए गए पहले अक्षर
• और के लिए सभी संभव दूसरे पत्र में शामिल है इतने पर जब तक आप प्रत्येक शब्द

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

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

Answer 3

कोई फर्क नहीं पड़ता कि आप कौन सी एल्गोरिदम चुनते हैं, आपके पास गति और स्मृति खपत के बीच एक व्यापार है।

यदि आप ~ ओ (एन * एल) मेमोरी (जहां एन आपके शब्दकोश का आकार है और एल शब्द की औसत लंबाई है) खर्च कर सकते हैं, तो आप इसे बहुत तेज़ एल्गोरिदम का प्रयास कर सकते हैं। सादगी के लिए, शब्द की अधिकतम लंबाई के रूप में 26 अक्षरों और MAX_LEN के साथ लैटिन वर्णमाला मान लेंगे।

पूर्णांकों के सेट में से एक 2 डी सरणी बनाएँ, set<int> table[26][MAX_LEN].

प्रत्येक शब्द आप में शब्दकोश के लिए, शब्द के अक्षरों में से प्रत्येक के लिए इसी स्थिति में सेट करने के लिए शब्द सूचकांक जोड़ें। उदाहरण के लिए, यदि शब्दकोश में "नारंगी" 12345 वें शब्द है, तो आप [ओ] [0], [आर] [1], [ए] [2], [एन] से संबंधित सेट में 12345 जोड़ते हैं [ 3], [जी] [4], [ई] [5]।

फिर, "या..ge" से संबंधित शब्दों को पुनर्प्राप्त करने के लिए, आपको [ओ] [0], [आर] [1], [जी] [4], [ई] पर सेट का चौराहे मिलते हैं। [5]।

Answer 4

आप एक स्ट्रिंग-मैट्रिक्स की कोशिश कर सकते हैं:

0,1: A 
1,5: APPLE 
2,5: AXELS 
3,5: EAGLE 
4,5: HELLO 
5,5: WORLD 
6,6: ORANGE 
7,8: LONGWORD 
8,13:SUPERLONGWORD 

की, यह एक प्रचंड सूचकांक-मैट्रिक्स फोन कुछ स्मृति अतिरिक्त करते हैं। इसे लंबाई पर, और उसके बाद वर्णमाला क्रम पर ऑर्डर करें। किसी चरित्र को संबोधित करने के लिए मैं नोटेशन x,y:z: x का उपयोग करता हूं, सूचकांक y प्रविष्टि की लंबाई है, z स्थिति है। आपकी स्ट्रिंग की लंबाई f और g शब्दकोश में प्रविष्टियों की संख्या है।

• सूची m, जो संभावित मैच अनुक्रमित x शामिल बनाएँ।
• z पर 0 से f पर Iterate।
  • क्या यह वाइल्डकार्ड है और खोज स्ट्रिंग का नवीनतम चरित्र नहीं है?
    • जारी रखें लूप (सभी मैच)।
  • m खाली है?
    • कि लंबाई से मेल खाता है y के लिए g 0 से सब x के माध्यम से खोज। !!ए!!
      • क्या z चरित्र z पर खोज स्ट्रिंग के साथ मेल खाता है? xm में सहेजें।
    • m खाली है? ब्रेक लूप (कोई मिलान नहीं)।
  • m खाली नहीं है?
    • m के सभी तत्वों के माध्यम से खोजें। बी !! !!
      • खोज के साथ मिलान नहीं है? m से निकालें।
    • m खाली है? ब्रेक लूप (कोई मिलान नहीं)।

किसी वाइल्डकार्ड हमेशा "खोज स्ट्रिंग के साथ मैच?" पारित करेंगे। और m समान रूप से मैट्रिक्स के रूप में आदेश दिया गया है।

!! ए !!: Binary search खोज स्ट्रिंग की लंबाई पर। O(log n)
!! बी !!: वर्णानुक्रमिक क्रम पर बाइनरी खोज। O(log n)

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

Answer 5

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

आप केवल मिलान करने वाले शब्द हैं, इसलिए आप शब्दकोश को तारों की एक सरणी में तोड़ सकते हैं। चूंकि आप केवल ज्ञात लंबाई के खिलाफ सटीक मिलान कर रहे हैं, इसलिए प्रत्येक शब्द की लंबाई के लिए शब्द सरणी को एक अलग सरणी में विभाजित करें। तो बाईथेंथ [3] लंबाई 3 के साथ सभी शब्दों को सरणी है। प्रत्येक शब्द सरणी को सॉर्ट किया जाना चाहिए।

अब आपके पास शब्दों की एक सरणी है और संभावित जंगली कार्ड्स खोजने वाला शब्द है। गीलेर और जहां वाइल्डकार्ड हैं, के आधार पर कुछ दृष्टिकोण हैं।

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

यदि खोज शब्द में कुछ शाब्दिक पात्रों के बाद वाइल्डकार्ड हैं, तो ऊपरी और निचले बाउंड को खोजने के लिए क्रमबद्ध सरणी में बाइनरी खोज करें, फिर उस बाउंड में एक रैखिक खोज करें। यदि वाइल्डकार्ड सभी पीछे हैं तो एक खाली खाली सीमा खोजना पर्याप्त है।

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

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

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

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

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

Answer 6

Generalized Suffix Tree बनाने का प्रयास करें यदि शब्दकोश क्वेरी के अनुक्रम से मेल किया जाएगा। रैखिक समय एल्गोरिदम है जिसका उपयोग ऐसे पेड़ (Ukkonen Suffix Tree Construction) बनाने के लिए किया जा सकता है।

आप आसानी से मिलान कर सकते हैं (यह ओ (के) है, जहां के प्रश्न का आकार है) रूट क्वेरी नोड से ट्रैवर्स करके प्रत्येक क्वेरी, और वाइल्डकार्ड वर्ण का उपयोग किसी भी चरित्र से मेल खाने के लिए प्रत्यय पेड़ में विशिष्ट पैटर्न खोजना है।