जानकारी खोजने के कार्यों में, सबसे महत्वपूर्ण कार्यों में से एक स्ट्रिंग में ठीक से दिए गए प्रतिस्थापन की खोज करना है। एक स्ट्रिंग में एक विकल्प के लिए आदिम खोज एल्गोरिथ्म सभी सब्सट्रिंग्स की गणना पर आधारित है, जिसकी लंबाई खोज पैटर्न की लंबाई के बराबर है, और इस तरह के सब्सट्रिंग्स की चरित्र-दर-खोज खोज पैटर्न के साथ तुलना की जाती है। परंपरा के अनुसार, यह एक खोज पैटर्न या पैटर्न को सुई (अंग्रेजी "सुई") के रूप में निर्दिष्ट करने के लिए प्रथागत है, और वह रेखा जिसमें खोज को हिस्टैक (अंग्रेजी "हैस्टैक") के रूप में संचालित किया जाता है। पायथन में, एक आदिम एल्गोरिथ्म इस तरह दिखता है:
index = -1 for i in xrange(len(haystack)-len(needle)+1): success = True for j in xrange(len(needle)): if needle[j]<>haystack[i+j]: success = False break if success: index = i break print index
Denote n = | haystack |, m = | सुई | सबसे अच्छा खोज एल्गोरिथ्म, यहां तक कि सबसे अच्छे मामले में, n - m + 1 तुलना करता है; यदि कई आंशिक मैच हैं, तो गति O (n * m) तक गिर जाती है।
नीचे दिए गए एल्गोरिथ्म पर विचार किया जाता है, हालांकि इसमें "अच्छे" डेटा की कम गति है, "खराब" डेटा पर प्रतिगमन की अनुपस्थिति से मुआवजा दिया जाता है। नट-मॉरिस-प्रैट एल्गोरिथ्म पहले सबसे खराब स्थिति रैखिक अनुमान एल्गोरिदम में से एक है।
एल्गोरिथ्म के वर्णन के लिए आगे बढ़ने से पहले, एक उपसर्ग फ़ंक्शन की अवधारणा पर विचार करना आवश्यक है।
स्ट्रिंग (S, i) का उपसर्ग फ़ंक्शन स्ट्रिंग S [1..i] के सबसे बड़े उपसर्ग की लंबाई है, जो इस स्ट्रिंग के साथ मेल नहीं खाता है और एक ही समय में इसका प्रत्यय है। सीधे शब्दों में कहें, यह एक पंक्ति की सबसे लंबी शुरुआत की लंबाई है, जो इसका अंत भी है। स्ट्रिंग S के लिए, लंबाई के वेक्टर के रूप में उपसर्ग फ़ंक्शन का प्रतिनिधित्व करना सुविधाजनक है। S | -1 | हम लंबाई के उपसर्ग समारोह पर विचार कर सकते हैं | S | π (S, 1) = 0 सेट करके। स्ट्रिंग "abcdabcabcdabcdab" के लिए उदाहरण फ़ंक्शन उपसर्ग:
| S [i] | एक | ख | ग | घ | एक | ख | ग | एक | ख | ग | घ | एक | ख | ग | घ | एक | ख |
| i (एस, आई) | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 4 | 5 | 6 |
मान लीजिए कि π (एस, आई) = के। उपसर्ग फ़ंक्शन के निम्नलिखित गुणों पर ध्यान दें।
- यदि S [i + 1] = S [k + 1], तो S (S, i + 1) = k + 1।
- S [1.. suff (S, k)] स्ट्रिंग S [1..i] का प्रत्यय है। दरअसल, अगर स्ट्रिंग S [1..i] स्ट्रिंग S [1 ... S (S, i)] = S [1..k] के साथ समाप्त होता है, और स्ट्रिंग S [1..k] स्ट्रिंग S [1.. S के साथ समाप्त होता है (एस, के)], फिर लाइन S [1..i] लाइन S [1..π (S, k)] के साथ समाप्त होती है।
- ∀ j 1. (k, i), S [1..j] स्ट्रिंग S [1..i] का प्रत्यय नहीं है। अन्यथा, धारणा π (S, i) = k झूठी होगी, क्योंकि j> k
माना गया गुण उपसर्ग फ़ंक्शन की गणना के लिए एक एल्गोरिथ्म प्राप्त करना संभव बनाता है।
आज्ञा देना Let (S, i) = k Π (एस, आई + 1) की गणना करना आवश्यक है।
- यदि S [i + 1] = S [k + 1], तो S (S, i + 1) = k + 1।
- अन्यथा, यदि k = 0, तो π (S, i + 1) = 0।
- अन्यथा, k: = π (S, k) डालें और चरण 1 पर जाएं।
एल्गोरिथ्म के सार को समझने की कुंजी यह तथ्य है कि यदि पिछले चरण में पाए गए प्रत्यय को अगली स्थिति में विस्तारित नहीं किया जा सकता है, तो हम यथासंभव छोटे प्रत्ययों पर विचार करने का प्रयास करते हैं।
पायथन में एक उपसर्ग समारोह की गणना के लिए एल्गोरिथ्म:
def prefix(s): v = [0]*len(s) for i in xrange(1,len(s)): k = v[i-1] while k > 0 and s[k] <> s[i]: k = v[k-1] if s[k] == s[i]: k = k + 1 v[i] = k return v
हम दिखाते हैं कि एल्गोरिथ्म का रनिंग टाइम O (n) है, जहाँ n = | S | ध्यान दें कि एल्गोरिथ्म के स्पर्शोन्मुख व्यवहार को लूप के पुनरावृत्तियों की कुल संख्या से निर्धारित किया जाता है। ऐसा इसलिए है क्योंकि लूप को ध्यान में रखे बिना, लूप के लिए प्रत्येक पुनरावृत्ति एक समय में किया जाता है जो एक स्थिर से अधिक नहीं होता है। चक्र के प्रत्येक पुनरावृत्ति पर, k के लिए एक से अधिक नहीं बढ़ता है, जिसका अर्थ है अधिकतम संभव मान k = n - 1। चूँकि k का मान केवल लूप के अंदर कम हो जाता है, इसलिए यह पता चलता है कि k कुल n - 1 से अधिक बार घट नहीं सकता है। इसका मतलब यह है कि जबकि लूप को अंततः n से अधिक बार निष्पादित नहीं किया जाएगा, जो O (n) एल्गोरिथ्म के समय का अंतिम अनुमान देता है।
उपसर्ग फ़ंक्शन के उपयोग के आधार पर नथ-मॉरिस-प्रैट एल्गोरिथ्म पर विचार करें। जैसे कि आदिम स्थानापन्न खोज एल्गोरिथ्म में, पैटर्न एक मैच का पता लगाने के लिए बाएं से दाएं की रेखा के साथ "चलता है"। हालांकि, महत्वपूर्ण अंतर यह है कि उपसर्ग फ़ंक्शन की मदद से, हम जानबूझकर बेकार बदलावों से बच सकते हैं।
S [0..m - 1] को नमूना होने दें, T [0..n - 1] वह स्ट्रिंग जिसमें खोज की जाती है। स्थिति i पर पंक्तियों की तुलना पर विचार करें, अर्थात, पैटर्न S [0..m - 1] को स्ट्रिंग T [i..i + m - 1] के भाग में मैप किया जाता है। मान लीजिए कि पहला बेमेल S [j] और T [i + j] अक्षर के बीच हुआ है, जहां i <j <m है। Denote P = S [0..j - 1] = T [i..i + j - 1]। शिफ्ट करते समय, हम यह उम्मीद कर सकते हैं कि उपसर्ग S, स्ट्रिंग P के कुछ प्रत्यय के साथ अभिसरण करता है। चूंकि सबसे लंबे उपसर्ग की लंबाई, जो कि एक प्रत्यय भी है, सूचकांक j के लिए स्ट्रिंग S का एक उपसर्ग कार्य है, हम निम्नलिखित एल्गोरिथ्म में आते हैं:
- नमूना एस के उपसर्ग समारोह का निर्माण, एफ द्वारा इसे निरूपित करें।
- K = 0, i = 0 रखो।
- अक्षर S [k] और T [i] की तुलना करें। यदि वर्ण बराबर होते हैं, तो k 1 से बढ़ाएं। यदि एक ही समय में k नमूना की लंबाई के बराबर हो जाता है, तो स्ट्रिंग T में नमूना S की घटना पाई जाती है, घटना का सूचकांक i है - S | | + 1. एल्गोरिथ्म समाप्त होता है। यदि वर्ण समान नहीं हैं, तो फेरबदल का अनुकूलन करने के लिए उपसर्ग फ़ंक्शन का उपयोग करें। जब तक k> 0, k = F [k - 1] असाइन करें और चरण 3 की शुरुआत में जाएं।
- जबकि मैं <| T | 1 से बढ़ाता हूं और चरण 3 पर जाता हूं।
पायथन में नट-मॉरिस-प्रैट एल्गोरिथ्म का एक संभावित कार्यान्वयन इस तरह दिखता है:
def kmp(s,t): index = -1 f = prefix(s) k = 0 for i in xrange(len(t)): while k > 0 and s[k] <> t[i]: k = f[k-1] if s[k] == t[i]: k = k + 1 if k == len(s): index = i - len(s) + 1 break return index