स्ट्रिंग-सर्चिंग एल्गोरिदम

कंप्यूटर विज्ञान में, स्ट्रिंग-विवृत्त कलन-विधि, कभी-कभी स्ट्रिंग-मैचिंग कलन-विधि के रूप में जाने जाते हैं, स्ट्रिंग कलन-विधि की एक महत्वपूर्ण श्रेणी हैं, जो एक या एक से अधिक स्ट्रिंग को एक बड़े स्ट्रिंग या पाठ में ढूंढने का प्रयास करते हैं।

स्ट्रिंग विवृत्त का एक मूलभूत उदाहरण होता है जब पैटर्न और विवृत्त ी गई टेक्स्ट एक वर्णमाला Σ के तत्वों के सारणी, होते हैं। Σ मानवीय भाषा वर्णमाला हो सकता है, उदाहरण के लिए, A से Z तक के अक्षर और अन्य एप्लिकेशन द्वारा बाइनरी वर्णमाला (Σ = {0,1}) या जैवविज्ञान में डीएनए वर्णमाला (Σ = {A,C,G,T}) का उपयोग कर सकते हैं।

व्यावहारिकता में, संभवतः स्ट्रिंग-विवृत्त कलन-विधि के तरीके को स्ट्रिंग एनकोडिंग प्रभावित कर सकते हैं। विशेष रूप से, यदि एक परिवर्तनशील-चौड़ाई एनकोडिंग का उपयोग हो रहा है, तो एनवेती वाले वर्ण को ढूंढने में धीमा हो सकता है,प्रायः N के प्रस्ताव समय की आवश्यकता हो सकती है। इससे कुछ विवृत्त कलन-विधि को काफी धीमा कर सकता है। इसमें एक संभवतः हल कई संभावित समाधानों में से एक है, जिसमें कोड इकाइयों के अनुक्रम की विवृत्त की जाती है, लेकिन ऐसा करने से यदि एनकोडिंग इसे टालने के लिए विशेष रूप से आरेखित नहीं की गई है, तो यह गलत मिलान प्रदर्शित कर सकता है।

अवलोकन

स्ट्रिंग विवृत्त का सबसे मूल स्थिति एक स्ट्रिंग और एक स्ट्रिंग के बीच का होता है, जिसे कभी-कभी हेस्टेक कहा जाता है और जिसे कभी-कभी नीडल कहा जाता है। लक्ष्य होता है कि हेस्टेक में नीडल के एक या एक से अधिक प्रतिस्थानों का पता लगाया जाए। उदाहरण के लिए, किसी व्यक्ति की हिंदी भाषा में "तो" की विवृत्त की जा सकती है।

Some books are to be tasted, others to be swallowed, and some few to be chewed and digested

किसी व्यक्ति की विवृत्त कर सकती है, "तो" का पहला प्रतिस्थान, जो चौथा शब्द है; या सभी प्रतिस्थान, जिनमें 3 हैं; या अंतिम प्रतिस्थान, जो अंत से पांचवा शब्द है।

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

एक और सामान्य उदाहरण "मानकीकरण" से जुड़ा होता है। कई उद्देश्यों के लिए, "होना" जैसी वाक्यांश की विवृत्त को "तक" और "होना" के बीच किसी अन्य वस्तु के संबंध में सफल होना चाहिए, भले ही "तक" और "होना" के बीच कुछ और अवरुद्ध हो।:

• एक से अधिक स्थान
• टैग, गैर-टूटने वाले रिक्त स्थान, लाइन टोडने आदि जैसे अन्य "व्हाट्सएप" वर्ण भी हो सकते हैं।
• कम सामान्यतः, एक हाइफ़न या नरम हाइफ़न
• संरचित पाठों में, मार्कअप भाषा या यहां तक ​​कि मनमाने ढंग से बड़ी लेकिन पैरेंटेटिकल वस्तुए जैसे फ़ुटनोट्स, सूची-संख्याएं या अन्य मार्कर, अंतर्निहित छवियां इत्यादि।

कई प्रतीक प्रणालियों में ऐसे वर्ण सम्मिलित होते हैं जो पर्यायवाची होते हैं (कम से कम कुछ उद्देश्यों के लिए):

• लैटिन-आधारित वर्णमाला लोअर-केस को अपर-केस से अलग करती है, लेकिन कई उद्देश्यों के लिए स्ट्रिंग विवृत्त से इस अंतर को अनदेखा करने की उम्मीद की जाती है।
• कई भाषाओं में मुद्रण संयुक्ताक्षर सम्मिलित हैं, जहां एक मिश्रित वर्ण दो या दो से अधिक अन्य वर्णों के बराबर होता है।
• कई लेखन प्रणालियों में उच्चारण या स्वर संकेत जैसे विशेषक चिह्न सम्मिलित होते हैं, जो उनके उपयोग में भिन्न हो सकते हैं, या मिलान में अलग-अलग महत्व के हो सकते हैं।
• डीएनए अनुक्रमों में गैर-कोडिंग खंड सम्मिलित हो सकते हैं जिन्हें कुछ उद्देश्यों के लिए अनदेखा किया जा सकता है, या बहुरूपताएं जो एन्कोडेड प्रोटीन में कोई बदलाव नहीं लाती हैं, जो कुछ अन्य उद्देश्यों के लिए वास्तविक अंतर के रूप में नहीं गिना जा सकता है।
• कुछ भाषाओं में ऐसे नियम होते हैं जहां शब्दों के आरंभ, मध्य या अंत में एक अलग वर्ण या वर्ण के रूप का उपयोग किया जाना चाहिए।

