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

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

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

अवलोकन

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

• प्रविष्टि: खाट → 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) समय लगता है।

एक और हाल की विचारधारा है समरूपता का जुड़ाव। जब डेटाबेस के मिलान को बड़ी मात्रा में डेटा के साथ संबंधित होता है, तो गतिशील प्रोग्रामिंग कलन-विधि, के साथ 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