स्क्रैबल शब्द खोजक:एक ट्री का निर्माण, एक ट्री को स्टोर करना, एक ट्री का उपयोग करना?

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

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

एक ट्री मूल रूप से 26-आर्य पेड़ से ज्यादा कुछ नहीं है (मान लीजिए कि आप रोमन वर्णमाला का उपयोग कर रहे हैं) जहां प्रत्येक नोड में एक अक्षर होता है और प्रत्येक नोड पर एक अतिरिक्त बिट होता है जो कहता है कि यह शब्द का अंत है या नहीं।

तो चलिए डेटा संरचना को स्केच करते हैं:

class TrieNode
{
    char Letter;
    bool IsEndOfWord;
    List<TrieNode> children; 
}

यह निश्चित रूप से सिर्फ एक स्केच है; आप शायद इन्हें उचित संपत्ति एक्सेसर्स और कन्स्ट्रक्टर और क्या नहीं बनाना चाहते हैं। साथ ही, शायद एक फ्लैट सूची सर्वोत्तम डेटा संरचना नहीं है; शायद किसी प्रकार का शब्दकोश बेहतर है। मेरी सलाह है कि इसे पहले काम करें, और फिर इसके प्रदर्शन को मापें, और यदि यह अस्वीकार्य है, तो इसके प्रदर्शन को बेहतर बनाने के लिए परिवर्तन करने के साथ प्रयोग करें।

आप एक खाली ट्राई से शुरुआत कर सकते हैं:

TrieNode root = new TrieNode('^', false, new List<TrieNode>());

यानी, यह "रूट" ट्री नोड है जो किसी शब्द की शुरुआत का प्रतिनिधित्व करता है।

आप स्क्रैबल डिक्शनरी में पहला शब्द "एए" शब्द कैसे जोड़ते हैं? ठीक है, पहले पहले अक्षर के लिए एक नोड बनाएं:

root.Children.Add('A', false, new List<TrieNode>());

ठीक है, अब हमारी कोशिश है

^
|
A

अब दूसरे अक्षर के लिए एक नोड जोड़ें:

root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));

हमारी कोशिश अब है

^
|
A
|
A$   -- we notate the end of word flag with $

महान। अब मान लीजिए हम AB जोड़ना चाहते हैं। हमारे पास पहले से ही "A" के लिए एक नोड है, इसलिए इसमें "B$" नोड जोड़ें:

root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());

और अब हमारे पास है

    ^
    |
    A
   / \
  A$   B$

ऐसे ही चलते रहो। बेशक, "root.Children[0]..." लिखने के बजाय, आप एक लूप लिखेंगे जो ट्री को यह देखने के लिए खोजता है कि आप जो नोड चाहते हैं वह मौजूद है या नहीं, और यदि नहीं, तो इसे बनाएं।

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

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

मुझे एक कार्यात्मक-शैली की लगातार कोशिश का कार्यान्वयन मिला है जिसका अर्थ है कि मैं थोड़ी देर के लिए ब्लॉग करना चाहता हूं लेकिन इसके आसपास कभी नहीं मिला। अगर मैं अंततः पोस्ट करता हूं तो मैं इस प्रश्न को अपडेट कर दूंगा।