अनुमानित स्ट्रिंग मिलान

क्रोधित इमोटिकॉन के लिए एक अस्पष्ट मीडियाविकी खोज में एंड्रे भावनाओं का सुझाव दिया गया है

कंप्यूटर विज्ञान में, अनुमानित स्ट्रिंग मिलान एक तकनीक है जिसका उपयोग पैटर्न के लगभग सही रूप में मिलने वाली स्ट्रिंग की खोज के लिए किया जाता है। अनुमानित स्ट्रिंग मिलान की समस्या को सामान्यतः दो उप-समस्याओं में विभाजित किया जाता है। किसी दिए गए स्ट्रिंग के अंदर अनुमानित सबस्ट्रिंग मिलान ढूंढना और ऐसे शब्दकोश स्ट्रिंग ढूंढना जो पैटर्न से लगभग मेल खाते हों।

अवलोकन

मिलान की कटिबद्धता को स्ट्रिंग को सही मिलान में बदलने के लिए आवश्यक मूलभूत परिचालनों, की संख्या के माध्यम से मापा जाता है। इस संख्या को स्ट्रिंग और पैटर्न के बीच संपादन दूरी कहा जाता है। सामान्यतः मूलभूत परिचालन, निम्नलिखित होते हैं:

• प्रविष्टि: खाट → co'a't
• विलोपन: co'a't → cot
• प्रतिस्थापन: co'a't → cot

जहां भी कोई वर्ण हटा दिया गया है या डाला गया है, वहां एक शून्य वर्ण (यहां * द्वारा दर्शाया गया है) जोड़कर इन तीन परिचालनों को प्रतिस्थापन के रूप में सामान्यीकृत किया जा सकता है:

• प्रविष्टि: co'*'t → co'a't
• विलोपन: co'a't → co'*'t
• प्रतिस्थापन: co'a't → cot

कुछ अनुमानित मिलान करने वाले तकनीकों में स्थानांतरण, को भी एक मूलभूत परिचालक के रूप में माना जाता है, जिसमें स्ट्रिंग में दो अक्षरों की स्थिति बदल जाती है।।

• स्थानांतरण, : co'st' → co'ts'

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

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

समस्या सूत्रीकरण और एल्गोरिदम

अनुमानित स्ट्रिंग मिलान समस्या की एक संभावित परिभाषा निम्नलिखित हो सकती है: एक पैटर्न स्ट्रिंग P = p_1p_2...p_m और एक टेक्स्ट स्ट्रिंग T = t_1t_2...t_n दी गई हो, तो T के सभी उप-स्ट्रिंगों में से पैटर्न P के सबसे कम संपादन दूरी वाला उप-स्ट्रिंग $T_{j',j}=t_{j'}...t_{j}$ का पता लगाएं।

एक क्रूर-बल दृष्टिकोण यह होगा कि टी के सभी सबस्ट्रिंग के लिए संपादन दूरी को पी तक गणना करें, और फिर न्यूनतम दूरी के साथ सबस्ट्रिंग चुनें। हालाँकि, इस एल्गोरिदम में रनिंग टाइम बिग ओ नोटेशन (एन) होगा³ m).

