🐾 🐆 ☄️ सबसे छोटी सामान्य सुपरस्ट्रिंग समस्या 👩🏻‍🌾 🏢 👩🏼‍🏭

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

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

सावधानी, 4 मेगाबाइट!

अधिकांश भाग के लिए, लेख एक समझने योग्य भाषा में अनुवाद करने का प्रयास है, उदाहरण के साथ सीज़न, और निश्चित रूप से, जावा में डैन गैसफ़ील्ड की पुस्तक (उपयोग किए गए साहित्य देखें) से सुपरलाइन बनाने के लिए एक 4-अनुमानित एल्गोरिथ्म में लागू करें। लेकिन पहले, एक छोटा सा परिचय और एक 2-अनुमानित, लालची एल्गोरिथ्म।

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

इनपुट: एस ₁ , एस ₂ , ..., एस _एन - परिमित वर्णमाला ई * की लाइनों का सेट।
निष्कर्ष: X वर्णमाला E * की एक स्ट्रिंग है जिसमें प्रत्येक स्ट्रिंग S _1. है। एक _{विकल्प के} रूप में, जहाँ लंबाई X है। कम से कम।

एक उदाहरण है। लाइनों का सेट S = {abc, cde, eab} लें। संघनन के मामले में, आउटपुट सुपरलाइन की लंबाई 9 (X = abccdeeab) होगी, जो स्पष्ट रूप से सबसे अच्छा विकल्प नहीं है, क्योंकि लाइनों का प्रत्यय-उपसर्ग मैच हो सकता है। इस मैच की लंबाई को ओवरलैप कहा जाएगा। (अंग्रेजी शब्द का चुनाव आकस्मिक नहीं था, क्योंकि इसका रूसी में विशिष्ट और अस्पष्ट अनुवाद नहीं है। रूसी भाषा के साहित्य में, शब्द ओवरलैप, चौराहे, ओवरलैप और प्रत्यय-उपसर्ग मैच आमतौर पर उपयोग किए जाते हैं)।

रिट्रीट। ऐड-इन्स के लिए निर्माण एल्गोरिदम को लागू करने की प्रक्रिया में ओवरलैप की अवधारणा सबसे महत्वपूर्ण है। स्ट्रिंग एस के उपसर्ग के साथ स्ट्रिंग एस _i के प्रत्यय के अधिकतम मैच की लंबाई खोजने के लिए स्ट्रिंग्स की एक ऑर्डर की गई जोड़ी (S _i , S _j ) के लिए ओवरलैप की गणना कम हो जाती है।

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

/* *       s1 *     s2 (  s1  s2) */ private static int overlap(String s1, String s2) { int s1last = s1.length() - 1; int s2len = s2.length(); int overlap = 0; for (int i = s1last, j = 1; i > 0 && j < s2len; i--, j++) { String suff = s1.substring(i); String pref = s2.substring(0, j); if (suff.equals(pref)) overlap = j; } return overlap; }

उदाहरण के लिए लौटें। यदि हम स्ट्रिंग्स S = {abc, cde, eab} को उनके ओवरलैप्स को ध्यान में रखते हैं, तो हमें स्ट्रिंग X = abcdeab 7 की लंबाई के साथ मिलता है, जो पिछले एक की तुलना में छोटा है, लेकिन सबसे छोटा नहीं है। सबसे छोटी स्ट्रिंग तब प्राप्त की जाएगी जब 3-1-2 के क्रम में ओवरलैप्स के साथ तार को समतल करते हैं, फिर परिणामस्वरूप स्ट्रिंग एक्स = ईबकेड की लंबाई 6. होगी। इस प्रकार, हमने अपने ओवरलैप को ध्यान में रखते हुए समवर्ती तारों के इष्टतम क्रम को खोजने में समस्या को कम किया।

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

लालची एल्गोरिथ्म

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

1. जबकि S में एक से अधिक रेखाएँ हैं, हम अधिकतम ओवरलैप के साथ दो रेखाएँ पाते हैं और उन्हें एक में मिलाते हैं (उदाहरण के लिए, ABCD + CDEFG = ABCDEFG)।
2. हम एस में बची एक लाइन को वापस करते हैं।

इस एल्गोरिथ्म का एक उदाहरण कार्यान्वयन निम्नलिखित सूची में प्रस्तुत किया गया है।

  /* *         , *      ( ). */ public static String createSuperString(ArrayList<String> strings) { while (strings.size() > 1) { int maxoverlap = 0; String msi = strings.get(0), msj = strings.get(1); for (String si : strings) for (String sj : strings) { if (si.equals(sj)) continue; int curoverlap = overlap(si, sj); if (curoverlap > maxoverlap) { maxoverlap = curoverlap; msi = si; msj = sj; } } strings.add(merge(msi, msj, maxoverlap)); strings.remove(msi); strings.remove(msj); } return strings.get(0); }

इस सूची में एक और सरल मर्ज फ़ंक्शन दिखाई दिया, जो एक ओवरलैप को ध्यान में रखते हुए दो लाइनों को एक में मिला देता है। चूंकि उत्तरार्द्ध की गणना पहले ही की जा चुकी है, इसलिए इसे केवल एक पैरामीटर के रूप में पारित करना तर्कसंगत है।

  /* *    s1  s2   len,   *   overlap(s1, s2) */ private static String merge(String s1, String s2, int len) { s2 = s2.substring(len); return s1 + s2; }

एक उदाहरण ( सबसे खराब स्थिति ):
● दर्ज करें : S = {"ab ^k ", "b ^k c", "b ^{k + 1} "}
● लालची एल्गोरिथ्म का निष्कर्ष : 4 + 4 k की लंबाई के साथ "ab ^k cb ^{k + 1} "
● इष्टतम एल्गोरिथ्म का निष्कर्ष : 4 + 2k की लंबाई के साथ "ab ^{k + 1} c"

सबसे खराब स्थिति सन्निकटन कारक

4-अनुमानित ब्लूम-यांग-ली-ट्रॉमप-यानाककिस एल्गोरिथ्म

सामान्यतया, इस एल्गोरिथ्म का कोई नाम नहीं है और कोई भी इसे मेरी तरह नहीं कहता है। इसे बस सबसे छोटी सुपरलाइन बनाने के लिए 4-अनुमानित एल्गोरिथ्म कहा जाता है। लेकिन जब से ब्लम, यंग, ली, ट्रम्प और यानाकिस इसके साथ आए, तो इस तरह की हेडलाइन क्यों नहीं दी गई?

स्पष्टता के लिए , एल्गोरिथ्म के विश्लेषण के दौरान मैं S = {S ₀ : "cde", S ₁ : "abc", S ₂ : "eab", S ₃ : "fgh, S ₄ :" सेट के लिए एक सुपरलाइन बनाने का एक उदाहरण दूंगा। ghf ”, S ₅ :“ hed ”} ।

एल्गोरिथ्म का मुख्य विचार एक पूर्ण दिशात्मक भारित ग्राफ के लिए न्यूनतम पूर्ण लंबाई के चक्रों द्वारा आवरणों का पता लगाना है, जिनके कोने किसी दिए गए सेट की पंक्तियाँ हैं और S _i से S _j तक के किनारे का वजन सभी i, j के लिए ओवरलैप (S _i , S _j ) के बराबर है।

हमारे उदाहरण के लिए ग्राफ (दृश्यता के लिए कोने एस के बजाय i द्वारा हस्ताक्षरित हैं):

मेरे कार्यान्वयन में, मैं इस ग्राफ को एक आसन्न मैट्रिक्स के रूप में प्रतिनिधित्व करूँगा, जो निम्न सूची में दिखाए गए भोजपूर्ण तरीके से बनेगा (धारा 16.17 [1] डी। में गैसफील्ड का तर्क है कि मैट्रिक्स अधिक कुशलता से बन सकता है, लेकिन जिस तरह से यह मैट्रिक्स उत्पन्न होता है, वह विचार को प्रभावित नहीं करता है। इस एल्गोरिथ्म का)।

  int n = strings.size(); //   overlap'   //   (Si, Sj). int[][] overlaps = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) overlaps[i][j] = overlap(strings.get(i), strings.get(j));

हमारे उदाहरण के लिए, आसन्न मैट्रिक्स इस तरह दिखेगा:

आसन्न मैट्रिक्स के निर्माण के बाद, न्यूनतम पूर्ण लंबाई के चक्र द्वारा एक आवरण को खोजने के लिए आवश्यक हो जाता है। इस समस्या को "असाइनमेंट समस्या" को कम करके इस तरह के कवरेज को पाया जा सकता है। तो, कार्य अधिकतम वजन का पूरा उद्देश्य खोजने के लिए था (जैसा कि यह निकला, एल्गोरिथ्म का यह कदम प्रमुख समय लेता है)। तेज़ और आसान ([1] p.16.19.13) यह गंतव्य लालची विधि से पाया जा सकता है।

लालची नियुक्ति ([१] p.16.19.13)

इनपुट डेटा: मैट्रिक्स ए आकार k × k।
परिणाम: पूर्ण असाइनमेंट एम।

एम = Ø रखो और सभी कोशिकाओं को एक सुलभ घोषित करें।
जबकि A में उपलब्ध कोशिकाएं हैं
1. उपलब्ध कोशिकाओं में से, उच्चतम वजन वाले सेल (i, j) का चयन करें।
2. M में सेल (i, j) रखें और पंक्ति I और कॉलम j को दुर्गम में सेल बनाएँ।
3. अंत;
पूर्ण असाइनमेंट जारी करें एम।

आप एक सरणी (int [] M = new int [k]) के रूप में कोड में M का प्रतिनिधित्व कर सकते हैं और निर्देश 2.2 के पहले भाग को M [i] = j के रूप में मान सकते हैं; चूंकि पूर्ण असाइनमेंट में, प्रत्येक नंबर 0 से k तक पंक्ति सूचकांक के रूप में एक बार और स्तंभ सूचकांक के रूप में एक बार होता है।

पूर्ण असाइनमेंट गणना कार्यान्वयन का एक उदाहरण निम्नलिखित सूची में प्रस्तुत किया गया है।

  /* * ,     *   .  - O(k*k*log(k)) */ private static int[] assignment(int[][] a) { int n = a.length; boolean[][] notallow = new boolean[n][n]; int[] m = new int[n]; while (true) { int max = -1, maxi = -1, maxj = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (notallow[i][j]) continue; if (a[i][j] > max) { max = a[i][j]; maxi = i; maxj = j; } } } if (max == -1) break; m[maxi] = maxj; for (int i = 0; i < n; i++) { notallow[maxi][i] = true; notallow[i][maxj] = true; } } return m; }

हमारे उदाहरण के लिए लालची विधि द्वारा पूर्ण अधिकतम भार असाइनमेंट की चरण-दर-चरण गणना:

अब जब अधिकतम भार के पूर्ण असाइनमेंट की गणना की गई है, तो न्यूनतम कुल लंबाई के चक्रों में कवरेज की गणना करना आवश्यक है। ऐसा करने के लिए, आपको चाहिए:

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

लूप की मेमोरी कवरेज प्रतिनिधित्व को पंक्ति सूचकांक सूचियों की सूची के रूप में व्यवस्थित किया जा सकता है ।

एल्गोरिथ्म लिस्टिंग (असाइन - पूर्ण असाइनमेंट):

  //       //    assign ArrayList<ArrayList<Integer>> cycles = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> cycle = new ArrayList<Integer>(); boolean[] mark = new boolean[assign.length]; for (int i = 0; i < assign.length; i++) { if (mark[i]) continue; cycle.add(i); mark[i] = true; if (assign[i] == cycle.get(0)) { cycles.add(cycle); cycle = new ArrayList<Integer>(); i = 0; } else { i = assign[i] - 1; } }

