💬 NLP

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

यह शोध पत्र SETH और त्रिकोण पहचान (triangle detection) धारणाओं के तहत सशर्त निचली सीमाओं (conditional lower bounds) को सिद्ध करते हुए और 1-उपयोग बैकरेफरेंस (1-use backreferences) के लिए एक बेहतर $O(n \log^2 n)$ एल्गोरिदम प्रस्तुत करते हुए, बैकरेफरेंस के साथ रेगुलर एक्सप्रेशंस को मिलाने की सूक्ष्म-स्तरीय (fine-grained) कम्प्यूटेशनल जटिलता को स्थापित करता है।

मूल लेखक: Soh Kumabe, Yuya Uezato

प्रकाशित 2026-05-11

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

CC BY 4.0

मूल लेखक: Soh Kumabe, Yuya Uezato

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

यहाँ "On the Complexity of the Matching Problem of Regular Expressions with Backreferences" शोध पत्र का सरल भाषा में अनुवाद दिया गया है:

बड़ी तस्वीर: "रेगेक्स" (Regex) ट्रैफिक जाम

कल्पना कीजिए कि आप एक क्लब के सुरक्षा गार्ड (कंप्यूटर सिस्टम) हैं। आपके पास अंदर आने वालों के लिए नियमों की एक सूची (Regular Expression) है।

साधारण नियम: "केवल वे लोग जो लाल शर्ट पहने हैं।" इसे जाँचना आसान है। आप एक शर्ट देखते हैं, कहते हैं, "लाल? हाँ, अंदर आओ।" चाहे लाइन में 10 लोग हों या 10,000, इसमें उतना ही समय लगता है।
समस्या (ReDoS): कभी-कभी, हैकर्स लोगों की एक ऐसी विशेष कतार तैयार करते हैं जो गार्ड को बहुत अधिक अनावश्यक काम करने के लिए मजबूर कर देती है। एक व्यक्ति को जाँचकर आगे बढ़ने के बजाय, गार्ड व्यक्ति A को जाँचता है, फिर व्यक्ति B को, फिर वापस व्यक्ति A को, फिर व्यक्ति C को, फिर फिर से व्यक्ति A को... जब तक कि गार्ड थकान से ढह न जाए। इसे Denial of Service (ReDoS) हमला कहा जाता है।

वास्तविक दुनिया में, इसने स्टैक ओवरफ्लो (Stack Overflow) और क्लाउडफ्लेयर (Cloudflare) जैसी बड़ी वेबसाइटों को क्रैश कर दिया है। शोध पत्र नोट करता है कि यहाँ तक कि "क्वाड्रेटिक" (quadratic) सुस्ती भी (जहाँ 100 लोगों को जाँचने में 10,000 कदम लगते हैं) सिस्टम को क्रैश करने के लिए पर्याप्त है।

विलेन: "बैकरेफरेंस" (Backreferences)

मानक नियम सरल होते हैं। लेकिन आधुनिक "Regex" इंजन में एक बहुत शक्तिशाली फीचर होता है जिसे Backreferences कहते हैं।

उपमा (Analogy):
कल्पना कीजिए कि एक नियम कहता है: "एक शब्द ढूँढो, उसे याद रखो, और फिर सुनिश्चित करो कि वही सटीक शब्द बाद में फिर से दिखाई दे।"

उदाहरण: "एक शब्द ढूँढो, उसे 'X' नाम दो। फिर, 'X' को फिर से ढूँढो।"
यदि इनपुट apple ... apple है, तो यह काम करेगा।
यदि इनपुट apple ... banana है, तो यह विफल हो जाएगा।

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

शोध पत्र के निष्कर्ष: अच्छा, बुरा और बदतर

लेखकों ने ठीक से जाँच की कि इन मिलान समस्याओं (matching problems) को हल करना कितना कठिन है। उन्होंने इसे दो पक्षों में विभाजित किया: कठिनाई (Hardness) (यह क्यों कठिन है) और एल्गोरिदम (Algorithms) (इसे कैसे ठीक करें)।

1. बुरी खबर: कुछ नियम तेज़ करना असंभव है

शोध पत्र सिद्ध करता है कि कुछ प्रकार के जटिल नियमों के लिए, उन्हें तेज़ बनाने के लिए कोई "जादुई समाधान" नहीं है।

