💻 computer science

Ranked MSO-enumeration over compressed words

यह शोध पत्र व्याकरण-संकुचित (grammar-compressed) स्ट्रिंग्स पर रैंक किए गए MSO-क्वेरी एन्यूमरेशन के लिए पहले एल्गोरिदम को प्रस्तुत करता है, जो संकुचित सेटिंग के अनुकूल फैक्टरिज़ेशन ट्री (factorization trees) को अपनाकर रैखिक प्रीप्रोसेसिंग और निरंतर विलंब (constant delay) प्राप्त करता है, जो तत्पश्चात संकुचित इनपुट पर पॉलीरेगुलर फलनों (polyregular functions) के कुशल एन्यूमरेशन को सक्षम बनाता है।

मूल लेखक: Markus Lohrey

प्रकाशित 2026-06-03

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Markus Lohrey

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आपके पास किताबों का एक विशाल पुस्तकालय है, लेकिन आप हर एक पन्ने को स्टोर करने के बजाय, केवल एक छोटा सा निर्देश मैनुअल (एक "रेसिपी") रखते हैं जो आपको पूरा बुक पुनर्गठित करने का तरीका बताता है। यह ग्रामर कम्प्रेशन (grammar compression) डेटा के लिए क्या करता है: यह एक बहुत बड़े टेक्स्ट स्ट्रिंग को एक बहुत छोटे, संकुचित (compressed) प्रारूप में स्टोर करता है जिसे स्ट्रेट-लाइन प्रोग्राम (SLP) कहा जाता है। SLP को "Hello" शब्द को 100 बार दोहराने, फिर उसमें "World" जोड़ने जैसे नेस्टेड निर्देशों के रूप में सोचें।

यह समस्या यह पेपर हल करता है: आप इस संकुचित किताब के अंदर विशिष्ट उत्तरों को बिना उसे पूरी तरह से अनपैक किए कैसे ढूंढ सकते हैं?

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

मुख्य उपलब्धि: "मैजिक इंडेक्स" (The "Magic Index")

लेखकों, मार्कस लोहरी (Markus Lohrey) ने इन संकुचित किताबों को खोजने का एक नया तरीका बनाया है। यहाँ उनकी सफलता का विवरण दिया गया है:

सेटअप (The Setup): आपके पास एक संकुचित स्ट्रिंग (रेसिपी) है और एक विशिष्ट प्रश्न (क्वेरी) है जो MSO (मोनैडिक सेकंड-ऑर्डर लॉजिक) नामक एक शक्तिशाली लॉजिक भाषा में लिखा गया है। यह भाषा एक सटीक सर्च इंजन क्वेरी की तरह है जो कह सकती है जैसे "तीसरे अक्षर को खोजें जो पांचवें अक्षर से अलग है।"
लक्ष्य (The Goal): आप सभी उत्तरों (टुपल्स या स्थितियों) को एक-एक करके सूचीबद्ध करना चाहते हैं।
"रैंक्ड" ट्विस्ट (The "Ranked" Twist): अतीत में, कंप्यूटर उत्तरों को एक रैंडम, अराजक क्रम में देते थे। यह पेपर "रैंक्ड एन्यूमरेशन" (Ranked Enumeration) पेश करता है। इसका अर्थ है कि कंप्यूटर उत्तरों को एक विशिष्ट, अनुमानित क्रम में सूचीबद्ध करता है (जैसे वर्णानुक्रम या संख्यात्मक क्रम) जिसे आप पहले से परिभाषित करते हैं।
परिणाम (The Result): लेखक दिखाते हैं कि आप संकुचित रेसिपी को लीनियर टाइम (linear time) में तैयार कर सकते हैं (बहुत तेज़, रेसिपी के आकार के अनुपात में, न कि उस विशाल किताब के आकार के अनुपात में जिसे वह दर्शाती है)। एक बार तैयार होने के बाद, कंप्यूटर उत्तरों को कॉन्स्टेंट डिले (constant delay) के साथ एक-एक करके निकाल सकता है।
- उपमा: कल्पना कीजिए कि एक लाइब्रेरियन एक छोटे से इंडेक्स कार्ड को व्यवस्थित करने में 5 मिनट बिताता है (प्रीप्रोसेसिंग)। इसके बाद, वे आपको अगला सही बुक पेज तुरंत दे सकते हैं, चाहे किताब कितनी भी लंबी क्यों न हो। आपको पेज 1 और पेज 2 देने के बीच में कोई प्रतीक्षा समय नहीं मिलता है।

