🤔 🦐 🍸 मुलायम हाइफ़न की व्यवस्था के लिए लियांग-नुट एल्गोरिथ्म 🌠 🤙🏾 🎧

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

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

उदाहरण के नियम:

  pri1  
 3 बी पर 
 2 और 1 वी
 .po3zh2

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

एल्गोरिथ्म के मुख्य चरण:

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

आइए देखें कि एल्गोरिथ्म एक उदाहरण पर कैसे काम करता है:

स्रोत शब्द: एल्गोरिथ्म
नियमों का एक सेट (TeX से लिया गया):

     lgo1
     1g
     o1ri
     और 1t
     i2tm
     TM2

सभी नियमों के साथ शब्द की तुलना करें और उच्चतम स्तर चुनें:

स्तर 1 के साथ पदों में, आप सुरक्षित रूप से कैरी सेट कर सकते हैं। हमें परिणाम "अल-गो-ताल" मिलता है ।

कार्यान्वयन

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

struct pattern_t { std::basic_string<unichar> str; std::vector<unsigned char> levels; };

हम प्रत्येक नियम को "वर्णों के शुद्ध अनुक्रम" + "स्तरों के सेट" के रूप में बदल देंगे, ताकि भविष्य में इसे लागू करना सुविधाजनक हो।
नियमों का एक सेट:

 struct pattern_list_t { std::vector<pattern_t*> list; };

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

 bool pattern_compare(const pattern_t* a, const pattern_t* b) { bool first = a->str.size() < b->str.size(); size_t min_size = first ? a->str.size() : b->str.size(); for (size_t i = 0; i < min_size; ++i) { if (a->str[i] < b->str[i]) return true; else if (a->str[i] > b->str[i]) return false; } return first; } void sort_pattern_list(pattern_list_t* pattern_list) { if (!pattern_list) return; std::sort(pattern_list->list.begin(), pattern_list->list.end(), pattern_compare); }

अब सीधे हाइफ़नेशन को खोजने वाला एल्गोरिथ्म:

 std::vector<unsigned char> levels; levels.assign(word_string.size(), 0); for (size_t i = 0; i < word_string.size()-2; ++i) { std::vector<pattern_t*>::const_iterator pattern_iter = pattern_list->list.begin(); for (size_t count = 1; count <= word_string.size()-i; ++count) { pattern_t pattern_from_word; pattern_from_word.str = word_string.substr(i, count); if (pattern_compare(&pattern_from_word, *pattern_iter)) continue; pattern_iter = std::lower_bound(pattern_iter, pattern_list->list.end(), &pattern_from_word, pattern_compare); if (pattern_iter == pattern_list->list.end()) break; if (!pattern_compare(&pattern_from_word, *pattern_iter)) { for (size_t level_i = 0; level_i < (*pattern_iter)->levels.size(); ++level_i) { unsigned char l = (*pattern_iter)->levels[level_i]; if (l > levels[i+level_i]) levels[i+level_i] = l; } } } }

स्ट्रिंग शब्द_स्ट्रिंग में हमने मूल शब्द को जोड़ा वर्णों के साथ रखा है '।' किनारों के साथ, ताकि नियमों को स्वचालित रूप से चयनित किया जाए जिसमें शब्द में उनकी स्थिति के बारे में निर्देश हों। अब I = 0 से N के साथ प्रत्येक वर्ण के लिए स्रोत शब्द में , हम 1 से नी तक की लंबाई और i के साथ शुरू होने वाले सभी सबस्ट्रिंग के माध्यम से सॉर्ट करते हैं। हम मानक वेक्टर के साथ नियम वेक्टर में प्रत्येक प्रतिस्थापन के लिए खोज करते हैं :: निचला_बाउंड एल्गोरिथ्म । हम मानते हैं कि नियमों को हमारी ज़रूरत के अनुसार क्रमबद्ध किया गया है और हर चरण पर इसे फिर से पूरा करने की आवश्यकता नहीं है। जब हम एक मैच पाते हैं, तो स्तर वेक्टर लेते हैं और इसे वर्तमान परिणाम पर लागू करते हैं, अर्थात। यदि नियम में वर्तमान स्थिति का स्तर अधिक है, तो इसे पुराने के बजाय याद रखें।

वेक्टर स्तर में, प्रत्येक स्थिति के लिए अधिकतम स्तर मान संचित होते हैं। यह विषम मूल्यों के लिए इसकी जांच करने के लिए बना हुआ है।

 mask_size = levels.size()-2; mask = new unsigned char[mask_size]; for (size_t i = 0; i < mask_size; ++i) { if (levels[i+1] % 2 && i) mask[i] = 1; else mask[i] = 0; }

TeX से नियमों के एक सेट के लिए एल्गोरिथ्म के उदाहरण:

  प्रो ग्राम
 बेर-की-नहीं-ti-का
 रोना
 इन-द-मैं ची-ya
 टू-एक-सौ-एट-मुझे-चा-तेल सत्ता
 जब-गीला

उदाहरणों के साथ तैयार सी ++ कोड यहां डाउनलोड किया जा सकता है । मुख्य मामला फ़ाइल में परीक्षण केस (एन्कोडिंग विंडोज़ -1251), पैटर्न में नियम। h फ़ाइल।

मुलायम हाइफ़न की व्यवस्था के लिए लियांग-नुट एल्गोरिथ्म

उदाहरण के नियम:

एल्गोरिथ्म के मुख्य चरण:

आइए देखें कि एल्गोरिथ्म एक उदाहरण पर कैसे काम करता है:

कार्यान्वयन

More articles: