Closest string
सैद्धांतिक कंप्यूटर विज्ञान में, निकटतम स्ट्रिंग एक एनपी-हार्ड कम्प्यूटेशनल समस्या है, जो इनपुट स्ट्रिंग्स के एक सेट के ज्यामितीय केंद्र को खोजने का प्रयास करती है। "केंद्र" शब्द को समझने के लिए, दो तारों के बीच की दूरी को परिभाषित करना आवश्यक है। आमतौर पर, इस समस्या का अध्ययन हैमिंग दूरी को ध्यान में रखते हुए किया जाता है। औपचारिक परिभाषा अधिक औपचारिक रूप से, n लंबाई-m स्ट्रिंग s1, s2,., sn को देखते हुए, निकटतम स्ट्रिंग समस्या एक नई लंबाई-m स्ट्रिंग s की मांग करती है जैसे कि सभी i के लिए d (s, si) ≤ k, जहां d हैमिंग दूरी को दर्शाता है, और जहां k जितना संभव हो उतना छोटा है। निकटतम स्ट्रिंग समस्या का एक निर्णय समस्या संस्करण, जो एन. पी.-पूर्ण है, इसके बजाय के को एक अन्य इनपुट के रूप में लेता है और सवाल करता है कि क्या सभी इनपुट स्ट्रिंग के हैमिंग दूरी के भीतर एक स्ट्रिंग है। निकटतम स्ट्रिंग समस्या को सामान्य 1-केंद्र समस्या के एक विशेष मामले के रूप में देखा जा सकता है जिसमें तत्वों के बीच की दूरी को हैमिंग दूरी का उपयोग करके मापा जाता है। जैव सूचना विज्ञान में, निकटतम स्ट्रिंग समस्या डीएनए में संकेत खोजने की समस्या का एक गहन अध्ययन पहलू है। सरलीकरण और डेटा में कमी निकटतम स्ट्रिंग के उदाहरणों में ऐसी जानकारी हो सकती है जो समस्या के लिए आवश्यक नहीं है। कुछ अर्थों में, निकटतम स्ट्रिंग के सामान्य इनपुट में जानकारी होती है, जो समस्या की कठोरता में योगदान नहीं करती है। उदाहरण के लिए, यदि कुछ स्ट्रिंग्स में वर्ण a होता है, लेकिन किसी में भी वर्ण z नहीं होता है, तो सभी को zs के साथ बदलने से एक अनिवार्य रूप से समतुल्य उदाहरण मिलेगा, अर्थात्ः संशोधित उदाहरण के समाधान से, मूल समाधान को पुनर्स्थापित किया जा सकता है, और इसके विपरीत। इनपुट को सामान्य बनाना जब समान लंबाई साझा करने वाले सभी इनपुट स्ट्रिंग्स को एक दूसरे के ऊपर लिखा जाता है, तो वे एक मैट्रिक्स बनाते हैं। कुछ पंक्ति प्रकारों का समाधान पर अनिवार्य रूप से समान प्रभाव पड़ता है। उदाहरण के लिए, एक कॉलम को प्रविष्टियों (ए, ए, बी) के साथ दूसरे कॉलम (एक्स, एक्स, वाई) के साथ बदलने से एक अलग समाधान स्ट्रिंग हो सकती है, लेकिन समाधानशीलता को प्रभावित नहीं कर सकती है, क्योंकि दोनों कॉलम एक ही संरचना को व्यक्त करते हैं, अर्थात। पहली दो प्रविष्टियाँ बराबर हैं, लेकिन तीसरी से अलग हैं। एक इनपुट उदाहरण को प्रत्येक कॉलम में, ए के साथ सबसे अधिक बार होने वाले वर्ण, बी के साथ सबसे अधिक बार होने वाले वर्ण आदि को प्रतिस्थापित करके सामान्यीकृत किया जा सकता है। सामान्यीकृत उदाहरण के समाधान को देखते हुए, मूल उदाहरण को प्रत्येक कॉलम में समाधान के वर्णों को उसके मूल संस्करण में पुनर्निर्मित करके पाया जा सकता है। स्तंभों का क्रम समस्या की कठोरता में योगदान नहीं देता है। इसका मतलब है, अगर हम एक निश्चित क्रमपरिवर्तन π के अनुसार सभी इनपुट स्ट्रिंग्स को क्रमबद्ध करते हैं और उस संशोधित उदाहरण के लिए एक समाधान स्ट्रिंग s प्राप्त करते हैं, तो π−1 (s) मूल उदाहरण का समाधान होगा। उदाहरण तीन इनपुट स्ट्रिंग्स uvwx, xuwv और xvwu के साथ एक उदाहरण दिया गया है। इसे इस तरह एक मैट्रिक्स के रूप में लिखा जा सकता हैः पहले कॉलम में मान (u, x, x) हैं। चूँकि x वह वर्ण है जो सबसे अधिक बार दिखाई देता है, हम इसे a द्वारा प्रतिस्थापित करते हैं, और हम नए पहले स्तंभ (b, a, a) को प्राप्त करते हुए, b द्वारा दूसरे सबसे अधिक बार वर्ण u को प्रतिस्थापित करते हैं। दूसरे कॉलम में मान (v, u, v) हैं। जहाँ तक पहले स्तंभ का संबंध है, v को a द्वारा प्रतिस्थापित किया जाता है और u को b द्वारा प्रतिस्थापित किया जाता है, जिससे नया दूसरा स्तंभ (a, b, a) प्राप्त होता है। सभी कॉलम के साथ ऐसा करने से सामान्यीकृत उदाहरण मिलता है सामान्यीकरण से प्राप्त डेटा में कमी इनपुट को सामान्य बनाने से वर्णमाला का आकार कम हो जाता है और इनपुट स्ट्रिंग की संख्या कम हो जाती है। यह उन एल्गोरिदम के लिए उपयोगी हो सकता है जिनका चलने का समय वर्णमाला के आकार पर निर्भर करता है। सन्निकटन ली और अन्य। एक बहुपद-समय सन्निकटन योजना विकसित की जो बड़े छिपे हुए स्थिरांकों के कारण व्यावहारिक रूप से अनुपयोगी है। फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी सबसे करीबी स्ट्रिंग को हल किया जा सकता है, जहां k इनपुट स्ट्रिंग की संख्या है, L सभी स्ट्रिंग की लंबाई है और d समाधान स्ट्रिंग से किसी भी इनपुट स्ट्रिंग तक वांछित अधिकतम दूरी है। अन्य समस्याओं के साथ संबंध निकटतम स्ट्रिंग अधिक सामान्य निकटतम सबस्ट्रिंग समस्या का एक विशेष मामला है, जो सख्ती से अधिक कठिन है। जबकि निकटतम स्ट्रिंग कई तरीकों से फिक्स्ड-पैरामीटर ट्रैक्टेबल साबित होती है, इन मापदंडों के संबंध में निकटतम सबस्ट्रिंग डब्ल्यू [1]-हार्ड है। संदर्भ एन. पी.-कठिन समस्याएं औपचारिक भाषाएँ