👂🏾 🔟 ⌚️ प्रत्यय सरणी - प्रत्यय पेड़ के लिए एक सुविधाजनक प्रतिस्थापन 📎 🏼 📷

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

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

प्रत्यय सरणी अनुप्रयोगों

सभी पेड़ समान रूप से उपयोगी नहीं हैं।

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

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

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

प्रत्यय सरणी

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

#	प्रत्यय	प्रत्यय संख्या
1	मैं	11
2	ippi	8
3	issippi	5
4	ississippi	2
5	मिसीसिपी	1
6	अनुकरणीय	10
7	ppi	9
8	Sippi	7
9	sissippi	4
10	ssippi	6
11	ssissippi	3

इसके अलावा एक महत्वपूर्ण अवधारणा प्रत्यय की रैंक है - वह स्थान जो छंटनी के समय प्रत्यय लेता है, अर्थात, प्रत्यय सरणी में इसकी स्थिति। ये पारस्परिक मात्राएँ हैं। हम विशेष रूप से उनके बीच अंतर नहीं करते हैं, क्योंकि एक सरणी होने के बाद, आप ओ (एन) के लिए अन्य प्राप्त कर सकते हैं, इसलिए आपके पास हमेशा दोनों हो सकते हैं।

सबसे सरल प्रतिस्थापन खोज

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

एसपी	सी पी	घूंट
मैं	मैं	मैं
ippi	ippi	ippi
issippi	issippi	issippi
ississippi	ississippi	ississippi
मिसीसिपी	मिसीसिपी	मिसीसिपी
अनुकरणीय	अनुकरणीय	अनुकरणीय
ppi	ppi	ppi
एस इप्पी	स पपी	घूंट पी
ssippi है	सी एसआईपीआई	sissippi
sipp s	ssippi	ssippi
s sippippi	ssissippi	ssissippi

यदि हम द्विआधारी खोज "हेड-ऑन" का उपयोग करते हैं तो हमें बिल्कुल वैसी ही जटिलता मिलती है: किनारों के साथ और मध्य रेखा में पूर्ण लेक्सिकोग्राफ़िक तुलना नमूने के साथ: O (log | A |) की तुलना ओ ( एक्स ! एक्स ) की औसत "कीमत" के साथ होती है।

तेजी से

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

मान लें कि हम बायीं ओर के नमूने के सामान्य उपसर्ग की लंबाई को वर्तमान सीमा l = lcp ( X , S [ L ] ) और r = lcp ( X , S [ R ] ) के किनारों से बाएँ और दाएँ किनारों ( lcp - सबसे लंबे समय तक सामान्य उपसर्ग) के किनारों के साथ जानते हैं । पहला कथन यह है कि lcp सीमा के भीतर किसी भी लाइन के लिए, इन दोनों संख्याओं के न्यूनतम से कम नहीं हैं। यदि यह ऐसा नहीं था, तो उपसर्ग के प्रारंभिक भाग के साथ अपरिवर्तित, एक ऐसी स्थिति होगी जहां प्रतीक पहले पैटर्न के संबंधित प्रतीक के साथ संयोग करेगा, फिर संयोग नहीं, और फिर फिर से संयोग होगा। यह रेंज की छंटाई का खंडन करेगा। इस विचार के लिए एक अच्छा अनुभव प्राप्त करना महत्वपूर्ण है, क्योंकि हम इसे बाद के लिए उपयोग करेंगे। दूसरा कथन स्पष्ट है: यदि नमूने का सामान्य उपसर्ग और सीमा के भीतर कोई रेखा m = मिनट (l, r) से कम नहीं है, तो m वर्णों को तुरंत छोड़ दिया जा सकता है, यह जानकर कि वे किसी भी मामले में मेल खाते हैं, और m + 1 (और एक दिए गए लाइन के लिए lcp के परिणामस्वरूप)।

lcp (X, L) और lcp (X, R)