उन्होंने यह कैसे किया: "फैक्टराइजेशन ट्री" (The "Factorization Tree")

इसे हासिल करने के लिए, लेखकों ने एक चतुर उपकरण का उपयोग किया जिसे फैक्टराइजेशन ट्री (Factorization Tree) कहा जाता है।

रूपक (The Metaphor): कल्पना कीजिए कि आपके पास अक्षरों की एक लंबी स्ट्रिंग है। फैक्टराइजेशन ट्री उस स्ट्रिंग के लिए एक फैमिली ट्री की तरह है। यह स्ट्रिंग को छोटे टुकड़ों में तोड़ देता है।
नियम (The Rule): यदि कोई टुकड़ा कई छोटे टुकड़ों से बना है जो सभी एक ही पैटर्न को "दोहराते" हैं (गणितीय रूप से, वे "इडम्पोटेंट" हैं), तो ट्री उन्हें एक विशेष समूह के रूप में मानता है।
नवाचार (The Innovation): लेखकों ने यह पता लगाया कि कैसे इस फैमिली ट्री को सीधे संकुचित रेसिपी (SLP) से बनाया जाए, बिना कभी पूर्ण स्ट्रिंग को लिखे। वे इसे "साइमन SLP" (Simon SLP) कहते हैं।
ट्रैवर्सल (The Traversal): उन्होंने इस संकुचित पेड़ के माध्यम से तुरंत "चलने" (walk) का एक तरीका भी विकसित किया। कल्पना कीजिए कि आप एक भूलभुलैया में चल रहे हैं जहाँ दीवारें निर्देश हैं। आमतौर पर, आपको यह जानने के लिए कि कहाँ मुड़ना है, हर निर्देश को पढ़ना पड़ता है। उनका तरीका आपको तुरंत एक निर्देश से दूसरे निर्देश पर कूदने की अनुमति देता है, यह जानते हुए कि आप अंतिम, विशाल स्ट्रिंग में कहाँ हैं।

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

पॉलीरेगुलर फंक्शन्स (Polyregular Functions): पेपर एक विशिष्ट प्रकार के डेटा ट्रांसफॉर्मेशन का उल्लेख करता है जिसे "पॉलीरेगुलर फंक्शन" (जैसे एक जटिल टेक्स्ट एडिटर मैक्रो) कहा जाता है। पहले, यदि आपके पास एक संकुचित टेक्स्ट होता और आप इस मैक्रो को लागू करना चाहते, तो आप परिणामों को क्रम में सूचीबद्ध नहीं कर सकते थे। अब, आप ऐसा कर सकते हैं।
संकुचित डेटा के लिए पहली बार (First Time for Compressed Data): यह पहली बार है जब किसी ने संकुचित डेटा पर रैंक्ड (क्रमबद्ध) प्रश्नों के लिए यह "कॉन्स्टेंट डिले" गति प्राप्त की है। इससे पहले, या तो आपको उत्तरों के बीच अधिक प्रतीक्षा करनी पड़ती थी या उत्तरों के रैंडम क्रम में आने का सामना करना पड़ता था।

उन्होंने क्या नहीं किया (सीमाएं)

यह पेपर बहुत विशिष्ट है कि यह क्या कवर करता है:

