दीर्घ सामान्य उपरज्जु (लांगेस्ट कॉमन सबस्ट्रिंग)

Not to be confused with longest common subsequence.

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

उदाहरण

स्ट्रिंग्स BADANAT और CANADAS अधिकतम-लंबाई वाले सबस्ट्रिंग्स ADA और ANA को साझा करते हैं।

चित्र दो स्ट्रिंग दिखाता है जहां समस्या के कई समाधान हैं। हालाँकि सबस्ट्रिंग घटनाएँ हमेशा ओवरलैप होती हैं, अब उन्हें एकजुट करके सामान्य सबस्ट्रिंग प्राप्त नहीं किया जा सकता है।

स्ट्रिंग ABABC, BABCA और ABCBA में केवल एक सबसे लंबी उभयनिष्ठ उपस्ट्रिंग है, अर्थात। लंबाई की ABC 3. अन्य सामान्य उपस्ट्रिंग A , AB , B , BA , BC और C हैं।

  एबीएबीसी
    |||
   बाबा
    |||
    एबीसीबीए

समस्या परिभाषा

दो तार दिए गए, $S$ लम्बाई का $m$ और $T$ लम्बाई का $n$, एक सबसे लंबी स्ट्रिंग ढूंढें जो दोनों का उपस्ट्रिंग है $S$ और $T$.

एक सामान्यीकरण k-कॉमन सबस्ट्रिंग समस्या है। तारों के सेट को देखते हुए $S=\{S_{1},...,S_{K}\}$, कहाँ $|S_{i}|=n_{i}$ और $\Sigma n_{i}=N$. प्रत्येक के लिए खोजें $2\leq k\leq K$, एक सबसे लंबी स्ट्रिंग जो कम से कम सबस्ट्रिंग के रूप में होती है $k$ तार.

एल्गोरिदम

कोई सबसे लंबे सामान्य उपस्ट्रिंग की लंबाई और शुरुआती स्थिति का पता लगा सकता है $S$ और $T$ बिग ओ नोटेशन में#बैचमैन-लैंडौ नोटेशन का परिवार|$\Theta$$(n+m)$ सामान्यीकृत प्रत्यय वृक्ष की सहायता से समय। यदि आकार हो तो गणना के राम शब्द मॉडल में एक तेज़ एल्गोरिदम प्राप्त किया जा सकता है $\sigma$ इनपुट वर्णमाला में है $2^{o({\sqrt {\log(n+m)}})}$. विशेष रूप से, यह एल्गोरिथम चलता है $O((n+m)\log \sigma /{\sqrt {\log(n+m)}})$ समय का उपयोग $O((n+m)\log \sigma /\log(n+m))$ अंतरिक्ष। गतिशील प्रोग्रामिंग लागतों द्वारा समस्या का समाधान $\Theta (nm)$. सामान्यीकृत समस्या का समाधान लेते हैं $\Theta (n_{1}+...+n_{K})$ अंतरिक्ष और $\Theta (n_{1}$·...·$n_{K})$ गतिशील प्रोग्रामिंग के साथ समय और ले लो $\Theta ((n_{1}+...+n_{K})*K)$ सामान्यीकृत प्रत्यय वृक्ष के साथ समय।

प्रत्यय वृक्ष

स्ट्रिंग ABAB, BABA और ABBA के लिए सामान्यीकृत प्रत्यय वृक्ष, क्रमांकित 0, 1 और 2।

स्ट्रिंग्स के एक सेट की सबसे लंबी सामान्य सबस्ट्रिंग्स को स्ट्रिंग्स के लिए एक सामान्यीकृत प्रत्यय ट्री बनाकर पाया जा सकता है, और फिर सबसे गहरे आंतरिक नोड्स को ढूंढकर, जिनमें इसके नीचे के सबट्री में सभी स्ट्रिंग्स से लीफ नोड्स होते हैं। दाईं ओर का चित्र स्ट्रिंग ABAB, BABA और ABBA के लिए प्रत्यय वृक्ष है, जो अद्वितीय स्ट्रिंग टर्मिनेटर के साथ गद्देदार है, जो ABAB$0, BABA$1 और ABBA$2 बन जाता है। ए, बी, एबी और बीए का प्रतिनिधित्व करने वाले सभी नोड्स में सभी स्ट्रिंग्स के वंशज पत्ते हैं, जिनकी संख्या 0, 1 और 2 है।

