Monoids और उनके अनुप्रयोग: पेड़ों में मोनोइडल कम्प्यूटिंग

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



हमें अमूर्त सोच, कुछ संतुलित खोज वृक्ष के ज्ञान (उदाहरण के लिए, कार्टेशियन वृक्ष जिसे मैंने पहले वर्णित किया गया है) की आवश्यकता होगी, सरल सी # कोड को पढ़ने की क्षमता, और प्राप्त ज्ञान को लागू करने की इच्छा।



इसलिए, आज एजेंडा में पेड़ों में कैशिंग कम्प्यूटेशन के लिए मोनॉयड और उनके मुख्य अनुप्रयोग हैं।

अवधारणा के रूप में मोनॉयड

किसी भी चीज़ की भीड़, वस्तुओं की एक भीड़ की कल्पना करें जिसे हम हेरफेर करने जा रहे हैं। चलो इसे एम कहते हैं । इस सेट पर, हम एक बाइनरी ऑपरेशन पेश करते हैं, जो कि एक फ़ंक्शन है जो सेट के तत्वों की एक जोड़ी के साथ एक नए तत्व को जोड़ता है। इसके बाद, हम इस अमूर्त ऑपरेशन को "will" के द्वारा निरूपित करेंगे और भाव रूप में अभिव्यक्ति लिखेंगे: यदि a और b एक सेट के तत्व हैं, तो c = a is b भी इस सेट का कुछ तत्व है।



उदाहरण के लिए, दुनिया में मौजूद सभी लाइनों पर विचार करें। और स्ट्रिंग संघनन ऑपरेशन पर विचार करें, जिसे पारंपरिक रूप से "," के रूप में गणित में दर्शाया गया है, और अधिकांश प्रोग्रामिंग भाषाओं में "+": "John"



◦ "Doe"



= "JohnDoe"



। यहाँ सेट M एक स्ट्रिंग है, और ◦ ऑपरेशन a के रूप में कार्य करता है।

या एक और उदाहरण fst फ़ंक्शन है, जिसे कार्यात्मक भाषाओं में जाना जाता है जब टुपल्स में हेरफेर किया जाता है। उसके दो तर्कों में से, परिणाम के रूप में वह पहली बार लौटी। तो, fst (5, 2) = 5 ; fst ( "foo"



, "bar"



) = "foo"



। इससे कोई फर्क नहीं पड़ता कि कौन सा इस द्विआधारी ऑपरेशन पर विचार करने के लिए सेट है, इसलिए यह किसी भी चुनने के लिए आपकी पसंद है।



इसके बाद, हम अपने ऑपरेशन "।" पर एक सहयोगीता बाधा डालते हैं। इसका मतलब यह है कि इसके लिए निम्नलिखित की आवश्यकता होती है: यदि "a" वस्तुओं के अनुक्रम का उपयोग किया जाता है, तो परिणाम "⊗" के आवेदन के आदेश की परवाह किए बिना समान रहना चाहिए। अधिक सख्ती से, किसी भी तीन वस्तुओं के लिए ए , बी और सी होना चाहिए:

( ए ) बी ) = सी = ए b ( बी ) सी )

यह देखना आसान है कि स्ट्रिंग का संयोजन साहचर्य है: यह महत्वपूर्ण नहीं है कि स्ट्रिंग अनुक्रम में कौन सा ग्लूइंग पहले किया गया है, और जो बाद में, हम अभी भी अनुक्रम में सभी पंक्तियों की आम gluing प्राप्त करते हैं। यही बात फेस्ट पर लागू होती है, क्योंकि:

fst ( fst ( ए , बी ), सी ) = ए

fst ( ए , एफएसटी ( बी , सी )) = ए

किसी भी क्रम में एक अनुक्रम में fst अनुप्रयोगों की श्रृंखला अभी भी अपने प्रमुख तत्व का उत्पादन करेगी।



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

a a e = e e a = a

लाइनों के साथ उदाहरण में, तटस्थ तत्व खाली रेखा है ""



: जिस तरफ आप इसे किस रेखा से चिपकाते हैं, वह रेखा नहीं बदलेगी। लेकिन इस संबंध में फेस्ट हमें एक तरकीब दिखाएगा : इसके लिए एक तटस्थ तत्व के साथ आना असंभव है। वास्तव में, fst ( e , a ) = e हमेशा, और यदि then e है , तो हम तटस्थता गुण खो देते हैं। आप निश्चित रूप से, एक तत्व के सेट पर fst पर विचार कर सकते हैं, लेकिन इस तरह की बोरियत की जरूरत किसे है? :)