कोई सेट वेरिएबल्स नहीं (No Set Variables): उनके द्वारा हैंडल किए जाने वाले प्रश्न केवल विशिष्ट स्थितियों (जैसे "पांचवां अक्षर") को देखते हैं। वे अभी तक उन प्रश्नों को हैंडल नहीं करते जो "अक्षरों के सेट" (जैसे "ऐसे अक्षरों के समूह खोजें जो पैलिंड्रोम बनाते हैं") के बारे में पूछते हैं। यदि आप सेट के बारे में पूछते हैं, तो उत्तर इतने बड़े हो जाते हैं कि उन्हें तुरंत प्रिंट करना संभव नहीं है, और यह विधि अभी लागू नहीं होती है।
केवल स्ट्रिंग्स (Strings Only): यह टेक्स्ट (स्ट्रिंग्स) के लिए काम करता है। वे उल्लेख करते हैं कि इसे पेड़ों (जैसे XML फ़ाइलें) के लिए करना एक भविष्य का लक्ष्य है, लेकिन उन्होंने इसे अभी तक हल नहीं किया है।
कोई "वेट" सॉर्टिंग नहीं (No "Weight" Sorting): अन्य शोधकर्ता उत्तरों को "वेट" (जैसे महत्व स्कोर) के आधार पर सॉर्ट करते हैं। यह पेपर एक सख्त लॉजिकल ऑर्डर (जैसे डिक्शनरी ऑर्डर) द्वारा सॉर्ट करता है। वे नोट करते हैं कि इन दोनों विचारों को मिलाना अभी भी एक खुला प्रश्न है।

सारांश

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

तकनीकी सारांश: संकुचित शब्दों (Compressed Words) पर रैंक किया गया MSO-एन््युमरेशन

समस्या विवरण
यह शोध पत्र एक संकुचित प्रारूप में दिए गए स्ट्रिंग पर एक निश्चित मोनैडिक सेकंड-ऑर्डर (MSO) क्वेरी के उत्तरों को सूचीबद्ध (enumerate) करने की समस्या को संबोधित करता है। यहाँ इनपुट स्ट्रिंग $w$ को एक स्ट्रेट-लाइन प्रोग्राम (SLP) द्वारा दिया गया है, जो ठीक एक स्ट्रिंग उत्पन्न करने वाला कॉन्टेक्स्ट-फ्री ग्रामर है। लक्ष्य $w$ में उन स्थितियों (positions) के सभी टुपल्स $(a_1, \dots, a_k)$ की गणना करना है जो एक निश्चित MSO फॉर्मूला $\Phi(x_1, \dots, x_k)$ को संतुष्ट करते हैं।

इस कार्य की एक महत्वपूर्ण बाधा रैंक किया गया एन्नुमरेशन (ranked enumeration) है। मानक एन्नुमरेशन एल्गोरिदम के विपरीत, जहाँ आउटपुट का क्रम अस्पष्ट होता है, रैंक किए गए एन्नुमरेशन में आउटपुट टुपल्स को एक विशिष्ट, उपयोगकर्ता द्वारा परिभाषित क्रम में प्रिंट करना आवश्यक है, जो स्वयं MSO-परिभाषित (जैसे, स्थिति टुपल्स पर लेक्सिकोग्राफिक क्रम) होना चाहिए। ऐसे एल्गोरिदम के लिए दक्षता मीट्रिक रैखिक प्रीप्रोसेसिंग समय (SLP के आकार $|G|$ में रैखिक) और उसके बाद स्थिर विलंब (constant delay) (क्रमवार टुपल्स को आउटपुट करने के बीच का एक स्थिर अंतराल) है।

इस कार्य से पूर्व, अनकंप्रेस्ड स्ट्रिंग्स और ट्रीज़ के लिए MSO क्वेरी हेतु रैंक किए गए एन्नुमरेशन के बारे में ज्ञात था, लेकिन संकुचित डेटा के लिए कोई परिणाम मौजूद नहीं थे। इसके अतिरिक्त, संकुचित स्ट्रिंग्स के लिए मौजूदा एन्नुमरेशन परिणाम (जैसे, [29]) केवल आउटपुट-लीनियर विलंब प्राप्त करते थे और रैंक किए गए एन्नुमरेशन का समर्थन नहीं करते थे।

कार्यप्रणाली (Methodology)
समाधान तीन प्राथमिक तकनीकी घटकों को जोड़ता है:

