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

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

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

अवलोकन

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

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

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

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

कुछ अनुमानित मिलानकर्ता ट्रांसपोज़िशन को भी एक आदिम ऑपरेशन मानते हैं, जिसमें स्ट्रिंग में दो अक्षरों की स्थिति की अदला-बदली की जाती है।

• ट्रांसपोज़िशन: co'st' → co'ts'

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

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

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

अनुमानित स्ट्रिंग मिलान समस्या की एक संभावित परिभाषा निम्नलिखित है: एक पैटर्न स्ट्रिंग दी गई है $P=p_{1}p_{2}...p_{m}$ और एक टेक्स्ट स्ट्रिंग $T=t_{1}t_{2}\dots t_{n}$, एक सबस्ट्रिंग ढूंढें $T_{j',j}=t_{j'}\dots 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