दो शब्दों के बीच आसन्न शब्दों की एक सूची ढूँढना

Question

मैं अभ्यास के लिए एक प्रोग्रामिंग चुनौती पर काम कर रहा हूं और समाधान को लागू करने के लिए उपयोग करने के लिए एक अच्छी डेटा संरचना/एल्गोरिदम खोजने में परेशानी हो रही है।

पृष्ठभूमि:

कॉल दो शब्दों "आसन्न" अगर आप बताया हटाने, या एक भी पत्र बदलकर दूसरे में एक शब्द बदल सकते हैं।

एक "शब्द सूची" अद्वितीय शब्दों की एक आदेशित सूची है जहां लगातार शब्द निकट हैं।

समस्या:

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

उदाहरण:

hate → love:  hate, have, hove, love 
dogs → wolves: dogs, does, doles, soles, solves, wolves 
man → woman: man, ran, roan, roman, woman 
flour → flower: flour, lour, dour, doer, dower, lower, flower 

मैं काफी यकीन है कि कैसे इस समस्या दृष्टिकोण नहीं हूँ, मेरा पहला प्रयास तो पहला शब्द के क्रमपरिवर्तन बनाने में पत्र बदलने का प्रयास करने शामिल किया गया। मेरा दूसरा विचार शायद suffix tree

कम से कम समस्या को तोड़ने के लिए कोई विचार या विचारों की सराहना की जाएगी। ध्यान रखें कि यह होमवर्क नहीं है, लेकिन एक प्रोग्रामिंग चुनौती मैं अपने आप पर काम कर रहा हूं।

Answer 1

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

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

मैं इस समस्या पर चर्चा करता हूं, और एक कार्यान्वयन देता हूं जिसमें my blog पर "आसन्न" शब्दों की पहचान करने के लिए एक चालाक एल्गोरिदम शामिल है।

Answer 2

सरल (पुनरावर्ती) एल्गोरिथ्म मैं के बारे में सोच सकते हैं (अच्छी तरह से, केवल एक ही मैं इस पल में सोच सकते हैं)

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

शायद थोड़ा और समय इस बात के लिए गहरे लाल रंग का कोड जोड़ सकते हैं के साथ किसी?

Answer 3

मुझे नहीं पता कि यह किस प्रकार का समाधान है जिसे आप ढूंढ रहे हैं, लेकिन अनुसंधान का एक सक्रिय क्षेत्र निकटवर्ती शब्दों को देखने के लिए "दूरी 1 संपादित करें" शब्दकोशों का निर्माण करने में है (आपके अनुष्ठान का उपयोग करने के लिए) खोज शब्द के सुझावों के लिए, डेटा प्रविष्टि सुधार, और जैव सूचना विज्ञान (उदाहरण के लिए गुणसूत्रों में समानताएं ढूंढना)। उदाहरण के लिए देखें this research paper। अपने पूरे शब्दकोश को अनुक्रमणित करने से कम, कम से कम यह एक खोज हेरिस्टिक का सुझाव दे सकता है जिसका आप उपयोग कर सकते हैं।

Answer 4

मैंने इसे स्वयं किया है और इसे विंडोज़ गेम (बहुत अच्छा नहीं) बनाने के लिए इस्तेमाल किया है।

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

मुश्किल हिस्सा ग्राफ का निर्माण कर रहा है। बुरी खबर यह है कि यह ओ (एन^2) है। अच्छी खबर यह है कि इसे वास्तविक समय में नहीं किया जाना चाहिए - आपके प्रोग्राम के बजाय फ़ाइल से शब्दकोष शब्द पढ़ना, यह आपके द्वारा पहले की गई डेटा संरचना में पढ़ता है।

मुख्य अंतर्दृष्टि यह है कि आदेश कोई फर्क नहीं पड़ता, वास्तव में यह रास्ते में आता है। आपको एक और फॉर्म बनाने की आवश्यकता है जिसमें ऑर्डर जानकारी को स्ट्रिप करने वाले शब्दों को पकड़ने के लिए और शब्दों की तुलना आसानी से की जा सके। आप इसे ओ (एन) में कर सकते हैं। आपके पास बहुत सारे विकल्प हैं; मैं दो दिखाऊंगा।

1. शब्द पहेली के लिए मैं अक्सर एक एन्कोडिंग का उपयोग करता हूं जिसे मैं एनाग्राम शब्दकोश कहता हूं। एक शब्द को दूसरे शब्द द्वारा दर्शाया जाता है जिसमें एक ही अक्षर होते हैं लेकिन वर्णमाला अनुक्रम में। तो "कार" "acrs" बन जाती है। दोनों सूचियां और स्लिट "ilsst" बन जाते हैं। यह मूल शब्द की तुलना में तुलना के लिए एक बेहतर संरचना है, लेकिन बहुत बेहतर तुलना मौजूद है (हालांकि, यह अन्य शब्द पहेली के लिए एक बहुत ही उपयोगी संरचना है)।

2. पत्र मायने रखता है। 26 मानों की एक सरणी जो शब्द में उस पत्र की आवृत्ति दिखाती है। तो "कारों" के लिए यह 1,0,1,0,0 शुरू होता है ... क्योंकि एक "ए" और एक "सी" होता है। गैर-शून्य प्रविष्टियों की एक बाहरी सूची (शब्द में कौन से अक्षर दिखाई देते हैं) को पकड़ें ताकि आपको केवल 26 के बजाय 5 या 6 मानों की जांच करनी पड़े। इस फ़ॉर्म में दो शब्दों को जल्दी से दो शब्दों की तुलना करना बहुत आसान है गणना अलग हैं। यह वह है जिसका मैं उपयोग करूंगा।

तो, मैंने यह किया है।

मैंने एक कार्यक्रम लिखा जिसने उपरोक्त डेटा संरचना को लागू किया।

इसमें वर्ड नोड नामक एक कक्षा थी। इसमें मूल शब्द है; अन्य सभी वर्ड नोड्स की एक सूची जो एक पत्र अलग हैं; प्रत्येक पत्र की आवृत्ति देकर 26 पूर्णांक की एक सरणी, अक्षर गणना सरणी में गैर-शून्य मानों की एक सूची।

प्रारंभकर्ता अक्षर आवृत्ति सरणी और गैर-शून्य मानों की इसी सूची को पॉप्युलेट करता है। यह जुड़े वर्ड नोड्स की सूची शून्य पर सेट करता है।

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

इसका मतलब है कि अब हमारे पास सभी शब्दों का एक ग्राफ अलग है।

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

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

दयालुता मेरा खेल बकवास था।

Answer 5

इस

x = 'hate' 
puts x = x.next until x == 'love' 

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