स्ट्रिंग मीट्रिक: Difference between revisions

From Vigyanwiki
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{redirect|String distance|the distance between strings and the fingerboard in musical instruments|Action (music)}}
{{redirect|स्ट्रिंग दूरी|वाद्य यंत्रों में तार और अंगुलियों के मध्य की दूरी
|क्रिया (संगीत)}}


गणित और [[कंप्यूटर विज्ञान]] में, एक स्ट्रिंग मीट्रिक (जिसे स्ट्रिंग समानता मीट्रिक या स्ट्रिंग [[दूरी]] फ़ंक्शन के रूप में भी जाना जाता है) एक [[मीट्रिक (गणित)]] है जो अनुमानित [[स्ट्रिंग मिलान]] या तुलना के लिए दो [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के बीच की दूरी (प्रतिलोम समानता) को मापता है। [[अनुमानित स्ट्रिंग मिलान]]। एक स्ट्रिंग ''मीट्रिक'' के लिए एक आवश्यकता (उदाहरण के लिए स्ट्रिंग मिलान के विपरीत) त्रिकोण असमानता की पूर्ति है। उदाहरण के लिए, तार सैम और सैमुअल को करीब माना जा सकता है।<ref>{{cite journal
गणित और [[कंप्यूटर विज्ञान]] में, स्ट्रिंग मीट्रिक (जिसे स्ट्रिंग समानता मीट्रिक या स्ट्रिंग [[दूरी]] फ़ंक्शन के रूप में भी जाना जाता है) ऐसा [[मीट्रिक (गणित)]] है जो अनुमानित [[स्ट्रिंग मिलान]] या तुलना के लिए दो [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के मध्य की दूरी (प्रतिलोम समानता) को मापता है। स्ट्रिंग ''मीट्रिक'' की आवश्यकता (उदाहरण के लिए स्ट्रिंग मिलान के विपरीत) के लिए स्ट्रिंग मिलान के त्रिकोण असमानता की पूर्ति है। उदाहरण के लिए, तार सैम और सैमुअल को समीप माना जा सकता है।<ref>{{cite journal
  | last = Lu
  | last = Lu
  | first = Jiaheng |display-authors=etal  
  | first = Jiaheng |display-authors=etal  
Line 10: Line 11:
  | url=https://dl.acm.org/citation.cfm?id=2465313| doi = 10.1145/2463676.2465313
  | url=https://dl.acm.org/citation.cfm?id=2465313| doi = 10.1145/2463676.2465313
  | isbn = 9781450320375
  | isbn = 9781450320375
  | s2cid = 2091942 }}</ref> एक स्ट्रिंग मीट्रिक एक संख्या प्रदान करता है जो दूरी के एल्गोरिथम-विशिष्ट संकेत को दर्शाता है।
  | s2cid = 2091942 }}</ref> स्ट्रिंग मीट्रिक संख्या प्रदान करता है जो दूरी के एल्गोरिथम-विशिष्ट संकेत को दर्शाता है।


सबसे व्यापक रूप से ज्ञात स्ट्रिंग मीट्रिक एक अल्पविकसित है जिसे [[लेवेनशेटिन दूरी]] (जिसे संपादन दूरी भी कहा जाता है) कहा जाता है।<ref>{{cite journal
सबसे व्यापक रूप से ज्ञात स्ट्रिंग मीट्रिक अल्प विकसित है जिसे [[लेवेनशेटिन दूरी]] (जिसे संपादन दूरी भी कहा जाता है) कहा जाता है।<ref>{{cite journal
  | last = Navarro
  | last = Navarro
  | first = Gonzalo
  | first = Gonzalo
Line 22: Line 23:
  | s2cid = 207551224
  | s2cid = 207551224
  | hdl-access=free
  | hdl-access=free
  }}</ref> यह दो इनपुट स्ट्रिंग्स के बीच संचालित होता है, एक इनपुट स्ट्रिंग को दूसरे में बदलने के लिए आवश्यक प्रतिस्थापन और विलोपन की संख्या के बराबर संख्या लौटाता है। सरलीकृत स्ट्रिंग मेट्रिक्स जैसे कि लेवेनशेटिन दूरी का विस्तार ध्वन्यात्मक, [[टोकन (पार्सर)]], व्याकरणिक और सांख्यिकीय तुलना के चरित्र-आधारित तरीकों को शामिल करने के लिए किया गया है।
  }}</ref> यह दो इनपुट स्ट्रिंग्स के मध्य संचालित होता है, इनपुट स्ट्रिंग को दूसरे में परिवर्तित करने के लिए आवश्यक प्रतिस्थापन और विलोपन की संख्या के समान संख्या लौटाता है। सरलीकृत स्ट्रिंग मेट्रिक्स जैसे कि लेवेनशेटिन दूरी का विस्तार ध्वन्यात्मक, [[टोकन (पार्सर)]], व्याकरणिक और सांख्यिकीय तुलना के चरित्र-आधारित विधियों को सम्मिलित करने के लिए किया गया है।


[[सूचना एकीकरण]] में स्ट्रिंग मेट्रिक्स का अत्यधिक उपयोग किया जाता है और वर्तमान में धोखाधड़ी का पता लगाने, [[फिंगरप्रिंट विश्लेषण]], साहित्यिक चोरी का पता लगाने, [[सत्तामीमांसा विलय]], [[डीएनए विश्लेषण]], आरएनए विश्लेषण, [[छवि विश्लेषण]], साक्ष्य-आधारित [[ यंत्र अधिगम ]], [[डेटाबेस]] [[डेटा डुप्लिकेशन]] के लिए डेटा विश्लेषण तकनीकों सहित क्षेत्रों में उपयोग किया जाता है। [[डेटा खनन]], [[ वृद्धिशील खोज ]], [[डेटा एकीकरण]], मालवेयर डिटेक्शन, <ref>{{cite journal |author1=[[Shlomi Dolev]] | last2=Mohammad |first2=Ghanayim |last3=Alexander |first3=Binun |last4=Sergey |first4=Frenkel |last5=Yeali |first5=S. Sun |title=मैलवेयर क्लस्टरिंग और ऑनलाइन पहचान में जैककार्ड और संपादन दूरी का संबंध|journal=16th IEEE International Symposium on Network Computing and Applications |date=2017 |pages=369–373}}</ref> और शब्दार्थ [[ज्ञान एकीकरण]]।
[[सूचना एकीकरण]] में स्ट्रिंग मेट्रिक्स का अत्यधिक उपयोग किया जाता है और वर्तमान में धोखाधड़ी ज्ञात करने के लिए, [[फिंगरप्रिंट विश्लेषण]], साहित्यिक चोरी को ज्ञात करने के लिए, [[सत्तामीमांसा विलय|ऑन्कोलॉजी मर्जिंग]], [[डीएनए विश्लेषण]], आरएनए विश्लेषण, [[छवि विश्लेषण]], साक्ष्य-आधारित [[ यंत्र अधिगम |यंत्र अधिगम]], [[डेटाबेस|डेटाबेस,]] [[डेटा डुप्लिकेशन|डेटा डिडुप्लीकेशन]], [[डेटा खनन|डेटा माइनिंग]], [[ वृद्धिशील खोज |वृद्धिशील]] सहित क्षेत्रों में उपयोग किया जाता है। [[ वृद्धिशील खोज |खोज,]] [[डेटा एकीकरण]], मालवेयर डिटेक्शन, <ref>{{cite journal |author1=[[Shlomi Dolev]] | last2=Mohammad |first2=Ghanayim |last3=Alexander |first3=Binun |last4=Sergey |first4=Frenkel |last5=Yeali |first5=S. Sun |title=मैलवेयर क्लस्टरिंग और ऑनलाइन पहचान में जैककार्ड और संपादन दूरी का संबंध|journal=16th IEEE International Symposium on Network Computing and Applications |date=2017 |pages=369–373}}</ref> और सिमेंटिक नॉलेज [[ज्ञान एकीकरण|इंटीग्रेशन]] आदि।


== स्ट्रिंग मेट्रिक्स की सूची ==
== स्ट्रिंग मेट्रिक्स की सूची ==


<!-- This can be a separate article, someday. -->
* लेवेनशेटिन दूरी, या इसका सामान्यीकरण संपादन दूरी
* लेवेनशेटिन दूरी, या इसका सामान्यीकरण संपादन दूरी
* डमेराउ-लेवेनशेटिन दूरी
* डमेराउ-लेवेनशेटिन दूरी
Line 41: Line 41:
* हेलिंजर दूरी या [[भट्टाचार्य दूरी]]
* हेलिंजर दूरी या [[भट्टाचार्य दूरी]]
* [[सूचना त्रिज्या]] (जेन्सेन-शैनन विचलन)
* [[सूचना त्रिज्या]] (जेन्सेन-शैनन विचलन)
* [[तिरछा विचलन]]<ref name="sam"/>* [[भ्रम की संभावना]]<ref name="sam"/>* [[केंडल ताऊ दूरी]], कुल्बैक-लीब्लर विचलन का एक अनुमान
* [[तिरछा विचलन]]<ref name="sam"/>
* Fellegi और Sunters मेट्रिक (SFS)<ref name="sam"/>* [[अधिकतम मिलान]]<ref name="sam"/>* [[व्याकरण आधारित दूरी]]<ref>Russell, David J., et al. [https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-11-601 "A grammar-based distance metric enables fast and accurate clustering of large sets of 16S sequences."] BMC bioinformatics 11.1 (2010): 1-14.</ref>
*[[भ्रम की संभावना]]<ref name="sam" />
*[[केंडल ताऊ दूरी]], कुल्बैक-लीब्लर विचलन का अनुमान
* फेलेगी और सनटर्स मेट्रिक (एसएफएस)<ref name="sam" />  
*[[अधिकतम मिलान]]<ref name="sam" />
*[[व्याकरण आधारित दूरी]]<ref>Russell, David J., et al. [https://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-11-601 "A grammar-based distance metric enables fast and accurate clustering of large sets of 16S sequences."] BMC bioinformatics 11.1 (2010): 1-14.</ref>
* टीएफ-आईडीएफ दूरी मीट्रिक<ref>{{Cite journal|title = नाम-मिलान कार्यों के लिए स्ट्रिंग डिस्टेंस मेट्रिक्स की तुलना।|url = https://dl.acm.org/doi/10.5555/3104278.3104293|date = 2003-08-01|pages = 73–78|first1 = William|last1 = Cohen|first2 = Pradeep|last2 = Ravikumar|first3 = Stephen|last3 = Fienberg}}</ref>
* टीएफ-आईडीएफ दूरी मीट्रिक<ref>{{Cite journal|title = नाम-मिलान कार्यों के लिए स्ट्रिंग डिस्टेंस मेट्रिक्स की तुलना।|url = https://dl.acm.org/doi/10.5555/3104278.3104293|date = 2003-08-01|pages = 73–78|first1 = William|last1 = Cohen|first2 = Pradeep|last2 = Ravikumar|first3 = Stephen|last3 = Fienberg}}</ref>
ऐसे कार्य भी मौजूद हैं जो तारों के बीच असमानता को मापते हैं, लेकिन जरूरी नहीं कि त्रिकोण असमानता को पूरा करें, और जैसे कि गणितीय अर्थ में मीट्रिक नहीं हैं। जारो-विंकलर दूरी इस तरह के फ़ंक्शन का एक उदाहरण है।
ऐसे कार्य भी उपस्तिथ हैं जो तारों के मध्य असमानता को मापते हैं, किंतु आवश्यक नहीं कि त्रिकोण असमानता को पूर्ण करें, और जैसे कि गणितीय अर्थ में मीट्रिक नहीं हैं। जारो-विंकलर दूरी इस प्रकार के फ़ंक्शन का उदाहरण है।


== चयनित स्ट्रिंग उपाय उदाहरण ==
== चयनित स्ट्रिंग उपाय उदाहरण ==
Line 50: Line 54:
{| class="wikitable"
{| class="wikitable"
|-
|-
! Name
! नाम
! Description
! विवरण
! Example
! उदाहरण
|-
|-
|[[Hamming distance]]
|[[Hamming distance|आलोचनात्मक दूरी]]
| Only for strings of the same length. Number of changed characters.
| केवल समान लंबाई के तार के लिए। परिवर्तित वर्णों की संख्या।
| "'''{{mono|1=ka<span style="color:#0082ff">rol</span>in}}'''" and "'''{{mono|1=ka<span style="color:red;">thr</span>in}}'''" is 3.
| "'''करोलिन'''" और "'''कैथरीन'''" 3 है।
|-
|-
|[[Levenshtein distance]] and [[Damerau–Levenshtein distance]]
|[[Levenshtein distance|लेवेनशेटिन]] [[Hamming distance|दूरी]] और [[Damerau–Levenshtein distance|दमेरौ–लेवेनशेटिन दूरी]]
| Generalisation of Hamming distance that allows for different length strings, and (with Damerau) for transpositions
| हैमिंग दूरी का सामान्यीकरण जो अलग-अलग लंबाई के तारों की अनुमति देता है, और (डेमरौ के साथ) पारदर्शिता के लिए
| {{mono|'''k'''itt'''e'''n}} and {{mono|'''s'''itt'''i'''n'''g'''}} have a distance of 3.
| किटेन और सिटींग 3 की दूरी है।
# {{mono|'''k'''itten}} → {{mono|'''s'''itten}} (substitution of "s" for "k")
# किटेन → सिटींग ("k" के लिए "s" का प्रतिस्थापन)
# {{mono|sitt'''e'''n}} → {{mono|sitt'''i'''n}} (substitution of "i" for "e")
# सिटींग → सिटींग ("e" के लिए "i" का प्रतिस्थापन")
# {{mono|sittin}} → {{mono|sittin'''g'''}} (insertion of "g" at the end).
# सिटींग → सिटींग (अंत में "g" का सम्मिलन).
|-
|-
|[[Jaro–Winkler distance]]
|[[Jaro–Winkler distance|जारो–विंकलर]] [[Levenshtein distance|दूरी]]
|
|
| JaroWinklerDist("MARTHA","MARHTA") =
| जारोविंक्लरडिस्ट ("मार्था", "मार्था")=
:<math>d_j = \frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m}\right) = \frac{1}{3}\left(\frac{6}{6} + \frac{6}{6} + \frac{6-\frac{2}{2}}{6}\right) = 0.944</math>
:<math>d_j = \frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m}\right) = \frac{1}{3}\left(\frac{6}{6} + \frac{6}{6} + \frac{6-\frac{2}{2}}{6}\right) = 0.944</math>
* <math>m</math> is the number of ''matching characters'';
* <math>m</math> मेल खाने वाले वर्णों की संख्या है;
* <math>t</math> is half the number of ''transpositions''(<code>"MARTHA"[3]!=H, "MARHTA"[3]!=T</code>).
* पारदर्शिता की आधी संख्या है ("मार्था" [3]! =<code>H, "मारहटा"[3]!=T</code>).<math>t</math>
<!--|-
<!--|-
|[[Simple matching coefficient]] (SMC)
|[[Simple matching coefficient]] (SMC)
Line 79: Line 83:
|-->
|-->
|-
|-
 
|[[Most frequent k characters|सबसे लगातार k वर्ण]]
|
|
|MostFreqKeySimilarity('<span style= color:red; >r</span><span style= color:#0082ff >e</span>s<span style= color:#0082ff >e</span>a<span शैली = रंग: लाल;
|सबसे फ्रीक कुंजी समानता('<span style= color:red; >r</span><span style= color:#0082ff >e</span>s<span style= color:#0082ff >e</span>a<span शैली = रंग: लाल;
<!--|-
<!--|-
|[[Tversky index]]
|[[Tversky index]]
Line 114: Line 118:
|}
|}


[[Category:Articles with hatnote templates targeting a nonexistent page|String Metric]]
 
[[Category:CS1 errors]]
 
[[Category:Collapse templates|String Metric]]
 
[[Category:Created On 24/04/2023|String Metric]]
 
[[Category:Machine Translated Page|String Metric]]
 
[[Category:Missing redirects|String Metric]]
 
[[Category:Navigational boxes| ]]
 
[[Category:Navigational boxes without horizontal lists|String Metric]]
 
[[Category:Pages with math errors|String Metric]]
 
[[Category:Pages with math render errors|String Metric]]


==संदर्भ==
==संदर्भ==
Line 138: Line 141:
{{strings}}
{{strings}}


{{DEFAULTSORT:String Metric}}[[Category: स्ट्रिंग मेट्रिक्स | स्ट्रिंग मेट्रिक्स ]] [[Category: मेट्रिक्स]]
{{DEFAULTSORT:String Metric}}


 
[[Category:Articles with hatnote templates targeting a nonexistent page|String Metric]]
 
[[Category:CS1 errors|String Metric]]
[[Category: Machine Translated Page]]
[[Category:Collapse templates|String Metric]]
[[Category:Created On 24/04/2023]]
[[Category:Created On 24/04/2023|String Metric]]
[[Category:Machine Translated Page|String Metric]]
[[Category:Missing redirects|String Metric]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|String Metric]]
[[Category:Pages with math errors|String Metric]]
[[Category:Pages with script errors|String Metric]]
[[Category:Sidebars with styles needing conversion|String Metric]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats|String Metric]]
[[Category:Templates that are not mobile friendly|String Metric]]
[[Category:Templates using TemplateData|String Metric]]
[[Category:Webarchive template wayback links|String Metric]]
[[Category:Wikipedia metatemplates|String Metric]]
[[Category:मेट्रिक्स|String Metric]]
[[Category:स्ट्रिंग मेट्रिक्स| स्ट्रिंग मेट्रिक्स ]]

Latest revision as of 14:02, 1 May 2023

"स्ट्रिंग दूरी" redirects here. For वाद्य यंत्रों में तार और अंगुलियों के मध्य की दूरी, see क्रिया (संगीत).

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

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

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

स्ट्रिंग मेट्रिक्स की सूची

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

चयनित स्ट्रिंग उपाय उदाहरण

नाम विवरण उदाहरण
आलोचनात्मक दूरी केवल समान लंबाई के तार के लिए। परिवर्तित वर्णों की संख्या। "करोलिन" और "कैथरीन" 3 है।
लेवेनशेटिन दूरी और दमेरौ–लेवेनशेटिन दूरी हैमिंग दूरी का सामान्यीकरण जो अलग-अलग लंबाई के तारों की अनुमति देता है, और (डेमरौ के साथ) पारदर्शिता के लिए किटेन और सिटींग 3 की दूरी है।
  1. किटेन → सिटींग ("k" के लिए "s" का प्रतिस्थापन)
  2. सिटींग → सिटींग ("e" के लिए "i" का प्रतिस्थापन")
  3. सिटींग → सिटींग (अंत में "g" का सम्मिलन).
जारो–विंकलर दूरी जारोविंक्लरडिस्ट ("मार्था", "मार्था")=
  • मेल खाने वाले वर्णों की संख्या है;
  • पारदर्शिता की आधी संख्या है ("मार्था" [3]! =H, "मारहटा"[3]!=T).
सबसे लगातार k वर्ण सबसे फ्रीक कुंजी समानता('resea<span शैली = रंग: लाल;






संदर्भ

  1. ↑ Lu, Jiaheng; et al. (2013). "String similarity measures and joins with synonyms". Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data: 373–384. doi:10.1145/2463676.2465313. ISBN 9781450320375. S2CID 2091942.
  2. ↑ Navarro, Gonzalo (2001). "A guided tour to approximate string matching". ACM Computing Surveys. 33 (1): 31–88. doi:10.1145/375360.375365. hdl:10533/172862. S2CID 207551224.
  3. ↑ Shlomi Dolev; Mohammad, Ghanayim; Alexander, Binun; Sergey, Frenkel; Yeali, S. Sun (2017). "मैलवेयर क्लस्टरिंग और ऑनलाइन पहचान में जैककार्ड और संपादन दूरी का संबंध". 16th IEEE International Symposium on Network Computing and Applications: 369–373.
  4. ↑ 4.0 4.1 4.2 4.3 4.4 Sam's String Metrics - Computational Linguistics and Phonetics
  5. ↑ Russell, David J., et al. "A grammar-based distance metric enables fast and accurate clustering of large sets of 16S sequences." BMC bioinformatics 11.1 (2010): 1-14.
  6. ↑ Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (2003-08-01). "नाम-मिलान कार्यों के लिए स्ट्रिंग डिस्टेंस मेट्रिक्स की तुलना।": 73–78. {{cite journal}}: Cite journal requires |journal= (help)


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=स्ट्रिंग_मीट्रिक&oldid=147307’