2010-04-25 16 views
6

मैं दो बहुत बड़ी तार है और मैं उनके Longest Common Substring पता लगाने के लिए कोशिश कर रहा हूँ।सबसे लंबे समय तक सामान्य सबस्ट्रिंग की लंबाई की गणना कैसे करें?

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

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

समस्या गतिशील प्रोग्रामिंग विधि एक विशाल चल रहा समय है कि (जटिलता O(n*m), जहां n और m दो तार की लंबाई हो रहा है) का उपयोग करना।

क्या मैं (प्रत्यय के पेड़ को लागू करने के कूदने से पहले) जानना चाहता हूँ: यह एल्गोरिथ्म तेजी लाने के लिए अगर मैं केवल आम-स्ट्रिंग की लंबाई पता करने के लिए (और नहीं आम-स्ट्रिंग ही) चाहते हैं संभव है?

उत्तर

2

यह व्यवहार में तेजी से हो जाएगा? हाँ। क्या यह बिग-ओह के बारे में तेज़ होगा? नहीं। गतिशील प्रोग्रामिंग समाधान हमेशा ओ (एन * एम) होता है।

समस्या यह है कि आप प्रत्यय के पेड़ के साथ हो सकती हैं कि आप अंतरिक्ष में एक विशाल दंड के लिए प्रत्यय पेड़ के रैखिक समय स्कैन व्यापार है। प्रत्यय पेड़ आम तौर पर उस तालिका से काफी बड़े होते हैं जिसे आपको एल्गोरिदम के गतिशील प्रोग्रामिंग संस्करण के लिए लागू करने की आवश्यकता होती है। अपने तारों की लंबाई के आधार पर, यह पूरी तरह से संभव है कि गतिशील प्रोग्रामिंग तेज़ी से हो जाएगी।

गुड लक :)

+2

@Billy ONeal: आप प्रत्यय पेड़ और गतिशील प्रोग्रामिंग तुलना कर रहे हैं? मैं इसके लिए नहीं पूछ रहा हूँ।'मुझे क्या पता होना चाहिए कि क्या गतिशील प्रोग्रामिंग एल्गोरिदम तेजी से बनाने का कोई तरीका है यदि मैं केवल सामान्य सबस्ट्रिंग की लंबाई जानना चाहता हूं?' – Lazer

+0

@eSKay: मेरा मानना ​​है कि मेरे उत्तर का पहला भाग उस प्रश्न का उत्तर देता है। –

+0

ठीक है, * मैं इसे अभ्यास में तेज़ी से कैसे बना सकता हूं? – Lazer

3

ये यह तेजी से चलाने कर देगा, हालांकि यह अभी भी O(nm) हो जाएगा।

एक अनुकूलन अंतरिक्ष में है (यदि आप एक छोटे से आवंटन समय बचाने के लिए हो सकता है) देख रहा है कि LCSuff केवल पिछली पंक्ति पर निर्भर करता है - इसलिए यदि आप केवल लंबाई के बारे में परवाह है, तो आप O(min(n,m)) करने के लिए नीचे O(nm) अंतरिक्ष का अनुकूलन कर सकते हैं। वर्तमान पंक्ति है कि आप कार्रवाई कर रहे हैं, और पिछली पंक्ति है कि आप बस संसाधित, और बाकी फेंक -

विचार केवल दो पंक्तियों रखने के लिए है।

+0

@ लैरी: धन्यवाद! हालांकि, मैंने पहले ही इसे लागू कर लिया था। कोई अन्य जो आपके साथ होता है? – Lazer

+0

दूसरा टॉप-डाउन और डाउन-अप दोनों को लागू करना है। चीजों को गति देने के लिए आप कुछ शाखाओं और बाध्य तकनीकों को ऊपर-नीचे लागू कर सकते हैं, और संभवतः उन राज्यों को छोड़ सकते हैं जिनकी कभी आवश्यकता नहीं होगी। – Larry

-1

Myer's bit vector algorithm आप कर सकते हैं। यह बिट मैनिप्ल्यूशन का उपयोग करके काम करता है और यह एक बहुत तेज दृष्टिकोण है।

+0

@ लांस: "एक्स नाम कैनोनिकल एल्गोरिदम का उपयोग करें" ** निश्चित रूप से ** एक उत्तर है, यद्यपि कुछ हद तक स्पैस। –

+0

उम, मुझे उस टिप्पणी को बनाने की कोई याद नहीं है। माफ़ कीजिये। यदि कुछ भी हो, तो मैंने इसे केवल एक लिंक होने के उत्तर के लिए बुलाया होगा। – Lance

0

यहाँ एक सरल एल्गोरिथ्म है जो कर सकते हैं हे में खत्म ((m + n) * लॉग (m + n)), और बहुत आसान प्रत्यय पेड़ एल्गोरिथ्म की तुलना में लागू करने के लिए जो ओ (m + n) क्रम है।

इसे न्यूनतम सामान्य लंबाई (minL) = 0, और अधिकतम सामान्य लंबाई (maxL) = min (m + n) +1 से शुरू करने दें।

1. if (minL == maxL - 1), the algorithm finished with common len = minL. 

2. let L = (minL + maxL)/2 

3. hash every substring of length L in S, with key = hash, val = startIndex. 

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1. 

शेष समस्या यह है कि समय ओ (एन) में लंबाई एल के साथ सभी सबस्ट्रिंग हैश को कैसे है। आप इस प्रकार एक बहुपद सूत्र का उपयोग कर सकते हैं:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p. 

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];