एक बड़े पैमाने पर स्ट्रिंग में लंबे समय से दोहराए गए सबस्ट्रिंग्स को ढूंढना

Question

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

मेरे पास वास्तव में वास्तव में लंबी स्ट्रिंग (सैकड़ों मेगाबाइट्स) हैं। मेरे पास लगभग 1 जीबी रैम है।

यही कारण है कि गिनती डेटा के साथ एक प्रत्यय त्रिभुज का निर्माण करना मेरे लिए काम करने के लिए बहुत अक्षम है। Wikipedia's Suffix tree उद्धरण करने के लिए:

स्ट्रिंग के प्रत्यय पेड़ को संग्रहीत करने के लिए आम तौर पर स्ट्रिंग को संग्रहित करने से अधिक स्थान की आवश्यकता होती है।

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

और यह पेड़ पर विकिपीडिया की टिप्पणियां थी, न कि त्रिभुज।

मुझे इतनी बड़ी मात्रा में डेटा और उचित समय में (जैसे आधुनिक डेस्कटॉप मशीन पर एक घंटे से भी कम समय में) लंबे समय से अनुक्रमित अनुक्रम कैसे मिल सकता है?

(कुछ विकिपीडिया लिंक लोग उन्हें 'जवाब' के रूप में पोस्टिंग से बचने के लिए: Algorithms on strings और विशेष रूप से Longest repeated substring problem ;-))

Answer 1

ऐसा करने का प्रभावी तरीका उप-तारों का सूचकांक बनाना है, और उन्हें सॉर्ट करना है। यह एक ओ (एन एलजी एन) ऑपरेशन है।

BWT संपीड़न इस चरण को करता है, इसलिए इसकी एक अच्छी तरह से समझी गई समस्या है और रेडिक्स और suffix (दावा ओ (एन)) सॉर्ट कार्यान्वयन और इस तरह के रूप में इसे यथासंभव कुशल बनाने के लिए हैं। यह अभी भी लंबे समय तक लेता है, शायद बड़े ग्रंथों के लिए कई सेकंड।

आप उपयोगिता कोड का उपयोग करना चाहते हैं, तो सी ++ std::stable_sort() प्रदर्शन ज्यादा प्राकृतिक भाषा के लिए std::sort() की तुलना में बेहतर है (और सी qsort() तुलना में बहुत तेज है, लेकिन के लिए विभिन्न कारणों से)।

फिर प्रत्येक आइटम को अपने पड़ोसियों के साथ अपने सामान्य सबस्ट्रिंग की लंबाई देखने के लिए ओ (एन) है।

Answer 2

शब्द टूट के साथ इस पाठ है? तो मुझे संदेह होगा कि आप कीवर्ड-इन-रेफरेंस की विविधता चाहते हैं: प्रत्येक पंक्ति में प्रत्येक शब्द को एन लाइन के लिए एन बार बनाएं, प्रत्येक शब्द पर प्रत्येक पंक्ति को तोड़ दें; पूरी चीज के अल्फा को सॉर्ट करें; दोहराने के लिए देखो।

यदि यह बायोइनफॉर्मेटिक डीएनए अनुक्रमों की तरह एक लंबी लंबी आकर्षक स्ट्रिंग है, तो आप डिस्क पर अपने त्रिभुज की तरह कुछ बनाना चाहते हैं; अगले-नोड्स के लिए डिस्क ऑफ़सेट वाले प्रत्येक वर्ण के लिए एक रिकॉर्ड बनाएं। मैं Knuth, खंड 5.4, "बाहरी सॉर्टिंग" के वॉल्यूम 3 पर एक नज़र डालेगा।

Answer 3

एक गुच्छा अधिक रैम के लिए सबसे आसान तरीका plunk down the $100 हो सकता है। अन्यथा, आपको अपने प्रत्यय पेड़ को पकड़ने के लिए डिस्क समर्थित संरचनाओं को देखना होगा।

Answer 4

आप डिस्क-आधारित प्रत्यय पेड़ देख सकते हैं। मुझे Google के माध्यम से यह Suffix tree implementation library मिला, साथ ही लेखों का एक समूह जो इसे स्वयं लागू करने में मदद कर सकता था।

Answer 5

क्या आप इसके बजाय suffix array बनाकर अपनी समस्या का समाधान कर सकते हैं? अन्यथा आपको अन्य उत्तरों में वर्णित डिस्क-आधारित प्रत्यय पेड़ों में से एक का उपयोग करने की आवश्यकता होगी।

Answer 6

आप विभाजन और जीत का उपयोग कर इसे हल कर सकते हैं। मुझे लगता है कि यह एक Trie का उपयोग कर के रूप में ही एल्गोरिथम जटिलता है, लेकिन होना चाहिए शायद कम कुशल कार्यान्वयन के लिहाज से

void LongSubstrings(string data, string prefix, IEnumerable<int> positions) 
{ 
    Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>(); 
    foreach (int position in positions) 
    { 
     char nextChar = data[position]; 
     buffers[nextChar].Add(position+1); 
    } 

    foreach (char c in buffers.Keys) 
    { 
     if (buffers[c].Count > 1) 
      LongSubstrings(data, prefix + c, buffers[c]); 
     else if (buffers[c].Count == 1) 
      Console.WriteLine("Unique sequence: {0}", prefix + c); 
    } 
} 

void LongSubstrings(string data) 
{ 
    LongSubstrings(data, "", Enumerable.Range(0, data.Length)); 
} 

इस के बाद, आप एक वर्ग है कि DiskBackedBuffer ऐसी है कि वह नंबर की एक सूची था कार्यान्वित करने की जरूरत होगी, और जब बफर को एक निश्चित आकार में मिला, तो यह एक अस्थायी फ़ाइल का उपयोग कर डिस्क पर खुद को लिख देगा, और पढ़ने से डिस्क से याद होगा।

यह देखते हुए कि एक लंबे मैच भी एक छोटी मुकाबला नहीं है, तो आपको पहले कम मैचों खोजने और फिर अगर आप इन मैचों 'हो जाना' कर सकते हैं देखकर राम के लिए कई गुजरता व्यापार कर सकते हैं:

Answer 7

मेरे अपने प्रश्न का उत्तर देना।

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

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

Answer 8

बस एक विलम्बित सोचा कि मेरे पास हुई ...

अपने ओएस/पर्यावरण पर निर्भर करता है। (जैसे 64 बिट पॉइंटर्स & एमएमएपी() उपलब्ध हैं।)

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

Answer 9

क्या इस तरह एक साधारण कार्यक्रम के बारे में:

S = "ABAABBCCAAABBCCM" 

def findRepeat(S): 
    n = len(S) 
    #find the maxim lenth of repeated string first 
    msn = int(floor(n/2)) 
    #start with maximum length 
    for i in range(msn,1,-1): 
     substr = findFixedRepeat(S, i) 
     if substr: 
      return substr 
    print 'No repeated string' 
    return 0 

def findFixedRepeat(str, n): 
    l = len(str) 
    i = 0 
    while ((i + n -1) < l): 
     ss = S[i:i+n] 
     bb = S[i+n:] 
     try: 
      ff = bb.index(ss) 
     except: 
      ff = -1 

     if ff >= 0: 
      return ss; 
     i = i+1 
    return 0 
print findRepeat(S)