स्ट्रिंग-सर्चिंग एल्गोरिदम
कंप्यूटर विज्ञान में, स्ट्रिंग-खोज कलन-विधि, कभी-कभी स्ट्रिंग-मैचिंग कलन-विधि के रूप में जाने जाते हैं, स्ट्रिंग कलन-विधि की एक महत्वपूर्ण श्रेणी हैं, जो एक या एक से अधिक स्ट्रिंग को एक बड़े स्ट्रिंग या पाठ में ढूंढने का प्रयास करते हैं।
स्ट्रिंग खोज का एक मूलभूत उदाहरण होता है जब पैटर्न और खोजी गई टेक्स्ट एक वर्णमाला Σ के तत्वों के सारणी, होते हैं। Σ मानवीय भाषा वर्णमाला हो सकता है, उदाहरण के लिए, A से Z तक के अक्षर और अन्य एप्लिकेशन द्वारा बाइनरी वर्णमाला (Σ = {0,1}) या जैवविज्ञान में डीएनए वर्णमाला (Σ = {A,C,G,T}) का उपयोग कर सकते हैं।
व्यावहारिकता में, संभवतः स्ट्रिंग-खोज कलन-विधि के तरीके को स्ट्रिंग एनकोडिंग प्रभावित कर सकते हैं। विशेष रूप से, यदि एक परिवर्तनशील-चौड़ाई एनकोडिंग का उपयोग हो रहा है, तो एनवेती वाले वर्ण को ढूंढने में धीमा हो सकता है,प्रायः N के प्रस्ताव समय की आवश्यकता हो सकती है। इससे कुछ खोज कलन-विधि को काफी धीमा कर सकता है। इसमें एक संभवतः हल कई संभावित समाधानों में से एक है, जिसमें कोड इकाइयों के अनुक्रम की खोज की जाती है, लेकिन ऐसा करने से यदि एनकोडिंग इसे टालने के लिए विशेष रूप से आरेखित नहीं की गई है, तो यह गलत मिलान प्रदर्शित कर सकता है।
अवलोकन
स्ट्रिंग खोज का सबसे मूल स्थिति एक स्ट्रिंग और एक स्ट्रिंग के बीच का होता है, जिसे कभी-कभी हेस्टेक कहा जाता है और जिसे कभी-कभी नीडल कहा जाता है। लक्ष्य होता है कि हेस्टेक में नीडल के एक या एक से अधिक प्रतिस्थानों का पता लगाया जाए। उदाहरण के लिए, किसी व्यक्ति की हिंदी भाषा में "तो" की खोज की जा सकती है।
कुछ किताबें चखने के लिए होती हैं, कुछ निगलने के लिए, और कुछ चबाने और पचाने के लिए होती हैं।
किसी व्यक्ति की खोज कर सकती है, "तो" का पहला प्रतिस्थान, जो चौथा शब्द है; या सभी प्रतिस्थान, जिनमें 3 हैं; या अंतिम प्रतिस्थान, जो अंत से पांचवा शब्द है।
सामान्यतः, इसके साथ-साथ विभिन्न प्रतिबंध भी लगाए जाते हैं। उदाहरण के लिए, कोई व्यक्ति "नीडल" के सिर्फ उन प्रतिस्थानों का मेल करना चाह सकता है जहां वह एक पूर्ण शब्द के रूप में होती है प्रायः उसे उनके दोनों ओर संबंधित अक्षरों के आसपास कोई अन्य अक्षर नहीं होने के रूप में परिभाषित किया गया हो। इस स्थिति में, उपरोक्त उदाहरण में "ह्यू" या "लो" की खोज विफल होनी चाहिए, यद्यपि वास्तविक तत्व उपस्थित हैं।
एक और सामान्य उदाहरण "मानकीकरण" से जुड़ा होता है। कई उद्देश्यों के लिए, "होना" जैसी वाक्यांश की खोज को "तक" और "होना" के बीच किसी अन्य वस्तु के संबंध में सफल होना चाहिए, भले ही "तक" और "होना" के बीच कुछ और अवरुद्ध हो।:
- एक से अधिक स्थान
- टैग, गैर-टूटने वाले रिक्त स्थान, लाइन टोडने आदि जैसे अन्य "व्हाट्सएप" वर्ण भी हो सकते हैं।
- कम सामान्यतः, एक हाइफ़न या नरम हाइफ़न
- संरचित पाठों में, मार्कअप भाषा या यहां तक कि मनमाने ढंग से बड़ी लेकिन पैरेंटेटिकल चीजें जैसे फ़ुटनोट्स, सूची-संख्याएं या अन्य मार्कर, एम्बेडेड छवियां इत्यादि।
कई प्रतीक प्रणालियों में ऐसे वर्ण शामिल होते हैं जो पर्यायवाची होते हैं (कम से कम कुछ उद्देश्यों के लिए):
- लैटिन-आधारित वर्णमाला लोअर-केस को अपर-केस से अलग करती है, लेकिन कई उद्देश्यों के लिए स्ट्रिंग खोज से इस अंतर को अनदेखा करने की उम्मीद की जाती है।
- कई भाषाओं में मुद्रण संयुक्ताक्षर शामिल हैं, जहां एक मिश्रित वर्ण दो या दो से अधिक अन्य वर्णों के बराबर होता है।
- कई लेखन प्रणालियों में उच्चारण या स्वर संकेत (बहुविकल्पी) जैसे विशेषक चिह्न शामिल होते हैं, जो उनके उपयोग में भिन्न हो सकते हैं, या मिलान में अलग-अलग महत्व के हो सकते हैं।
- डीएनए अनुक्रमों में गैर-कोडिंग खंड शामिल हो सकते हैं जिन्हें कुछ उद्देश्यों के लिए अनदेखा किया जा सकता है, या बहुरूपताएं जो एन्कोडेड प्रोटीन में कोई बदलाव नहीं लाती हैं, जो कुछ अन्य उद्देश्यों के लिए वास्तविक अंतर के रूप में नहीं गिना जा सकता है।
- कुछ भाषाओं में ऐसे नियम होते हैं जहां शब्दों के आरंभ, मध्य या अंत में एक अलग वर्ण या वर्ण के रूप का उपयोग किया जाना चाहिए।
अंततः, प्राकृतिक भाषा का प्रतिनिधित्व करने वाली स्ट्रिंग के लिए, भाषा के पहलू स्वयं शामिल हो जाते हैं। उदाहरण के लिए, कोई व्यक्ति वैकल्पिक वर्तनी, उपसर्ग या प्रत्यय आदि होने के बावजूद किसी शब्द की सभी घटनाओं को ढूंढना चाह सकता है।
खोज का एक और अधिक जटिल प्रकार नियमित अभिव्यक्ति खोज है, जहां उपयोगकर्ता वर्णों या अन्य प्रतीकों का एक पैटर्न बनाता है, और पैटर्न के किसी भी मिलान से खोज पूरी होनी चाहिए। उदाहरण के लिए, अमेरिकी अंग्रेजी शब्द कलर और ब्रिटिश समकक्ष कलर दोनों को पकड़ने के लिए, दो अलग-अलग शाब्दिक तारों की खोज करने के बजाय, कोई नियमित अभिव्यक्ति का उपयोग कर सकता है जैसे:
रंग
जहां ? परंपरागत रूप से पूर्ववर्ती वर्ण (u) को वैकल्पिक बनाता है।
यह आलेख मुख्य रूप से सरल प्रकार की स्ट्रिंग खोज के लिए कलन-विधि पर चर्चा करता है।
जैव सूचना विज्ञान और जीनोमिक्स के क्षेत्र में पेश की गई एक समान समस्या अधिकतम सटीक मिलान (एमईएम) है।[1] दो स्ट्रिंग्स को देखते हुए, एमईएम सामान्य सबस्ट्रिंग हैं जिन्हें बेमेल पैदा किए बिना बाएं या दाएं नहीं बढ़ाया जा सकता है।[2]
खोज कलन-विधि के उदाहरण
अनुभवहीन स्ट्रिंग खोज
यह देखने का एक सरल और अप्रभावी तरीका है कि एक स्ट्रिंग दूसरे के अंदर कहां होती है, प्रत्येक सूचकांक को एक-एक करके जांचना। सबसे पहले, हम देखते हैं कि क्या भूसे के ढेर के पहले अक्षर से शुरू होने वाली सुई की कोई प्रति है; यदि नहीं, तो हम यह देखना चाहेंगे कि क्या भूसे के ढेर के दूसरे अक्षर से शुरू होने वाली सुई की कोई प्रतिलिपि है, इत्यादि। सामान्य मामले में, हमें यह देखने के लिए कि यह एक गलत स्थिति है, प्रत्येक गलत स्थिति के लिए केवल एक या दो वर्णों को देखना होगा, इसलिए औसत मामले में, यह बिग ओ अंकन (एन + एम) चरण लेता है, जहां एन है घास के ढेर की लंबाई और मी सुई की लंबाई है; लेकिन सबसे खराब स्थिति में, आआआआआआआब जैसी स्ट्रिंग में आआआआब जैसी स्ट्रिंग की खोज करने पर बिग ओ नोटेशन(एनएम) की आवश्यकता होती है
परिमित-अवस्था-ऑटोमेटन-आधारित खोज
इस दृष्टिकोण में, एक नियतात्मक परिमित ऑटोमेटन (डीएफए) का निर्माण करके बैकट्रैकिंग से बचा जाता है जो संग्रहीत खोज स्ट्रिंग को पहचानता है। इन्हें बनाना महंगा है—ये आम तौर पर पावरसेट निर्माण का उपयोग करके बनाए जाते हैं—लेकिन इनका उपयोग बहुत जल्दी हो जाता है। उदाहरण के लिए, दाईं ओर दिखाया गया नियतात्मक परिमित ऑटोमेटन MOMMY शब्द को पहचानता है। मनमाने ढंग से नियमित अभिव्यक्तियों की खोज के लिए इस दृष्टिकोण को अक्सर अभ्यास में सामान्यीकृत किया जाता है।
स्टब्स
नुथ-मॉरिस-प्रैट कलन-विधि |नुथ-मॉरिस-प्रैट एक नियतात्मक परिमित ऑटोमेटन की गणना करता है जो प्रत्यय के रूप में खोज करने के लिए स्ट्रिंग के साथ इनपुट को पहचानता है, बॉयर-मूर स्ट्रिंग-खोज कलन-विधि |बॉयर-मूर सुई के अंत से खोज शुरू करता है, इसलिए यह आमतौर पर प्रत्येक चरण में पूरी सुई-लंबाई तक आगे कूद सकता है। बेज़ा-येट्स इस बात पर नज़र रखता है कि क्या पिछले j अक्षर खोज स्ट्रिंग का उपसर्ग थे, और इसलिए यह फ़ज़ी स्ट्रिंग खोज के लिए अनुकूल है। थकना बेज़ा-येट्स के दृष्टिकोण का एक अनुप्रयोग है।
सूचकांक विधियाँ
तेज़ खोज कलन-विधि टेक्स्ट को प्रीप्रोसेस करते हैं। एक सबस्ट्रिंग सूचकांक बनाने के बाद, उदाहरण के लिए एक प्रत्यय वृक्ष या प्रत्यय सरणी, एक पैटर्न की घटनाओं को जल्दी से पाया जा सकता है। उदाहरण के तौर पर, एक प्रत्यय वृक्ष बनाया जा सकता है समय, और सब कुछ एक पैटर्न की घटनाएँ पाई जा सकती हैं इस धारणा के तहत समय कि वर्णमाला का एक स्थिर आकार होता है और प्रत्यय वृक्ष के सभी आंतरिक नोड्स जानते हैं कि उनके नीचे कौन सी पत्तियाँ हैं। उत्तरार्द्ध को प्रत्यय वृक्ष की जड़ से गहराई-पहली खोज चलाकर पूरा किया जा सकता है।
अन्य प्रकार
कुछ खोज विधियाँ, उदाहरण के लिए ट्रिग्राम खोज, का उद्देश्य मिलान/गैर-मिलान के बजाय खोज स्ट्रिंग और पाठ के बीच निकटता स्कोर ढूंढना है। इन्हें कभी-कभी अनुमानित स्ट्रिंग मिलान कहा जाता है| अस्पष्ट खोजें.
खोज कलन-विधि का वर्गीकरण
कई पैटर्न द्वारा वर्गीकरण
विभिन्न कलन विधि को प्रत्येक उपयोग किए जाने वाले पैटर्न की संख्या के आधार पर वर्गीकृत किया जा सकता है।
एकल-पैटर्न कलन-विधि
निम्नलिखित संकलन में, m पैटर्न की लंबाई है, n खोजने योग्य पाठ की लंबाई है, और k = |Σ| वर्णमाला का आकार है.
| Algorithm | Preprocessing time | Matching time[1] | 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[3][2] | Θ(m) | O(n) | O(log(m)) |
| Backward Non-Deterministic DAWG Matching (BNDM)[4][3] | O(m) | Ω(n/m) at best, O(mn) at worst |
|
| Backward Oracle Matching (BOM)[5] | O(m) | O(mn) |
- 1.^ एसिम्प्टोटिक समय को बिग ओ नोटेशन|ओ, Ω, और Θ नोटेशन का उपयोग करके व्यक्त किया जाता है।
- 2.^ ग्लिबैक में मेमम और सी स्ट्रिंग हैंडलिंग#फ़ंक्शन खोज फ़ंक्शन को कार्यान्वित करने के लिए उपयोग किया जाता है[6] और माँसपेशियाँ[7] सी मानक पुस्तकालय।
- 3.^ अनुमानित स्ट्रिंग मिलान और (संभावित-अनंत) पैटर्न के सेट को नियमित भाषाओं के रूप में प्रदर्शित करने के लिए बढ़ाया जा सकता है।[citation needed]
बॉयर-मूर स्ट्रिंग-खोज एल्गोरिथ्म व्यावहारिक स्ट्रिंग-खोज साहित्य के लिए मानक बेंचमार्क रहा है।[8]
पैटर्न के एक सीमित सेट का उपयोग करने वाले कलन-विधि
निम्नलिखित संकलन में, एम सबसे लंबे पैटर्न की लंबाई है, एम उनकी कुल लंबाई है, एन खोजे जाने योग्य पाठ की लंबाई है, ओ घटनाओं की संख्या है।
| Algorithm | Extension of | Preprocessing time | Matching time[4] | Space |
|---|---|---|---|---|
| Aho–Corasick | Knuth–Morris–Pratt | Θ(m) | Θ(n + o) | Θ(m) |
| Commentz-Walter | Boyer-Moore | Θ(m) | Θ(M * n) worst case sublinear in average[9] |
Θ(m) |
| Set-BOM | Backward Oracle Matching |
अनंत संख्या में पैटर्न का उपयोग करने वाले कलन-विधि
स्वाभाविक रूप से, इस मामले में पैटर्न को अंतिम रूप से गिना नहीं जा सकता है। इन्हें आमतौर पर नियमित व्याकरण या नियमित अभिव्यक्ति द्वारा दर्शाया जाता है।
प्रीप्रोसेसिंग प्रोग्राम के उपयोग द्वारा वर्गीकरण
अन्य वर्गीकरण दृष्टिकोण संभव हैं। सबसे आम में से एक मुख्य मानदंड के रूप में प्रीप्रोसेसिंग का उपयोग करता है।
| Text not preprocessed | Text preprocessed | |
|---|---|---|
| Patterns not preprocessed | Elementary algorithms | Index methods |
| Patterns preprocessed | Constructed search engines | Signature methods :[11] |
मिलान रणनीतियों द्वारा वर्गीकरण
एक अन्य कलन-विधि को उनकी मिलान रणनीति के आधार पर वर्गीकृत करता है:[12]
- पहले उपसर्ग का मिलान करें (नुथ-मॉरिस-प्रैट, शिफ्ट-एंड, अहो-कोरासिक)
- पहले प्रत्यय का मिलान करें (बॉयर-मूर और वेरिएंट, कमेंट्ज़-वाल्टर)
- सबसे पहले सर्वोत्तम कारक का मिलान करें (बीएनडीएम, बीओएम, सेट-बीओएम)
- अन्य रणनीति (भोले, राबिन-कार्प)
यह भी देखें
संदर्भ
- ↑ Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). "बड़े जीनोम की तुलना के लिए बहुमुखी और खुला सॉफ्टवेयर". Genome Biology. 5 (2): R12. doi:10.1186/gb-2004-5-2-r12. ISSN 1465-6906. PMC 395750. PMID 14759262.
- ↑ Khan, Zia; Bloom, Joshua S.; Kruglyak, Leonid; Singh, Mona (2009-07-01). "विरल प्रत्यय सरणियों का उपयोग करके बड़े अनुक्रम डेटासेट में अधिकतम सटीक मिलान खोजने के लिए एक व्यावहारिक एल्गोरिदम". Bioinformatics. 25 (13): 1609–1616. doi:10.1093/bioinformatics/btp275. PMC 2732316. PMID 19389736.
- ↑ Crochemore, Maxime; Perrin, Dominique (1 July 1991). "Two-way string-matching" (PDF). Journal of the ACM. 38 (3): 650–674. doi:10.1145/116825.116845. S2CID 15055316. Archived (PDF) from the original on 24 November 2021. Retrieved 5 April 2019.
- ↑ Navarro, Gonzalo; Raffinot, Mathieu (1998). "A bit-parallel approach to suffix automata: Fast extended string matching" (PDF). Combinatorial Pattern Matching. Lecture Notes in Computer Science. Springer Berlin Heidelberg. 1448: 14–33. doi:10.1007/bfb0030778. ISBN 978-3-540-64739-3. Archived (PDF) from the original on 2019-01-05. Retrieved 2019-11-22.
- ↑ Fan, H.; Yao, N.; Ma, H. (December 2009). "Fast Variants of the Backward-Oracle-Marching Algorithm" (PDF). 2009 Fourth International Conference on Internet Computing for Science and Engineering: 56–59. doi:10.1109/ICICSE.2009.53. ISBN 978-1-4244-6754-9. S2CID 6073627. Archived from the original on 2022-05-10. Retrieved 2019-11-22.
- ↑ "glibc/string/str-two-way.h". Archived from the original on 2020-09-20. Retrieved 2022-03-22.
- ↑ "musl/src/string/memmem.c". Archived from the original on 1 October 2020. Retrieved 23 November 2019.
- ↑ Hume; Sunday (1991). "तेज़ स्ट्रिंग खोज". Software: Practice and Experience. 21 (11): 1221–1248. doi:10.1002/spe.4380211105. S2CID 5902579. Archived from the original on 2022-05-10. Retrieved 2019-11-29.
- ↑ Commentz-Walter, Beate (1979). A String Matching Algorithm Fast on the Average (PDF). International Colloquium on Automata, Languages and Programming. LNCS. Vol. 71. Graz, Austria: Springer. pp. 118–132. doi:10.1007/3-540-09510-1_10. ISBN 3-540-09510-1. Archived from the original (PDF) on 2017-10-10.
- ↑ Melichar, Borivoj, Jan Holub, and J. Polcar. Text Searching Algorithms. Volume I: Forward String Matching. Vol. 1. 2 vols., 2005. http://stringology.org/athens/TextSearchingAlgorithms/ Archived 2016-03-04 at the Wayback Machine.
- ↑ Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007), Fast nGramBased String Search Over Data Encoded Using Algebraic Signatures, 33rd International Conference on Very Large Data Bases (VLDB)
{{citation}}: External link in|surname2= - ↑ Gonzalo Navarro; Mathieu Raffinot (2008), Flexible Pattern Matching Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences, ISBN 978-0-521-03993-2
- 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
