कोडिंग इंटरव्यू: सफिक्स ऐरे (Suffix Array) के साथ पैटर्न कैसे सर्च करें?

प्रॉम्प्ट और यह कब लागू होता है

एक सफिक्स ऐरे लेक्सिकोग्राफ़िकल (lexicographical) क्रम में सॉर्ट किए गए प्रत्येक सफिक्स के शुरुआती इंडेक्स को स्टोर करता है। जब किसी एक फ़िक्स्ड टेक्स्ट पर कई पैटर्न क्वेरी की जाती हैं, तो यह इंडेक्स शुरुआत से दोबारा स्कैन किए बिना मैच ढूंढ लेता है। Stanford CS166 उम्मीदवारों से searchFor को लागू करने, प्रत्येक मैच को वापस करने और आउटपुट साइज़ को ध्यान में रखने के लिए कहता है; यहाँ m पैटर्न की लंबाई है, n टेक्स्ट की लंबाई है, और z परिणामों की संख्या है।

इंटरव्यूअर क्या जांच रहा है

यह समझाना कि पैटर्न का मिलना एक ऐसा सफिक्स है जिसका प्रीफ़िक्स (prefix) पैटर्न के बराबर है।
केवल एक मैच पर रुकने के बजाय लोअर बाउंड (lower bounds) का उपयोग करके बाईं और दाईं सीमाओं को खोजना।
एकमुश्त निर्माण लागत (construction cost) को प्रति-क्वेरी लागत से अलग करना और आउटपुट के लिए O(z) चार्ज करना।
खाली पैटर्न, सेंटिनल्स, डुप्लिकेट सफिक्स और कैरेक्टर-तुलना लागत को संभालना।

पहले पूछे जाने वाले स्पष्टीकरण

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

30-सेकंड का उत्तर

"सफ़िक्स सॉर्ट किए गए होते हैं, इसलिए pattern से शुरू होने वाले सभी सफ़िक्स एक सन्निहित अंतराल (contiguous interval) बनाते हैं। मैं प्रीफ़िक्स द्वारा पैटर्न की तुलना text[sa[i]:] से करता हूँ, पैटर्न से छोटे न होने वाले पहले सफ़िक्स के लिए एक बाइनरी सर्च का उपयोग करता हूँ और उस प्रीफ़िक्स से सख्ती से बड़े पहले सफ़िक्स के लिए दूसरे बाइनरी सर्च का उपयोग करता हूँ। अंतराल में प्रत्येक sa मान एक मैच है, इसलिए रिपोर्टिंग लागत O(z) है और क्वेरी O(m log n + z) है। परिपाटी के अनुसार, एक खाली पैटर्न n+1 स्थितियाँ लौटाता है।"

चरण-दर-चरण समाधान

चरण 1: सफिक्स-ऐरे का अर्थ परिभाषित करें

banana के लिए, लेक्सिकोग्राफ़िकल क्रम में सफ़िक्स की शुरुआत [5, 3, 1, 0, 4, 2] हैं। ऐरे पूर्णांक शुरुआत (integer starts) को स्टोर करता है, न कि सफ़िक्स स्ट्रिंग्स की प्रतियों को। MIT के नोट्स ठीक इसी लेक्सिकोग्राफ़िकल इंडेक्स और बाइनरी-सर्च के उपयोग का वर्णन करते हैं।

चरण 2: मैचिंग को एक अंतराल में बदलें

ana से शुरू होने वाले सभी सफ़िक्स एक-दूसरे के आस-पास होते हैं, इसलिए उत्तर एक आधा-खुला अंतराल (half-open interval) [left, right) है। कंपैरेटर को तीन परिणामों की आवश्यकता होती है: सफ़िक्स प्रीफ़िक्स पैटर्न से छोटा है, बराबर है, या बड़ा है। समानता की स्थिति में भी हर घटना को कैप्चर करने के लिए बाईं और दाईं ओर सर्च करना जारी रखना चाहिए।

चरण 3: दो लोअर बाउंड लागू करें

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

चरण 4: जटिलता और निर्माण के विकल्प

प्रदान किए गए सफिक्स ऐरे के साथ, प्रत्येक तुलना में अधिकतम m कैरेक्टरों की जांच की जाती है और बाइनरी सर्च O(log n) तुलनाएं करता है, इसलिए क्वेरी O(m log n + z) है। Stanford स्पष्ट रूप से O(z) रिपोर्टिंग लागत को अलग करता है। एक बुनियादी निर्माण सफ़िक्स स्लाइस को सॉर्ट कर सकता है, लेकिन यह डेटा की प्रतिलिपि बनाता है और धीमा होता है; प्रोडक्शन को प्रीफ़िक्स डबलिंग, SA-IS, या एक जांची-परखी लाइब्रेरी का उपयोग करना चाहिए। MIT और Stanford की सामग्री सफिक्स ऐरे को फ़िक्स्ड-टेक्स्ट इंडेक्स के रूप में प्रस्तुत करती है जो सफिक्स ट्री की तुलना में पॉइंटर-भारी मेमोरी की बचत करते हैं।

