अनुमानित स्ट्रिंग मिलान: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(11 intermediate revisions by 3 users not shown)
Line 3: Line 3:


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


* प्रविष्टि: खाट → co'a't
* प्रविष्टि: खाट → co'a't
Line 9: Line 9:
* प्रतिस्थापन: co'a't → co''t
* प्रतिस्थापन: co'a't → co''t


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


कुछ अनुमानित मिलानकर्ता ट्रांसपोज़िशन को भी एक प्राथमिक , ऑपरेशन मानते हैं, जिसमें स्ट्रिंग में दो अक्षरों की स्थिति की अदला-बदली की जाती है।{{ref|CRMN01}}
कुछ अनुमानित मिलान करने वाले तकनीकों में स्थानांतरण, को भी एक मूलभूत परिचालक के रूप में माना जाता है, जिसमें स्ट्रिंग में दो अक्षरों की स्थिति बदल जाती है।।{{ref|CRMN01}}
* ट्रांसपोज़िशन: co'st' → co'ts'
* स्थानांतरण, : co'st' → co'ts'
 
विभिन्न अनुमानित मिलान करने वाले तकनीकों में विभिन्न प्रतिबंध लगाए जाते हैं। कुछ मिलान करने वाले तकनीक एकल वैश्विक अनवेशित लागत का उपयोग करते हैं, यानी मिलान को पैटर्न में बदलने के लिए आवश्यक मूलभूत आपरेशनों की कुल संख्या। उदाहरण के लिए, यदि पैटर्न कॉइल है, तो फ़ॉइल में एक प्रतिस्थापन अलग है, कॉइल में एक प्रविष्टि अलग है, ऑइल में एक विलोपन अलग है, और फ़ॉइल में दो प्रतिस्थापन अलग हैं। यदि सभी परिचालको को एकल लागत की इकाई के रूप में गिना जाए और सीमा को एक में सेट किया जाए, तो फ़ॉइल, कॉइल और को मिलान के रूप में गिना जाएगा जबकि फ़ॉइल को मिलान के रूप में नहीं गिना जाएगा।
 
अन्य मिलान करने वाले तकनीकों में, प्रत्येक प्रकार के परिचालको की अलग-अलग संख्या को निर्दिष्ट किया जाता है, जबकि कुछ अन्य अलग-अलग परिचालको के लिए विभिन्न वज़न निर्धारित करने की अनुमति देते हैं। कुछ मिलान करने वाले तकनीकों में पैटर्न में अलग-अलग समूहों के लिए सीमाएं और वज़न के अलग-अलग आवंटन की अनुमति दी जाती है।
 
== समस्या सूत्रीकरण और कलन-विधि  , ==
अनुमानित स्ट्रिंग मिलान समस्या की एक संभावित परिभाषा निम्नलिखित हो सकती है: एक पैटर्न स्ट्रिंग P = p_1p_2...p_m और एक टेक्स्ट स्ट्रिंग T = t_1t_2...t_n दी गई हो, तो ''T'' के सभी उप-स्ट्रिंगों में से पैटर्न ''P'' के सबसे कम संपादन दूरी वाला उप-स्ट्रिंग <math>T_{j',j} = t_{j'}...t_j</math> का पता लगाएं।
 
एक ब्रूट-फ़ोर्स दृष्टिकोण हो सकता है कि T के सभी उप-स्ट्रिंगों के लिए P तक संपादन दूरी की गणना की जाए, और फिर न्यूनतम दूरी वाली उप-स्ट्रिंग को चुना जाए। और पुनः न्यूनतम दूरी के साथ उपस्ट्रिंग चुनें। यद्यपि, इस कलन-विधि का समय O(n^3 * m) होगा।
 
