स्ट्रिंग-सर्चिंग एल्गोरिदम: Difference between revisions

Revision as of 12:25, 16 July 2023

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

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

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

अवलोकन

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

कुछ किताबें चखने के लिए होती हैं, कुछ निगलने के लिए, और कुछ चबाने और पचाने के लिए होती हैं।

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

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

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

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

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

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

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

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

colou?r

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

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

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

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

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

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

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

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

स्टब्स

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

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

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

अन्य प्रकार

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

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

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

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

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

निम्नलिखित संकलन में, 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

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

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

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

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

Classes of string searching algorithms^[10]
	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= (help)
↑ 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

[1] 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.

[2] 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.

[3] 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.

[4] 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.

[5] 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.

[6] "glibc/string/str-two-way.h". Archived from the original on 2020-09-20. Retrieved 2022-03-22.

[7] "musl/src/string/memmem.c". Archived from the original on 1 October 2020. Retrieved 23 November 2019.

[:0-8] 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-9] 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.

[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.

[11] 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= (help)

[12] 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

[1]

[2]

[1]

[3]

[2]

[4]

[3]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
 {{short description|Searches for patterns within strings}}
-[[कंप्यूटर विज्ञान]] में, स्ट्रिंग-खोज कलन-विधि, कभी-कभी स्ट्रिंग-मैचिंग कलन-विधि के रूप में जाने जाते हैं, [[स्ट्रिंग एल्गोरिदम|स्ट्रिंग कलन-विधि]] की एक महत्वपूर्ण श्रेणी हैं, जो एक या एक से अधिक [[स्ट्रिंग (कंप्यूटर विज्ञान)|स्ट्रिंग]] को एक बड़े स्ट्रिंग या पाठ में ढूंढने का प्रयास करते हैं।
+[[कंप्यूटर विज्ञान]] में, स्ट्रिंग-विवृत्त    कलन-विधि, कभी-कभी स्ट्रिंग-मैचिंग कलन-विधि के रूप में जाने जाते हैं, [[स्ट्रिंग एल्गोरिदम|स्ट्रिंग कलन-विधि]] की एक महत्वपूर्ण श्रेणी हैं, जो एक या एक से अधिक [[स्ट्रिंग (कंप्यूटर विज्ञान)|स्ट्रिंग]] को एक बड़े स्ट्रिंग या पाठ में ढूंढने का प्रयास करते हैं।
-स्ट्रिंग खोज का एक मूलभूत उदाहरण होता है जब पैटर्न और खोजी गई टेक्स्ट एक [[वर्णमाला (कंप्यूटर विज्ञान)|वर्णमाला]] Σ के तत्वों के सारणी, होते हैं। Σ मानवीय भाषा वर्णमाला हो सकता है, उदाहरण के लिए, A से Z तक के अक्षर और अन्य एप्लिकेशन द्वारा बाइनरी वर्णमाला (Σ = {0,1}) या जैवविज्ञान में डीएनए वर्णमाला (Σ = {A,C,G,T}) का उपयोग कर सकते हैं।
+स्ट्रिंग विवृत्त    का एक मूलभूत उदाहरण होता है जब पैटर्न और विवृत्त   ी गई टेक्स्ट एक [[वर्णमाला (कंप्यूटर विज्ञान)|वर्णमाला]] Σ के तत्वों के सारणी, होते हैं। Σ मानवीय भाषा वर्णमाला हो सकता है, उदाहरण के लिए, A से Z तक के अक्षर और अन्य एप्लिकेशन द्वारा बाइनरी वर्णमाला (Σ = {0,1}) या जैवविज्ञान में डीएनए वर्णमाला (Σ = {A,C,G,T}) का उपयोग कर सकते हैं।
-व्यावहारिकता में, संभवतः स्ट्रिंग-खोज कलन-विधि के तरीके को स्ट्रिंग एनकोडिंग प्रभावित कर सकते हैं। विशेष रूप से, यदि एक परिवर्तनशील-चौड़ाई एनकोडिंग का उपयोग हो रहा है, तो एनवेती वाले वर्ण को ढूंढने में धीमा हो सकता है,प्रायः N के प्रस्ताव समय की आवश्यकता हो सकती है। इससे कुछ खोज कलन-विधि को काफी धीमा कर सकता है। इसमें एक संभवतः हल कई संभावित समाधानों में से एक है, जिसमें कोड इकाइयों के अनुक्रम की खोज की जाती है, लेकिन ऐसा करने से यदि एनकोडिंग इसे टालने के लिए विशेष रूप से आरेखित नहीं की गई है, तो यह गलत मिलान प्रदर्शित कर सकता है।
+व्यावहारिकता में, संभवतः स्ट्रिंग-विवृत्त    कलन-विधि के तरीके को स्ट्रिंग एनकोडिंग प्रभावित कर सकते हैं। विशेष रूप से, यदि एक परिवर्तनशील-चौड़ाई एनकोडिंग का उपयोग हो रहा है, तो एनवेती वाले वर्ण को ढूंढने में धीमा हो सकता है,प्रायः N के प्रस्ताव समय की आवश्यकता हो सकती है। इससे कुछ विवृत्त    कलन-विधि को काफी धीमा कर सकता है। इसमें एक संभवतः हल कई संभावित समाधानों में से एक है, जिसमें कोड इकाइयों के अनुक्रम की विवृत्त    की जाती है, लेकिन ऐसा करने से यदि एनकोडिंग इसे टालने के लिए विशेष रूप से आरेखित नहीं की गई है, तो यह गलत मिलान प्रदर्शित कर सकता है।
 == अवलोकन ==
-स्ट्रिंग खोज का सबसे मूल स्थिति एक स्ट्रिंग और एक स्ट्रिंग के बीच का होता है, जिसे कभी-कभी हेस्टेक कहा जाता है और जिसे कभी-कभी नीडल कहा जाता है। लक्ष्य होता है कि हेस्टेक में नीडल के एक या एक से अधिक प्रतिस्थानों का पता लगाया जाए। उदाहरण के लिए, किसी व्यक्ति की हिंदी भाषा में "तो" की खोज की जा सकती है।
+स्ट्रिंग विवृत्त    का सबसे मूल स्थिति एक स्ट्रिंग और एक स्ट्रिंग के बीच का होता है, जिसे कभी-कभी हेस्टेक कहा जाता है और जिसे कभी-कभी नीडल कहा जाता है। लक्ष्य होता है कि हेस्टेक में नीडल के एक या एक से अधिक प्रतिस्थानों का पता लगाया जाए। उदाहरण के लिए, किसी व्यक्ति की हिंदी भाषा में "तो" की विवृत्त    की जा सकती है।
   कुछ किताबें चखने के लिए होती हैं, कुछ निगलने के लिए, और कुछ चबाने और पचाने के लिए होती हैं।
-किसी व्यक्ति की खोज कर सकती है, "तो" का पहला प्रतिस्थान, जो चौथा शब्द है; या सभी प्रतिस्थान, जिनमें 3 हैं; या अंतिम प्रतिस्थान, जो अंत से पांचवा शब्द है।
+किसी व्यक्ति की विवृत्त    कर सकती है, "तो" का पहला प्रतिस्थान, जो चौथा शब्द है; या सभी प्रतिस्थान, जिनमें 3 हैं; या अंतिम प्रतिस्थान, जो अंत से पांचवा शब्द है।
-सामान्यतः, इसके साथ-साथ विभिन्न प्रतिबंध भी लगाए जाते हैं। उदाहरण के लिए, कोई व्यक्ति "नीडल" के सिर्फ उन प्रतिस्थानों का मेल करना चाह सकता है जहां वह एक पूर्ण शब्द के रूप में होती है प्रायः उसे उनके दोनों ओर संबंधित अक्षरों के आसपास कोई अन्य अक्षर नहीं होने के रूप में परिभाषित किया गया हो। इस स्थिति में, उपरोक्त उदाहरण में "ह्यू" या "लो" की खोज विफल होनी चाहिए, यद्यपि वास्तविक तत्व उपस्थित हैं।
+सामान्यतः, इसके साथ-साथ विभिन्न प्रतिबंध भी लगाए जाते हैं। उदाहरण के लिए, कोई व्यक्ति "नीडल" के सिर्फ उन प्रतिस्थानों का मेल करना चाह सकता है जहां वह एक पूर्ण शब्द के रूप में होती है प्रायः उसे उनके दोनों ओर संबंधित अक्षरों के आसपास कोई अन्य अक्षर नहीं होने के रूप में परिभाषित किया गया हो। इस स्थिति में, उपरोक्त उदाहरण में "ह्यू" या "लो" की विवृत्त    विफल होनी चाहिए, यद्यपि वास्तविक तत्व उपस्थित हैं।
-एक और सामान्य उदाहरण "मानकीकरण" से जुड़ा होता है। कई उद्देश्यों के लिए, "होना" जैसी वाक्यांश की खोज को "तक" और "होना" के बीच किसी अन्य वस्तु के संबंध में सफल होना चाहिए, भले ही "तक" और "होना" के बीच कुछ और अवरुद्ध हो।:
+एक और सामान्य उदाहरण "मानकीकरण" से जुड़ा होता है। कई उद्देश्यों के लिए, "होना" जैसी वाक्यांश की विवृत्त    को "तक" और "होना" के बीच किसी अन्य वस्तु के संबंध में सफल होना चाहिए, भले ही "तक" और "होना" के बीच कुछ और अवरुद्ध हो।:
 *एक से अधिक स्थान
 *टैग, गैर-टूटने वाले रिक्त स्थान, लाइन टोडने आदि जैसे अन्य "व्हाट्सएप" वर्ण भी हो सकते हैं।
 *कम सामान्यतः, एक हाइफ़न या नरम हाइफ़न
-*संरचित पाठों में, मार्कअप भाषा या यहां तक कि मनमाने ढंग से बड़ी लेकिन पैरेंटेटिकल चीजें जैसे फ़ुटनोट्स, सूची-संख्याएं या अन्य मार्कर, एम्बेडेड छवियां इत्यादि।
+*संरचित पाठों में, मार्कअप भाषा या यहां तक कि मनमाने ढंग से बड़ी लेकिन पैरेंटेटिकल वस्तुए जैसे फ़ुटनोट्स, सूची-संख्याएं या अन्य मार्कर, अंतर्निहित छवियां इत्यादि।
-कई प्रतीक प्रणालियों में ऐसे वर्ण शामिल होते हैं जो पर्यायवाची होते हैं (कम से कम कुछ उद्देश्यों के लिए):
+कई प्रतीक प्रणालियों में ऐसे वर्ण सम्मिलित होते हैं जो पर्यायवाची होते हैं (कम से कम कुछ उद्देश्यों के लिए):
-*लैटिन-आधारित वर्णमाला लोअर-केस को अपर-केस से अलग करती है, लेकिन कई उद्देश्यों के लिए स्ट्रिंग खोज से इस अंतर को अनदेखा करने की उम्मीद की जाती है।
+*लैटिन-आधारित वर्णमाला लोअर-केस को अपर-केस से अलग करती है, लेकिन कई उद्देश्यों के लिए स्ट्रिंग विवृत्त    से इस अंतर को अनदेखा करने की उम्मीद की जाती है।
-*कई भाषाओं में [[मुद्रण संयुक्ताक्षर]] शामिल हैं, जहां एक मिश्रित वर्ण दो या दो से अधिक अन्य वर्णों के बराबर होता है।
+*कई भाषाओं में [[मुद्रण संयुक्ताक्षर]] सम्मिलित हैं, जहां एक मिश्रित वर्ण दो या दो से अधिक अन्य वर्णों के बराबर होता है।
-*कई लेखन प्रणालियों में उच्चारण या [[स्वर संकेत (बहुविकल्पी)]] जैसे विशेषक चिह्न शामिल होते हैं, जो उनके उपयोग में भिन्न हो सकते हैं, या मिलान में अलग-अलग महत्व के हो सकते हैं।
+*कई लेखन प्रणालियों में उच्चारण या [[स्वर संकेत (बहुविकल्पी)|स्वर संकेत]] जैसे विशेषक चिह्न सम्मिलित होते हैं, जो उनके उपयोग में भिन्न हो सकते हैं, या मिलान में अलग-अलग महत्व के हो सकते हैं।
-*डीएनए अनुक्रमों में [[गैर-कोडिंग]] खंड शामिल हो सकते हैं जिन्हें कुछ उद्देश्यों के लिए अनदेखा किया जा सकता है, या बहुरूपताएं जो एन्कोडेड प्रोटीन में कोई बदलाव नहीं लाती हैं, जो कुछ अन्य उद्देश्यों के लिए वास्तविक अंतर के रूप में नहीं गिना जा सकता है।
+*डीएनए अनुक्रमों में [[गैर-कोडिंग]] खंड सम्मिलित हो सकते हैं जिन्हें कुछ उद्देश्यों के लिए अनदेखा किया जा सकता है, या बहुरूपताएं जो एन्कोडेड प्रोटीन में कोई बदलाव नहीं लाती हैं, जो कुछ अन्य उद्देश्यों के लिए वास्तविक अंतर के रूप में नहीं गिना जा सकता है।
 * कुछ भाषाओं में ऐसे नियम होते हैं जहां शब्दों के आरंभ, मध्य या अंत में एक अलग वर्ण या वर्ण के रूप का उपयोग किया जाना चाहिए।
-अंततः, प्राकृतिक भाषा का प्रतिनिधित्व करने वाली स्ट्रिंग के लिए, भाषा के पहलू स्वयं शामिल हो जाते हैं। उदाहरण के लिए, कोई व्यक्ति वैकल्पिक वर्तनी, उपसर्ग या प्रत्यय आदि होने के बावजूद किसी शब्द की सभी घटनाओं को ढूंढना चाह सकता है।
+अंततः, प्राकृतिक भाषा का प्रतिनिधित्व करने वाली स्ट्रिंग के लिए, भाषा के पहलू स्वयं सम्मिलित हो जाते हैं। उदाहरण के लिए, कोई व्यक्ति वैकल्पिक वर्तनी, उपसर्ग या प्रत्यय आदि होने के अतिरिक्त किसी शब्द की सभी घटनाओं को विवृत्त   ा जा सकता है।
-खोज का एक और अधिक जटिल प्रकार [[नियमित अभिव्यक्ति]] खोज है, जहां उपयोगकर्ता वर्णों या अन्य प्रतीकों का एक पैटर्न बनाता है, और पैटर्न के किसी भी मिलान से खोज पूरी होनी चाहिए। उदाहरण के लिए, अमेरिकी अंग्रेजी शब्द कलर और ब्रिटिश समकक्ष कलर दोनों को पकड़ने के लिए, दो अलग-अलग शाब्दिक तारों की खोज करने के बजाय, कोई नियमित अभिव्यक्ति का उपयोग कर सकता है जैसे:
+विवृत्त    का एक और अधिक जटिल प्रकार [[नियमित अभिव्यक्ति]] विवृत्त    है, जहां उपयोगकर्ता वर्णों या अन्य प्रतीकों का एक पैटर्न बनाता है, और पैटर्न के किसी भी मिलान से विवृत्त    पूरी होनी चाहिए। उदाहरण के लिए, अमेरिकी अंग्रेजी शब्द कलर और ब्रिटिश समकक्ष कलर दोनों को पकड़ने के लिए, दो अलग-अलग शाब्दिक तारों की विवृत्त    करने के अतिरिक्त, कोई नियमित अभिव्यक्ति का उपयोग कर सकता है जैसे:
-  रंग
+  colou?r
-जहां  ? परंपरागत रूप से पूर्ववर्ती वर्ण (u) को वैकल्पिक बनाता है।
+जहां ? परंपरागत रूप से पूर्ववर्ती वर्ण (u) को वैकल्पिक बनाता है।
-यह आलेख मुख्य रूप से सरल प्रकार की स्ट्रिंग खोज के लिए कलन-विधि   पर चर्चा करता है।
+यह आलेख मुख्य रूप से सरल प्रकार की स्ट्रिंग विवृत्त के लिए कलन-विधि पर चर्चा करता है।
-जैव सूचना विज्ञान और जीनोमिक्स के क्षेत्र में पेश की गई एक समान समस्या अधिकतम सटीक मिलान (एमईएम) है।<ref>{{Cite journal|last1=Kurtz|first1=Stefan|last2=Phillippy|first2=Adam|last3=Delcher|first3=Arthur L|last4=Smoot|first4=Michael|last5=Shumway|first5=Martin|last6=Antonescu|first6=Corina|last7=Salzberg|first7=Steven L|date=2004|title=बड़े जीनोम की तुलना के लिए बहुमुखी और खुला सॉफ्टवेयर|journal=Genome Biology |volume=5|issue=2|pages=R12|doi=10.1186/gb-2004-5-2-r12|issn=1465-6906 |pmc= 395750|pmid=14759262}}</ref> दो स्ट्रिंग्स को देखते हुए, एमईएम सामान्य सबस्ट्रिंग हैं जिन्हें बेमेल पैदा किए बिना बाएं या दाएं नहीं बढ़ाया जा सकता है।<ref>{{Cite journal|last1=Khan|first1=Zia|last2=Bloom|first2=Joshua S.|last3=Kruglyak|first3=Leonid|last4=Singh|first4=Mona|date=2009-07-01|title=विरल प्रत्यय सरणियों का उपयोग करके बड़े अनुक्रम डेटासेट में अधिकतम सटीक मिलान खोजने के लिए एक व्यावहारिक एल्गोरिदम|url= |journal=Bioinformatics |volume=25|issue=13|pages=1609–1616|doi=10.1093/bioinformatics/btp275 |pmc=2732316|pmid=19389736}}</ref>
+जैव सूचना विज्ञान और जीनोमिक्स के क्षेत्र में पेश की गई एक समान समस्या अधिकतम सटीक मिलान (एमईएम) है।<ref>{{Cite journal|last1=Kurtz|first1=Stefan|last2=Phillippy|first2=Adam|last3=Delcher|first3=Arthur L|last4=Smoot|first4=Michael|last5=Shumway|first5=Martin|last6=Antonescu|first6=Corina|last7=Salzberg|first7=Steven L|date=2004|title=बड़े जीनोम की तुलना के लिए बहुमुखी और खुला सॉफ्टवेयर|journal=Genome Biology |volume=5|issue=2|pages=R12|doi=10.1186/gb-2004-5-2-r12|issn=1465-6906 |pmc= 395750|pmid=14759262}}</ref> दो स्ट्रिंग्स को देखते हुए, एमईएम सामान्य उपस्ट्रिंग हैं जिन्हें असंगत उत्पन्न किए बिना बाएं या दाएं नहीं बढ़ाया जा सकता है।<ref>{{Cite journal|last1=Khan|first1=Zia|last2=Bloom|first2=Joshua S.|last3=Kruglyak|first3=Leonid|last4=Singh|first4=Mona|date=2009-07-01|title=विरल प्रत्यय सरणियों का उपयोग करके बड़े अनुक्रम डेटासेट में अधिकतम सटीक मिलान खोजने के लिए एक व्यावहारिक एल्गोरिदम|url= |journal=Bioinformatics |volume=25|issue=13|pages=1609–1616|doi=10.1093/bioinformatics/btp275 |pmc=2732316|pmid=19389736}}</ref>
-== खोज कलन-विधि   के उदाहरण ==
+== विवृत्त कलन-विधि के उदाहरण ==
-=== अनुभवहीन स्ट्रिंग खोज ===
+=== सरल स्ट्रिंग विवृत्त   ===
-यह देखने का एक सरल और अप्रभावी तरीका है कि एक स्ट्रिंग दूसरे के अंदर कहां होती है, प्रत्येक सूचकांक को एक-एक करके जांचना। सबसे पहले, हम देखते हैं कि क्या भूसे के ढेर के पहले अक्षर से शुरू होने वाली सुई की कोई प्रति है; यदि नहीं, तो हम यह देखना चाहेंगे कि क्या भूसे के ढेर के दूसरे अक्षर से शुरू होने वाली सुई की कोई प्रतिलिपि है, इत्यादि। सामान्य मामले में, हमें यह देखने के लिए कि यह एक गलत स्थिति है, प्रत्येक गलत स्थिति के लिए केवल एक या दो वर्णों को देखना होगा, इसलिए औसत मामले में, यह [[ बिग ओ अंकन ]] (एन + एम) चरण लेता है, जहां एन है घास के ढेर की लंबाई और मी सुई की लंबाई है; लेकिन सबसे खराब स्थिति में, आआआआआआआब जैसी स्ट्रिंग में आआआआब जैसी स्ट्रिंग की खोज करने पर बिग ओ नोटेशन(एनएम) की आवश्यकता होती है
+एक सरल और अप्रभावी विधि जिसके द्वारा देखा जा सकता है कि एक स्ट्रिंग किसी अन्य स्ट्रिंग में कहां होती है, सबसे पहले, हम देखते हैं कि क्या हेस्टेक के पहले अक्षर से पैटर्न की एक प्रतिलिपि है; यदि नहीं, तो हम देखते हैं कि क्या हेस्टेक के दूसरे अक्षर से पैटर्न की एक प्रतिलिपि है, और ऐसा आगे भी होता है। सामान्य विधि में, हमें गलत स्थान के प्रत्येक अक्षर को देखने के लिए केवल एक या दो अक्षर देखने की जरूरत होती है जिससे हम यह देख सकें कि यह गलत स्थान है, इसलिए औसत स्थितियों में, इसमें O(n + m) चरण लगते हैं, जहां n हेस्टेक की लंबाई है और m पैटर्न की लंबाई है; लेकिन सबसे खराब मामले में, "aaaaaaaaab" जैसे स्ट्रिंग में "aaaab" जैसे स्ट्रिंग की विवृत्त करने में O(nm) समय लगता है।
-=== परिमित-अवस्था-ऑटोमेटन-आधारित खोज ===
+=== परिमित-अवस्था-ऑटोमेटन-आधारित विवृत्त   ===
-[[Image:DFA search mommy.svg|200px|right]]इस दृष्टिकोण में, एक [[नियतात्मक परिमित ऑटोमेटन]] (डीएफए) का निर्माण करके बैकट्रैकिंग से बचा जाता है जो संग्रहीत खोज स्ट्रिंग को पहचानता है। इन्हें बनाना महंगा है—ये आम तौर पर पावरसेट निर्माण का उपयोग करके बनाए जाते हैं—लेकिन इनका उपयोग बहुत जल्दी हो जाता है। उदाहरण के लिए, दाईं ओर दिखाया गया नियतात्मक परिमित ऑटोमेटन MOMMY शब्द को पहचानता है। मनमाने ढंग से नियमित अभिव्यक्तियों की खोज के लिए इस दृष्टिकोण को अक्सर अभ्यास में सामान्यीकृत किया जाता है।
+[[Image:DFA search mommy.svg|200px|right]]इस दृष्टिकोण में, पीछे जाने को दूर किया जाता है द्वारा एक निर्दिष्ट सीमित स्वतंत्र ऑटोमेटन का निर्माण करके जो संग्रहीत विवृत्त स्ट्रिंग को मान्य करता है। इनका निर्माण करना खर्चीला होता है सामान्यतः यह पावरसेट निर्माण का उपयोग करके बनाया जाता है - लेकिन उपयोग करने में बहुत तेज होते हैं। उदाहरण के लिए, दिए गए डीएफए में "एमओएमएमवाई" शब्द को मान्य करता है। यह दृष्टिकोण सामान्यतः व्यावहारिक रूप से सामान्य किया जाता है जिससे  विचाराधीन नियमित अभिव्यक्तियों के लिए खोज की जा सके।
 ===स्टब्स===
-नुथ-मॉरिस-प्रैट कलन-विधि  |नुथ-मॉरिस-प्रैट एक नियतात्मक परिमित ऑटोमेटन की गणना करता है जो प्रत्यय के रूप में खोज करने के लिए स्ट्रिंग के साथ इनपुट को पहचानता है, बॉयर-मूर स्ट्रिंग-खोज कलन-विधि  |बॉयर-मूर सुई के अंत से खोज शुरू करता है, इसलिए यह आमतौर पर प्रत्येक चरण में पूरी सुई-लंबाई तक आगे कूद सकता है। बेज़ा-येट्स इस बात पर नज़र रखता है कि क्या पिछले j अक्षर खोज स्ट्रिंग का उपसर्ग थे, और इसलिए यह फ़ज़ी स्ट्रिंग खोज के लिए अनुकूल है। [[थकना]] बेज़ा-येट्स के दृष्टिकोण का एक अनुप्रयोग है।
+नुथ-मॉरिस-प्रैट कलन-विधि  |नुथ-मॉरिस-प्रैट एक नियतात्मक परिमित ऑटोमेटन की गणना करता है जो प्रत्यय के रूप में विवृत्त    करने के लिए स्ट्रिंग के साथ इनपुट को पहचानता है, बॉयर-मूर स्ट्रिंग-विवृत्त    कलन-विधि  |बॉयर-मूर सुई के अंत से विवृत्त    शुरू करता है, इसलिए यह आमतौर पर प्रत्येक चरण में पूरी सुई-लंबाई तक आगे कूद सकता है। बेज़ा-येट्स इस बात पर नज़र रखता है कि क्या पिछले j अक्षर विवृत्त    स्ट्रिंग का उपसर्ग थे, और इसलिए यह फ़ज़ी स्ट्रिंग विवृत्त    के लिए अनुकूल है। [[थकना]] बेज़ा-येट्स के दृष्टिकोण का एक अनुप्रयोग है।
 === सूचकांक विधियाँ ===
-तेज़ खोज कलन-विधि   टेक्स्ट को प्रीप्रोसेस करते हैं। एक [[ सबस्ट्रिंग सूचकांक ]] बनाने के बाद, उदाहरण के लिए एक [[प्रत्यय वृक्ष]] या [[प्रत्यय सरणी]], एक पैटर्न की घटनाओं को जल्दी से पाया जा सकता है। उदाहरण के तौर पर, एक प्रत्यय वृक्ष बनाया जा सकता है <math>\Theta(n)</math> समय, और सब कुछ <math>z</math> एक पैटर्न की घटनाएँ पाई जा सकती हैं <math>O(m)</math> इस धारणा के तहत समय कि वर्णमाला का एक स्थिर आकार होता है और प्रत्यय वृक्ष के सभी आंतरिक नोड्स जानते हैं कि उनके नीचे कौन सी पत्तियाँ हैं। उत्तरार्द्ध को प्रत्यय वृक्ष की जड़ से [[गहराई-पहली खोज]] चलाकर पूरा किया जा सकता है।
+तेज़ विवृत्त    कलन-विधि   टेक्स्ट को प्रीप्रोसेस करते हैं। एक [[ सबस्ट्रिंग सूचकांक ]] बनाने के बाद, उदाहरण के लिए एक [[प्रत्यय वृक्ष]] या [[प्रत्यय सरणी]], एक पैटर्न की घटनाओं को जल्दी से पाया जा सकता है। उदाहरण के तौर पर, एक प्रत्यय वृक्ष बनाया जा सकता है <math>\Theta(n)</math> समय, और सब कुछ <math>z</math> एक पैटर्न की घटनाएँ पाई जा सकती हैं <math>O(m)</math> इस धारणा के तहत समय कि वर्णमाला का एक स्थिर आकार होता है और प्रत्यय वृक्ष के सभी आंतरिक नोड्स जानते हैं कि उनके नीचे कौन सी पत्तियाँ हैं। उत्तरार्द्ध को प्रत्यय वृक्ष की जड़ से [[गहराई-पहली खोज|गहराई-पहली विवृत्त]]    चलाकर पूरा किया जा सकता है।
 === अन्य प्रकार ===
-कुछ खोज विधियाँ, उदाहरण के लिए [[ट्रिग्राम खोज]], का उद्देश्य मिलान/गैर-मिलान के बजाय खोज स्ट्रिंग और पाठ के बीच निकटता स्कोर ढूंढना है। इन्हें कभी-कभी अनुमानित स्ट्रिंग मिलान कहा जाता है| अस्पष्ट खोजें.
+कुछ विवृत्त    विधियाँ, उदाहरण के लिए [[ट्रिग्राम खोज|ट्रिग्राम विवृत्त]]   , का उद्देश्य मिलान/गैर-मिलान के बजाय विवृत्त    स्ट्रिंग और पाठ के बीच निकटता स्कोर ढूंढना है। इन्हें कभी-कभी अनुमानित स्ट्रिंग मिलान कहा जाता है| अस्पष्ट विवृत्त   ें.
-== खोज कलन-विधि   का वर्गीकरण ==
+== विवृत्त    कलन-विधि   का वर्गीकरण ==
 === कई पैटर्न द्वारा वर्गीकरण ===
@@ Line 64: / Line 64: @@
 ==== एकल-पैटर्न कलन-विधि  ====
-निम्नलिखित संकलन में, m पैटर्न की लंबाई है, n खोजने योग्य पाठ की लंबाई है, और k = |Σ| वर्णमाला का आकार है.
+निम्नलिखित संकलन में, m पैटर्न की लंबाई है, n विवृत्त   ने योग्य पाठ की लंबाई है, और k = |Σ| वर्णमाला का आकार है.
 {| class="wikitable"
 |-
@@ Line 108: / Line 108: @@
 |}
 :1.{{note|Asymptotic times}}एसिम्प्टोटिक समय को बिग ओ नोटेशन|ओ, Ω, और Θ नोटेशन का उपयोग करके व्यक्त किया जाता है।
-:2.{{note|libc}}ग्लिबैक में मेमम और सी स्ट्रिंग हैंडलिंग#फ़ंक्शन खोज फ़ंक्शन को कार्यान्वित करने के लिए उपयोग किया जाता है<ref>{{cite web |title=glibc/string/str-two-way.h |url=https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |access-date=2022-03-22 |archive-date=2020-09-20 |archive-url=https://web.archive.org/web/20200920180414/https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |url-status=live }}</ref> और [[माँसपेशियाँ]]<ref>{{cite web |title=musl/src/string/memmem.c |url=http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |access-date=23 November 2019 |archive-date=1 October 2020 |archive-url=https://web.archive.org/web/20201001184748/http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |url-status=live }}</ref> [[सी मानक पुस्तकालय]]।
+:2.{{note|libc}}ग्लिबैक में मेमम और सी स्ट्रिंग हैंडलिंग#फ़ंक्शन विवृत्त    फ़ंक्शन को कार्यान्वित करने के लिए उपयोग किया जाता है<ref>{{cite web |title=glibc/string/str-two-way.h |url=https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |access-date=2022-03-22 |archive-date=2020-09-20 |archive-url=https://web.archive.org/web/20200920180414/https://code.woboq.org/userspace/glibc/string/str-two-way.h.html |url-status=live }}</ref> और [[माँसपेशियाँ]]<ref>{{cite web |title=musl/src/string/memmem.c |url=http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |access-date=23 November 2019 |archive-date=1 October 2020 |archive-url=https://web.archive.org/web/20201001184748/http://git.musl-libc.org/cgit/musl/tree/src/string/memmem.c |url-status=live }}</ref> [[सी मानक पुस्तकालय]]।
 :3.{{note|fuzzy+regexp}}[[अनुमानित स्ट्रिंग मिलान]] और (संभावित-अनंत) पैटर्न के सेट को नियमित भाषाओं के रूप में प्रदर्शित करने के लिए बढ़ाया जा सकता है।{{Citation needed|date=March 2022|reason=No reference found for the 2-way algorithm}}
-बॉयर-मूर स्ट्रिंग-खोज एल्गोरिथ्म व्यावहारिक स्ट्रिंग-खोज साहित्य के लिए मानक बेंचमार्क रहा है।<ref name=":0">{{cite journal |last1=Hume |last2=Sunday |year=1991 |title=तेज़ स्ट्रिंग खोज|journal=Software: Practice and Experience |volume=21 |issue=11 |pages=1221–1248 |doi=10.1002/spe.4380211105 |s2cid=5902579 |url=https://semanticscholar.org/paper/d9912ea262986794e29e3f15e5f8930d42f2ced4 |access-date=2019-11-29 |archive-date=2022-05-10 |archive-url=https://web.archive.org/web/20220510030246/https://www.semanticscholar.org/paper/Fast-string-searching-Hume-Sunday/d9912ea262986794e29e3f15e5f8930d42f2ced4 |url-status=live }}</ref>
+बॉयर-मूर स्ट्रिंग-विवृत्त    एल्गोरिथ्म व्यावहारिक स्ट्रिंग-विवृत्त    साहित्य के लिए मानक बेंचमार्क रहा है।<ref name=":0">{{cite journal |last1=Hume |last2=Sunday |year=1991 |title=तेज़ स्ट्रिंग खोज|journal=Software: Practice and Experience |volume=21 |issue=11 |pages=1221–1248 |doi=10.1002/spe.4380211105 |s2cid=5902579 |url=https://semanticscholar.org/paper/d9912ea262986794e29e3f15e5f8930d42f2ced4 |access-date=2019-11-29 |archive-date=2022-05-10 |archive-url=https://web.archive.org/web/20220510030246/https://www.semanticscholar.org/paper/Fast-string-searching-Hume-Sunday/d9912ea262986794e29e3f15e5f8930d42f2ced4 |url-status=live }}</ref>
 ==== पैटर्न के एक सीमित सेट का उपयोग करने वाले कलन-विधि  ====
-निम्नलिखित संकलन में, एम सबसे लंबे पैटर्न की लंबाई है, एम उनकी कुल लंबाई है, एन खोजे जाने योग्य पाठ की लंबाई है, ओ घटनाओं की संख्या है।
+निम्नलिखित संकलन में, एम सबसे लंबे पैटर्न की लंबाई है, एम उनकी कुल लंबाई है, एन विवृत्त   े जाने योग्य पाठ की लंबाई है, ओ घटनाओं की संख्या है।
 {| class="wikitable"
@@ Line 181: / Line 181: @@
 *[[संपीड़ित पैटर्न मिलान]]
 *[[वाइल्डकार्ड का मिलान]]
-*[[पूरा पाठ खोजें]]
+*[[पूरा पाठ खोजें|पूरा पाठ विवृत्त   ें]]
 ==संदर्भ==

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt Pattern Matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting

Anonymous

Search

स्ट्रिंग-सर्चिंग एल्गोरिदम: Difference between revisions

Namespaces

More

Page actions

Revision as of 12:25, 16 July 2023

Contents

अवलोकन