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