प्रथम-घटना समानांतर स्ट्रिंग मिलान एल्गोरिदम

Question

आगे बढ़ने के लिए, यह होमवर्क है। ऐसा कहा जा रहा है, यह बेहद खुला है और हमारे पास इस समस्या के बारे में सोचने के तरीके के बारे में लगभग शून्य मार्गदर्शन है (या सामान्य रूप से समांतर एल्गोरिदम)। मैं सही दिशा में पॉइंटर्स और पूर्ण समाधान नहीं चाहता हूं। कोई भी पढ़ाई जो मदद कर सकती है वह भी उत्कृष्ट होगी।

मैं समांतर एल्गोरिदम का उपयोग करके बड़ी मात्रा में टेक्स्ट में पैटर्न की पहली घटना से मेल खाने के लिए एक कुशल तरीके से काम कर रहा हूं। पैटर्न सरल चरित्र मिलान है, कोई regex शामिल नहीं है। मै मैचों के सभी खोजने के संभावित तरीके से आने में सफल रहा हूं, लेकिन इसके बाद मुझे सभी मैचों में देखना और पहला ढूंढना होगा।

तो सवाल यह है कि, क्या प्रक्रियाओं और स्कैनिंग के बीच पाठ को तोड़ने में मुझे और सफलता मिल जाएगी? या यह सबसे अच्छा होगा कि प्रक्रिया के सिंक्रनाइज़ किए गए कुछ प्रकार की खोज हो जहां j'th प्रक्रिया पैटर्न के j'th चरित्र की खोज करे? यदि तब सभी प्रक्रियाएं उनके मैच के लिए सच होती हैं, तो प्रक्रियाएं बताई गई पैटर्न से मेल खाने में अपनी स्थिति बदलती हैं और फिर से आगे बढ़ती रहती हैं, जब तक कि सभी पात्रों का मिलान नहीं हो जाता है और फिर पहले मैच की अनुक्रमणिका लौटाते हैं।

जो अब तक है वह बेहद बुनियादी है, और संभावना से अधिक काम नहीं करता है। मैं इसे लागू नहीं करूँगा, लेकिन किसी भी पॉइंटर्स की सराहना की जाएगी।

पी प्रोसेसर, लंबाई टी का एक पाठ, और लंबाई एल के एक पैटर्न, और उपयोग एल प्रोसेसर की एक छत के साथ

:

 
for i=0 to t-l: 
    for j=0 to p: 
     processor j compares the text[i+j] to pattern[i+j] 
      On false match: 
       all processors terminate current comparison, i++ 
      On true match by all processors: 
       Iterate p characters at a time until L characters have been compared 
       If all L comparisons return true: 
        return i (position of pattern) 
       Else: 
        i++ 

Answer 1

मुझे डर है कि स्ट्रिंग तोड़ना नहीं होगा।

आम तौर पर, जल्दी से बचने में मुश्किल होती है, तो आप भाग में पाठ को तोड़ने से बेहतर होंगे।

लेकिन चलिए हर्ब सटर से पहले Dr Dobbs पर समांतर एल्गोरिदम के साथ खोज करने के लिए कहें। विचार है कि वितरण की गैर-समानता का उपयोग जल्दी वापसी के लिए किया जाए। बेशक Sutter किसी भी मैच में रुचि रखते हैं, जो हाथ में समस्या नहीं है, तो चलो अनुकूलित करें।

यहाँ मेरा विचार है, मान लीजिए कि हमारे पास करते हैं:

• लंबाई का पाठ N
• p प्रोसेसर
• अनुमानी: max पात्रों एक हिस्सा शामिल करना चाहिए की अधिकतम संख्या, शायद के आदेश है पैटर्न की लंबाई M से अधिक परिमाण।

अब, क्या आप चाहते हैं k बराबर मात्रा, जहां k है कम से कम है और अधिक से अधिक size(chunk) अभी तक max से हीन है में अपने पाठ विभाजित करने के लिए है।

फिर, हमारे पास शास्त्रीय Producer-Consumer पैटर्न है: p प्रक्रियाओं को पाठ के भाग के साथ खिलाया जाता है, प्रत्येक प्रक्रिया इसे प्राप्त होने वाले खंड में पैटर्न की तलाश में होती है।

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

के 3 प्रोसेसर के साथ, एक उदाहरण है दो:

[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ] 
         x  x 

हिस्सा 6 और 8 दोनों स्ट्रिंग होते हैं।

निर्माता पहले प्रक्रियाओं में 1, 2 और 3 खिलाएगा, फिर प्रत्येक प्रक्रिया अपनी लय पर आगे बढ़ेगी (यह पाठ की खोज और पैटर्न की समानता पर निर्भर करती है)।

मान लें कि 6 में हमें इसे खोजने से पहले हमें 8 में पैटर्न मिल गया है। फिर 7 पर काम कर रही प्रक्रिया समाप्त होती है और एक और हिस्सा पाने की कोशिश करता है, निर्माता इसे रोकता है -> यह अप्रासंगिक होगा। फिर परिणामस्वरूप 6 पर काम करने वाली प्रक्रिया समाप्त होती है, और इस प्रकार हम जानते हैं कि पहली घटना 6 में थी, और हमारे पास इसकी स्थिति है।

मुख्य विचार यह है कि आप पूरे पाठ को देखना नहीं चाहते हैं! यह अपमानजनक है!

Answer 2

लंबाई एल के एक पैटर्न को देखते हुए, और लंबाई की एक श्रंखला खोज पी प्रोसेसर पर एन मैं बस प्रोसेसर पर स्ट्रिंग विभाजित होगा। प्रत्येक प्रोसेसर अगले प्रो-प्रोसेसर से संबंधित स्ट्रिंग को ओवरलैप करने वाले अंतिम एल -1 के साथ लंबाई एन/पी + एल -1 का एक हिस्सा लेगा। फिर प्रत्येक प्रोसेसर बॉयर मूर करेगा (दो प्री-प्रोसेसिंग टेबल साझा किए जाएंगे)। प्रत्येक खत्म, वे पहले प्रोसेसर है, जो एक तालिका बनाता है

Process Index 
    1 -1 
    2 2 
    3 23 

के बाद सभी प्रक्रियाओं प्रतिक्रिया व्यक्त की है करने के लिए परिणाम वापस आ जाएगी जब (या सोचा था की एक बिट के साथ एक प्रारंभिक भागने हो सकता है), तो आपको पहले मैच वापसी । यह औसतन ओ (एन/(एल * पी) + पी) होना चाहिए।

i'th चरित्र से मेल खाने वाले प्रोसेसर होने का दृष्टिकोण बहुत अधिक इंटर प्रोसेस संचार ओवरहेड की आवश्यकता होगी।

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