मुझे आश्चर्य है कि अगर कोई सबसे लंबे समय तक आवर्ती गैर-ओवरलैपिंग उप स्ट्रिंग के लिए (इष्टतम?) एल्गोरिदम जानता है।सबसे लंबे समय तक गैर-ओवरलैपिंग सबस्ट्रिंग
उदाहरण के लिए, स्ट्रिंग
ABADZEDGBADEZ
सबसे लंबे समय तक आवर्ती "बुरा" हो सकता है में। संयोग से यदि ऐसा कोई परिणाम नहीं है, तो एल्गोरिदम को सतर्क करना चाहिए कि ऐसी चीज हुई है। मेरा अनुमान है कि इसमें प्रत्यय पेड़ शामिल हैं।
मुझे यकीन है कि यह कहीं पहले से मौजूद होना चाहिए। सहायता के लिए धन्यवाद!
चूंकि आप इसे संगीत में लागू कर रहे हैं, इसलिए आप शायद 100% मैचों की तलाश नहीं कर रहे हैं; थीम के एक उदाहरण से दूसरे में विसंगतियों की उम्मीद की जाएगी। आप जीन अनुक्रम विश्लेषण एल्गोरिदम को देखने का प्रयास कर सकते हैं - वहां इस तरह की कई सारी चीज़ें चल रही हैं। ब्लास्ट या अन्य संरेखण एल्गोरिदम का प्रयास करें।
तुम भी एल्गोरिदम के WinEPI परिवार, साथ ही इस विशिष्ट परिणाम सेट के विभिन्न उपसर्ग पेड़ कार्यान्वयन की कोशिश कर सकते (इन परिणामों सबस्ट्रिंग में अंतराल की अनुमति देते हैं, उदाहरण के लिए, ABCID और AFBCD दोनों एबीसीडी होते हैं)। मेरे पास वास्तव में एक एल्गोरिदम पर एक पेपर है जो आपको रुचि रखने पर लायक हो सकता है; मुझे वितरण प्राधिकरण प्राप्त करने की आवश्यकता होगी, इसलिए मुझे बताएं।
ध्यान दें कि यह वास्तव में बड़े डेटासेट के लिए एक बहुत ही जटिल विषय (कुशलतापूर्वक करने के लिए) है।
स्रोत: तुलनीय (विषय-पहचान) विषय पर एक या दो साल के लिए शोध।
यदि आप मुझे पहुंच प्रदान कर सकते हैं, तो इसकी सराहना की जाएगी! –
मुझे लगता है कि वह गीतों को लागू कर रहा है, इसलिए मुझे लगता है कि वह 100% मैचों की तलाश में है। – las3rjock
@ ब्रैंडन - मैंने अनुमति का अनुरोध किया है, मैं देखूंगा कि मैं क्या कर सकता हूं। @ las3rjock - वास्तव में नहीं। उदाहरण के लिए: मैं एक मूर्ख व्यक्ति था मैं मूर्ख था, आदमी उदाहरण विषय: पिछला तनाव। स्ट्रिंग्स एक सटीक मैच नहीं हैं। इसके अलावा, बहुत से गीतों में अलग विराम चिह्न और क्या नहीं है। तो मुझे यकीन नहीं है कि वह सटीक मैच की तलाश में है। –
Suffix array उस समस्या को हल करने के लिए एक अच्छी डेटा संरचना है।
जॉन बेंटले द्वारा Programming Pearls में इस समस्या का समाधान है।
प्रोग्रामिंग मोती में कहां? –
@ एमिल एच, ** 15.2 वाक्यांश ** –
@ निक मुझे नहीं लगता कि प्रोग्रामिंग मोती में एक ही समाधान सीधे लागू किया जा सकता है। "बनाना" का उदाहरण "एएनए" देता है जो दो बार होता है, और इस प्रकार ओपी द्वारा उल्लिखित शर्त के विपरीत ओवरलैपिंग होता है। गैर ओवरलैपिंग स्थिति के लिए कुछ संशोधन की आवश्यकता हो सकती है। आपका क्या कहना है? –
एक साधारण एल्गोरिथ्म यह करने के लिए है:
(के रूप में पोस्ट किया गया दूसरा उत्तर इंगित करता है, मैं यहां एक प्रत्यय सरणी का वर्णन कर रहा हूं।)
यह अभी भी क्रूर बल है। मैं सोच रहा हूं कि थोड़ा और सुरुचिपूर्ण दृष्टिकोण है या नहीं? मेरा मानना है कि एक पेड़-आधारित दृष्टिकोण संरचनात्मक जानकारी को संरक्षित करेगा और साथ ही साथ कुछ प्रकार की गहराई की जानकारी प्रदान करेगा जिसे जल्दी से लंबी लंबाई की जानकारी प्रदान करने के लिए पार किया जा सकता है। –
उचित प्रकार के साथ - प्रत्यय सरणी विकिपीडिया आलेख देखें - चलने का समय सबसे खराब स्थिति में आमतौर पर ओ (एन लॉग एन) होता है और आमतौर पर बेहतर होता है। पुनरावृत्ति ओ (एन) है, इसलिए लागत को सॉर्ट करके प्रभुत्व है। स्पष्ट ब्रूट फोर्स कम से कम ओ (एन^2) होने जा रहा है (हर संभव जोड़ी की तुलना)। पेड़ों के निर्माण की संभावना बहुत अधिक मेमोरी होगी, जिसके प्रदर्शन पर प्रतिकूल असली दुनिया के प्रभाव होंगे (कैश आदि पर विचार करें)। –
ठीक है, यहां एक पागल विचार है।
एक ऐसा फ़ंक्शन बनाएं जो निर्धारित करता है कि ओ (एन) में लंबाई के आवर्ती सबस्ट्रिंग है (जहां एन टेक्स्ट की लंबाई है)। यह रोलिंग हैश का उपयोग करके किया जा सकता है (Rabin-Karp String Matching Algorithm के लिए विकिपीडिया देखें) रैखिक समय में सभी एन हैंश उत्पन्न करने के लिए और संबंधित सबस्ट्रिंग स्थितियों को संग्रहीत करने के लिए हैशटेबल/बीएसटी (या नक्शा या निर्देश या जो भी आपकी भाषा इसे कॉल करता है) का उपयोग करके किया जा सकता है। डेटा संरचना में वर्तमान हैश डालने से पहले, हम जांचते हैं कि हमने इसे पहले देखा है या नहीं।यदि यह पहले देखा गया है, तो हम केवल उन इंडेक्स को देखते हैं जहां यह हैश उत्पन्न हुआ था और देखें कि संबंधित सबस्ट्रिंग एक गैर-ओवरलैपिंग मैच है या नहीं।
अब हम ओ (एन) समय में एक के लंबाई की लंबाई को पा सकते हैं, हम बस सबसे बड़ा के खोजने के लिए एक बाइनरी खोज चलाते हैं जिसके लिए हम अपने फ़ंक्शन का उपयोग करके एक गैर-ओवरलैपिंग सबस्ट्रिंग मैच पा सकते हैं। अजगर में
कोड इस प्रकार
A=23
MOD=10007 # use a random value in the real world
def hsh(text):
return sum([ord(c)*A**(len(text)-i-1) for i,c in enumerate(text)])%MOD
def k_substring(text, k):
substrings={}
cur=hsh(text[:k])
pwr=(A**(k-1))%MOD
substrings[cur]=[0]
for i in xrange(k,len(text)):
to_remove=(ord(text[i-k])*pwr)%MOD
to_add=ord(text[i])
cur-=to_remove
if cur<0:
cur+=MOD
cur=(cur*A)%MOD
cur=(cur+to_add)%MOD
if cur in substrings:
lst=substrings[cur]
for index in lst:
if index+k<=i-k+1 and text[index:index+k]==text[i-k+1:i+1]:
return index
lst.append(i-k+1)
else:
substrings[cur]=[i-k+1]
return -1
def longest_substring(text):
hi,lo=len(text),0
while hi>lo:
mid=(hi+lo+1)>>1
if k_substring(text,mid)==-1:
hi=mid-1
else:
lo=mid
index=k_substring(text,lo)
return text[index:index+lo]
(माफ करना अगर यह स्पष्ट नहीं है। यह 6:30 बजे यहाँ है और मैं वास्तव में बिस्तर पर वापस जाने की जरूरत है :))
सिर्फ curious- व्यापार आवेदन क्या इसके लिए? – Beth
यह एक व्यावसायिक अनुप्रयोग नहीं है। यह एक गीत में थीम ढूंढने से संबंधित है और इस समय एक क्यूरियो है जब तक कि मुझे इसमें शामिल एक प्रोजेक्ट नहीं मिलता है। =] –