एक बेहतर समाधान, जो विक्रेताओं द्वारा प्रस्तावित किया गया था, गतिशील प्रोग्रामिंग पर निर्भर करता है। यह समस्या के वैकल्पिक सूत्रीकरण का उपयोग करता है: पाठ T में प्रत्येक स्थिति j और पैटर्न P में प्रत्येक स्थिति i के लिए, पैटर्न के i पहले वर्णों के बीच न्यूनतम संपादन दूरी की गणना करें, $P_{i}$, और कोई भी सबस्ट्रिंग $T_{j',j}$ T का जो स्थिति j पर समाप्त होता है।

पाठ टी में प्रत्येक स्थिति जे के लिए, और पैटर्न पी में प्रत्येक स्थिति आई के लिए, स्थिति जे पर समाप्त होने वाले टी के सभी सबस्ट्रिंग से गुजरें, और निर्धारित करें कि उनमें से किसमें न्यूनतम है पैटर्न P के प्रथम वर्णों के लिए दूरी संपादित करें। इस न्यूनतम दूरी को E(i,j) के रूप में लिखें। सभी i और j के लिए E(i, j) की गणना करने के बाद, हम आसानी से मूल समस्या का समाधान पा सकते हैं: यह वह सबस्ट्रिंग है जिसके लिए E(m, j) न्यूनतम है (m पैटर्न P की लंबाई है।)

E(m,j) की गणना करना दो स्ट्रिंग्स के बीच संपादन दूरी की गणना करने के समान है। वास्तव में, हम E(m,j) के लिए लेवेनशेटिन दूरी#कंप्यूटिंग लेवेनशेटिन दूरी का उपयोग कर सकते हैं, एकमात्र अंतर यह है कि हमें पहली पंक्ति को शून्य के साथ प्रारंभ करना होगा, और गणना के पथ को सहेजना होगा, अर्थात, चाहे हमने E( का उपयोग किया हो) ई(आई, जे) की गणना में i − 1,j), E(i,j − 1) या E(i − 1,j − 1)।

E(x,y) मान वाली सरणी में, हम अंतिम पंक्ति में न्यूनतम मान चुनते हैं, इसे E(x) होने दें₂, और₂), और गणना के पथ का पीछे की ओर अनुसरण करें, पंक्ति संख्या 0 पर वापस जाएं। यदि हम जिस फ़ील्ड पर पहुंचे वह E(0,y) था₁), फिर टी[य₁+ 1]...टी[य₂] पैटर्न पी से न्यूनतम संपादन दूरी के साथ टी का एक सबस्ट्रिंग है।

E(x,y) सरणी की गणना करने में डायनामिक प्रोग्रामिंग एल्गोरिदम के साथ बिग O नोटेशन (mn) समय लगता है, जबकि बैकवर्ड-वर्किंग चरण में बिग O नोटेशन (n + m) समय लगता है।

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

ऑन-लाइन बनाम ऑफ-लाइन

परंपरागत रूप से, अनुमानित स्ट्रिंग मिलान एल्गोरिदम को दो श्रेणियों में वर्गीकृत किया जाता है: ऑनलाइन एल्गोरिदम|ऑन-लाइन और ऑफ-लाइन। ऑन-लाइन एल्गोरिदम के साथ पैटर्न को खोज से पहले संसाधित किया जा सकता है लेकिन टेक्स्ट को नहीं। दूसरे शब्दों में, ऑन-लाइन तकनीकें बिना किसी अनुक्रमणिका के खोज करती हैं। ऑन-लाइन अनुमानित मिलान के लिए प्रारंभिक एल्गोरिदम वैगनर और फिशर द्वारा सुझाए गए थे और विक्रेताओं द्वारा. दोनों एल्गोरिदम गतिशील प्रोग्रामिंग पर आधारित हैं लेकिन विभिन्न समस्याओं का समाधान करते हैं। विक्रेताओं का एल्गोरिदम किसी पाठ में लगभग एक सबस्ट्रिंग की खोज करता है जबकि वैगनर और फिशर का एल्गोरिदम लेवेनशेटिन दूरी की गणना करता है, जो केवल शब्दकोश अस्पष्ट खोज के लिए उपयुक्त है।

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

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

अनुप्रयोग

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

स्ट्रिंग मिलान का उपयोग अधिकांश बाइनरी डेटा, जैसे छवियों और संगीत के लिए नहीं किया जा सकता है। उन्हें अलग-अलग एल्गोरिदम की आवश्यकता होती है, जैसे ध्वनिक फ़िंगरप्रिंटिंग।

एक सामान्य कमांड-लाइन टूल fzf का उपयोग अक्सर विभिन्न कमांड-लाइन अनुप्रयोगों में अनुमानित स्ट्रिंग खोज को एकीकृत करने के लिए किया जाता है।