"ट्रायंगल" (Triangle) की समस्या: उन्होंने दिखाया कि यदि आपके पास एक नियम है जो दो वेरिएबल्स का उपयोग करता है (जैसे दो अलग-अलग शब्दों को याद रखना और बाद में उन्हें जाँचना), तो इसे हल करना एक विशाल सोशल नेटवर्क ग्राफ में त्रिकोण (triangle) खोजने जितना ही कठिन है। यदि आप उस नियम को जल्दी हल कर सकते, तो आप ग्राफ समस्या को भी जल्दी हल कर सकते। चूंकि ग्राफ विशेषज्ञ मानते हैं कि ग्राफ समस्या स्वाभाविक रूप से धीमी है, इसलिए नियम वाली समस्या भी धीमी ही होगी।
"ऑर्थोगोनल वेक्टर्स" (Orthogonal Vectors) की समस्या: और भी अधिक वेरिएबल्स वाले नियमों के लिए, उन्होंने सिद्ध किया कि वेरिएबल्स की संख्या के साथ आवश्यक समय तेजी से (exponentially) बढ़ता है। यह एक ताले में विशिष्ट कुंजी के संयोजन को खोजने जैसा है; जितने अधिक चाबियाँ होंगी, इसे जल्दी से ब्रूट-फोर्स करना उतना ही असंभव होता जाएगा।

निष्कर्ष: यदि आपका नियम बहुत जटिल है (कई "इसे याद रखो" फीचर्स का उपयोग करता है), तो आप एक तेज़ इंजन नहीं बना सकते। आप हमेशा एक दीवार से टकरा जाएंगे।

2. अच्छी खबर: सरल मामलों के लिए एक "निकट-रैखिक" (Near-Linear) समाधान

हालाँकि, शोध पत्र ने एक "स्वीट स्पॉट" (सही संतुलन) खोजा। उन्होंने एक विशिष्ट, सामान्य प्रकार के नियम पर ध्यान केंद्रित किया:

"ABCBD" पैटर्न: "एक शब्द (A) ढूँढें, फिर एक शब्द (B), फिर एक शब्द (C), फिर वही सटीक शब्द B फिर से, और फिर एक शब्द (D)।"
- वास्तविक दुनिया का उदाहरण: "एक यूजरनेम ढूँढें, फिर पासवर्ड, फिर एक संदेश, फिर वही यूजरनेम फिर से, और फिर एक सिग्नेचर।"

लेखकों ने पाया कि हालांकि यह पेचीदा दिखता है, इसे बहुत कुशलता से हल किया जा सकता है।

पुराना तरीका: पिछले तरीके एक लाइब्रेरी में हर संभव संयोजन को जाँचने जैसे थे, जिसमें $O(n^2)$ समय (क्वाड्रेटिक) लगता था। यदि किताब 1,000 पन्नों की थी, तो इसमें 1,000,000 कदम लगते थे।
नया तरीका: लेखकों ने एक नया एल्गोरिदम बनाया जो लगभग $O(n \log^2 n)$ $O (n lo g^{2} n)$ समय लेता है।
- उपमा: कल्पना कीजिए कि लाइब्रेरी एक जादुई इंडेक्स सिस्टम (जिसमें Suffix Trees और Factorization Forests का उपयोग किया गया है) के साथ व्यवस्थित है। हर पन्ने को पढ़ने के बजाय, गार्ड सीधे प्रासंगिक अनुभागों पर कूद सकता है। यदि किताब 1,000 पन्नों की है, तो नया तरीका लगभग 10,000 कदम लेगा (या उससे भी कम), जो एक बड़ा सुधार है।

यह नया एल्गोरिदम कैसे काम करता है (जादुई तकनीकें)

इस गति को प्राप्त करने के लिए, लेखकों ने कई चतुर तकनीकों का उपयोग किया, जिनका वे शोध पत्र में वर्णन करते हैं:

द सफिक्स ट्री (The Suffix Tree - मानचित्र): उन्होंने इनपुट स्ट्रिंग का एक विशाल मानचित्र बनाया। यह मानचित्र स्ट्रिंग के हर संभावित अंत को दिखाता है। यह गार्ड को तुरंत देखने में मदद करता है, "ओह, यह शब्द 'B' यहाँ भी है, और यह वहाँ भी है।"
हेवी-लाइट डिकंपोजिशन (Heavy-Light Decomposition - सॉर्टिंग हैट): उन्होंने मानचित्र को "भारी" पथों (बहुत सामान्य पथ) और "हल्के" पथों (दुर्लभ पथ) में विभाजित किया। वे केवल दुर्लभ पथों पर भारी काम करते हैं, जिससे समय बचता है।
पीरियडिसिटी (Periodicity - लय): उन्होंने देखा कि जब एक शब्द दोहराता है (जैसे "B...B"), तो स्ट्रिंग में अक्सर एक लय या पैटर्न होता है। उन्होंने हर अक्षर को जाँचने के बजाय इन पैटर्नों की भविष्यवाणी करने के लिए गणित का उपयोग किया।
फैक्टराइजेशन फॉरेस्ट्स (Factorization Forests - इंडेक्स): यह एक डेटा स्ट्रक्चर है जो एक सुपर-फास्ट इंडेक्स की तरह काम करता है, जिससे गार्ड यह जाँच सकता है कि टेक्स्ट का एक हिस्सा नियम से मेल खाता है या नहीं, चाहे टेक्स्ट कितना भी लंबा क्यों न हो।