इस प्रकार, हम स्ट्रिंग "माथे" की द्विआधारी खोज में अनुकूलित स्ट्रिंग तुलना लागू करेंगे। सबसे खराब स्थिति में, निश्चित रूप से हमें इसका लाभ नहीं मिला: यदि वांछित तत्व सरणी के किनारे पर है, लेकिन पड़ोसी lcp में बिल्कुल समान नहीं हैं, तो आर (या l) हर बार छोटा होगा, मी भी छोटा होगा, जिसका अर्थ है कि आपको प्रत्येक को जांचना होगा चरित्र द्वारा लॉग | ए | समय। लेकिन प्रायोगिक टिप्पणियों से संकेत मिलता है कि प्राकृतिक ग्रंथों के लिए, O (log | A || X |) की तुलना में खोज समय में काफी कमी आई है, हालांकि एक विशिष्ट स्पर्शोन्मुख दवाओं के बारे में कुछ भी कहना मुश्किल है।

सिद्धांत रूप में, व्यावहारिक अनुप्रयोगों के लिए यह पहले से ही पर्याप्त है, लेकिन अगर आप सब कुछ निचोड़ना चाहते हैं, तो ...

और भी तेज

यह सीमा नहीं है। सरणी अनुभाग के किनारों की स्थिति इस खंड के केंद्र को परिभाषित करती है, और ऐसे सभी कॉन्फ़िगरेशन जो बाइनरी खोज में कार्यान्वित किए जाते हैं, वे निश्चित आकार के सेट का सबसेट होते हैं। क | -२ मान लीजिए कि हमने इन विन्यासों में गणना करने के लिए अग्रिम रूप से मात्रा m _l = lcp ( S [ M ] , S [ L ] ) और m _r = lcp ( S [ M ] , S [ R ] ), जहाँ M, L और R के बीच खंड का मध्य भाग लिया है जो हम द्विआधारी खोज चरण में जाएंगे।

बाइनरी सर्च टीडी

आइए किनारों में से एक को देखें, कहते हैं, बाएं। यदि हमने l <m _{l की} गणना की है, तो बायाँ किनारा मध्य के समान है (और उनके बीच किसी भी तत्व के लिए) जितना हम चाहते हैं उससे कहीं अधिक मजबूत है, और तुलनात्मक परिणाम L और M: lcp ( X , S) के बीच पूरे खंड के लिए पहले से जाना जाता है। [ एम ] ) = एल। इससे यह तुरंत स्पष्ट होता है कि मांगा गया तत्व निश्चित रूप से इस खंड में नहीं है, और यदि आप इसकी तलाश करते हैं, तो विपरीत आधे में। यदि l> m _l , तो मध्य वांछित नमूने से कम बाएं किनारे के समान है। तो lcp ( X , S [ M ] ) = m _l , और वांछित तत्व को बीच में कहीं खोजा जाना चाहिए।

स्वाभाविक रूप से, तर्क में कुछ भी नहीं बदलता है यदि आप बाएं किनारे को दाईं ओर बदलते हैं। केवल एक मामले पर विचार नहीं किया गया था: एल = एम _एल और आर = एम _आर (यदि कम से कम एक समानता सच नहीं है, तो परिणाम पिछले पैराग्राफ के अनुसार जाना जाता है)। फिर यह स्पष्ट है कि lcp ( X , S [ M ] ) अधिकतम (l, r) से कम नहीं है, लेकिन इसकी सटीक परिभाषा और यह पता लगाने के लिए कि किस तरह से वर्णों की तुलना करना आवश्यक होगा (अंत में!) स्थिति अधिकतम (l, r) से शुरू होती है। ) +1।

lcp (M, L) और lcp (M, R)

हमें क्या मिला? हम द्विआधारी खोज चरणों का एक दूसरे के साथ कुछ lcp की तुलना करके भाग लेंगे, और यहां तक कि अगर हमें वर्णों की तुलना करने के लिए मिलता है, तो चरित्र X के अनुसार एक बार से अधिक नहीं (हम अधिकतम (l, r) +1 लेते हैं, जिसका अर्थ है कि हम कभी पीछे नहीं हटते) इस प्रकार, हम सबसे खराब स्थिति में O (लॉग | A | + | X |) एल्गोरिथ्म की जटिलता प्राप्त करते हैं। सच है, हमें पाठ ए के प्रत्ययों के लिए पूर्व-गणना किए गए एलसीपी की आवश्यकता है जो कि बाइनरी सर्च एल्गोरिदम द्वारा प्रेरित खोज ट्री में पाए जाते हैं।