हमारे उदाहरण के लिए, लूप द्वारा कवरेज ढूंढना इस तरह होगा:

चक्र में परिणामी कवरेज को मूल ग्राफ पर प्रदर्शित किया जा सकता है, केवल उन किनारों को छोड़कर जो कवरेज में गिर गए।

विधानसभा। अब जब कवरेज के सभी चक्रों की गणना की गई है, तो आप सीधे, सुपरस्ट्रक्चर को असेंबल करना शुरू कर सकते हैं।

ऐसा करने के लिए, आपको उपसर्ग फ़ंक्शन की आवश्यकता होती है, जो स्ट्रिंग्स S ₁ और S _{2 को ले जाता है} और स्ट्रिंग S ₁ को दाएं से ओवरलैप (S ₁ , S ₂ ) वर्णों से काट देता है। लेकिन जब से सभी ओवरलैप्स को हमारे द्वारा लंबे समय तक गिना जाता है, तो फ़ंक्शन को लिखा जा सकता है ताकि यह केवल एक पंक्ति और वर्णों की संख्या ले जाए जिसके द्वारा इसे छोटा करने की आवश्यकता है।

  /* *    s1,   *  ov  */ private static String prefix(String s1, int ov) { return s1.substring(0, s1.length() - ov); }

अब, प्रत्येक चक्र C _i = {S ₁ , S ₂ , ..., S _k-1 , S _k } के लिए, उप-लाइन X _Ci = उपसर्ग (S ₁ , ओवरलैप (S ₁ , S ₂ )) ++ उपसर्ग (S ₂ ) को लिखना आवश्यक है। , ओवरलैप (S ₂ , S ...)) ++ उपसर्ग (S ..., ओवरलैप (S ..., S _k-1 )) ++ _{k k} ।

समस्या यह है कि, चूंकि एक कवरेज में लूप्स लूप हैं , इसका मतलब है कि हम उन्हें चक्रीय रूप से मोड़ सकते हैं और यह स्पष्ट नहीं है कि एक्स _सी सुपरस्ट्रक्चर के साथ किस लाइन का निर्माण शुरू करना है। उत्तर सरल है - आपको लूप को शिफ्ट करने की आवश्यकता है ताकि अंतिम और पहली पंक्ति के ओवरलैप को कम किया जा सके ।

उदाहरण से चक्रीय कोटिंग के पहले चक्र पर विचार करें।

यदि आप अंतिम और पहली पंक्तियों के ओवरलैप को कम नहीं करते हैं, लेकिन C ₀ = {1, 0, 2} लें, तो लाइन X _C0 = abc ++ cde ++ eb = abcdeab होगी, जो जाहिर तौर पर सबसे कम संभव नहीं है। इस लूप में न्यूनतम ओवरलैप 1 है, जिसका अर्थ है कि कोई भी अनुक्रम {0, 2, 1} (cde ++ eab ++ abc = cdeabc) या {2, 1, 0} (eab ++ abc ++ cc =) eabcde)।
निम्नलिखित एक कोड है जो कवरेज में प्रत्येक चक्र को बदलता है ताकि प्रत्येक चक्र की पहली और आखिरी पंक्तियों के ओवरलैप को कम किया जा सके और प्रत्येक चक्र के लिए ऐड-इन्स का निर्माण किया जा सके।

  //       ,  //  overlap       //      . ArrayList<String> superstrings = new ArrayList<String>(); for (ArrayList<Integer> c : cycles) { String str = ""; ArrayList<Integer> ovs = new ArrayList<Integer>(); for (int i = 0; i < c.size() - 1; i++) ovs.add(overlaps[c.get(i)][c.get(i+1)]); int min = overlaps[c.get(c.size()-1)][c.get(0)]; int shift = 0; for (int i = 0; i < ovs.size(); i++) if (ovs.get(i) < min) { min = ovs.get(i); shift = i + 1; } Collections.rotate(c, -shift); for (int i = 0; i < c.size() - 1; i++) str += prefix(strings.get(c.get(i)), overlaps[c.get(i)][c.get(i+1)]); str += strings.get(c.get(c.size()-1)); superstrings.add(str); }