प्रत्येक ऐसे ट्रिपल <M, ⊗, e> को पूरी तरह से एक मोनॉयड कहा जाएगा। हम इस ज्ञान को कोड में ठीक करते हैं:

 public interface IMonoid<T> { T Zero { get; } T Append(T a, T b); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

मोनोइड्स के अधिक उदाहरण, साथ ही जहां हम वास्तव में उनका उपयोग करेंगे, कट के नीचे झूठ बोलते हैं।

उदाहरण

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



तो, लोकप्रिय मुद्राएं:

• <संख्याएँ, +, 0>। संख्याएं प्राकृतिक से जटिल तक कोई भी संख्यात्मक सेट होती हैं।
• <संख्‍या, *, 1>।
• <बूलियन, &&, True>।
• <बूलियन, ||, गलत>।
• <स्ट्रिंग्स, संघनन at, खाली स्ट्रिंग ""
  
  
  
  >।
• <सूचियाँ, संक्षिप्त नाम ++, खाली सूची []>।
• <सेट, संघ ∪, खाली सेट,>।
• <क्रमबद्ध सूची, विलय, खाली सूची []>। यहाँ, मर्ज दो ऑर्डर की गई सूचियों को विलय करने के रैखिक संचालन को संदर्भित करता है, जो संभवत: मर्ज सॉर्ट सॉर्टिंग एल्गोरिदम द्वारा आपको ज्ञात है। वैसे, मर्ज सॉर्ट एल्गोरिथ्म की शुद्धता स्वयं इस तथ्य से सटीक रूप से अनुसरण करती है कि मर्ज एक मोनोइडल ऑपरेशन है। इसके अलावा, उनके मुख्य विचार के समान एक विचार आज एक से अधिक बार उपयोग किया जाएगा।
• <Integers, NOC, 1>।
• <एक चर, एनओसी, 1> के बहुपद।
• <पूर्णांक और बहुपद, जीसीडी, 0>। सबसे बड़े सामान्य भाजक की संगति समझ में आती है। एक तटस्थ तत्व के रूप में शून्य के लिए, इस संपत्ति को अक्सर परिभाषा द्वारा माना जाता है, क्योंकि यह यूक्लिडियन एल्गोरिथ्म के साथ आसानी से संगत है।
• <मैट्रिक्स, *, पहचान मैट्रिक्स>। दिलचस्प बात यह है कि अगर हम सेट को गैर-पतित मैट्रीस तक सीमित कर देते हैं (जिसके लिए निर्धारक 0 के बराबर नहीं है), तो परिणामस्वरूप संरचना अभी भी एक शून्य रहेगी - गैर-पतित मैट्रीस का उत्पाद एक गैर-अध: पतन मैट्रिक्स देता है। यह सरल कथन निर्धारक के गुणों से आता है।
• <नंबर, मिनट, +।>।
• <नंबर, अधिकतम, -∞>।
• <क्रमांक 1 से N तक के क्रमपरिवर्तन, क्रमपरिवर्तन के उत्पाद identity, पहचान क्रमचय (123..N)>।
  
  असतत गणित में एस और टी के उत्पाद के तहत हमारा मतलब है कि निम्नलिखित ऑपरेशन: हम पहली स्थिति में एक संख्या लेते हैं, इस सूचकांक में हम एक संख्या लेते हैं और इसे परिणाम की पहली स्थिति में डालते हैं; फिर दूसरी स्थिति के लिए इस दोहरे सूचकांक को दोहराएं और इसी तरह Nth तक। यही है, अगर u = s , t , तो u[i] = t[s[i]], i = 1..N
  
  
  
  । प्रोग्रामिंग में उत्पन्न होने वाली विभिन्न समस्याओं में क्रमपरिवर्तन और उनके उत्पाद बहुत बार पाए जाते हैं।
• कुछ सेट X पर विचार करें। गणित में X ^X द्वारा एंडोमोर्फ़िज्म के सेट को निरूपित करने के लिए प्रथागत है - इसमें सेट X से मनमाने कार्य। तो, यदि X एक पूर्णांक है, तो फॉर्म का कोई भी कार्य int → int
  
  
  
  उस पर एक एंडोमॉर्फिज़्म है। कार्यों की संरचना "functions" क्या है, यह भी "है।" हास्केल और ">>" में एफ #, हर कोई जानता है।
  
  तो, <एंडोमॉर्फिज्म, कार्यों की संरचना, समान फ़ंक्शन आईडी > एक मोनॉइड है।
• सामान्य रैखिक पूर्णांक ऑपरेशन ("+" या "*") लें और एक निश्चित संख्या P के शेष भाग से लिए गए संख्याओं तक इसके उपयोग को सीमित करें । उदाहरण के लिए, हम गुणा मॉडुलो 7 पर विचार कर सकते हैं, जहां 3 * 4 = 5, क्योंकि 12% 7 = 5. इस तरह के सेट पर परिणामी संचालन बंद रहेगा और एक मोनॉइड भी बनेगा - संख्या सिद्धांत और क्रिप्टोग्राफी के लिए एक अत्यंत महत्वपूर्ण मोनॉयड।
  
  वैसे, यदि हम पी = 2 लेते हैं, तो हमें बिटवाइज़ ऑपरेशन मिलते हैं। तो, "और" एक गुणा मोडुलो 2 है, और "^", जिसे एक्सओआर के रूप में भी जाना जाता है, एक अतिरिक्त मॉड्यूल 2 है। इस प्रकार, <बूलियन, ^, फाल्स> भी एक मोनोड है।
• <शब्दकोश (सहयोगी सरणियाँ), संघ, खाली शब्दकोश>। स्वयं शब्दकोश में संग्रहीत डेटा को एक मोनॉइड बनाना होगा, इस प्रकार संयोजन करते समय संघर्षों को हल करना चाहिए: (map1 ∪ map2)[key] = map1[key] ⊗ map2[key]
  
  
  
  ।
  
  या आप केवल कुंजियों से मानों ( K -> V
  
  
  
  ) तक ही शब्दकोशों पर विचार नहीं कर सकते हैं, लेकिन मानों की सूचियों ( K -> [V]
  
  
  
  ) की कुंजियों से बहु-शब्दकोशों, फिर जब शब्दकोशों का संयोजन करते हैं, तो समान कुंजियों वाली सूचियों का उपयोग करके विलय किया जा सकता है कि सूचियाँ स्वयं एक मोनॉयड बनाती हैं।

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

हम एकल के रूप में सभी monoids को लागू करेंगे। किसी अज्ञात अज्ञात प्रकार के उदाहरण को एक्सेस करने के लिए इसे बाद में सुविधाजनक बनाने के लिए, मैंने इसकी रचना को एक अलग स्टेटिक क्लास में रखा।

 public static class Singleton<T> where T : new() { private static readonly T _instance = new T(); public static T Instance { get { return _instance; } } } public class AddMonoid : IMonoid<int> { public AddMonoid() {} public int Zero { get { return 0; } } public int Append(int a, int b) { return a + b; } } public class FunctionMonoid<T> : IMonoid<Func<T, T>> { public FunctionMonoid() {} public Func<T, T> Zero { get { return x => x; } } public Func<T, T> Append(Func<T, T> f, Func<T, T> g) { return x => g(f(x)); } } public class GCDMonoid : IMonoid<int> { public GCDMonoid() {} private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } public int Zero { get { return 0; } } public int Append(int a, int b) { return gcd(a, b); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

जहाँ कंप्यूटर विज्ञान में रस्सियाँ

इस क्षण से हम व्यावहारिक अनुप्रयोगों के क्षेत्र में प्रवेश करते हैं।



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



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



ऐसी डेटा संरचना को रस्सी कहा जाएगा।

इंडेक्स एक्सेस

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



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

एक साथ चिपकाने

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

अनुरोध अनुरोध

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



सबसे पहले, दो चरम मामलों पर विचार करें।

यदि start = 0



, और len = T.Left.Size



, तो इसका उत्तर T.Left



का संपूर्ण उपशीर्षक है। इसी तरह, यदि start = T.Left.Size



, और len = T.Right.Size



, तो इसका उत्तर T.Right



का संपूर्ण T.Right



। ऊपर दिए गए आंकड़े में, दूसरे मामले का एहसास होता है यदि आप Substring( start : 18, len : 37)



फ़ंक्शन को कॉल करते हैं Substring( start : 18, len : 37)



, तो फ़ंक्शन तुरंत " , "



के जरूरी विकल्प के साथ सही सबट्री वापस कर देगा " , "



।



इसके अलावा, मामला तब संभव है जब वांछित विकल्प पूरी तरह से बाएं सबट्री में निहित है, यानी, start < T.Left.Size



और start + len ≤ T.Left.Size



। फिर घटिया खोज फ़ंक्शन को पुन: बाएं सबट्री के लिए पुन: कॉल किया जाना चाहिए।

सममित मामला पूरी तरह से सही start ≥ T.Left.Size



में एक विकल्प है, अर्थात् start ≥ T.Left.Size



और start + len ≤ T.Left.Size + T.Right.Size



। फिर पुनरावर्ती खोज सही सबट्री पर जाती है, बस start



से बाएं सबट्री के आकार को घटाना याद रखें - आखिरकार, सही उपरी में अनुक्रमण शून्य से शुरू होगा, यह खुद को एक स्वतंत्र पेड़ मानता है।

हमारे उदाहरण में, हम Substring( start : 18, len : 18)



को कॉल कर सकते हैं Substring( start : 18, len : 18)



। फिर, पहले चरण में, फ़ंक्शन यह निर्धारित करता है कि दाईं ओर पुनरावर्ती रूप से नीचे जाने के लिए और सही सबट्री पर Substring( start : 0, len : 18)



को कॉल करना Substring( start : 0, len : 18)



। और वह, बदले में, पहले मामले के अनुसार, " , "



अनुरूप, पूरी तरह से अपने बाएं सबट्री में हमारे पास वापस आ जाएगा।



और अंत में, सबसे मुश्किल मामला - वांछित विकल्प बाएं और दाएं सबट्री के एक टुकड़े को ओवरलैप करता है।

इस मामले में, हमें उस टुकड़े का चयन करना होगा जो केवल बाएं सबट्री में जाता है, फिर वह टुकड़ा जो दाईं ओर जाता है, और उन्हें मर्ज करता है। हम पहले से ही जानते हैं कि दो रस्सियों को एक साथ कैसे मिलाया जाए।

वांछित टुकड़ों के सूचकांक का निर्धारण करना बिल्कुल भी मुश्किल नहीं है। बाएं सबट्री के लिए पुनरावर्ती कॉल:

Substring( start : start, len : T.Left.Size - start)





दाईं ओर:

Substring( start : 0, len : len - (T.Left.Size - start))



।

फिर से, हमें start



तर्क के रूप में शून्य से दाएं उपप्रकार में पास करना था, क्योंकि इस पर फ़ंक्शन स्वतंत्र रूप से काम करेगा।

यदि ये संकेत स्पष्ट नहीं हैं, तो एक नज़र डालें।


अंत में, पुनरावर्ती कॉल उन पत्तियों तक पहुंचते हैं जिसमें सेगमेंट अनुरोध पहले से ही खंड के साथ सामान्य रैखिक तरीके से किया जाता है। यह अधिकतम प्रदर्शन सुनिश्चित करता है। ऑपरेशन की कुल जटिलता हे (लॉग एन)।

अन्य

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

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

परिशोधन, या एक पेड़ को कैसे मापना है

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



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



एनोटेशन के साथ फिर से निहित कार्टेशियन के पेड़ पर विचार करें - उपशीर्षक के योग - कोने पर, और इसे सबसिलेशन पर योग के लिए क्वेरी करने का प्रयास करें [4; 8]



[4; 8]



।



परिणाम को प्रारंभिक ०।

1 पुनरावृत्ति में, हम बाएं उपश्रेणी में उतरते हैं [0; 9]। परिणाम 0 रहता है।

पुनरावृत्ति 2 पर, हम सही उपश्रेणी में उतरते हैं [5]; 9]। परिणाम मूल में मूल्य से बढ़ता है - 42।

पुनरावृत्ति 3 पर, हम सही उपश्रेणी में उतरते हैं [8; 9]। परिणाम बाएं सबट्री के योग से बढ़ा है [5; ६] जड़ में मान और ४२ + २३ + ३ = ६ in हो जाता है।

पुनरावृत्ति 4 पर, हम बाएं उपश्रेणी में उतरते हैं [8]; 8]। परिणाम 68 रहता है।