यह भी देखें

• संकल्पना खोज
• जारो-विंकलर दूरी
• लेवेनशेटिन दूरी
• स्थानीयता-संवेदनशील हैशिंग
• मेटाफोन
• नीडलमैन-वुन्श एल्गोरिथम
• साहित्यिक चोरी का पता लगाना
• फ़ज़ी और नॉन-फ़ज़ी मिलान के लिए नियमित अभिव्यक्ति
• स्मिथ-वाटरमैन एल्गोरिथम
• साउंडेक्स
• स्ट्रिंग मीट्रिक

संदर्भ

• ^ Baeza-Yates, R.; Navarro, G. (June 1996). "A faster algorithm for approximate string matching". In Dan Hirchsberg; Gene Myers (eds.). Combinatorial Pattern Matching (CPM'96), LNCS 1075. Irvine, CA. pp. 1–23. CiteSeerX 10.1.1.42.1593.
• ^ Baeza-Yates, R.; Navarro, G. "Fast Approximate String Matching in a Dictionary" (PDF). Proc. SPIRE'98. IEEE CS Press. pp. 14–22.
• ^ Boytsov, Leonid (2011). "Indexing methods for approximate dictionary searching: Comparative analysis". Journal of Experimental Algorithmics. 16 (1): 1–91. doi:10.1145/1963190.1963191. S2CID 15635688.
• ^ Cormen, Thomas; Leiserson, Rivest (2001). Introduction to Algorithms (2nd ed.). MIT Press. pp. 364–7. ISBN 978-0-262-03293-3.
• ^ Galil, Zvi; Apostolico, Alberto (1997). Pattern matching algorithms. Oxford [Oxfordshire]: Oxford University Press. ISBN 978-0-19-511367-9.
• ^ Gusfield, Dan (1997). Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge, UK: Cambridge University Press. ISBN 978-0-521-58519-4.
• ^ Myers, G. (May 1999). "A fast bit-vector algorithm for approximate string matching based on dynamic programming" (PDF). Journal of the ACM. 46 (3): 395–415. doi:10.1145/316542.316550. S2CID 1158099.
• ^ Navarro, Gonzalo (2001). "A guided tour to approximate string matching". ACM Computing Surveys. 33 (1): 31–88. CiteSeerX 10.1.1.96.7225. doi:10.1145/375360.375365. S2CID 207551224.
• ^ Navarro, Gonzalo; Baeza-Yates, Ricardo; Sutinen, Erkki; Tarhio, Jorma (2001). "Indexing Methods for Approximate String Matching" (PDF). IEEE Data Engineering Bulletin. 24 (4): 19–27.
• ^ Sellers, Peter H. (1980). "The Theory and Computation of Evolutionary Distances: Pattern Recognition". Journal of Algorithms. 1 (4): 359–73. doi:10.1016/0196-6774(80)90016-4.
• ^ Skiena, Steve (1998). Algorithm Design Manual (1st ed.). Springer. ISBN 978-0-387-94860-7.
• ^ Ukkonen, E. (1985). "Algorithms for approximate string matching". Information and Control. 64 (1–3): 100–18. doi:10.1016/S0019-9958(85)80046-2.
• ^ Wagner, R.; Fischer, M. (1974). "The string-to-string correction problem". Journal of the ACM. 21: 168–73. doi:10.1145/321796.321811. S2CID 13381535.
• ^ Zobel, Justin; Dart, Philip (1995). "Finding approximate matches in large lexicons". Software: Practice and Experience. 25 (3): 331–345. CiteSeerX 10.1.1.14.3856. doi:10.1002/spe.4380250307. S2CID 6776819.

बाहरी संबंध

• Flamingo Project
• Efficient Similarity Query Processing Project with recent advances in approximate string matching based on an edit distance threshold.
• StringMetric project a Scala library of string metrics and phonetic algorithms
• Natural project a JavaScript natural language processing library which includes implementations of popular string metrics