निष्पादन योग्य Python कार्यान्वयन

python

def build_suffix_array(text):
    # Teaching build for verification, not a production complexity claim.
    return sorted(range(len(text)), key=lambda start: text[start:])


def compare_suffix_prefix(text, start, pattern):
    suffix = text[start:]
    prefix = suffix[:len(pattern)]
    if prefix < pattern:
        return -1
    if prefix > pattern:
        return 1
    if len(suffix) < len(pattern):
        return -1
    return 0


def search_with_suffix_array(text, suffix_array, pattern):
    if pattern == "":
        return list(range(len(text) + 1))

    def lower_bound(strict):
        lo, hi = 0, len(suffix_array)
        while lo < hi:
            mid = (lo + hi) // 2
            cmp = compare_suffix_prefix(text, suffix_array[mid], pattern)
            take_right = cmp < 0 or (strict and cmp == 0)
            if take_right:
                lo = mid + 1
            else:
                hi = mid
        return lo

    left = lower_bound(strict=False)
    right = lower_bound(strict=True)
    return sorted(suffix_array[left:right])

कोड निर्माण और क्वेरी को अलग करता है। अंतिम सॉर्ट टेक्स्ट क्रम में शुरुआत लौटाता है; यदि सफिक्स-ऐरे क्रम ही API अनुबंध है तो इसे छोड़ दें। खाली टेक्स्ट, खाली पैटर्न, कोई मैच नहीं, और बार-बार होने वाले मैच सीधे परीक्षण मामले (test cases) हैं।

एक उच्च-गुणवत्ता वाला नमूना उत्तर

"मैं पहले पुष्टि करता हूँ कि टेक्स्ट फ़िक्स्ड है और कई पैटर्न प्राप्त करता है, फिर प्रत्येक सफ़िक्स शुरुआत को लेक्सिकोग्राफ़िकल क्रम में स्टोर करता हूँ। चूंकि एक पैटर्न मैचिंग सफ़िक्स का एक सामान्य प्रीफ़िक्स होता है, इसलिए सभी उत्तर एक सन्निहित सीमा में आते हैं। दो लोअर बाउंड उस सीमा को ढूंढते हैं; तुलना केवल पैटर्न की लंबाई का निरीक्षण करती है और छोटे सफ़िक्स को कम मानती है। ऐरे दिए जाने पर, क्वेरी O(m log n + z) है, जहाँ z आउटपुट है। एक शैक्षणिक निर्माण सॉर्टिंग का उपयोग कर सकता है, लेकिन एक बड़े इंडेक्स के लिए एक परिभाषित कैरेक्टर-नॉर्मलाइज़ेशन नीति के साथ प्रीफ़िक्स डबलिंग, SA-IS, या एक जांची-परखी कार्यान्वयन की आवश्यकता होती है।"

सामान्य गलतियाँ

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

फॉलो-अप और मजबूत प्रतिक्रियाएं

आप एक लंबे पैटर्न के लिए बार-बार होने वाली कैरेक्टर तुलनाओं को कैसे कम करते हैं?

पड़ोसी सफ़िक्स के लिए LCP (Longest Common Prefix) जानकारी जोड़ें और बाइनरी सर्च के दौरान ज्ञात सामान्य प्रीफ़िक्स का पुनः उपयोग करें। यह O(m + log n) तक पहुँच सकता है, लेकिन इसके लिए अतिरिक्त LCP स्थिति और मजबूत इनवेरिएंट्स की आवश्यकता होती है; इसके बिना, ईमानदारी से O(m log n) बताएं।

क्या आप सफिक्स ऐरे का उपयोग करेंगे यदि टेक्स्ट अक्सर बदलता है?

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

आप कैसे परीक्षण करते हैं कि बाइनरी-सर्च सीमाएं सही हैं?

यादृच्छिक (random) छोटे टेक्स्ट और पैटर्न पर ब्रूट-फ़ोर्स स्कैन से तुलना करें। खाली पैटर्न, दोहराए गए कैरेक्टर, टेक्स्ट से लंबे पैटर्न, कोई मैच नहीं, और प्रत्येक स्थिति के मैच होने वाले मामलों को शामिल करें। पुष्टि (assert) करें कि सीमा से बाहर की पड़ोसी स्थितियाँ प्रीफ़िक्स प्रेडिकेट में विफल होती हैं।

सीधे KMP का उपयोग क्यों न करें?

एक पैटर्न और टेक्स्ट पर एक पास के लिए, KMP O(n+m) पर सरल है। एक सफिक्स ऐरे फ़िक्स्ड टेक्स्ट पर कई पैटर्न के लिए और दोहराए गए सबस्ट्रिंग, LCP, या BWT से जुड़े ऑफ़लाइन संचालन के लिए फ़ायदेमंद होता है।

कोडिंग इंटरव्यू: सफिक्स ऐरे (Suffix Array) के साथ पैटर्न कैसे सर्च करें?

प्रश्न