अब हमारे पास कवरेज में प्रत्येक चक्र के लिए सबसे छोटा ऐड-इन्स है। 4 के कारक के साथ माना जाने वाला एल्गोरिदम इन पंक्तियों का एक सरल संयोजन मानता है।

  //     superstrings StringBuilder superstring = new StringBuilder(); for (String str : superstrings) superstring.append(str); return superstring.toString();

स्रोत कोड और परीक्षण

लालची (Greedy.java) और ब्लम-यांग-ली-ट्रॉमप-यानाककिस (Assign.java) एल्गोरिदम के लिए कोड बिट बिटकॉइन.org.andkorsh/scss/src पर गिट रिपॉजिटरी में उपलब्ध हैं। एक निष्पादन योग्य क्लास Main.java भी है, जो स्टार्टअप पर एल्गोरिदम की गति और इनपुट फ़ाइल के पथ को मापने के लिए प्रारंभ की संख्या पूछता है। इसके अलावा, मुख्य वर्ग स्वयं इनपुट उत्पन्न कर सकता है, इसके लिए फ़ाइल नाम के बजाय आपको "यादृच्छिक" दर्ज करने की आवश्यकता होती है, जिसके बाद लाइनों की संख्या, अधिकतम लाइन की लंबाई, एक निश्चित लंबाई या नहीं और वर्णमाला में वर्णों की संख्या का अनुरोध किया जाएगा। रिपोर्ट output.txt फ़ाइल में लिखी जाती है।

स्रोत कोड "1.6.0_05" संस्करण से शुरू होने वाले जावाक द्वारा संकलित किए जाने की गारंटी है।

मुख्य वर्ग के परीक्षण समारोह का उपयोग करके परीक्षण किया जाता है।

  private static int test(ArrayList<String> substrings, String superstring) { int errors = 0; for (String substring : substrings) if (superstring.indexOf(substring) < 0) errors++; return errors; }

साहित्य का इस्तेमाल किया

[१] : डैन गैसफ़ील्ड। एल्गोरिदम में लाइनें, पेड़ और क्रम। कंप्यूटर विज्ञान और कम्प्यूटेशनल जीव विज्ञान। नेवस्की बोली, BHV-पीटर्सबर्ग, 2003 - 656 पी .: आईएसबीएन 5-7940-0103-8, 5-94157-321-9, 0-521-58519-8।
www.ozon.ru/context/detail/id/1393109

[२] : डैन गुसफ़ील्ड। स्ट्रिंग्स, ट्रीज़ और सीक्वेंस पर एल्गोरिदम: कंप्यूटर साइंस और कम्प्यूटेशनल बायोलॉजी। कैंब्रिज, 1997 की एकता का दबाव - 534 पी .: आईएसबीएन -10: 0521585198, आईएसबीएन -13: 978-0521585194।
www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198

[३] : शुनजी ली, वेनझेंग ची। व्याख्यान # 3: सबसे छोटा सामान्य सुपरस्ट्रिंग - CS 352 (उन्नत एल्गोरिदम), स्प्रिंग 2011।
cs.carleton.edu/faculty/dlibenno/old/cs352-spring11/L03-shortest-superstring.pdf

सबसे छोटी सामान्य सुपरस्ट्रिंग समस्या

लालची एल्गोरिथ्म

4-अनुमानित ब्लूम-यांग-ली-ट्रॉमप-यानाककिस एल्गोरिथ्म

स्रोत कोड और परीक्षण

साहित्य का इस्तेमाल किया

More articles: