वाइल्डकार्ड के साथ स्क्रैबल शब्द खोजक

आप नहीं। एक संबंधपरक डेटाबेस तालिका इस समस्या को उतनी कुशलता से हल करने के लिए उपयुक्त डेटा संरचना नहीं है जितनी आपको चाहिए।

इसके बजाय आप एक trie बनाते हैं। शब्दकोश से बाहर डेटा संरचना (या, यदि आप वास्तव में शौकीन हैं, तो आप एक dawg बनाते हैं -- एक निर्देशित विश्वकोश शब्द ग्राफ़ -- जो एक प्रकार का संपीडित त्रिभुज है।)

एक बार जब आपके पास एक ट्री/डॉग होता है तो हर . का परीक्षण करना बहुत सस्ता हो जाता है किसी दिए गए रैक के खिलाफ शब्दकोश में शब्द, क्योंकि आप शब्दकोश की पूरी विशाल शाखाओं को "छंटनी" कर सकते हैं जो रैक संभवतः मेल नहीं खा सकता है।

आइए एक छोटा सा उदाहरण देखें। मान लीजिए कि आपके पास "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" शब्दकोश है, जिससे आप इस त्रिभुज का निर्माण करते हैं:($ वाले नोड्स वे हैं जिन्हें "शब्द यहां समाप्त हो सकता है" के रूप में चिह्नित किया गया है। ।

           ^root^
           /  |  \
         O    P    S
         |    |   / \
         P$   O  O   T   
        / \   |  |   |
       T$  S$ T$ P$  O
       |      |  |   |
       S$     S$ S$  P$
                     |
                     S$

और आपके पास रैक "OPS" है -- आप क्या करते हैं?

पहले आप कहते हैं, "क्या मैं ओ शाखा के नीचे जा सकता हूँ?" हाँ आप कर सकते हैं। तो अब समस्या ओ शाखा के खिलाफ "पीएस" से मेल खा रही है। क्या आप P उपशाखा से नीचे जा सकते हैं? हां। क्या इसमें शब्द का अंत मार्कर है? हाँ, तो ओपी एक मैच है। अब समस्या ओपी शाखा के खिलाफ "एस" से मेल खा रही है। क्या आप टी शाखा से नीचे जा सकते हैं? नहीं। क्या आप S शाखा से नीचे जा सकते हैं? हां। अब आपके पास खाली रैक है और आपको इसे OPS शाखा से मिलाना है। क्या इसमें शब्द का अंत मार्कर है? हां! तो ओपीएस भी मेल खाता है। अब जड़ तक वापस जाएँ।

क्या आप पी शाखा से नीचे जा सकते हैं? हां। अब समस्या OS को P शाखा से मिलाने की है। पीओ शाखा के नीचे जाएं और एस का मिलान करें - जो विफल हो जाता है। रूट पर वापस जाएं।

और फिर, आप देखते हैं कि यह कैसे जाता है। आखिरकार हम एसओपी शाखा में जाते हैं और एसओपी पर अंतिम शब्द ढूंढते हैं, इसलिए "एसओपी" इस रैक से मेल खाता है। हम एसटी शाखा में नहीं जाते क्योंकि हमारे पास टी नहीं है।

हमने शब्दकोश में हर संभव शब्द की कोशिश की है और पता चला है कि ओपी, ओपीएस और एसओपी सभी मेल खाते हैं। लेकिन हमें कभी भी OPTS, POTS, STOP या STOPS की जांच नहीं करनी पड़ी क्योंकि हमारे पास T नहीं था।

आप देखते हैं कि यह डेटा संरचना कैसे इसे बहुत कुशल बनाती है? एक बार जब आप यह निर्धारित कर लें कि आपके पास शुरुआत . करने के लिए रैक पर अक्षर नहीं हैं एक शब्द के लिए, आपको किसी . की जांच करने की आवश्यकता नहीं है शब्दकोश शब्द जो उस शुरुआत से शुरू होते हैं। यदि आपके पास PO है लेकिन T नहीं है, तो आपको POTSHERD या POTATO या POTASH या POTLATCH या POTABLE की जांच करने की आवश्यकता नहीं है; वे सभी महंगी और निष्फल खोजें बहुत जल्दी चली जाती हैं।

"जंगली" टाइलों से निपटने के लिए सिस्टम को अपनाना बहुत सीधा है; यदि आपके पास ओपीएस है?, तो ओपीएसए, ओपीएसबी, ओपीएससी पर 26 बार खोज एल्गोरिथम चलाएं ... )

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

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

आप ट्री के बाहर एक DAWG बनाकर मेमोरी उपयोग को अनुकूलित कर सकते हैं। ध्यान दें कि कैसे बहुत अधिक दोहराव होता है क्योंकि अंग्रेज़ी में बहुत सारे शब्द समाप्त . होते हैं वही, जैसे बहुत सारे शब्द शुरू होते हैं वही। ट्री शुरुआत में नोड्स को साझा करने का एक अच्छा काम करता है लेकिन अंत में उन्हें साझा करने का एक घटिया काम करता है। उदाहरण के लिए आप देख सकते हैं कि "S$ विद नो चिल्ड्रन" पैटर्न बेहद सामान्य है, और ट्री को इसमें बदल दें:

           ^root^
          / |  \
        O   P    S
        |   |   / \
        P$  O  O   T   
       /  \ |  |   |
      T$  | T$ P$  O
      |    \ | |   |
       \    \| /   P$
        \    |/    |
         \   |    /
          \  |   /  
           \ |  /
            \| /  
             |/
             |       
             S$

नोड्स का एक पूरा ढेर सहेजा जा रहा है। और फिर आप देख सकते हैं कि दो शब्द अब O-P$-S$ में समाप्त होते हैं, और दो शब्द T$-S$ में समाप्त होते हैं, इसलिए आप इसे और अधिक संकुचित कर सकते हैं:

           ^root^
           / | \
          O  P  S
          |  | / \
          P$ O \  T   
         /  \|  \ |
         |   |   \|
         |   |    O
         |   T$   |
          \  |    P$
           \ |   /
            \|  /  
             | /
             |/   
             S$

और अब हमारे पास इस शब्दकोश के लिए न्यूनतम DAWG है।

आगे पढ़ना:

http://dl.acm.org/citation.cfm?id=42420

http://archive.msdn.microsoft.com/dawg1

http://www.gtoal.com/wordgames/scrabble.html