पुनरावृत्ति 5 पर, हम परिणाम के लिए (29) के मूल में मान जोड़ते हैं, हमें कुल 97 मिलते हैं, और यह समस्या का उत्तर है।



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



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



और इसे समझना भी आसान है। वास्तव में, हम एक ही योग करते हैं जैसे कि हम बस रैखिक रूप से सबसिलेशन की सभी कोशिकाओं के माध्यम से चले गए, हम अब केवल एक) कोशिकाओं के पूरे ब्लॉक को संक्षेप में प्रस्तुत करते हैं; ख) जरूरी नहीं कि बाएं से दाएं। वास्तव में, आप इस प्रक्रिया की कल्पना कर सकते हैं:

लाइन पास: (C _l + C _{l + 1} + ... + C _r )

ट्री अनुरोध: (C _l + (((C _{l + 1} + ... + C _i ) + (C _{i + 1} + ... + C _j )) + (C _{j + 1} + ... + C _r-1 ) + ... + सी _आर ))

वास्तव में, हम बस कोष्ठकों को किसी अन्य क्रम में रखते हैं, और इससे किसी भी तरह से परिणाम में बदलाव नहीं होता है, क्योंकि "+" एक सहयोगी ऑपरेशन है! ओह, मैं पहले पैराग्राफ से एक परिचित शब्द मिला :) ऐसा लगता है कि एक बहुत अधिक सामान्य अवधारणा यहां आंकी जा रही है ...