अंततः, प्राकृतिक भाषा का प्रतिनिधित्व करने वाली स्ट्रिंग के लिए, भाषा के पहलू स्वयं सम्मिलित हो जाते हैं। उदाहरण के लिए, कोई व्यक्ति वैकल्पिक वर्तनी, उपसर्ग या प्रत्यय आदि होने के अतिरिक्त किसी शब्द की सभी घटनाओं को विवृत्त ा जा सकता है।

विवृत्त का एक और अधिक जटिल प्रकार नियमित अभिव्यक्ति विवृत्त है, जहां उपयोगकर्ता वर्णों या अन्य प्रतीकों का एक पैटर्न बनाता है, और पैटर्न के किसी भी मिलान से विवृत्त पूरी होनी चाहिए। उदाहरण के लिए, अमेरिकी अंग्रेजी शब्द कलर और ब्रिटिश समकक्ष कलर दोनों को पकड़ने के लिए, दो अलग-अलग शाब्दिक तारों की विवृत्त करने के अतिरिक्त, कोई नियमित अभिव्यक्ति का उपयोग कर सकता है जैसे:

colou?r

जहां ? परंपरागत रूप से पूर्ववर्ती वर्ण (u) को वैकल्पिक बनाता है।

यह आलेख मुख्य रूप से सरल प्रकार की स्ट्रिंग विवृत्त के लिए कलन-विधि पर चर्चा करता है।

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

विवृत्त कलन-विधि के उदाहरण

सरल स्ट्रिंग विवृत्त

एक सरल और अप्रभावी विधि जिसके द्वारा देखा जा सकता है कि एक स्ट्रिंग किसी अन्य स्ट्रिंग में कहां होती है, सबसे पहले, हम देखते हैं कि क्या हेस्टेक के पहले अक्षर से पैटर्न की एक प्रतिलिपि है; यदि नहीं, तो हम देखते हैं कि क्या हेस्टेक के दूसरे अक्षर से पैटर्न की एक प्रतिलिपि है, और ऐसा आगे भी होता है। सामान्य विधि में, हमें गलत स्थान के प्रत्येक अक्षर को देखने के लिए केवल एक या दो अक्षर देखने की जरूरत होती है जिससे हम यह देख सकें कि यह गलत स्थान है, इसलिए औसत स्थितियों में, इसमें O(n + m) चरण लगते हैं, जहां n हेस्टेक की लंबाई है और m पैटर्न की लंबाई है; लेकिन सबसे खराब मामले में, "aaaaaaaaab" जैसे स्ट्रिंग में "aaaab" जैसे स्ट्रिंग की विवृत्त करने में O(nm) समय लगता है।

परिमित-अवस्था-ऑटोमेटन-आधारित विवृत्त

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

स्टब्स

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

सूचकांक विधियाँ

तेज़ खोजकलन विधि प्राकृतिक भाषा में पूर्वप्रसंस्कृत करते हैं। एक उपस्ट्रिंग सूचकांक का निर्माण करने के बाद, जैसे कि सफिक्स ट्री या सफिक्स एरे, पैटर्न की प्रतिस्थान तेजी से मिल सकते हैं। एक उदाहरण के रूप में, एक सफिक्स ट्री $\Theta (n)$ समय में निर्मित की जा सकती है $z$ प्रतिस्थान $O(m)$ समय में मिल सकते हैं, यहां इस परिकल्पना के तहत कि अक्षरमाला का एक स्थायी आकार है और उप स्ट्रिंग ट्री के सभी आंतरिक नोड़ जानते हैं कि उनके नीचे कौन से पत्ते हैं। इसको उपसर्ग ट्री के रूट से एक डीएफएस कलन-विधि चलाकर प्राप्त किया जा सकता है।

अन्य प्रकार

कुछ विवृत्त विधियाँ, उदाहरण के लिए ट्रिग्राम विवृत्त, का उद्देश्य मिलान/गैर-मिलान के अतिरिक्त विवृत्त स्ट्रिंग और टेक्स्ट के बीच निकटता स्कोर खोजता है। इन्हें कभी-कभी अनुमानित स्ट्रिंग मिलान कहा जाता है|

विवृत्त कलन-विधि का वर्गीकरण

विभिन्न पैटर्न द्वारा वर्गीकरण

विभिन्न कलन विधि को प्रत्येक उपयोग किए जाने वाले पैटर्न की संख्या के आधार पर वर्गीकृत किया जा सकता है।

एकल-पैटर्न कलन-विधि

इस प्रकार के संकलन में, m पैटर्न की लंबाई है, n खोजने योग्य टेक्स्ट की लंबाई है, और k = |Σ| अक्षरमाला का आकार है।