यह ध्यान रखना महत्वपूर्ण है कि यदि हम m _{r को} नहीं जानते हैं, लेकिन केवल m _{l को} जानते हैं, तो चिंता की कोई बात नहीं है। हम पहले से कहने के अवसर से वंचित हैं कि कोई प्रविष्टि नहीं है, लेकिन इससे जटिलता नहीं बिगड़ती है: हम सिर्फ दाहिने किनारे पर नहीं दिखेंगे, केवल बाईं ओर। यदि l <m _l , तो हम दूसरे आधे भाग में आगे देखते हैं, और l संरक्षित है, यदि l> m _l , तो r हम m _{l के} रूप में लेते हैं और इस छमाही में देखते हैं, लेकिन यदि l = m _l , तो हम माध्य तत्व की तुलना वांछित स्ट्रिंग से करते हैं। एल + 1 स्थिति से शुरू। हम इस मामले में वापस नहीं लौटेंगे, जिसका अर्थ है कि आप एल्गोरिथ्म की जटिलता से समझौता किए बिना केवल बाएं किनारों के लिए एलसीपी कर सकते हैं।

LCP प्रीप्रोसेसिंग

जैसा कि आपको याद है, प्रभावी विकल्प खोज के लिए हमें प्रत्यय के कुछ संयोजनों के लिए पूर्व-गणना किए गए lcp की आवश्यकता थी। उन्हें कैसे प्राप्त किया जाए, यह समझाना आवश्यक है। आमतौर पर सेगमेंट पर न्यूनतम खोजने की समस्या के लिए तरीके नीचे आते हैं - आरएमक्यू, इसलिए एल्गोरिथ्म की एल्गोरिथ्म जटिलता मोटे तौर पर इस वजह से है कि आप आरएमक्यू समस्या को हल करने में कितने कुशल हैं। कम या ज्यादा सरल एल्गोरिथ्म में प्रीप्रोसेसिंग पर O (NlogN) और अनुरोध पर O (1) होगा। यही है, यदि आप ओ (NlogN) में एक प्रत्यय सरणी के निर्माण का उपयोग करते हैं, तो इसका उपयोग करना काफी संभव है। बेशक, यदि आप रैखिक समय में एक प्रत्यय सरणी का निर्माण करना चाहते हैं, तो आपको निरंतर प्रश्नों के साथ रैखिक समय के लिए RMQ प्रीप्रोसेसिंग एल्गोरिदम का उपयोग करना होगा।

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