उपाय

हम एक फ़ंक्शन को कहते हैं जो पेड़ में एक पेड़ के माप में निहित तत्वों के सेट को चिह्नित करता है। आमतौर पर, एक पेड़ का माप ठीक वह ऑपरेशन है जिसके लिए हम बाद में प्रश्न करेंगे।मैंने पहले ही उदाहरण दिए हैं: तत्वों का योग, तत्वों की अधिकतम, तत्वों पर एक ध्वज की उपस्थिति, और इसी तरह। एक और अधिक जटिल उपायों की कल्पना कर सकता है, उदाहरण के लिए, वर्गों की राशि या वर्णों की आवृत्ति का हिस्टोग्राम।



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



हमें एक सार्वभौमिक डेटा संरचना मिलती है: एक रस्सी, जो किसी भी उप-खंड पर माप के मूल्य को जल्दी से क्वेरी करने की अनुमति देती है, जिसमें रस्सियों को चमकाने और काटने के बाद भी शामिल है। एक्सेस टाइम लॉगरिदमिक रहता है, क्योंकि पेड़ अपने आप संतुलित होता है! तत्वों को जोड़ते समय, नए उपप्रकार के लिए कैश्ड माप मान पुनर्गणित होते हैं, अछूते लोगों के लिए वे समान रहते हैं। और यह सब O (log N) के लिए है। बहुत खूब।



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



