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

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

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

अवलोकन

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

• प्रविष्टि: खाट → 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}$ का पता लगाएं।

एक ब्रूट-फ़ोर्स दृष्टिकोण हो सकता है कि T के सभी उप-स्ट्रिंगों के लिए P तक संपादन दूरी की गणना की जाए, और फिर न्यूनतम दूरी वाली उप-स्ट्रिंग को चुना जाए। और पुनः न्यूनतम दूरी के साथ उपस्ट्रिंग चुनें। यद्यपि, इस कलन-विधि का समय O(n^3 * m) होगा।

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

एक सामान्य कमांड-लाइन टूल 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