फैक्टरइज़ेशन ट्रीज़ और साइमन SLP (Factorization Trees and Simon SLPs):
मुख्य संरचनात्मक उपकरण फैक्टरइज़ेशन ट्री है, जो एक परिमित मोनोइड (finite monoid) में एक मॉर्फिज्म के सापेक्ष एक शब्द का पार्स ट्री है, जहाँ $\ge 3$ बच्चों वाले नोड्स एक ही इडेम्पोटेंट तत्व (idempotent element) को मूल्यांकित करते हैं। साइमन का प्रमेय गारंटी देता है कि ऐसे ट्री की ऊँचाई मोनोइड के आकार पर निर्भर एक स्थिरांक (constant) द्वारा सीमित होती है।
यह शोध पत्र साइमन SLP (SSLP) की अवधारणा पेश करता है: एक ऐसा SLP जो शब्द के फैक्टरइज़ेशन ट्री के साथ संरचनात्मक रूप से संगत है। लेखक सिद्ध करते हैं (थ्योरम 3.1) कि किसी भी दिए गए SLP को रैखिक समय में एक समतुल्य SSLP में बदला जा सकता है। इस रूपांतरण में एक नॉन-डिटरमिनिस्टिक ट्रांसड्यूसर का निर्माण शामिल है जो फैक्टरइज़ेशन ट्री जनरेट करता है और फिर व्याकरण को पुनर्गठित करता है ताकि वह ट्री के पदानुक्रम को दर्शा सके, जिससे यह सुनिश्चित होता है कि SLP की "इडेम्पोटेंट-कॉन्ट्रैक्टेड डेप्थ" एक स्थिरांक ( $3|M|$ ) द्वारा सीमित है।
संकुचित स्ट्रिंग्स में निरंतर-समय नेविगेशन (Constant-Time Traversal in Compressed Strings):
संकुचित स्ट्रिंग में कुशलतापूर्वक नेविगेट करने के लिए, यह शोध पत्र दो-तरफा निरंतर-समय नेविगेशन के लिए [26] की तकनीकों का उपयोग और विस्तार करता है। लेखक संकुचित पथ (compressed paths) (SLP के DAG में लेफ्ट/राइट मूव्स का प्रतिनिधित्व करने वाले ट्रिपल्स के अनुक्रम) को परिभाषित करते हैं और एक डायनेमिक डेटा स्ट्रक्चर (एक बाइनरी ट्री $B$ ) बनाए रखते हैं जो "सक्रिय" पथों की एक निश्चित संख्या को संग्रहीत करता है।
महत्वपूर्ण रूप से, वे right और left प्रक्रियाओं को परिभाषित करते हैं जो, संकुचित प्रतिनिधित्व में एक पथ दिए जाने पर, उसके लेक्सिकोग्राफिक उत्तराधिकारी (successor) या पूर्ववर्ती (predecessor) की गणना निरंतर समय में करती हैं। इसमें नेविगेशन ट्री में किनारों (edges) को विभाजित करना और विशिष्ट भागों (e-parts) के भीतर "इडेम्पोटेंट-कॉन्ट्रैक्टेड" उप-पथों को प्रबंधित करना शामिल है।
MSO इंटरप्रिटेशन और उत्तराधिकारी गणना (MSO Interpretation and Successor Computation):
एन्नुमरेशन एल्गोरिदम को एक पॉलीरेगुलर फंक्शन (या अधिक सामान्य रूप से, एक MSO-स्ट्रिंग-टू-स्ट्रिंग इंटरप्रिटेशन) के इमेज की गणना करने के रूप में फ्रेम किया गया है। एल्गोरिदम क्रमिक रूप से स्थितियों के टुपल्स के "उत्तराधिकारी" (successor) की गणना करता है।
प्रमाण में MSO फॉर्मूला को नॉन-डונोमिस्टिक फाइनाइट ऑटोमेटा (NFA) में बदलना और एक परिमित मोनोइड $M$ प्राप्त करना शामिल है। फैक्टरइज़ेशन ट्री (या समकक्ष SSLP) के नोड्स के लिए मोनोइड तत्वों को प्रीकंप्यूट करके, एल्गोरिदम क्रमबद्ध अनुक्रम में अगली स्थिति को निरंतर समय में निर्धारित कर सकता है। यह वर्तमान स्थितियों के बीच के सेगमेंट्स के मोनोइड तत्वों का विश्लेषण करके और अगले वैध स्थान पर जाने के लिए फैक्टरइज़ेशन ट्री की संरचना का उपयोग करके स्थितियों के बीच संक्रमण को संभालता है, जिससे स्ट्रिंग को डिकंप्रेस करने की आवश्यकता नहीं होती।

प्रमुख योगदान और परिणाम

