स्ट्रिंग टाइलिंग एल्गोरिदम

मैं स्ट्रिंग टाइलिंग करने के लिए एक कुशल एल्गोरिदम खोज रहा हूं। मूल रूप से, आप स्ट्रिंग की एक सूची दी गई है, का कहना है कि BCD, CDE, ABC, A, और जिसके परिणामस्वरूप टाइलों स्ट्रिंग ABCDE होना चाहिए, क्योंकि BCDCDE उपज BCDE है, जो के साथ संरेखित फिर ABC के साथ अंतिम ABCDE उपज के साथ गठबंधन किया गया।स्ट्रिंग टाइलिंग एल्गोरिदम

वर्तमान में, मैं थोड़ा सा भद्दा एल्गोरिदम का उपयोग कर रहा हूं, जो निम्नानुसार काम करता है। तार के एक यादृच्छिक जोड़ी के साथ शुरू, BCD और CDE कहता हूँ, मैं का उपयोग करें (जावा में) के बाद:

public static String tile(String first, String second) { 
    for (int i = 0; i < first.length() || i < second.length(); i++) { 
    // "right" tile (e.g., "BCD" and "CDE") 
    String firstTile = first.substring(i); 
    // "left" tile (e.g., "CDE" and "BCD") 
    String secondTile = second.substring(i); 
    if (second.contains(firstTile)) { 
     return first.substring(0, i) + second; 
    } else if (first.contains(secondTile)) { 
     return second.substring(0, i) + first; 
    } 
    } 
    return EMPTY; 
} 

System.out.println(tile("CDE", "ABCDEF")); // ABCDEF 
System.out.println(tile("BCD", "CDE")); // BCDE 
System.out.println(tile("CDE", "ABC")); // ABCDE 
System.out.println(tile("ABC", tile("BCX", "XYZ"))); // ABCXYZ

हालांकि यह काम करता है, यह बहुत ही कुशल नहीं है, के रूप में यह बार-बार एक ही से अधिक अक्षर iterates।

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

मैं वर्तमान में Rabin-Karp algorithm का एल्गोरिदम की एसिम्प्टोटिक जटिलता में सुधार करने के लिए अनुकूलन की तलाश में हूं, लेकिन मैं इस मामले में आगे बढ़ने से पहले कुछ सलाह सुनना चाहता हूं।

अग्रिम धन्यवाद। उदाहरण के लिए, {ABC, CBA} जिसमें ABCBA या CBABC परिणाम सकता है - -, किसी भी खपरैल वापस किया जा सकता

स्थितियों के लिए जहां अस्पष्टता नहीं है। हालांकि, यह स्थिति शायद ही कभी होती है, क्योंकि मैं शब्दों को टाइल कर रहा हूं, उदा। {This is, is me} => {This is me}, जो छेड़छाड़ की जाती है ताकि उपर्युक्त एल्गोरिदम काम करता है।

इसी प्रकार के प्रश्न: Efficient Algorithm for String Concatenation with Overlap

स्रोत

2009-09-17 João Silva

+1 एक अच्छी तरह से लिखित प्रश्न के लिए +1 (लेकिन वास्तव में 'ï' कुंजी 8-) – RichieHindle

ओएस एक्स में आई कुंजी' उल्ट + यू 'है जिसे' i' ' लागू है। –

http://stackoverflow.com/questions/1285434/efficient-algorithm-for-string-concatenation-with-overlap के बहुत करीब है। –

पहली बात पूछने के लिए यदि आप {CDB, सीडीए} की तिलिन्ग लगाना चाहते है? कोई एकल टिलिंग नहीं है।

स्रोत

2009-09-17 20:48:53 user172818

या एबीसी + सीडीई + सीएफजी –

नहीं, मुझे तारों में से एक का पूर्ण ओवरलैप चाहिए। मेरे एल्गोरिदम का उपयोग करके, तारों की जोड़ी EMPTY स्ट्रिंग को वापस कर देगी। –

एक साधारण अनुमानित एल्गोरिदम एक डी ब्रुज़न ग्राफ बनाने के लिए होगा। मैं दूसरों को सोच रहा हूँ। – user172818

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

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

string Tile(string a, string b) 
{ 
    // Try both orderings of a and b, 
    // since TileLeftToRight is not commutative. 

    string ab = TileLeftToRight(a, b); 

    if (ab != "") 
     return ab; 

    return TileLeftToRight(b, a); 

    // Alternatively you could return whichever 
    // of the two results is longest, for cases 
    // like ("ABC" "BCABC"). 
} 

string TileLeftToRight(string left, string right) 
{ 
    int i = 0; 
    int j = 0; 

    while (true) 
    { 
     if (left[i] != right[j]) 
     { 
      i++; 

      if (i >= left.Length) 
       return ""; 
     } 
     else 
     { 
      i++; 
      j++; 

      if (i >= left.Length) 
       return left + right.Substring(j); 

      if (j >= right.Length) 
       return left; 
     } 
    } 
}

स्रोत

2009-09-18 02:06:07 Joren

हां, यह निश्चित रूप से तेज़ है, धन्यवाद। –

आदेश पहले वर्ण से तार, तो लंबाई (छोटी सबसे बड़ा करने के लिए), और फिर KMP के प्रति अनुकूलन लागू ओवरलैपिंग तार श्रृंखलाबद्ध के बारे में this question में पाया।

स्रोत

2009-09-18 02:27:49

धन्यवाद, मैं टाइलिंग और संरेखण की खोज कर रहा था और वह प्रश्न नहीं मिला। –

यह * इसे खोजने में मुश्किल थी। सौभाग्य से, मैंने इसका उत्तर दिया था, इसलिए यह थोड़ी सी खोज को कम कर दिया। –

दिलचस्प समस्या। आपको किसी प्रकार की बैकट्रैकिंग की ज़रूरत है। उदाहरण के लिए अगर आपके पास:

ABC, DBCD

कौन सा व्याख्या करने योग्य नहीं है:

ABC, BCD, DBC

में बीसीडी परिणामों के साथ डीबीसी का मेल। लेकिन में बीसीडी परिणामों के साथ एबीसी के संयोजन:

एबीसीडी, डीबीसी

कौन सा करने के लिए जोड़ा जा सकता है:

ABCDBC.

स्रोत

2009-09-18 12:03:16

हां, मुझे उसमें प्रवेश करने की ज़रूरत है। विकल्प तारों के सभी 'एन!' क्रमपरिवर्तन उत्पन्न करना है, और फिर प्रत्येक संभावित क्रमपरिवर्तन के लिए बाएं से दाएं आगे बढ़ना है, लेकिन यह स्पष्ट रूप से उबर-धीमा है। –

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

स्रोत

2009-09-21 13:21:03 redtuna

हां, यह पूरी तरह स्वीकार्य है। आपका बहुत बहुत धन्यवाद! –

स्ट्रिंग टाइलिंग एल्गोरिदम

उत्तर

संबंधित मुद्दे