"अधिकतम" माप x का एक प्राथमिक कार्य है जिसमें मोनॉइड <संख्या, अधिकतम, -∞> के परिणाम हैं।

"वर्गों का योग" माप एक प्राथमिक कार्य x ² है जिसका परिणाम मोनॉइड <संख्या, +, 0> में है।

उपाय "फ़्रीक्वेंसी हिस्टोग्राम" - प्रारंभिक फ़ंक्शन "एक दिए गए प्रतीक के लिए 100%"मोनोड में परिणाम के साथ <हिस्टोग्राम्स, हिस्टोग्राम्स को वर्णों की संख्या को ध्यान में रखते हुए संयोजन करते हैं, एक खाली हिस्टोग्राम>। पाठक, एक अभ्यास के रूप में, आवृत्ति हिस्टोग्राम के संयोजन के एक पूरी तरह से साहचर्य संचालन पर सोचना पड़ता है।



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

मैं संतुलन के बिना एक सरल द्विआधारी पेड़ का कार्यान्वयन दूंगा और वास्तव में जोड़ने / gluing / काटने। इन कार्यों को कैसे कार्यान्वित किया जाता है यह प्रत्येक विशेष प्रकार के संतुलित पेड़ के लिए विशिष्ट है और इसके लिए एक अलग लेख की आवश्यकता होगी, जैसा कि मैंने कहा, मेरा लक्ष्य नहीं है। पाठक आसानी से वर्ग के स्थान पर कल्पना कर सकते हैं Tree



, उदाहरण के लिए FingerTree



। या कुछ जटिल है ImplicitTreap



, जिसमें "न्याय बहाल करने" के संबंधित कार्य को फिर से लिखा गया है और यह ध्यान में रखा जाता है कि डेटा को पेड़ के कोने में भी संग्रहीत किया जाता है, और पेड़ के वंशज भी पतले हो सकते हैं।

 //  ,   . public interface IMeasured<V> { V Measure { get; } } //  :      public class IdentityMeasure<T> : IMeasured<T> { public readonly T Data; public IdentityMeasure(T data) { Data = data; } public T Measure { get { return Data; } } } // T -      // V -      // M - ,         public class Tree<T, M, V> : IMeasured<V> where M: IMonoid<V>, new() where T: IMeasured<V> { public readonly T Data; //    public readonly Tree<T, M, V> Left; public readonly Tree<T, M, V> Right; private readonly V _measure; public V Measure { get { return _measure; } } public Tree(T data) //   { Left = Right = null; Data = data; _measure = data.Measure; } public Tree(Tree<T, M, V> left, Tree<T, M, V> right) //   { Left = left; Right = right; Data = default(T); _measure = Singleton<M>.Instance.Append(left.Measure, right.Measure); } } //  ,      public class SumTree : Tree<IdentityMeasure<int>, AddMonoid, int> { public SumTree(int data) //   : base(new IdentityMeasure<int>(data)) {} public SumTree(SumTree left, SumTree right) //   : base(left, right) {} } //  ,      public class PriorityTree : Tree<IdentityMeasure<double>, MaxMonoid, double> { public PriorityTree(double data) //   : base(new IdentityMeasure<double>(data)) {} public PriorityTree(PriorityTree left, PriorityTree right) //   : base(left, right) {} }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

इस खंड में हमारे सभी प्रयासों की परिणति उप-ट्रिम उपाय का अनुरोध करने के लिए एक सामान्यीकृत तरीका होगा।

 //  . //      : Size = 1 + left.Size + right.Size; public readonly int Size = 1; public V MeasureOn(int start, int length) { if (start == 0 && length == Left.Size) return Left.Measure; if (start == Left.Size && length == Right.Size) return Right.Measure; if (start + length <= Left.Size) return Left.MeasureOn(start, length); if (start >= Left.Size) return Right.MeasureOn(start - Left.Size, length); var monoidV = Singleton<M>.Instance; var leftValue = Left.MeasureOn(start, Left.Size - start); var rightValue = Right.MeasureOn(0, length - (Left.Size - start)); return monoidV.Append(leftValue, rightValue); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

नया चरण: भविष्यवाणी करता है

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



उदाहरण के लिए, यदि माप किसी सेगमेंट में तत्वों की अधिकतम है, तो यह जानना अच्छा होगा कि यह खाता किस विशेष तत्व तक पहुंचता है। हमारी पुरानी अच्छी इंडेक्स एक्सेस भी उसी ऑपरेशंस पर लागू होती है। ये सभी ऑपरेशन, जैसा कि हम याद करते हैं, एक बहुत ही समान एल्गोरिथ्म द्वारा वर्णित हैं - यह रैखिक रूप से पेड़ के एक शीर्ष से दूसरे तक पहुंचता है जब तक कि यह वांछित पत्ती तक नहीं पहुंचता। इसलिए, इस तरह के सभी कार्यों को सामान्य बनाने का एक बहुत ही सरल तरीका है।



एक पर विचार करें विधेय पी, अर्थात्, एक मनमानी तर्क का बूलियन कार्य।

हम वस्तुओं की एक अनुक्रम करते हैं एक ₁ ... एक _{एन की} । वस्तुएं किसी प्रकार के मोनॉइड के तत्व हैं। उदाहरण के लिए, इसे लाइनें होने दें।



हम क्रमिक रूप से हमारे अनुक्रम के उपसर्गों की गणना करेंगे । यह इस नए अनुक्रम है:

एक ₁

एक ₁ ⊗ एक ₂

एक ₁ ⊗ एक ₂ ⊗ एक ₃

...

एक ₁ ⊗ एक ₂ ⊗ एक ₃ ⊗ ... ⊗ एक _{एन की}

जहां "⊗", हम सहमति के रूप में, - monoid के आपरेशन। तार के साथ एक उदाहरण के लिए यह समवर्ती होगा।



अब हम इन सभी उपसर्गों पर विधेय मूल्य की गणना करते हैं। हमें बूलियन मूल्यों का एक क्रम मिलता है।

और अंत में, हम एक विधेय मोनोटोन कहते हैं यदि यह हमेशा हमारे उपसर्गों पर गलत होता है, तो कुछ बिंदु पर गलत को सही पर बदल देता है, जिसके बाद अनुक्रम के अंत तक यह सही रहता है।

सीधे शब्दों में कहें, यदि आप 1 के साथ झूठी और 1 के साथ सच की जगह लेते हैं, तो विधेय परिणामों का क्रम गैर-घटता होना चाहिए।



मैं इस संपत्ति को मोनोड स्ट्रिंग्स के लिए आंकड़े में प्रदर्शित करूंगा। चलो पी ( रों ) = { s शामिल ""



सबस्ट्रिंग के रूप में}।

रस्सी के शीर्ष पर कैश्ड माप मान होते हैं, अर्थात, उपरी रेखाओं का संघटन।



एल्गोरिथ्म लगातार दो उपसर्गों का समर्थन करता है: एक वर्तमान बाएं बेटे को ध्यान में रखे बिना, दूसरा - इसमें शामिल है। इन उपसर्गों पर विधेय के मूल्य के आधार पर, आप लगातार सही ढंग से यह निर्धारित कर सकते हैं कि कौन सा "कूद" हुआ है।

उदाहरण के लिए, जब हम रस्सी के मूल में थे, एल्गोरिथ्म ने देखा कि पी ( " "



) = गलत , जिसका अर्थ है कि कूदना सही सबट्री में हुआ, जहां हम नीचे गए थे। लेकिन अगले पुनरावृत्ति पर, बाईं उपसर्ग पी पर मान( " , "



) = सही है , इसलिए, बाएं सबट्री के लिए नीचे जाना आवश्यक है।