निष्कर्ष का सारांश

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

यह शोध पत्र मूल रूप से एक रेखा खींचता है: यहाँ वह सीमा है जिसे तोड़ना असंभव है, और यहाँ वह जगह है जहाँ हमने तेज़ी से चलाने का तरीका खोज लिया है।

तकनीकी सारांश: बैकरेफरेंस के साथ नियमित अभिव्यक्तियों (Regular Expressions) की मिलान समस्या की जटिलता पर

1. समस्या की परिभाषा और प्रेरणा

यह शोध पत्र बैकरेफरेंस के साथ नियमित अभिव्यक्ति मिलान समस्या (Regular Expression Matching with Backreferences - REWB) की सूक्ष्म-स्तरीय गणनात्मक जटिलता (fine-grained computational complexity) की जांच करता है। जबकि शास्त्रीय नियमित अभिव्यक्तियाँ (Regex) थॉमसन के निर्माण (Thompson's construction) का उपयोग करके इनपुट स्ट्रिंग की लंबाई $|w|$ के सापेक्ष रैखिक समय (linear time) में मेल खा सकती हैं, व्यावहारिक इंजन बैकरेफरेंस (जैसे, सबस्ट्रिंग को कैप्चर करने के लिए (E)x और उसे पुनः उपयोग करने के लिए \x) का समर्थन करते हैं। यह विशेषता Regex की अभिव्यंजक शक्ति (expressive power) को कड़ाई से विस्तारित करती है (जैसे $\{ww \mid w \in \Sigma^*\}$ जैसी गैर-नियमित भाषाओं को पहचानना अनुमति देती है) लेकिन महत्वपूर्ण एल्गोरिद्मिक जोखिम भी उत्पन्न करती है।

इसकी प्रेरणा रेगुलर एक्सप्रेशन डिनायल ऑफ सर्विस (ReDoS) हमलों से आती है, जहाँ हमलावर ऐसे इनपुट तैयार करते हैं जो बैकट्रैकिंग-आधारित मिलान इंजनों में सबसे खराब स्थिति (worst-case behavior) को ट्रिगर कर सकें। स्टैक ओवरफ्लो (2016) और क्लाउडफ्लेयर (2019) जैसी उल्लेखनीय घटनाओं ने प्रदर्शित किया कि बैकट्रैकिंग-आधारित इंजनों में द्विघात-समय व्यवहार ( $O(|w|^2)$ ) भी विनाशकारी सेवा आउटेज का कारण बन सकता है। लेखक एक मौलिक प्रश्न पूछते हैं: क्या REWB के लिए ReDoS-सुरक्षित इंजन बनाना संभव है जो रैखिक या लगभग रैखिक समय में चल सकें?

यह शोध पत्र $r$ -use $k$ -REWBs पर केंद्रित है, जिसे $k$ अलग-अलग चरों (variables) वाली अभिव्यक्तियों के रूप में परिभाषित किया गया है जहाँ किसी भी गणना में बैकरेफरेंस निष्पादन की कुल संख्या $r$ द्वारा सीमित है।

2. कार्यप्रणाली और तकनीकी दृष्टिकोण

यह शोध पत्र एक दोहरी पद्धति का उपयोग करता है: सशर्त निचली सीमाओं (hardness) को स्थापित करना और विशिष्ट उप-वर्गों के लिए कुशल एल्गोरिदम डिजाइन करना।

2.1 कठोरता के परिणाम (Hardness Results)

लेखक REWB मिलान में प्रसिद्ध कठिन समस्याओं को कम (reduce) करके पिछले जटिलता परिणामों को सुदृढ़ करते हैं:

W[2]-कठोरता: $k$ -डोमिनेटिंग सेट (k-Dominating Set) समस्या को कम करके, वे सिद्ध करते हैं कि REWB मिलान अभिव्यक्ति आकार $|E|$ के आधार पर W[2]-हार्ड है। यह ज्ञात W[1]-कठोरता परिणाम को मजबूत करता है।
सशर्त निचली सीमाएं (ट्रायंगल डिटेक्शन): "नो-ऑलमोस्ट-लीनियर-टाइम हाइपोथेसिस" (No-Almost-Linear-Time Hypothesis) के तहत, वे दिखाते हैं कि अत्यधिक प्रतिबंधित 2-use 2-REWB समस्या को किसी भी $\delta > 0$ के लिए $O(|w|^{1+\delta})$ समय में हल नहीं किया जा सकता है।
सशर्त निचली सीमाएं (k-OV): $k$ -ऑर्थोगोनल वेक्टर्स (k-OV) परिकल्पना (जो SETH से कमजोर है) के तहत, वे सिद्ध करते हैं कि $k$ -REWB मिलान को $O(|w|^{2k-\epsilon})$ समय में हल नहीं किया जा सकता है। इसका तात्पर्य है कि सामान्य $k$ के लिए, निकट-रैखिक समय (near-linear time) की संभावना कम है।

2.2 एल्गोरिद्मिक परिणाम

प्राथमिक एल्गोरिद्मिक योगदान 1-use REWBs (एक चर वाली अभिव्यक्तियाँ जिसका संदर्भ ठीक एक बार दिया गया है) पर केंद्रित है।

कैनोनिकल फॉर्म ट्रांसफॉर्मेशन: लेखक सिद्ध करते हैं कि किसी भी 1-use REWB को $A (B)_x C \backslash x D$ जैसे पदों के योग वाले एक कैनोनिकल रूप में बदला जा सकता है, जहाँ $A, B, C, D$ शास्त्रीय Regex हैं। इसे ABCBD समस्या कहा जाता है।
विघटन रणनीति (Decomposition Strategy): ABCBD समस्या को दो उप-समस्याओं में विभाजित किया गया है:
1. XYYZ समस्या: वह मामला जहाँ $B$ के दो उदाहरण आसन्न (adjacent) हैं ( $w = w_A w_B w_B w_D$ )। इसे क्रोचेमोर के मैक्सिमल लोकल पावर एन्यूमरेशन (Crochemore's maximal local power enumeration) और ट्रांजिशन मोनोइड्स से प्राप्त अल्टीमेटली पीरियडिक सेट्स के गुणों का उपयोग करके हल किया जाता है।
2. ब्रांचिंग ABCBD समस्या: वह मामला जहाँ दो $B$ के उदाहरण एक गैर-रिक्त $C$ द्वारा अलग किए गए हैं, और दो $B$ के तुरंत बाद आने वाले वर्ण भिन्न हैं।
सफिक्स ट्री और हेवी-लाइट डिकंपोजिशन: ब्रांचिंग मामले के लिए, एल्गोरिदम इनपुट स्ट्रिंग $w$ के सफिक्स ट्री का उपयोग करता है। यह खोज स्थान को विभाजित करने के लिए हेवी-लाइट डिकंपोजिशन का उपयोग करता है।
डेटा संरचनाएं:
- फैक्टराइजेशन फॉरेस्ट्स (Factorization Forests): सबस्ट्रिंग्स पर Regex सदस्यता का निरंतर समय (constant time) में मूल्यांकन करने के लिए उपयोग किया जाता है।
- ट्रांजिशन मोनोइड्स (Transition Monoids): Regex $A, B, C, D$ की स्थिति को कुशलतापूर्वक ट्रैक करने के लिए उपयोग किया जाता है।
- कस्टम एन्यूमेटर्स (Custom Enumerators): लेखक ट्रांजिशन एन्यूमरेशन को संभालने के लिए विशेष डेटा संरचनाएं (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) डिजाइन करते हैं। ये संरचनाएं सबस्ट्रिंग $w_B$ की लंबाई के साथ बदलने वाले बाधाओं को प्रबंधित करने के लिए लेजी अपडेट्स (lazy updates) और डिस्जॉइंट-सेट यूनियन (DSU) रणनीतियों का उपयोग करती हैं।

3. मुख्य परिणाम

कठोरता (Hardness)

प्रमेय 3: REWB मिलान अभिव्यक्ति आकार द्वारा पैरामीटराइज्ड होने पर W[2]-हार्ड है।
प्रमेय 4: ट्रायंगल डिटेक्शन हाइपोथेसिस के तहत, 2-use 2-REWB मिलान के लिए सुपर-लीनियर समय (विशेष रूप से, $O(|w|^{1+\delta})$ नहीं) की आवश्यकता होती है।
प्रमेय 5: $k$ -OV हाइपोथेसिस के तहत, $k$ -REWB मिलान के लिए $\Omega(|w|^{2k-\epsilon})$ समय की आवश्यकता होती है।

एल्गोरिदम

प्रमेय 7 (मुख्य परिणाम): ABCBD समस्या के लिए एक $O(|w| \log^2 |w|)$ समय का एल्गोरिदम उपलब्ध है। छिपा हुआ स्थिरांक (hidden constant) Regex के आकार ( $2^{O((|A|+|B|+|C|+|D|)^2)}$ ) पर चरघातांकीय रूप से निर्भर करता है।
प्रमेय 8: फलस्वरूप, 1-use REWB मिलान समस्या के लिए एक $O(|w| \log^2 |w|)$ समय का एल्गोरिदम उपलब्ध है।
प्रमेय 9: XY $\alpha$ Z समस्या ( $\alpha$ दोहराव के लिए XYYZ का सामान्यीकरण) $O(|w| \log |w|)$ समय का एल्गोरिदम प्रदान करती है।

ये परिणाम नोगामी और टेराउची (MFCS 2025) द्वारा ABCBD समस्या के लिए ज्ञात पिछले सर्वश्रेष्ठ $O(|w|^2)$ एल्गोरिदम की तुलना में एक महत्वपूर्ण सुधार का प्रतिनिधित्व करते हैं।

4. महत्व और दावे

यह शोध पत्र REWB मिलान की जटिलता परिदृश्य की मौलिक समझ प्रदान करने का दावा करता है:

ReDoS सुरक्षा: यह स्थापित करता है कि जबकि सामान्य REWB मिलान निकट-रैखिक समय के लिए संभवतः कठिन है, एक व्यावहारिक रूप से प्रासंगिक उप-वर्ग (1-use REWB) को निकट-रैखिक समय में मिलाया जा सकता है। यह सुझाव देता है कि 1-use बैकरेफरेंस का समर्थन करने वाले इंजनों को सैद्धांतिक रूप से ReDoS-सुरक्षित बनाया जा सकता है।
सूक्ष्म-स्तरीय जटिलता (Fine-Grained Complexity): यह कार्य व्यवहार्य और अव्यवहार्य मामलों के बीच की सीमा को रेखांकित करता है। यह दिखाता है कि बैकरेफरेंस उपयोगों की संख्या को 1 से बढ़ाकर 2 करने से (केवल 2 चरों के साथ भी) समस्या के निकट-रैखिक शासन (near-linear regime) से बाहर जाने की संभावना है।
एल्गोरिद्मिक नवाचार: यह शोध पत्र एक जटिल लेकिन अत्यधिक गैर-तुच्छ (non-trivial) एल्गोरिद्मिक ढांचे को पेश करता है जो पहले से सोचा गया था कि इसके लिए द्विघात समय की आवश्यकता होगी, उसे हल करने के लिए सफिक्स ट्री, फैक्टराइजेशन फॉरेस्ट और ट्रांजिशन मोनोइड्स को जोड़ता है।

लेखक स्पष्ट रूप से कहते हैं कि उनका एल्गोरिदम यूनिफॉर्म (uniform) है, जिसका अर्थ है कि यह फिक्स्ड एक्सप्रेशन पर निर्भर गैर-यूनिफॉर्म सलाह के बिना अभिव्यक्ति और इनपुट स्ट्रिंग को एक साथ प्रोसेस करता है। वे स्वीकार करते हैं कि बहुत बड़ी अभिव्यक्तियों के लिए अभिव्यक्ति के आकार $|E|$ पर चरघातांकीय निर्भरता एक सीमा बनी हुई है, और वे इस प्रश्न को खुला छोड़ देते हैं कि क्या वास्तव में रैखिक-समय ( $O(|w|)$ ) एल्गोरिदम मौजूद है या क्या लॉगरिदमिक कारकों को हटाया जा सकता है।

5. सीमाएं और खुले प्रश्न

शोध पत्र कई खुले दिशाओं की पहचान करता है:

$r$ -use 1-REWB की जटिलता: $r$ -use 1-REWBs के लिए जटिलता जहाँ $r \ge 2$ है, अभी भी खुली है।
रैखिक समय: क्या $O(|w| \log^2 |w|)$ सीमा को $O(|w|)$ में सुधारा जा सकता है।
अभिव्यक्ति निर्भरता: $|w|$ पर निकट-रैखिक निर्भरता बनाए रखते हुए $|E|$ पर चरघातांकीय निर्भरता को बहुपद (polynomial) तक कम करना।
व्यापक विशेषताएं: लुकअराउंड (lookarounds), एटॉमिक ग्रुपिंग (atomic grouping), और ग्रीडी/लेजी स्टार्स (greedy/lazy stars) जैसी अन्य व्यावहारिक regex विशेषताओं तक इन परिणामों का विस्तार करना।