एक lcp सरणी बनाना काफी सरल है। बेशक, प्रत्यय सरणी से गुजरना और पड़ोसी तत्वों के एलसीपी की गणना करना काम नहीं करेगा - यह ओ (एन ² ) है। लेकिन अगर आप सही क्रम में सरणी से गुजरते हैं, तो आप गणना के लिए पिछले चरण से जानकारी का उपयोग कर सकते हैं। अर्थात्, यदि आप मूल पंक्ति में दिखाई देने वाले प्रत्ययों के माध्यम से क्रमबद्ध करते हैं, तो प्रत्येक चरण पर पिछले चरण की तुलना में lcp 1 से अधिक नहीं घट सकता है, अर्थात यह अधिक हो सकता है, यह परिवर्तित नहीं हो सकता है, लेकिन यदि यह बन जाता है कम तो केवल 1. यह निम्नलिखित कारण से होता है। यदि आपको पता है कि lcp ( A [i ..], A [j ..] = l है, तो पहले वर्ण को स्पष्ट रूप से छोड़ने से यह एक से कम हो जाता है: lcp ( A [i + 1 ..], A [j +1 ..]) = एल -1। बेशक, अगर i-th और j-th प्रत्यय समीपस्थ रूप से आसन्न हो गए हैं, तो यह गारंटी नहीं देता है कि i + 1st और j + 1st आसन्न होंगे - दूसरों के बीच संभवतः सबसे अधिक पच्चर होगा। लेकिन, जैसा कि हम पहले ही पता लगा चुके हैं, उनके बीच का lcp उनके बीच के पूरे खंड पर न्यूनतम lcp है, जिसका अर्थ है कि i + 1th प्रत्यय और lexicographically के बीच lcp का पालन करना l-1 से कम नहीं है।

#	प्रत्यय	कदम	LCP
1	मैं	10	1
2	ippi	7	1
3	issippi	4	4
4	ississippi	2	0
5	मिसीसिपी	1	0
6	अनुकरणीय	9	1
7	ppi	8	0
8	Sippi	6	2
9	sissippi	3	1
10	ssippi	5	3
11	ssissippi	छोड़

यह आपको सभी वर्णों को दंडात्मक (एल -1) तक छोड़ने की अनुमति देता है, क्योंकि हम सुनिश्चित हैं कि वे समान हैं, और केवल एल-वें चरित्र और आगे की तुलना करें। इसका मतलब यह है कि हम जो भी चेक करते हैं, वे या तो वर्तमान lcp को बढ़ाते हैं या हमें अगले पुनरावृत्ति पर जाने के लिए मजबूर करते हैं। इस प्रकार, शाब्दिक रूप से पिछले एक को छोड़कर सभी प्रत्ययों को पारित करने (इसे छोड़ दिया जाना चाहिए), हमें रैखिक समय ओ (एन) में एक एलसीपी सरणी मिलती है।

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

मैंने RMQ को हल करने के तरीके के बारे में नहीं लिखा - हे (NlogN) के लिए एक सरल संस्करण के बारे में Habré पर पहले से ही एक अच्छा लेख था, और, मुझे आशा है, एक निरंतरता होगी जिसमें वे O (N - Farah-Colton एल्गोरिथ्म ) के लिए एक कट्टर संस्करण के बारे में लिखते हैं। शराबी ।

एक प्रत्यय सरणी का निर्माण

महान, यहां हम जानते हैं कि प्रत्यय सरणी कैसे लागू करें, लेकिन यह कहां से आएगा? जाहिर है, इसे प्रत्यक्ष तरीके से बनाना, प्रत्ययों को छांटना, एक लंबा व्यवसाय है - O (N ² logN), जहाँ = | ए | ऐसे कई एल्गोरिदम हैं जो O (NlogN) के लिए काम करते हैं, O (Nlog) के लिए काम करने वाले लोग हैं। वे ओ (एन) बहुत भ्रमित हैं (उदाहरण के लिए, पहले एक प्रत्यय पेड़ का निर्माण, और फिर उसमें से पहले से ही एक प्रत्यय सरणी एकत्र करते हैं)। यदि किसी विशेष कार्य में अधिकतम दक्षता इतनी महत्वपूर्ण नहीं है, तो आपको कोड की समझ के बारे में सोचना चाहिए और NlogN विकल्प पर रुकना चाहिए। अगला, हम इन श्रेणियों में से एक रनिंग एल्गोरिदम का उपयोग करेंगे।

प्रति हे (NlogN)

याद रखें कि बिटवाइज़ छँटाई कैसे काम करती है: पहले हम निचले क्रम के आधार पर गिनती करके तत्वों को बाल्टी में वितरित करते हैं, फिर अगले बिट के साथ भी ऐसा ही करते हैं, आदि। यहां हम एक समान तरीके से कार्य करेंगे, लेकिन फिर भी थोड़ा अलग ढंग से - यदि हम सीधे प्रत्यय के आधार पर बिटवाइज़ सॉर्टिंग लागू करते हैं, तो हमें ओ (एन ² ) मिलता है।

मान लीजिए कि कुछ कदम पर हमने एच पहले वर्णों के अनुसार छांटे गए (या बाल्टी में व्यवस्थित किए गए) पंक्तियाँ। हम लाइनों के इन हिस्सों को उनके बास्केट की संख्या के साथ संख्या दे सकते हैं। लेकिन प्रत्येक प्रत्यय S [ i ] = A [ i .. ] न केवल सरणी के एक तत्व के रूप में पाया जाता है, बल्कि सरणी के अन्य तत्वों के भाग के रूप में भी पाया जाता है, विशेष रूप से प्रत्यय S [ iH ] की स्थिति H के स्थानापन्न के रूप में (स्पष्टता के लिए अंत में सीमा प्रभाव छोड़ना) तार - अंत तक प्रहरी की वांछित संख्या लिखकर उन्हें दरकिनार किया जा सकता है)। अर्थात्, टोकरी संख्याओं के साथ पहले एच प्रत्यय वर्णों की संख्या होती है, हम स्वचालित रूप से दूसरे एच वर्णों को भी संख्या देते हैं। फिर हमें एक जोड़ी संख्या मिलती है जिसमें टोकरी संख्या (कुछ कदम की) होती है। इन जोड़ो को बिटवाइज़ सॉर्ट करके, हम 2H पहले अक्षर द्वारा बास्केट में क्रमाई गई पंक्तियों के लिए O (N) प्राप्त करते हैं। इस प्रकार, प्रत्येक चरण पर संसाधित वर्णों की संख्या दोगुनी हो जाएगी। यह O (logN) चरणों और O (NlogN) एल्गोरिथ्म की समग्र जटिलता देता है।

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