वंश के दौरान, आपको लगातार उपसर्ग के सही मूल्य को बनाए रखना चाहिए, इसे वर्तमान बाएं बेटे की माप के साथ सही सबट्री में वंश के मामले में चमकाना चाहिए।



अंत में, लॉगरिदमिक संख्या के चरणों में, हम उस शीट पर पहुंचते हैं जिसमें कूद हुआ था। लीफ सेगमेंट के अंदर, अलग-अलग तरीके से सटीक कूद स्थान की तलाश करना पहले से ही आवश्यक है, सबसे अधिक संभावना है कि एक अनुक्रमिक चेक द्वारा। हालाँकि, यह इतना तुच्छ नहीं हो सकता है: विधेय के बदले कल्पना करें "एक दिया गया विकल्प है", विधेय "एक नियमित रूप से अभिव्यक्ति को संतुष्ट करता है"। यह नीरस भी है, लेकिन इसकी गणना के लिए कुछ प्रयास की आवश्यकता है।



उदाहरण के लिए, "वर्गों का योग" और "256 से अधिक" का अनुमान लगाने के लिए, हमें जंप की सटीक स्थिति निर्धारित करने के लिए शीट में सेगमेंट से प्रत्येक विशिष्ट संख्या के वर्गों की अलग से गणना करने की आवश्यकता होगी।



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

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

, . , . .

लेकिन अब यह स्पष्ट है कि, उदाहरण के लिए, इंडेक्स I के तहत एक तत्व तक पहुंच केवल मोनोटोन का उपयोग करके पेड़ में एक खोज है "पूर्वसर्ग लंबाई> i "। उपसर्ग की लंबाई एक सामान्य उपाय है, हमने इसे एक माप के रूप में उपयोग किया जब हमने उपप्रकार के आकारों को संग्रहीत किया। इस उपाय के लिए, प्रारंभिक कार्य पहचान इकाई है, और मान मोनॉइड <, +, 0> में हैं। स्थिति संख्या i - यह ठीक वही स्थिति है जहाँ अनुक्रम उपसर्ग की लंबाई i से अधिक होने लगती है ।

चयनित उदाहरण

इसलिए, हमने सभी मुख्य फायदों की जांच की कि इस अवधारणा को रस्सी के पैरामीटर के रूप में कुछ मोनॉयड के साथ हमें दिया जाता है। हम "औसत दर्जे का" मूल्यों के मनमाने ढंग से अनुक्रम ले सकते हैं और उन्हें एक के बाद एक जोड़ सकते हैं, जिसके परिणामस्वरूप अनुक्रमों के किसी भी सबसेप्शन के लिए, माप के मूल्य को पहचान सकते हैं। यदि हम रुचि रखते हैं, तो हम कुछ मोनोटोन के अनुसार परिणामी रस्सी को काटकर उपलब्धि की सही स्थिति का पता लगा सकते हैं। और यह सब एक लघुगणक समय में, जो हमें असीमित संभावनाओं की गुंजाइश देता है। मैं अब इस असीमित दायरे को लागू करने जा रहा हूं, जिसमें आपको तीन नहीं बल्कि गैर-मानक, बहुत महत्वपूर्ण और दिलचस्प मोनॉयड दिखाई देंगे।

उदाहरण नंबर 1: आंकड़े

इस बार हम बोरिंग नंबरों, स्ट्रिंग्स या बल्स की तुलना में कुछ अधिक उबाऊ बना रहे हैं। हमारे करीब ध्यान का उद्देश्य होगा ... नमूने।



एक नमूना, अर्थात्, एक निश्चित आबादी से यादृच्छिक मूल्यों का एक निश्चित सेट, औसत दर्जे का हो सकता है। हर कोई नमूने की मुख्य विशेषताओं को जानता है:

एन - नमूना आकार।

एम नमूने का औसत मूल्य है।

V नमूने का विचरण है, अर्थात्, औसत नमूने से विचलन के वर्गों का औसत मूल्य है।

हम अनियंत्रित विचरण पर विचार करते हैं, अर्थात् , मतलब से चुकता विचलन का योग है। यदि आवश्यक हो, यह से बाहर निकलने के इस प्राथमिक हो सकता है, बस पर की संख्या से विभाजित एन की ।






मैंने नीचे दिए पैराग्राफ में कहा कि नमूना "औसत दर्जे का हो सकता है।" हां, मैंने गलती से इस शब्द का उपयोग नहीं किया था :) नमूना के इन तीन बुनियादी विशेषताओं का एक सेट इसके उपाय के रूप में काम कर सकता है।

