स्ट्रिंग विश्लेषण

Question

आपरेशन के एक दृश्य को देखते हुए:

एक * ख * एक * ख * एक * एक * ख * एक * ख

वहाँ एक रास्ता के लिए इष्टतम उपखंड प्राप्त करने के लिए है सबस्ट्रिंग के पुन: उपयोग सक्षम करें।

बनाने

एक * ख * एक * ख * एक * एक * ख * एक * ख => ग * एक * सी, जहाँ c = एक * ख * एक * ख

और फिर देखकर कि

एक * ख * एक * ख => d * डी, जहां d = एक * ख

सब सब में वें में 8 प्रारंभिक संचालन कम करने

ई 4 यहाँ वर्णित है?

(c = (घ = एक * ख) * घ) * एक * ग

निश्चित रूप से लक्ष्य संचालन

की संख्या

कम करने के लिए मैं एक suffixtree पर विचार कर रहा हूँ है प्रकार के।

मैं विशेष रूप से रैखिक समय हेरिस्टिक या समाधान में रूचि रखता हूं। '*' ऑपरेशंस वास्तव में मैट्रिक्स गुणात्मक हैं।

Answer 1

यह पूरी समस्या "Common Subexpression Elimination" or CSE के रूप में जानी जाती है। यह कार्यात्मक प्रोग्रामिंग भाषाओं के लिए कंपाइलर्स के कार्यान्वयनकर्ता द्वारा सामना किए जाने वाले "Graph Reduction" नामक समस्या का थोड़ा सा छोटा संस्करण है। Googling "सामान्य Subexpression उन्मूलन एल्गोरिदम" बहुत सारे समाधान देता है, हालांकि कोई भी जो मैं विशेष रूप से मैट्रिक्स गुणा द्वारा दी गई बाधाओं के लिए देख सकता हूं।

बहुत से संदर्भ देने के लिए जुड़े पृष्ठ।

मेरा पुराना उत्तर नीचे है। हालांकि, थोड़ा और शोध करने के बाद, समाधान बस suffix tree का निर्माण कर रहा है। यह ओ (एन) समय (विकिपीडिया पेज पर कई संदर्भ) में किया जा सकता है। ऐसा करने के बाद, उप-अभिव्यक्ति (सी, डी आदि) आपके प्रश्न में केवल प्रत्यय वृक्ष में नोड्स हैं - बस उन्हें बाहर खींचें।

---

हालांकि, मुझे लगता है कि मार्कोस, Longest repeating Substring के सुझाव के साथ कुछ करने के बारे में है के रूप में ग्राफ में कमी पूर्वता अनुकूलन कि यहाँ अनुमति दी जा सकती अनुमति न दें। एल्गोरिथ्म के

स्केच:

optimise(s): 
    let sub = longestRepeatingSubstring(s). 
    optimisedSub = optimise(sub) 
    return s with sub replaced by optimisedSub 

सबसे लंबे समय तक दोहराए जाने-स्ट्रिंग के प्रत्येक रन लेता है समय एन आप शायद फिर से उपयोग कर सकते हैं suffix tree आप समय एन

Answer 2

संपादित करें: इस जवाब में आदेशों के-विकास क्रम, एक संपीड़न एल्गोरिथ्म हो सकता है कि आप क्या चाहते सीएसई या मैट्रिक्स श्रृंखला गुणा चलाने के लिए

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

ऐसे परिचालनों का चयन करने में आपके संचालन के कौन से सबसेट कम्यूटेटिव हैं, इस पर एक एल्गोरिदम चुनने में एक महत्वपूर्ण विचार होगा। [संपादित करें: ओ पी का कहना है कोई आपरेशन उसका/उसकी स्थिति में विनिमेय हैं],

हम भी सर्वोत्कृष्ट समाधान परिभाषित कर सकते हैं, तो हम इस तरह के कैशिंग के रूप में प्रभाव की अनदेखी:

input: [some product of matrices to compute] 

given that multiplying two NxN matrices is O(N^2.376) 
given we can visualize the product as follows: 
    [[AxB][BxC][CxD][DxE]...] 
we must for example perform O(max(A,B,C)^2.376) or so operations in order to combine 
    [AxB][BxC] -> [AxC] 

The max(...) is an estimate based on how fast it is to multiply two square matrices; 
a better estimate of cost(A,B,C) for multiplying an AxB * BxC matrix can be gotten 
from actually looking at the algorithm, or running benchmarks if you don't know the 
algorithm used. 

However note that multiplying the same matrix with itself, i.e. calculating 
a power, can be much more efficient, and we also need to take that into account. 
At worst, it takes log_2(power) multiplies each of O(N^2.376), but this could be 
made more efficient by diagonalizing the matrix first. 

है कि क्या एक लालची के बारे में सवाल ही नहीं है दृष्टिकोण इस के लिए व्यवहार्य नहीं है: क्या प्रत्येक को प्रत्येक चरण में दोहराने वाले सबस्ट्रिंग को संपीड़ित करना चाहिए। यह मामला नहीं हो सकता है, उदा।

aaaaabaab 
compressing 'aa' results in ccabcb and compressing 'aab' is now impossible 

हालांकि मैं एक कूबड़ है कि, अगर हम संपीड़ित करने सबस्ट्रिंग सभी आदेशों की कोशिश, हम शायद इस मुद्दे में भी अक्सर नहीं चलेंगे है।

इस प्रकार नीचे लिखा होने हम क्या चाहते हैं (लागत) और संभवतः माना मुद्दों, हम पहले से ही एक जानवर बल एल्गोरिथ्म जो ऐसा कर सकते हैं, और यह मैट्रिक्स की बहुत छोटी संख्या के लिए चलेंगे:

# pseudocode 

def compress(problem, substring) 
    x = new Problem(problem) 
    x.string.replaceall(substring, newsymbol) 
    x.subcomputations += Subcomputation(newsymbol=substring) 

def bestCompression(problem) 
    candidateCompressions = [compress(problem,substring) for each substring in problem.string] 
    # etc., recursively return problem with minimum cost 
    # dynamic programming may help make this more efficient, but one must watch 
    # out for the note above, how it may be hard to be greedy 

नोट: Asgeir द्वारा एक और जवाब के अनुसार, यह मैट्रिक्स चेन गुणा अनुकूलन समस्या के रूप में जाना जाता है। निक फोर्टसेक्यू नोट्स को यह आमतौर पर http://en.wikipedia.org/wiki/Common_subexpression_elimination के रूप में भी जाना जाता है - इस प्रकार कोई भी साहित्य से कोई सामान्य सीएसई या मैट्रिक्स-चेन-गुणात्मक एल्गोरिदम/लाइब्रेरी पा सकता है, और प्लग ऑर्डर-ऑफ-आयाम में प्लग करता है जिसका मैंने पहले उल्लेख किया था (आप उन नामकों की आवश्यकता होगी जो आप उपयोग करते हैं)। ध्यान दें कि उपर्युक्त गणनाओं की लागत (गुणा, एक्सपोनिएशन, इत्यादि) मानते हैं कि उन्हें अत्याधुनिक एल्गोरिदम के साथ कुशलतापूर्वक किया जा रहा है; यदि यह मामला नहीं है, तो एक्सपोनेंट को उचित मूल्यों से प्रतिस्थापित करें जो संचालन के तरीके से मेल खाते हैं।

Answer 3

क्या यह Longest repeated substring problem नहीं है?

Answer 4

में पूरी बात को हल करने से निर्माण सिर के शीर्ष में समस्या मेरे लिए एनपी में दिखाई देती है। प्रतिस्थापन के आधार पर आप अन्य सबस्टेशन कर रहे हैं उदाहरण के लिए स्ट्रिंग d*e*a*b*c*d*e*a*b*c*d*e*a के लिए कई संभावनाएं संभव हैं या असंभव हो सकती हैं।

आप सबसे लंबे समय तक आम स्ट्रिंग ले अगर यह हो जाएगा: f = d*e*a*b*c और आप f*f*e*a स्थानापन्न सकता है अंत में तीन गुणा और चार मध्यवर्ती लोगों (कुल सात) के साथ छोड़।

आप के बजाय निम्नलिखित तरीके स्थानापन्न हैं: f = d*e*a आप f*b*c*f*b*c*f जो आप आगे छह गुणा के लिए कुल g = f*b*c g*g*f के लिए प्रयोग कर स्थानापन्न कर सकते हैं।

इस समस्या में अन्य संभावित प्रतिस्थापन हैं, लेकिन मेरे पास अभी उन्हें गिनने का समय नहीं है।

मैं एक पूर्ण न्यूनतम प्रतिस्थापन के लिए अनुमान लगा रहा हूं, यह केवल सबसे लंबे समय तक सामान्य सबस्ट्रिंग को समझना आवश्यक नहीं है बल्कि प्रत्येक सबस्ट्रिंग दोहराए जाने की संख्या भी है, जिसका शायद मतलब है कि आपको अब तक सभी प्रतिस्थापनों को ट्रैक करना है और बैकट्रैक करना है। फिर भी यह वास्तविक गुणाओं की तुलना में तेज़ हो सकता है।

Answer 5

आप सबसे कम अंकगणितीय आपरेशनों का उपयोग करने के तो आप matrix chain multiplication पर एक नज़र जो हे को कम किया जा सकता होना चाहिए चाहते हैं (एन एन लॉग इन करें)