स्ट्रिंग मिलान
स्ट्रिंग मिलान एक टेक्स्ट के भीतर एक पैटर्न के सभी घटनाओं को ढूंढता है; क्लासिक एल्गोरिदम अनावश्यक तुलनाओं को छोड़ने और रैखिक या उप-रैखिक खोज समय प्राप्त करने के लिए पैटर्न को पूर्व-संसाधित करते हैं।
Definition
स्ट्रिंग मिलान एक टेक्स्ट में उन सभी स्थितियों को खोजने की समस्या है जहाँ एक दिया गया पैटर्न स्ट्रिंग होता है; एक सटीक स्ट्रिंग-मिलान एल्गोरिदम हर उस ऑफसेट की रिपोर्ट करता है जिस पर पैटर्न टेक्स्ट के एक सबस्ट्रिंग के साथ समान रूप से संरेखित होता है।
Scope
यह विषय सटीक एकल-पैटर्न मिलान एल्गोरिदम को कवर करता है — भोली विधि, नुथ-मॉरिस-प्रैट, बोयर-मूर, और हैशिंग-आधारित राबिन-कार्प — उनके पूर्व-संसाधन (विफलता कार्य, शिफ्ट टेबल, रोलिंग हैश) के साथ जो उन्हें कुशल बनाता है, और अहो-कोरासिक ऑटोमेटन के माध्यम से बहु-पैटर्न मिलान के विस्तार को भी। अनुमानित मिलान और अनुक्रमणिका-आधारित खोज संबंधित विषयों में शामिल हैं।
Core questions
- भोली मिलान में पैटर्न और टेक्स्ट की लंबाई के गुणनफल के समानुपाती समय क्यों लगता है?
- पैटर्न को पूर्व-संसाधित करने से टेक्स्ट वर्णों की पुनः जांच से कैसे बचा जा सकता है?
- नुथ-मॉरिस-प्रैट विफलता कार्य और बोयर-मूर शिफ्ट नियम कैसे काम करते हैं?
- राबिन-कार्प संरेखण का तेजी से परीक्षण करने के लिए हैशिंग का उपयोग कैसे करता है?
- एक साथ कई पैटर्न के लिए मिलान को कैसे बढ़ाया जाता है?
Key concepts
- भोली मिलान
- नुथ-मॉरिस-प्रैट एल्गोरिदम
- विफलता कार्य
- बोयर-मूर एल्गोरिदम
- खराब-वर्ण और अच्छे-प्रत्यय नियम
- राबिन-कार्प एल्गोरिदम
- रोलिंग हैश
- अहो-कोरासिक ऑटोमेटन
Key theories
- नुथ-मॉरिस-प्रैट विफलता कार्य
- प्रत्येक पैटर्न उपसर्ग के लिए, सबसे लंबे उचित उपसर्ग की पूर्व-गणना करके जो एक प्रत्यय भी है, नुथ-मॉरिस-प्रैट एल्गोरिदम एक बेमेल के बाद पैटर्न को बुद्धिमानी से स्थानांतरित करता है और कभी भी टेक्स्ट वर्णों की पुनः जांच नहीं करता है, जिससे रैखिक-समय मिलान होता है।
- बोयर-मूर दाएँ-से-बाएँ स्कैनिंग
- बोयर-मूर पैटर्न की तुलना उसके अंतिम वर्ण से पीछे की ओर करता है और टेक्स्ट के बड़े हिस्सों को छोड़ने के लिए खराब-वर्ण और अच्छे-प्रत्यय नियमों का उपयोग करता है, जिससे विशिष्ट इनपुट पर उप-रैखिक औसत-केस प्रदर्शन प्राप्त होता है।
Clinical relevance
स्ट्रिंग मिलान रोजमर्रा के उपकरणों और बुनियादी ढांचे का आधार है: टेक्स्ट संपादकों और कमांड-लाइन उपयोगिताओं में खोज, सामग्री फ़िल्टरिंग और घुसपैठ-पहचान हस्ताक्षर स्कैनिंग, साहित्यिक चोरी का पता लगाना, और जैविक अनुक्रमों में रूपांकनों का स्थान। बहु-पैटर्न मिलान इन सभी को एक साथ कई पैटर्न के शब्दकोशों तक बढ़ाता है।
History
नुथ-मॉरिस-प्रैट एल्गोरिदम (1977 में प्रकाशित, पहले विकसित) ने पहला व्यापक रूप से ज्ञात रैखिक-समय सटीक मिलानकर्ता दिया, और बोयर और मूर (1977) ने उसी वर्ष उप-रैखिक औसत-केस मिलान पेश किया। राबिन और कार्प का हैशिंग दृष्टिकोण और अहो-कोरासिक बहु-पैटर्न ऑटोमेटन (1975) ने इस क्षेत्र को और विस्तृत किया।
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Michael Rabin
- Richard Karp
Related topics
Seminal works
- knuth1977
- boyer1977
- cormen2009
Frequently asked questions
- कौन सा सटीक स्ट्रिंग-मिलान एल्गोरिदम सबसे तेज़ है?
- यह इनपुट पर निर्भर करता है। नुथ-मॉरिस-प्रैट रैखिक सबसे खराब स्थिति वाले समय की गारंटी देता है; बोयर-मूर अक्सर प्राकृतिक टेक्स्ट पर व्यवहार में सबसे तेज़ होता है क्योंकि यह वर्णों को छोड़ देता है और औसतन उप-रैखिक रूप से चलता है; राबिन-कार्प तब चमकता है जब कई पैटर्न की खोज की जाती है या फिंगरप्रिंट तुलना की जाती है। कोई एक सार्वभौमिक विजेता नहीं है।
- राबिन-कार्प हर स्थिति में हर वर्ण की तुलना करने से कैसे बचता है?
- यह पैटर्न और समान लंबाई की प्रत्येक टेक्स्ट विंडो को एक रोलिंग हैश का उपयोग करके हैश करता है जो विंडो के स्लाइड होने पर स्थिर समय में अपडेट होता है। केवल जब हैश मेल खाते हैं तो यह वास्तविक वर्णों को सत्यापित करता है, इसलिए अधिकांश गैर-मिलान वाली स्थितियों को एक ही सस्ती तुलना द्वारा अस्वीकार कर दिया जाता है।