Algorithm	Preprocessing time	Matching time	Space
Naïve algorithm	none	Θ(mn)	none
Rabin–Karp	Θ(m)	Θ(n) in average, O(mn) at worst	O(1)
Knuth–Morris–Pratt	Θ(m)	Θ(n)	Θ(m)
Boyer–Moore	Θ(m + k)	Ω(n/m) at best, O(mn) at worst	Θ(k)
Two-way algorithm	Θ(m)	O(n)	O(log(m))
Backward Non-Deterministic DAWG Matching (BNDM)	O(m)	Ω(n/m) at best, O(mn) at worst
Backward Oracle Matching (BOM)	O(m)	O(mn)

1.संक्षेप में,कलन विधि विश्लेषण में व्यास्तिक काल को सामान्यतः O (बड़ा ओ), Ω (ओमेगा) और Θ (थीटा) नोटेशन का प्रयोग करके व्यक्त किया जाता है।

2.^ यह O(m + n) समय में काम करता है, जहां m पैटर्न की लंबाई है और n खोजने योग्य पाठ की लंबाई है। इसलिए,अधिकांश स्थितियों में यह तेजी से काम करता है

3.^ यह सुनिश्चित करने के लिए कि लगभग सही स्ट्रिंग मैचिंग को हैंडल किया जा सके और नियमित भाषाओं के रूप में प्रतिष्ठित विभिन्न पैटर्नों के सेट को हैंडल किया जा सके, इसे विस्तारित किया जा सकता है।

बॉयर-मूर स्ट्रिंग-विवृत्त कलन विधि व्यावहारिक स्ट्रिंग-विवृत्त साहित्य के लिए मानक बेंचमार्क रहा है।

पैटर्न के एक सीमित सेट का उपयोग करने वाले कलन-विधि

निम्नलिखित संकलन में, एम सबसे लंबे पैटर्न की लंबाई है, m उनकी कुल लंबाई है, n विवृत्त जाने योग्य टेक्स्ट की लंबाई है, o घटनाओं की संख्या है।

Algorithm	Extension of	Preprocessing time	Matching time	Space
Aho–Corasick	Knuth–Morris–Pratt	Θ(m)	Θ(n + o)	Θ(m)
Commentz-Walter	Boyer-Moore	Θ(m)	Θ(M * n) worst case sublinear in average	Θ(m)
Set-BOM	Backward Oracle Matching

अनंत संख्या में पैटर्न का उपयोग करने वाले कलन-विधि

स्वाभाविक रूप से, इस मामले में पैटर्न को अंतिम रूप से गिना नहीं जा सकता है। इन्हें आमतौर पर नियमित व्याकरण या नियमित अभिव्यक्ति द्वारा दर्शाया जाता है।

पूर्वप्रसंस्करण प्रोग्राम के उपयोग द्वारा वर्गीकरण

अन्य वर्गीकरण दृष्टिकोण भी संभव हैं। सबसे सामान्य उपयोग पूर्वसंस्कारण को मुख्य मापदंड के रूप में होता है।

Classes of string searching algorithms

	Text not preprocessed	Text preprocessed
Patterns not preprocessed	Elementary algorithms	Index methods
Patterns preprocessed	Constructed search engines	Signature methods :

मिलान रणनीतियों द्वारा वर्गीकरण

एक अन्य कलन-विधि को उनकी मिलान रणनीति के आधार पर वर्गीकृत करता है:

• पहले उपसर्ग का मिलान करें (नुथ-मॉरिस-प्रैट, शिफ्ट-एंड, अहो-कोरासिक)
• पहले प्रत्यय का मिलान करें (बॉयर-मूर और वेरिएंट, कमेंट्ज़-वाल्टर)
• सबसे पहले सर्वोत्तम कारक का मिलान करें (बीएनडीएम, बीओएम, सेट-बीओएम)
• अन्य रणनीति (भोले, राबिन-कार्प)

यह भी देखें

• अनुक्रम संरेखण
• ग्राफ़ मिलान
• पैटर्न मिलान
• संपीड़ित पैटर्न मिलान
• वाइल्डकार्ड का मिलान
• पूरा पाठ विवृत्त ें

संदर्भ

• R. S. Boyer and J. S. Moore, A fast string searching algorithm, Carom. ACM 20, (10), 262–272(1977).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press and McGraw-Hill, 2009. ISBN 0-262-03293-7. Chapter 32: String Matching, pp. 985–1013.

बाहरी संबंध

• Huge list of pattern matching links Last updated: 12/27/2008 20:18:38
• Large (maintained) list of string-matching algorithms
• NIST list of string-matching algorithms
• StringSearch – high-performance pattern matching algorithms in Java – Implementations of many String-Matching-Algorithms in Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
• StringsAndChars – Implementations of many String-Matching-Algorithms (for single and multiple patterns) in Java
• Exact String Matching Algorithms — Animation in Java, Detailed description and C implementation of many algorithms.
• (PDF) Improved Single and Multiple Approximate String Matching
• Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features
• NyoTengu – high-performance pattern matching algorithm in C – Implementations of Vector and Scalar String-Matching-Algorithms in C