सरलीकृत बॉयर-मूर एल्गोरिदम

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

एल्गोरिथ्म

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

ऑफसेट तालिका

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

चित्रण

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

s->5
t->4
r->3
i->2
n->1
g->6

अब हमारी लाइनों को संयोजित करें:
somestring
string

अंतिम वर्णों की तुलना करें: हम देखते हैं कि "t" "g" के बराबर नहीं है। हम "t" प्रतीक के लिए ऑफसेट मान लेते हैं। यह 4 है। हम पंक्ति को दाईं ओर 4 स्थिति में स्थानांतरित करते हैं, और वॉइला:

somestring
string

अगला, एल्गोरिथ्म स्रोत स्ट्रिंग में संबंधित वर्णों के साथ टेम्पलेट में पिछले से लेकर पहले तक के पात्रों की तुलना करेगा। जैसे ही वह बाद की तुलना करता है, यह पता चलेगा कि यह पहली घटना है।

कोड

इस सिद्धांत को मसाला देने के लिए कुछ जावा कोड लिखे। किसी भी टिप्पणी का स्वागत है।

 /** *      template   source,  * -1,      . * * @param source *  ,     . * @param template *  ,     source. * @return     template   source,  -1, *      . */ public int getFirstEntry(String source, String template) { int sourceLen = source.length(); int templateLen = template.length(); if (templateLen > sourceLen) { return -1; } HashMap<Character, Integer> offsetTable = new HashMap<Character, Integer>(); for (int i = 0; i <= 255; i++) { offsetTable.put((char) i, templateLen); } for (int i = 0; i < templateLen - 1; i++) { offsetTable.put(template.charAt(i), templateLen - i - 1); } int i = templateLen - 1; int j = i; int k = i; while (j >= 0 && i <= sourceLen - 1) { j = templateLen - 1; k = i; while (j >= 0 && source.charAt(k) == template.charAt(j)) { k--; j--; } i += offsetTable.get(source.charAt(i)); } if (k >= sourceLen - templateLen) { return -1; } else { return k + 1; } } 

निष्कर्ष

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