एक बेहतर समाधान, जो Sellers{{ref|Sel80}} द्वारा प्रस्तावित किया गया था, डायनामिक प्रोग्रामिंग पर आधारित है। यह समस्या के एक पर्यायी सूत्र का उपयोग करता है: प्रत्येक स्थान ''j'' में टेक्स्ट,  ''T'' और प्रत्येक स्थान ''i'' में पैटर्न ''P'' के लिए, पैटर्न के ''i'' पहले वर्णों, <math>P_i</math>, और किसी भी ''T'' के उप-स्ट्रिंग <math>T_{j',j}</math> के बीच न्यूनतम संपादन दूरी की गणना करें, जो स्थान ''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) समय सीमा के अंदर काम नहीं कर सकता है। इसलिए, स्ट्रिंग के सभी जोड़ियों की समानता की गणना करने के अतिरिक्त, उम्मीदवार जोड़ियों की संख्या को कम करने का विचार है।
 
व्यापक रूप से उपयोग किए जाने वाले कलन-विधि, फ़िल्टर-सत्यापन, हैशिंग, स्थानीयता-संवेदनशील हैशिंग, ट्राइज़ और अन्य सन्निकटन कलन-विधि पर आधारित हैं। इनमें से अधिकांश का निर्माण किसी न किसी फ्रेमवर्क के साथ काम करने के लिए किया गया है जिससे समय साथ साथ गणना की जा सके।


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


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


== समस्या सूत्रीकरण और एल्गोरिदम ==
अनुमानित स्ट्रिंग मिलान समस्या की एक संभावित परिभाषा निम्नलिखित है: एक पैटर्न स्ट्रिंग दी गई है <math>P = p_1p_2...p_m</math> और एक टेक्स्ट स्ट्रिंग <math>T = t_1t_2\dots t_n</math>, एक सबस्ट्रिंग ढूंढें <math>T_{j',j} = t_{j'}\dots t_j</math> टी में, जिसमें, टी के सभी सबस्ट्रिंग में से, पैटर्न पी के लिए सबसे छोटी संपादन दूरी है।


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


एक बेहतर समाधान, जो विक्रेताओं द्वारा प्रस्तावित किया गया था{{ref|Sel80}}, [[गतिशील प्रोग्रामिंग]] पर निर्भर करता है। यह समस्या के वैकल्पिक सूत्रीकरण का उपयोग करता है: पाठ T में प्रत्येक स्थिति j और पैटर्न P में प्रत्येक स्थिति i के लिए, पैटर्न के i पहले वर्णों के बीच न्यूनतम संपादन दूरी की गणना करें, <math>P_i</math>, और कोई भी सबस्ट्रिंग <math>T_{j',j}</math> 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) होने दें<sub>2</sub>, और<sub>2</sub>), और गणना के पथ का पीछे की ओर अनुसरण करें, पंक्ति संख्या 0 पर वापस जाएं। यदि हम जिस फ़ील्ड पर पहुंचे वह E(0,y) था<sub>1</sub>), फिर टी[य<sub>1</sub>+ 1]...टी[य<sub>2</sub>] पैटर्न पी से न्यूनतम संपादन दूरी के साथ टी का एक सबस्ट्रिंग है।


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


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


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


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


हालाँकि बहुत तेज़ ऑनलाइन तकनीकें मौजूद हैं, बड़े डेटा पर उनका प्रदर्शन अस्वीकार्य है।
यद्यपि, बहुत तेज़ ऑनलाइन तकनीकों के उपस्थित होने के बाद भी, उनका प्रदर्शन बड़े डेटा पर अप्रत्याशित है। टेक्स्ट पूर्व संस्करण या अनुक्रमणिका से {{ref|Gus97}}खोजना बहुत तेज़ बनाता है।{{ref|Gus97}} इनमें सफ़िक्स ट्री, मापीय और एन-ग्राम विधियाँ सम्मिलित हैं।{{ref|Gus97}} टेक्स्ट में किसी भी विचित्र उपस्ट्रिंग को खोजने की अनुमति देने वाली अनुक्रमणिका तकनीकों {{ref|Gus97}}का एक विस्तृत सर्वेक्षण नवारो और उनके सहकर्मियों द्वारा दिया गया है।{{ref|Gus97}}अनुक्रमण तकनीकों का एक विस्तृत सर्वेक्षण जो किसी टेक्स्ट,{{ref|NBST01}} में एक यादृच्छिक उपस्ट्रिंग खोजने की अनुमति देता है, नवारो एट अल द्वारा दिया गया है।{{ref|NBST01}} शब्दकोश विधियों का एक कम्प्यूटेशनल सर्वेक्षण बॉयत्सोव द्वारा दिया गया है{{ref|Zob95}}{{ref|B11}}.
टेक्स्ट प्रीप्रोसेसिंग या इंडेक्स (खोज इंजन) खोज को नाटकीय रूप से तेज़ बनाता है।
आज, विभिन्न प्रकार के अनुक्रमण एल्गोरिदम प्रस्तुत किए गए हैं। इनमें [[प्रत्यय वृक्ष]] भी शामिल हैं{{ref|Gus97}}, मीट्रिक पेड़{{ref|NB98}} और [[एन-ग्राम]] विधियाँ।{{ref|NBST01}}{{ref|Zob95}}
अनुक्रमण तकनीकों का एक विस्तृत सर्वेक्षण जो किसी पाठ में एक मनमाना सबस्ट्रिंग खोजने की अनुमति देता है, नवारो एट अल द्वारा दिया गया है।{{ref|NBST01}} शब्दकोश विधियों का एक कम्प्यूटेशनल सर्वेक्षण (अर्थात्, वे विधियाँ जो सभी शब्दकोश शब्दों को खोजने की अनुमति देती हैं जो लगभग एक खोज पैटर्न से मेल खाते हैं) बॉयत्सोव द्वारा दिया गया है{{ref|B11}}.


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


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


एक सामान्य कमांड-लाइन टूल fzf का उपयोग अक्सर विभिन्न कमांड-लाइन अनुप्रयोगों में अनुमानित स्ट्रिंग खोज को एकीकृत करने के लिए किया जाता है।<ref>{{Cite web |date=2018-11-08 |title=Fzf - लिनक्स टर्मिनल से एक त्वरित फ़ज़ी फ़ाइल खोज|url=https://www.tecmint.com/fzf-fuzzy-file-search-from-linux-terminal/ |access-date=2022-09-08 |website=www.tecmint.com |language=en-US}}</ref>
एक सामान्य कमांड-लाइन उपकरण fzf प्रायः अनुमानित स्ट्रिंग खोज को विभिन्न कमांड-लाइन एप्लिकेशन में सम्मिलित करने के लिए प्रयोग किया जाता है।<ref>{{Cite web |date=2018-11-08 |title=Fzf - लिनक्स टर्मिनल से एक त्वरित फ़ज़ी फ़ाइल खोज|url=https://www.tecmint.com/fzf-fuzzy-file-search-from-linux-terminal/ |access-date=2022-09-08 |website=www.tecmint.com |language=en-US}}</ref>




Line 101: Line 108:
{{strings}}
{{strings}}


{{DEFAULTSORT:Approximate String Matching}}[[Category: स्ट्रिंग मिलान एल्गोरिदम|*]] [[Category: पैटर्न मिलान]] [[Category: गतिशील प्रोग्रामिंग]]
{{DEFAULTSORT:Approximate String Matching}}
 
 


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 10/07/2023]]
[[Category:Collapse templates|Approximate String Matching]]
[[Category:Created On 10/07/2023|Approximate String Matching]]
[[Category:Lua-based templates|Approximate String Matching]]
[[Category:Machine Translated Page|Approximate String Matching]]
[[Category:Multi-column templates|Approximate String Matching]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Approximate String Matching]]
[[Category:Pages using div col with small parameter|Approximate String Matching]]
[[Category:Pages with script errors|Approximate String Matching]]
[[Category:Short description with empty Wikidata description|Approximate String Matching]]
[[Category:Sidebars with styles needing conversion|Approximate String Matching]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Approximate String Matching]]
[[Category:Templates generating microformats|Approximate String Matching]]
[[Category:Templates that add a tracking category|Approximate String Matching]]
[[Category:Templates that are not mobile friendly|Approximate String Matching]]
[[Category:Templates that generate short descriptions|Approximate String Matching]]
[[Category:Templates using TemplateData|Approximate String Matching]]
[[Category:Templates using under-protected Lua modules|Approximate String Matching]]
[[Category:Wikipedia fully protected templates|Div col]]
[[Category:Wikipedia metatemplates|Approximate String Matching]]
[[Category:गतिशील प्रोग्रामिंग|Approximate String Matching]]
[[Category:पैटर्न मिलान|Approximate String Matching]]
[[Category:स्ट्रिंग मिलान एल्गोरिदम|*]]

Latest revision as of 10:39, 27 July 2023

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

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

अवलोकन

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

  • प्रविष्टि: खाट → 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

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

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

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

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

समस्या सूत्रीकरण और कलन-विधि ,

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

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

एक बेहतर समाधान, जो Sellers[3] द्वारा प्रस्तावित किया गया था, डायनामिक प्रोग्रामिंग पर आधारित है। यह समस्या के एक पर्यायी सूत्र का उपयोग करता है: प्रत्येक स्थान j में टेक्स्ट, T और प्रत्येक स्थान i में पैटर्न P के लिए, पैटर्न के i पहले वर्णों, , और किसी भी T के उप-स्ट्रिंग के बीच न्यूनतम संपादन दूरी की गणना करें, जो स्थान 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) समय सीमा के अंदर काम नहीं कर सकता है। इसलिए, स्ट्रिंग के सभी जोड़ियों की समानता की गणना करने के अतिरिक्त, उम्मीदवार जोड़ियों की संख्या को कम करने का विचार है।

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






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

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

ऑनलाइन खोज तकनीकों को बार-बार सुधारा गया है। प्रायः सबसे प्रसिद्ध सुधार है बिटप कलन-विधि, जो निश्चित रूप से छोटे पैटर्न स्ट्रिंग्स के लिए बहुत प्रभावी होता है। बिटप कलन-विधि, जो यूनिक्स खोजने वाली यूटिलिटी एग्रेप का मुख्य भाग है, के बारे में एक समीक्षा जी. नवारो द्वारा की गई थी।[6]

यद्यपि, बहुत तेज़ ऑनलाइन तकनीकों के उपस्थित होने के बाद भी, उनका प्रदर्शन बड़े डेटा पर अप्रत्याशित है। टेक्स्ट पूर्व संस्करण या अनुक्रमणिका से [7]खोजना बहुत तेज़ बनाता है।[8] इनमें सफ़िक्स ट्री, मापीय और एन-ग्राम विधियाँ सम्मिलित हैं।[9] टेक्स्ट में किसी भी विचित्र उपस्ट्रिंग को खोजने की अनुमति देने वाली अनुक्रमणिका तकनीकों [10]का एक विस्तृत सर्वेक्षण नवारो और उनके सहकर्मियों द्वारा दिया गया है।[11]अनुक्रमण तकनीकों का एक विस्तृत सर्वेक्षण जो किसी टेक्स्ट,[12] में एक यादृच्छिक उपस्ट्रिंग खोजने की अनुमति देता है, नवारो एट अल द्वारा दिया गया है।[13] शब्दकोश विधियों का एक कम्प्यूटेशनल सर्वेक्षण बॉयत्सोव द्वारा दिया गया है[14][15].

अनुप्रयोग

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

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

एक सामान्य कमांड-लाइन उपकरण fzf प्रायः अनुमानित स्ट्रिंग खोज को विभिन्न कमांड-लाइन एप्लिकेशन में सम्मिलित करने के लिए प्रयोग किया जाता है।[1]


यह भी देखें

संदर्भ

  1. "Fzf - लिनक्स टर्मिनल से एक त्वरित फ़ज़ी फ़ाइल खोज". www.tecmint.com (in English). 2018-11-08. Retrieved 2022-09-08.


बाहरी संबंध