स्टॉप-स्टॉप-स्टॉप, आप कहते हैं, तीन शिथिल युग्मित संख्याओं का एक ही सेट क्या है - एक मोनोइड का एक तत्व? यह किस प्रकार का मोनॉयड है? किसी भी तरह नमूनों को संयोजित करना आवश्यक है, यह पता चला है? लेकिन इससे क्या?



यह सब खूबसूरती से किया गया है। मान लीजिए कि आपके पास एक ही जनसंख्या से दो नमूने A और B हैं । आप इन नमूनों को एक साथ जोड़ते हैं, एक संयुक्त नमूना एक्स बनाते हैं , जिसका आकार मूल लोगों के आकार का योग है। फिर, जैसा कि 1979 में टोनी चैन ने दिखाया था, एक नए नमूने के औसत और बिना बिके हुए संस्करण की गणना निम्न सूत्रों का उपयोग करके की जा सकती है:









जाहिर है, इससे कोई फर्क नहीं पड़ता कि नमूनों को एक साथ मिलाने के लिए किस क्रम में अंतिम नमूने की विशेषताएं समान होंगी। इस प्रकार, नमूने का विलय साहचर्य है।

यह निर्धारित करने के लिए एक औपचारिकता बनी हुई है कि खाली नमूने की विशेषताएं क्या हैं। इसका आकार स्पष्ट रूप से 0 है, व्यसन की वजह से औसत भी 0 होगा, लेकिन विचरण संतोषजनक ढंग से निर्धारित नहीं किया जा सकता है। हालाँकि, हमें इस बात की आवश्यकता नहीं है - हमारे पेड़ों में हम खाली नमूने के विचरण को बिल्कुल भी नहीं छूएंगे।



मुझे सांख्यिकीय विशेषताओं और सब कुछ जो कि pastie.org पर है , से मोनॉइड की परिभाषा डालनी थी , क्योंकि लेख के आकार पर हैब्राहब का प्रतिबंध कुछ हद तक तनाव शुरू होता है :)



आप आसानी से यादृच्छिक चर की धारा की कल्पना कर सकते हैं, जिस पर "विंडो" आकार K चलता है।, यानी। हमें लगातार अंतिम K राशियों के विचरण और अपेक्षा को जानना होगा । एक पेड़ बनाया जाता है, तत्वों को क्रमिक रूप से इसे हटा दिया जाता है और जोड़ा जाता है, जैसे कि एक कतार में, और गणना किए गए मान जिन्हें हमें हमेशा पेड़ की जड़ पर झूठ बोलने की आवश्यकता होती है। सौंदर्य।

उदाहरण नंबर 2: छवियों की अल्फा रचना

दो पारभासी चित्र हैं (अल्फा चैनल के साथ)। हम दो चित्रों के लिए एक ओवरले ऑपरेटर को परिभाषित करना चाहते हैं , जिसे अल्फा रचना के रूप में जाना जाता है । फ़ोटोशॉप में पारभासी छवियों के साथ खेलने वाले हर कोई इसकी कार्रवाई से परिचित है।


छवियों में प्रत्येक पिक्सेल के लिए दो पैरामीटर परिभाषित किए गए हैं: रंग सी और अल्फा चैनल α । इन मूल्यों की पूरी तरह से और स्पष्ट रूप से गणना करने के लिए सूत्रों को परिभाषित करना सुपरिम्पोजर ऑपरेटर को परिभाषित करता है। इसलिए, यह पता चला है कि निम्नलिखित तथ्यों को गणितीय रूप से आसानी से प्राप्त किया जा सकता है:

• ओवरले ऑपरेटर सहयोगी है;
• 0 के बराबर एक अल्फा चैनल के साथ कोई भी छवि ओवरले ऑपरेटर के लिए एक इकाई के रूप में कार्य करती है।

इन तथ्यों और विशिष्ट सूत्रों के प्रमाण के लिए, मैं आपको इसी विकिपीडिया लेख के बारे में बताता हूँ ।



इस प्रकार, अल्फा रचना के संचालन की पारदर्शी छवियां एक मोनॉइड बनाती हैं। यह हमें उचित पेड़ का उपयोग करते हुए, छवियों के विशाल सेटों को संसाधित करने का अवसर देता है, जो एक-दूसरे पर आरोपित होना चाहिए।

उदाहरण 3: नियमित अभिव्यक्ति

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









इस बीच, आप सभी का ध्यान आकर्षित करने के लिए धन्यवाद।