मुख्य प्रमेय (थ्योरम 5.1): $k$ फ्री फर्स्ट-ऑर्डर वेरिएबल्स वाले एक निश्चित MSO फॉर्मूला और $k$ -टुपल्स पर एक MSO-परिभाषित लीनियर ऑर्डर के लिए, SLP-संकुचित स्ट्रिंग पर क्वेरी उत्तरों को रैखिक प्रीप्रोसेसिंग समय ( $O(|G|)$ ) और स्थिर विलंब के साथ सूचीबद्ध किया जा सकता है। यह संकुचित डेटा पर रैंक किए गए एन्नुमरेशन के लिए इस प्रकार का पहला परिणाम है।
पॉलीरेगुलर फंक्शन्स के लिए कोरोलरी (कोरोलरी 5.3): यह परिणाम पॉलीरेगुलर स्ट्रिंग-टू-स्ट्रिंग फंक्शन्स पर सामान्यीकृत होता है। एक निश्चित पॉलीरेगुलर फंक्शन $f$ और एक SLP $G$ जो $w$ उत्पन्न करता है, के लिए $f(w)$ के प्रतीकों को रैखिक प्रीप्रोसेसिंग और स्थिर विलंब के साथ बाएं से दाएं सूचीबद्ध किया जा सकता है। यह बोजानज़िक [8] के पिछले परिणाम (जिसने अनकंप्रेस्ड इनपुट माना था) को संकुचित सेटिंग में विस्तारित करता है, बावजूद इसके कि पॉलीरेगुलर फंक्शन सामान्यतः कंप्रेशन साइज को सुरक्षित नहीं रखते हैं।
सक्सेसर-MSO के लिए कोरोलरी (कोरोलरी 5.5): यह परिणाम सक्सेसर-MSO स्ट्रिंग-टू-स्ट्रिंग इंटरप्रेशंस के व्यापक वर्ग के लिए भी मान्य है, जो पॉलीरेगुलर फंक्शन्स की तुलना में काफी बड़े हैं।
तकनीकी योगदान (साइमन SLPs): यह शोध पत्र स्थापित करता है कि प्रत्येक SLP को रैखिक समय में एक साइमन SLP में परिवर्तित किया जा सकता है। यह फैक्टरइज़ेशन ट्री को व्याकरण-संकुचित सेटिंग के लिए सुलभ बनाता है, जो एक स्वतंत्र महत्व का योगदान है।

महत्व और दावे

यह शोध पत्र दावा करता है कि यह संकुचित डेटा पर रैंक किए गए एन्नुमरेशन की दिशा में "पहला कदम" उठाता है। यह उस विशिष्ट अंतर को संबोधित करता है जहाँ पिछले संकुचित एन्नुमरेशन एल्गोरिदम (जैसे, [29]) आउटपुट क्रम को नियंत्रित नहीं कर सकते थे, और पिछले रैंक किए गए एन्नुमरेशन एल्गोरिदम (जैसे, [2, 12, 19]) संकुचित इनपुट को हैंडल नहीं कर सकते थे।

लेखक इस बात पर जोर देते हैं कि उनका दृष्टिकोण फैक्टरइज़ेशन ट्री की विशिष्ट संरचना और SLPs पर निरंतर-समय नेविगेशन करने की क्षमता पर निर्भर करता है। वे अपनी सीमाओं को स्पष्ट रूप से नोट करते हैं:

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

संक्षेप में, यह शोध पत्र अत्यधिक संकुचित डेटा पर कुशल, क्रमबद्ध क्वेरी प्रोसेसिंग के लिए एक सैद्धांतिक आधार प्रदान करता है, और यह प्रदर्शित करता है कि यदि आउटपुट क्रम MSO-परिभाषित हो, तो SLPs पर MSO क्वेरीज़ के लिए "गोल्ड स्टैंडर्ड" (रैखिक प्रीप्रोसेसिंग और स्थिर विलंब) प्राप्त करना संभव है।

मुख्य उपलब्धि: "मैजिक इंडेक्स" (The "Magic Index")

उन्होंने यह कैसे किया: "फैक्टराइजेशन ट्री" (The "Factorization Tree")

यह क्यों महत्वपूर्ण है (पेपर के अनुसार)

उन्होंने क्या नहीं किया (सीमाएं)

सारांश

इसी तरह के और पेपर