प्रति हे (N)

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

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

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

उदाहरण के लिए, ए = "मिसिसिपी" से आप ट्रिगर्स {मिस, आईएस, एससीआई, ... पीपीआई, पी $ $, आई $ डब्ल्यूओ}, और लेक्सिकोग्राफिक ऑर्डर {आई $ डब्ल्यूओपी, आईपीएस, आइएस ... एससीआई} प्राप्त कर सकते हैं। हमने सेंटिनल द्वारा आवश्यकतानुसार लाइन को पूरक किया और उन्हें न्यूनतम वर्ण माना।

मूल पंक्ति:	मीटर	मैं	रों	रों	मैं	रों	रों	मैं	पी	पी	मैं
संख्यात्मक स्ट्रिंग:	2	1	4	4	1	4	4	1	3	3	1
trigrams:	गलत	iss	लघु उद्योग	सीस	iss	लघु उद्योग	घूंट	IPP	ppi	$ पी	मैं $ $
ट्रिगर नंबर:	4	3	9	8	3	9	7	2	6	5	1

इस बिंदु पर, यह पता चल सकता है कि पंक्ति के सभी त्रिकोण अलग-अलग हैं। इसे शुरुआती टर्मिनल स्थिति के रूप में इस्तेमाल किया जा सकता है, क्योंकि यदि ट्रिगर्स अलग-अलग हैं, तो उनका लेक्सिकोग्राफिक ऑर्डर प्रत्ययों के लेक्सिकोग्राफिक ऑर्डर को निर्धारित करता है (आप इस स्थिति का उपयोग नहीं कर सकते हैं, लेकिन बस जब तक उत्तर स्पष्ट नहीं हो जाता है तब तक लाइन कम करते रहें)। हम तीन तरीकों से ट्रिग्राम के रूप में प्रारंभिक स्ट्रिंग का प्रतिनिधित्व कर सकते हैं: स्ट्रिंग को ट्रिग्राम में तोड़ना, पहले चरित्र के बिना स्ट्रिंग और पहले दो वर्णों के बिना स्ट्रिंग। तार ₀ , T ₁ और T _{2 के} इन अभ्यावेदन को बुलाओ। उनमें से प्रत्येक मूल से तीन गुना छोटा है। यदि हम स्थिति को शून्य से गिनते हैं, तो इन अभ्यावेदन को I i 3 = 0, i mod 3 = 1 और i mod 3 = 2 के पदों में प्रत्ययों के समूह के अनुरूप कहा जा सकता है।

T ₀ :	mis	sis	sip	pi$
	4	8	7	5
T ₁ :	iss	iss	ipp	i$$
	3	3	2	1
T ₂ :	ssi	ssi	ppi
	9	9	6

इसके बाद, एक फेंट कानों के साथ बनाया गया है, जिसका अर्थ बाद में स्पष्ट होगा: हम इन तीन लाइनों में से दो लेते हैं, समवर्ती के लिए, टी ₁ और टी ₂ , ट्रिगर्स के रूप में प्रस्तुत किए गए, समवर्ती और एक पुनरावर्ती कॉल में एक ही एल्गोरिथ्म को पास करते हैं। जाहिर है, संचरित स्ट्रिंग की लंबाई मूल से एक तिहाई कम है। एल्गोरिथ्म से बाहर निकलने पर, हम एक प्रत्यय सरणी (या, समकक्ष, रैंक की एक सरणी) की अपेक्षा करते हैं। एक संख्या रेखा पर त्रिकोण से वापस जाने पर, हमें समूह 1 और 2 के प्रत्ययों के बीच के शाब्दिक आदेश के बारे में जानकारी मिलती है।

