Knuth-Morris-Pratt और Boyer-Moore खोज एल्गोरिदम के बीच मुख्य अंतर क्या हैं?

Question

नुथ-मॉरिस-प्रैट खोज एल्गोरिथ्म और बोयर-मूर खोज एल्गोरिथ्म के बीच मुख्य अंतर क्या हैं?

मुझे पता है केएमपी वाई में वाई के लिए खोज, वाई में एक पैटर्न को परिभाषित करने की कोशिश कर रहा है, और एक वेक्टर में पैटर्न बचाता है। मुझे यह भी पता है कि बीएम छोटे शब्दों, जैसे डीएनए (ACTG) के लिए बेहतर काम करता है।

वे कैसे काम करते हैं में मुख्य अंतर क्या हैं? कौन सा तेज़ है? कौन सा कंप्यूटर लालची है? किस मामले में?

Answer 1

Moore's UTexas webpage एक कदम-दर-कदम फैशन में दोनों एल्गोरिदम के माध्यम से चलता है के लिए अनुकूल है (वह भी विभिन्न तकनीकी स्रोतों प्रदान करता है) :

• Knuth-Morris-Pratt
• Boyer-Moore

आदमी स्वयं के अनुसार,

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

हालांकि, कुछ modifications of BM हैं जिन्होंने छोटे-वर्णमाला खोज को व्यवहार्य बना दिया है।

Answer 2

एक किसी न किसी स्पष्टीकरण में

बोयर-मूर की दृष्टिकोण के बजाय इस धारणा के साथ पहली बार एक के पैटर्न के अंतिम वर्ण से मेल करने के लिए प्रयास करने के लिए है कि अगर वहाँ अंत में करने की कोशिश करने की कोई जरूरत से मेल नहीं है शुरुआत में मैच। यह "बड़ी छलांग" इसलिए बी.एम. बेहतर काम करता है जब पैटर्न और पाठ आप जैसे लगते हैं "प्राकृतिक पाठ" (यानी अंग्रेजी) खोज रहे हैं

नुथ-मॉरिस-प्रैट एक "शब्द" की घटनाओं के लिए खोजों के लिए अनुमति देता है अवलोकन को नियोजित करके मुख्य "टेक्स्ट स्ट्रिंग" एस के भीतर डब्लू डब्ल्यू जब एक मेल नहीं खाता है, तो शब्द यह निर्धारित करने के लिए पर्याप्त जानकारी देता है कि अगला मैच कहां से शुरू हो सकता है, इस प्रकार पहले मिलान किए गए पात्रों की पुन: परीक्षा को छोड़कर। (स्रोत: Wiki)

इसका मतलब यह है KMP बेहतर डीएनए (ACTG) जैसे छोटे सेट

Answer 3

बॉयर-मूर तकनीक वर्णों से दाएं से बाएं से मेल खाती है, लंबे पैटर्न पर अच्छी तरह से काम करती है। knuth moris pratt बाएं से दाएं वर्णों से मेल खाता है, छोटे पैटर्न पर तेज़ी से काम करता है।