प्रत्यय वृक्ष का निर्माण होता है $\Theta (N)$ समय (यदि वर्णमाला का आकार स्थिर है)। यदि पेड़ को नीचे से ऊपर तक एक बिट वेक्टर के साथ घुमाया जाता है जो बताता है कि प्रत्येक नोड के नीचे कौन सी स्ट्रिंग देखी जाती है, तो के-कॉमन सबस्ट्रिंग समस्या को हल किया जा सकता है $\Theta (NK)$ समय। यदि प्रत्यय वृक्ष को निरंतर समय न्यूनतम सामान्य पूर्वज पुनर्प्राप्ति के लिए तैयार किया जाता है, तो इसे हल किया जा सकता है $\Theta (N)$ समय।

गतिशील प्रोग्रामिंग

निम्नलिखित स्यूडोकोड गतिशील प्रोग्रामिंग के साथ दो स्ट्रिंग्स के बीच सबसे लंबे सामान्य सबस्ट्रिंग का सेट ढूंढता है:

फ़ंक्शन LongestCommonSubstring(S[1..r], T[1..n])
    एल := सरणी(1..आर, 1..एन)
    z := 0
    ret := {}

    i के लिए := 1..r
        j के लिए := 1..n
            यदि एस[आई] = टी[जे]
                यदि मैं = 1 या जे = 1
                    एल[आई, जे] := 1
                अन्य
                    एल[आई, जे] := एल[आई - 1, जे - 1] + 1
                यदि L[i, j] > z
                    जेड := एल[आई, जे]
                    ret := {S[i − z + 1..i]}
                अन्यथा यदि L[i, j] = z
                    ret := ret ∪ {S[i − z + 1..i]}
            अन्य
                एल[आई, जे] := 0
    वापसी सेवानिवृत्त

यह एल्गोरिदम चलता है $O(nr)$ समय। सरणी L उपसर्गों की सबसे लंबी सामान्य उपस्ट्रिंग की लंबाई संग्रहीत करता है S[1..i] और T[1..j] जो स्थिति पर समाप्त होता है i और j, क्रमश। परिवर्तनशील z अब तक पाए गए सबसे लंबे सामान्य सबस्ट्रिंग की लंबाई को पकड़ने के लिए उपयोग किया जाता है। सेट ret लंबाई के तारों के सेट को पकड़ने के लिए उपयोग किया जाता है z. सेट ret केवल सूचकांक को संग्रहित करके कुशलतापूर्वक सहेजा जा सकता है i, जो इसके बजाय सबसे लंबे सामान्य सबस्ट्रिंग (आकार z का) का अंतिम वर्ण है S[i-z+1..i]. इस प्रकार प्रत्येक i के लिए सभी सबसे लंबे सामान्य उपस्ट्रिंग होंगे ret, S[(ret[i]-z)..(ret[i])].

कार्यान्वयन के मेमोरी उपयोग को कम करने के लिए निम्नलिखित युक्तियों का उपयोग किया जा सकता है:

• मेमोरी बचाने के लिए DP तालिका की केवल अंतिम और वर्तमान पंक्ति रखें ($O(\min(r,n))$ के बजाय $O(nr)$)
  • आंतरिक लूप को पीछे की ओर घुमाकर अंतिम और वर्तमान पंक्ति को उसी 1D सरणी पर संग्रहीत किया जा सकता है
• पंक्तियों में केवल गैर-शून्य मान संग्रहीत करें। यह सरणियों के बजाय हैश-टेबल का उपयोग करके किया जा सकता है। यह बड़े अक्षरों के लिए उपयोगी है.

यह भी देखें

• सबसे सबसे लंबी पैलिंड्रोमिक सबस्ट्रिंग
• एन-ग्राम|एन-ग्राम, लंबाई एन के सभी संभावित सबस्ट्रिंग जो एक स्ट्रिंग में समाहित हैं

बाहरी संबंध

• Dictionary of Algorithms and Data Structures: longest common substring
• Perl/XS implementation of the dynamic programming algorithm
• Perl/XS implementation of the suffix tree algorithm
• Dynamic programming implementations in various languages on wikibooks
• working AS3 implementation of the dynamic programming algorithm
• Suffix Tree based C implementation of Longest common substring for two strings