सवाल
एक स्ट्रिंग s दिए जाने पर, ऑनलाइन एक सफिक्स ऑटोमेटन (SAM) बनाएं। extend(c) को लागू करें, len, link, ट्रांज़िशन और endpos की व्याख्या करें, और इस संरचना का उपयोग डिस्टिंक्ट सबस्ट्रिंग्स की गिनती करने, पैटर्न ऑकरेंस की गणना करने, या लॉन्गेस्ट कॉमन सबस्ट्रिंग खोजने के लिए करें। बताएं कि स्टेट्स की संख्या O(n) क्यों होती है और क्लोन की आवश्यकता कब होती है।
इंटरव्यूअर क्या जांच रहा है
- क्या आप किसी स्टेट को एक साधारण ट्राई (trie) नोड के बजाय एक
endposसमतुल्यता वर्ग के रूप में वर्णित कर सकते हैं। - क्या आप निर्माण के दौरान डायरेक्ट-लिंक, रूट-लिंक और क्लोन शाखाओं में अंतर कर पाते हैं।
- क्या आप
len[link[v]] < len[v], डिटरमिनिस्टिक ट्रांज़िशन और सफिक्स-लिंक ट्री इनवेरिएंट को बनाए रखते हैं। - क्या आप संरचनात्मक इनवेरिएंट को क्वेरी और जटिलता परिणामों में बदल सकते हैं।
मॉडल उत्तर
एक SAM न्यूनतम आंशिक DFA है जो स्रोत स्ट्रिंग के प्रत्येक सबस्ट्रिंग को पहचानता है। स्टेट v अधिकतम दर्शाई गई लंबाई len[v] को संग्रहीत करता है; link[v] किसी अन्य समतुल्यता वर्ग के सबसे लंबे सफिक्स की ओर इंगित करता है। स्टेट क्रमिक अंतराल (len[link[v]], len[v]] का प्रतिनिधित्व करता है, इसलिए एक स्टेट कई सबस्ट्रिंग लंबाइयों के लिए हो सकता है।
जब कोई कैरेक्टर जोड़ा जाता है, तो cur बनाएं और अनुपलब्ध ट्रांज़िशन जोड़ते हुए सफिक्स लिंक्स को वॉक करें। यदि कोई मौजूदा लक्ष्य q, len[p]+1 == len[q] को संतुष्ट करता है, तो cur को सीधे q से लिंक करें। अन्यथा q को len = len[p]+1 वाले क्लोन में कॉपी करें, सफिक्स-लिंक पाथ पर प्रासंगिक ट्रांज़िशन को पुनर्निर्देशित करें, और link[q] व link[cur] दोनों को क्लोन की ओर पॉइंट करें। क्लोन क्रमिक-लंबाई इनवेरिएंट को पुनर्स्थापित करता है।
प्रत्येक गैर-रूट स्टेट len[v] - len[link[v]] डिस्टिंक्ट सबस्ट्रिंग्स का योगदान देता है। ऑकरेंस की गणना करने के लिए, स्रोत प्रीफिक्स के अनुरूप स्टेट्स के लिए एक इनिशियलाइज़ करें, फिर घटते len क्रम में सफिक्स लिंक्स पर काउंट्स को प्रोपेगेट करें।
कार्यान्वयन का संक्षिप्त विवरण
नीचे दिया गया छद्म-कोड निर्माण दिखाता है; ट्रांज़िशन हैश मैप या ऑर्डर्ड मैप का उपयोग कर सकते हैं।
extend(c):
cur = new state
len[cur] = len[last] + 1
p = last
while p != -1 and c not in next[p]:
next[p][c] = cur
p = link[p]
if p == -1:
link[cur] = root
else:
q = next[p][c]
if len[p] + 1 == len[q]:
link[cur] = q
else:
clone = copy(q)
len[clone] = len[p] + 1
while p != -1 and next[p][c] == q:
next[p][c] = clone
p = link[p]
link[q] = link[cur] = clone
last = curडिस्टिंक्ट-सबस्ट्रिंग गिनती के लिए गैर-रूट स्टेट्स पर len[v] - len[link[v]] का योग करें। ऑकरेंस गिनती के लिए, पैटर्न स्टेट तक ट्रांज़िशन का अनुसरण करें और घटती-लंबाई क्रम में प्रोपेगेट किए गए काउंट को पढ़ें।
सामान्य गलतियाँ
- SAM को सभी
endposवर्गों के संपीड़न के बजाय केवल सफिक्स स्वीकार करने वाले ट्राई के रूप में मानना। - क्लोन के ट्रांज़िशन को कॉपी करना लेकिन उसके लिंक्स को असंगत छोड़ देना, जो बाद के लंबाई अंतरालों को बाधित करता है।
- बहुत कम ट्रांज़िशन को पुनर्निर्देशित करना क्योंकि सफिक्स-लिंक वॉक उस पहले स्टेट से पहले रुक जाता है जो अब
qकी ओर इंगित नहीं करता है। - प्रत्येक क्लोन को स्रोत-प्रीफिक्स ऑकरेंस के रूप में गिनना, जिससे सभी ऑकरेंस काउंट्स बढ़ जाते हैं।
- इसके मेमोरी और एन्कोडिंग मान्यताओं को बताए बिना बड़े वर्णमाला के लिए एक निश्चित ट्रांज़िशन ऐरे का उपयोग करना।
जटिलता समझौता (Complexity trade-offs)
एक निश्चित वर्णमाला या हैश किए गए ट्रांज़िशन के साथ, निर्माण में O(n) समय और स्थान लगता है, जिसमें अधिकतम लगभग 2n-1 स्टेट्स होते हैं। ऑर्डर्ड ट्रांज़िशन मैप वर्णमाला संचालन से संबंधित एक कारक जोड़ते हैं। SAM एक निश्चित टेक्स्ट पर कई सबस्ट्रिंग प्रश्नों के लिए बहुत उपयुक्त है; लेक्सिकोग्राफ़िक ट्रैवर्सल, LCP कार्य और कैश लोकैलिटी के लिए सफिक्स ऐरे को नियंत्रित करना आसान हो सकता है।
लीनियर बाउंड ऑनलाइन अपेंड्स मानता है। बीच में सम्मिलित या हटाना, या दोनों सिरों को अपडेट करना, एक अलग संरचना की आवश्यकता होती है; extend को उसके इनवेरिएंट को बनाए रखते हुए आसानी से पुन: उपयोग नहीं किया जा सकता है।
खाली स्ट्रिंग, एक कैरेक्टर, दोहराए गए कैरेक्टर और क्लोन को ट्रिगर करने वाले इनपुट जैसे abbb से शुरुआत करें। फिर डिस्टिंक्ट-सबस्ट्रिंग और ऑकरेंस काउंट्स के लिए यादृच्छिक स्ट्रिंग्स की तुलना ब्रूट-फ़ोर्स सेट से करें। लॉन्गेस्ट कॉमन सबस्ट्रिंग के लिए, दूसरी स्ट्रिंग को SAM के माध्यम से स्ट्रीम करें और बेमेल होने पर सफिक्स लिंक्स का अनुसरण करें।
संदर्भ
- CP-algorithms के SAM नोट्स: स्टेट अंतराल, क्लोन निर्माण और क्वेरी सूत्र।
- Blumer et al. का सबसे छोटा-सबस्ट्रिंग-ऑटोमेटन पेपर: सैद्धांतिक स्टेट और ट्रांज़िशन सीमाएं।
- Carnegie Mellon स्ट्रिंग-एल्गोरिदम नोट्स: सफिक्स ऐरे और सफिक्स ऑटोमेटा कब बेहतर होते हैं।
फॉलो-अप प्रश्न
प्रत्येक स्टेट एक क्रमिक लंबाई अंतराल का प्रतिनिधित्व क्यों करता है?
एक endpos वर्ग की सबस्ट्रिंग लंबाइयाँ बिना अंतराल का क्रम बनाती हैं। सफिक्स लिंक्स सबसे लंबे प्रॉपर सफिक्स वाले सीमा वर्ग की पहचान करते हैं, इसलिए अंतराल बिल्कुल (len[link[v]], len[v]] होता है।
क्लोन की आवश्यकता कब होती है?
यदि किसी मौजूदा लक्ष्य q में len[q] > len[p]+1 है, तो यह दो गैर-क्रमिक लंबाई श्रेणियों को ले जा रहा है। इसके ट्रांज़िशन की नकल करना और एक क्लोन को अलग करना इनवेरिएंट को पुनर्स्थापित करता है।
अंतराल योग डिस्टिंक्ट सबस्ट्रिंग्स की गणना क्यों करता है?
स्टेट अंतराल अलग-अलग (disjoint) होते हैं, और प्रत्येक दर्शाई गई लंबाई एक डिस्टिंक्ट सबस्ट्रिंग से मेल खाती है। इसलिए प्रत्येक अंतराल के आकार का योग प्रत्येक गैर-खाली डिस्टिंक्ट सबस्ट्रिंग को एक बार गिनता है।
SAM और Aho–Corasick की तुलना कैसे की जानी चाहिए?
SAM एक टेक्स्ट के सभी सबस्ट्रिंग्स को इंडेक्स करता है और समग्र आंकड़ों का समर्थन करता है। Aho–Corasick बैच मिलान के लिए पैटर्न के एक ज्ञात सेट को इंडेक्स करता है। टेक्स्ट या पैटर्न सेट का निश्चित होना आमतौर पर बेहतर निर्माण का निर्धारण करता है।
आप लॉन्गेस्ट कॉमन सबस्ट्रिंग कैसे ढूंढते हैं?
S के लिए एक SAM बनाएं, फिर T को स्कैन करें। वर्तमान मिलान लंबाई को ट्रैक करते हुए ट्रांज़िशन का पालन करें; बेमेल होने पर, सफिक्स लिंक्स का पालन करें और पुनः प्रयास करें। देखी गई अधिकतम लंबाई को बनाए रखें।