दो लाइनों में अधिकतम, सामान्य सबस्ट्रिंग की समानांतर खोज के लिए एल्गोरिदम और C ++ (C ++ 11) में इसका कार्यान्वयन

मैंने दो पंक्तियों के अधिकतम संभव चौराहों के लिए समानांतर खोज एल्गोरिदम के बारे में एक लेख लिखने का फैसला किया। दो इच्छाओं ने मुझे इस लेख को लिखने के लिए प्रेरित किया:

1. सभी दिलचस्प एल्गोरिथ्म और C ++ (C ++ 11 मानक) में इसके कार्यान्वयन के साथ साझा करें;
2. पता लगाएँ कि क्या इस एल्गोरिथ्म में एक नाम और / या औपचारिक विवरण है;

प्रागितिहास

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

समस्या का बयान

इस कार्य के विवरण से मैं इस प्रकार समझ गया:
S1 और S2 दो पंक्तियाँ हैं, आपको अधिकतम लंबी सामान्य सबस्ट्रिंग (s) खोजने की आवश्यकता है (इसके बाद हम आवश्यक सबस्ट्रिंग - सबसेट) कहेंगे, जिसकी लंबाई M से कम नहीं है । परिणामस्वरूप इसके निर्देशांक को वितरित करें।
निर्देशांक चार पूर्णांक हैं।
पहले दो लाइन S1 से संबंधित हैं - ये पाया गए विकल्प के पहले और अंतिम वर्णों की स्थिति संख्याएं हैं।
दूसरी दो संख्याओं का एक ही अर्थ है, केवल दूसरी पंक्ति - S2 पर लागू होता है।

उदाहरण के लिए, यदि हमारे पास निम्नलिखित इनपुट पैरामीटर हैं:

S1 = ABCCA
S2 = ACCABABCCBAABCBAABCBACBACBACBAC
म = २

तो उत्तर होगा:
0 3 5 8

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

समस्या की आवश्यकताएं एक अतिरिक्त इनपुट पैरामीटर K को इंगित करती हैं, थ्रेड्स की संख्या जो एल्गोरिथ्म को समानांतर करने के लिए उपयोग की जा सकती है।

हम संक्षेप में बताते हैं कि हमें प्रवेश द्वार पर क्या दिया गया है:

1. एस 1 , एस 2 - दो लाइनें जिसमें खोज करना है;
2. एम वांछित प्रतिस्थापन की न्यूनतम संभव लंबाई है;
3. K थ्रेड्स की संख्या है जो समानांतरकरण के लिए उपयोग किया जा सकता है;

एल्गोरिथ्म

वास्तव में, एक समाधान का विचार बहुत सरल है और इसमें 3 चरण होते हैं:

1. S1 को सबसे छोटे संभव (लंबाई M ) खंडों में विभाजित करें।
2. S2 पर प्रोजेक्ट सेगमेंट।
3. प्राप्त प्रक्षेपण पर, सबसे लंबे समय तक संभव सबसेट (लगातार खंडों की अधिकतम संख्या से युक्त) खोजें।

निम्नलिखित उदाहरण में एल्गोरिथ्म के संचालन पर विचार करें:

S1 = ABCCA
S2 = ACCABABCCBAABCBAABCBACBACBACBAC
म = २
के = २

1) खंडों में S1 को तोड़ें, लंबाई M = 2 में से प्रत्येक:
एबी , बीसी , सीसी , सीए

2) S2 पर प्रत्येक परिणामी खंड को प्रोजेक्ट करें:



या ऑफसेट के रूप में:



इसलिए हमें S1 से S2 का प्रक्षेपण मिलता है:



अब से हम इस प्रक्षेपण को प्रतिच्छेदन मानचित्र कहेंगे।

वास्तव में, चौराहे का नक्शा सभी खंडों का एक समन्वय मैट्रिक्स है जिसकी लंबाई एम है । यानी प्रत्येक मैट्रिक्स तत्व पंक्ति S2 में समन्वय की विशेषता है, जबकि मैट्रिक्स की पंक्ति संख्या पंक्ति S1 में समन्वय की विशेषता है। हमारे निपटान में चौराहे का नक्शा होने के बाद, हम सभी चौराहों (सबसेट) को ढूंढ सकते हैं और उनमें से अधिकतम चुन सकते हैं।

3) हम अधिकतम सबसेट (खंडों का समूह) की खोज करते हैं।
यदि आप प्रतीकात्मक रूप में चौराहे के नक्शे को देखते हैं, तो पहले से ही आप सबसे लंबे उपसमुच्चय पा सकते हैं:



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



यानी 5 के समन्वय की शुरुआत करने वाली सबसेट की लंबाई = 4 की अधिकतम लंबाई है, 3 के समन्वय की शुरुआत के लिए सबसेट की लंबाई 2 होगी, आदि।

इसी तरह, चौराहे के नक्शे में प्रत्येक खंड के माध्यम से चल रहा है, हम पाते हैं कि अधिकतम लंबे उपसमुच्चय क्रमशः S1 और S2 : 0 और 5 की पंक्तियों में निर्देशांक के साथ लंबाई 4 का एक सबसेट है।

साथ में चलाना

जैसा कि आप देख सकते हैं, इस समस्या को हल करने में प्रत्येक चरण (चरण 1, 2, 3) को समानांतर करना आसान है, मैप-रिड्यूस संभव है।

1, 2) प्रत्येक थ्रेड को अपना सेगमेंट (या कई सेगमेंट) सौंपा जाता है, जिसके लिए वह सेगमेंट का एक प्रोजेक्शन बनाता है। कुल मिलाकर, सभी खंडों के लिए संबंधित अनुमान प्राप्त होने के बाद, हम एक तैयार-किए गए चौराहे का नक्शा प्राप्त करते हैं।



3.1) प्रत्येक थ्रेड को अपना सीरियल नंबर (n) दिया जाता है। इसके बाद, nth स्ट्रीम, nth स्थिति से शुरू होकर, प्रत्येक Kth तत्व को चौराहे के नक्शे से संसाधित करता है। इस प्रकार, हम चौराहे के नक्शे को कई (प्रवाह की संख्या) भागों में तोड़ देते हैं। इन भागों में से, अधिकतम उपसमूह का चयन किया गया है, जैसा कि ऊपर वर्णित है:



3.2) सभी थ्रेड्स पूरे होने के बाद, हमें सबसेट के कई समूह मिलेंगे। प्राप्त समूहों से, अधिकतम सेगमेंट लंबाई वाले समूह का चयन करें। हमारे उदाहरण में, ये दो समूह हैं: धारा # 1 द्वारा गठित एक समूह, जिसमें लंबाई में 3 वर्णों के खंड होते हैं (दिशा-निर्देश के साथ: 0; 11 और 1; 6 ), और धारा # 2 द्वारा गठित एक समूह, जिसमें 4 वर्णों का एक खंड होता है। (निर्देशांक 0; 5 के साथ)। चूंकि दूसरे समूह में सबसे लंबे खंड की लंबाई होती है, इसलिए पहले समूह को तुरंत छोड़ दिया जाता है।
नतीजतन, हमें सबसेट ( 0; 5 ) के प्रारंभिक निर्देशांक मिले और इसकी लंबाई 4 है । अंतिम निर्देशांक खोजने के लिए, हम सूत्र का उपयोग करते हैं: end_coord = start_coord + len - 1।

इस प्रकार हमें उत्तर मिलता है: 0 3 5 8 ।

निष्कर्ष

मैंने C ++ में इस एल्गोरिथ्म के कार्यान्वयन के विवरण पर नहीं छूने का फैसला किया, क्योंकि यह पहले से ही इस लेख के दायरे से परे है। जीसीसी के साथ संकलन के लिए आप यहां C ++ (C ++ 11) में इस एल्गोरिदम के कार्यान्वयन से परिचित हो सकते हैं , -pthread और -std = c ++ 0X झंडे सेट करना न भूलें।

सवाल

यह एल्गोरिथ्म मेरे दिमाग में समस्या के एक स्पष्ट समाधान के रूप में आया था, लेकिन मुझे नहीं पता कि क्या इसका आधिकारिक नाम और / या औपचारिक विवरण है?