समूह 0 के प्रत्यय को एक वर्ण और समूह 1 के प्रत्यय या दो वर्णों के समूह के रूप में और समूह 2 के प्रत्यय के रूप में दर्शाया जा सकता है: A [ 3k ..] = (A [3k], A [3k + 1 ..]) = (A [3k], A [3k + 1], A[3k + 2 ..])। समान अभिव्यक्तियों को प्रत्ययों के अन्य समूहों को पड़ोसी लोगों में अनुवाद करने के लिए लिखा जा सकता है। हम एक प्रतीक के जोड़े के रूप में टाइप 0 प्रत्यय का प्रतिनिधित्व करते हैं और एक प्रकार 1 प्रत्यय (अधिक सटीक, टाइप 1 प्रत्यय की रैंक, प्रत्यय हमारे लिए दिलचस्प नहीं है), जिसके बाद हम उन्हें बिटवाइज़ सॉर्ट करके सॉर्ट करते हैं।

इस स्तर पर, हमारे पास टाइप 1 और 2 के परस्पर सॉर्ट किए गए प्रत्ययों के रूप में एक पुनरावर्ती फ़ंक्शन कॉल का परिणाम है, और टाइप 0. के छंटनी प्रत्यय हैं। हमें सॉर्ट किए गए सरणियों के सामान्य मर्ज का उपयोग करके उन्हें मर्ज करने की आवश्यकता है, लेकिन हमें टाइप 0 प्रत्ययों के साथ प्रभावी रूप से तुलना करने में सक्षम होने की आवश्यकता है। 1 और 2. टाइप 1 प्रत्यय के प्रकार 1 के साथ तुलना करने के लिए, आपको टाइप 0 प्रत्यय को टाइप 1 में बदलने की आवश्यकता है, और टाइप 1 के लिए टाइप 2: (ए [3 एल], ए [3 एल + 1 ..] वीएस (ए) [३ मी + १], ए[३ मी + २] ..)। इन दो जोड़ों की तुलना करना सरल है: या तो पहला चरित्र क्रम निर्धारित करता है, या यदि यह समान है, तो यह आदेश समूह 1 और 2 के प्रत्ययों के क्रम को निर्धारित करता है, जिसे हम इस एल्गोरिथम के पुनरावर्ती कॉल के परिणामों से जानते हैं। प्रकार 0 और 2 के प्रत्यय की तुलना करने के लिए, श्रृंखला थोड़ी बड़ी है, लेकिन सार समान है: (ए [3 एल], ए [3 एल + 1], ए [3 एल + 2 ..]) वीएस (ए [3 एम + 2], ए [3] (m + 1)], A [3 (m + 1) +1 ..])।

पहली नज़र में, यह स्पष्ट नहीं है कि यह सब हमें रैखिक जटिलता क्यों देनी चाहिए। पहले, हम पुनरावर्ती कॉल को छोड़कर सभी चीजों से निपटेंगे। सुपरस्क्रिप्ट की बिटवाइज़ छँटाई, प्रत्यय को चिह्नित करना सभी O (N) हैं, समूह 0 के प्रत्ययों की बिटवाइज़ सॉर्टिंग और सॉर्ट किए गए सरणियों का भी O (N) है। अब एक पुनरावर्ती कॉल - हम एल्गोरिथ्म को मूल स्ट्रिंग लंबाई के 2/3 कहते हैं, इसलिए एल्गोरिथ्म की जटिलता टी (एन) = टी (2 एन / 3) + ओ (एन) है। यदि हम इस अभिव्यक्ति को स्वयं में प्रतिस्थापित करके चित्रित करते हैं, तो हमें 2/3 के गुणांक के साथ ज्यामितीय प्रगति का योग मिलता है, और इसलिए O (N) को सीमित किया जाता है। परिणामी जटिलता इस प्रकार हे (एन) है।

निष्कर्ष

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

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

प्रत्यय सरणी - प्रत्यय पेड़ के लिए एक सुविधाजनक प्रतिस्थापन