स्ट्रिंग मीट्रिक: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
|क्रिया (संगीत)}} | |क्रिया (संगीत)}} | ||
गणित और [[कंप्यूटर विज्ञान]] में, | गणित और [[कंप्यूटर विज्ञान]] में, स्ट्रिंग मीट्रिक (जिसे स्ट्रिंग समानता मीट्रिक या स्ट्रिंग [[दूरी]] फ़ंक्शन के रूप में भी जाना जाता है) ऐसा [[मीट्रिक (गणित)]] है जो अनुमानित [[स्ट्रिंग मिलान]] या तुलना के लिए दो [[स्ट्रिंग (कंप्यूटर विज्ञान)]] के मध्य की दूरी (प्रतिलोम समानता) को मापता है। स्ट्रिंग ''मीट्रिक'' की आवश्यकता (उदाहरण के लिए स्ट्रिंग मिलान के विपरीत) के लिए स्ट्रिंग मिलान के त्रिकोण असमानता की पूर्ति है। उदाहरण के लिए, तार सैम और सैमुअल को समीप माना जा सकता है।<ref>{{cite journal | ||
| last = Lu | | last = Lu | ||
| first = Jiaheng |display-authors=etal | | first = Jiaheng |display-authors=etal | ||
| Line 11: | 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 | ||
| last = Navarro | | last = Navarro | ||
| first = Gonzalo | | first = Gonzalo | ||
| Line 23: | 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> और सिमेंटिक नॉलेज [[ज्ञान एकीकरण|इंटीग्रेशन]] आदि। | ||
== स्ट्रिंग मेट्रिक्स की सूची == | == स्ट्रिंग मेट्रिक्स की सूची == | ||
| Line 42: | Line 42: | ||
* हेलिंजर दूरी या [[भट्टाचार्य दूरी]] | * हेलिंजर दूरी या [[भट्टाचार्य दूरी]] | ||
* [[सूचना त्रिज्या]] (जेन्सेन-शैनन विचलन) | * [[सूचना त्रिज्या]] (जेन्सेन-शैनन विचलन) | ||
* [[तिरछा विचलन]]<ref name="sam"/>* [[भ्रम की संभावना]]<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> | * 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>{{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> | ||
ऐसे कार्य भी मौजूद हैं जो तारों के | ऐसे कार्य भी मौजूद हैं जो तारों के मध्य असमानता को मापते हैं, लेकिन जरूरी नहीं कि त्रिकोण असमानता को पूरा करें, और जैसे कि गणितीय अर्थ में मीट्रिक नहीं हैं। जारो-विंकलर दूरी इस तरह के फ़ंक्शन का उदाहरण है। | ||
== चयनित स्ट्रिंग उपाय उदाहरण == | == चयनित स्ट्रिंग उपाय उदाहरण == | ||
Revision as of 01:53, 28 April 2023
गणित और कंप्यूटर विज्ञान में, स्ट्रिंग मीट्रिक (जिसे स्ट्रिंग समानता मीट्रिक या स्ट्रिंग दूरी फ़ंक्शन के रूप में भी जाना जाता है) ऐसा मीट्रिक (गणित) है जो अनुमानित स्ट्रिंग मिलान या तुलना के लिए दो स्ट्रिंग (कंप्यूटर विज्ञान) के मध्य की दूरी (प्रतिलोम समानता) को मापता है। स्ट्रिंग मीट्रिक की आवश्यकता (उदाहरण के लिए स्ट्रिंग मिलान के विपरीत) के लिए स्ट्रिंग मिलान के त्रिकोण असमानता की पूर्ति है। उदाहरण के लिए, तार सैम और सैमुअल को समीप माना जा सकता है।[1] स्ट्रिंग मीट्रिक संख्या प्रदान करता है जो दूरी के एल्गोरिथम-विशिष्ट संकेत को दर्शाता है।
सबसे व्यापक रूप से ज्ञात स्ट्रिंग मीट्रिक अल्प विकसित है जिसे लेवेनशेटिन दूरी (जिसे संपादन दूरी भी कहा जाता है) कहा जाता है।[2] यह दो इनपुट स्ट्रिंग्स के मध्य संचालित होता है, इनपुट स्ट्रिंग को दूसरे में परिवर्तित करने के लिए आवश्यक प्रतिस्थापन और विलोपन की संख्या के समान संख्या लौटाता है। सरलीकृत स्ट्रिंग मेट्रिक्स जैसे कि लेवेनशेटिन दूरी का विस्तार ध्वन्यात्मक, टोकन (पार्सर), व्याकरणिक और सांख्यिकीय तुलना के चरित्र-आधारित विधियों को सम्मिलित करने के लिए किया गया है।
सूचना एकीकरण में स्ट्रिंग मेट्रिक्स का अत्यधिक उपयोग किया जाता है और वर्तमान में धोखाधड़ी ज्ञात करने के लिए, फिंगरप्रिंट विश्लेषण, साहित्यिक चोरी को ज्ञात करने के लिए, ऑन्कोलॉजी मर्जिंग, डीएनए विश्लेषण, आरएनए विश्लेषण, छवि विश्लेषण, साक्ष्य-आधारित यंत्र अधिगम, डेटाबेस डेटा डिडुप्लीकेशन, डेटा माइनिंग, वृद्धिशील सहित क्षेत्रों में उपयोग किया जाता है। खोज, डेटा एकीकरण, मालवेयर डिटेक्शन, [3] और सिमेंटिक नॉलेज इंटीग्रेशन आदि।
स्ट्रिंग मेट्रिक्स की सूची
- लेवेनशेटिन दूरी, या इसका सामान्यीकरण संपादन दूरी
- डमेराउ-लेवेनशेटिन दूरी
- सोरेनसेन-डाइस गुणांक
- ब्लॉक दूरी या L1 दूरी या शहर ब्लॉक दूरी
- हैमिंग दूरी
- सरल मिलान गुणांक (एसएमसी)
- जैकार्ड समानता या जैकार्ड गुणांक या टैनिमोटो गुणांक
- टावर्सकी इंडेक्स
- ओवरलैप गुणांक
- परिवर्तनशील दूरी[4]
- हेलिंजर दूरी या भट्टाचार्य दूरी
- सूचना त्रिज्या (जेन्सेन-शैनन विचलन)
- तिरछा विचलन[4]* भ्रम की संभावना[4]* केंडल ताऊ दूरी, कुल्बैक-लीब्लर विचलन का अनुमान
- Fellegi और Sunters मेट्रिक (SFS)[4]* अधिकतम मिलान[4]* व्याकरण आधारित दूरी[5]
- टीएफ-आईडीएफ दूरी मीट्रिक[6]
ऐसे कार्य भी मौजूद हैं जो तारों के मध्य असमानता को मापते हैं, लेकिन जरूरी नहीं कि त्रिकोण असमानता को पूरा करें, और जैसे कि गणितीय अर्थ में मीट्रिक नहीं हैं। जारो-विंकलर दूरी इस तरह के फ़ंक्शन का उदाहरण है।
चयनित स्ट्रिंग उपाय उदाहरण
| नाम | विवरण | उदाहरण |
|---|---|---|
| आलोचनात्मक दूरी | केवल समान लंबाई के तार के लिए। परिवर्तित वर्णों की संख्या। | "करोलिन" और "कैथरीन" 3 है। |
| लेवेनशेटिन दूरी और दमेरौ–लेवेनशेटिन दूरी | हैमिंग दूरी का सामान्यीकरण जो अलग-अलग लंबाई के तारों की अनुमति देता है, और (डेमरौ के साथ) पारदर्शिता के लिए | किटेन और सिटींग 3 की दूरी है।
|
| जारो–विंकलर दूरी | जारोविंक्लरडिस्ट ("मार्था", "मार्था")=
| |
| सबसे लगातार k वर्ण | सबसे फ्रीक कुंजी समानता('resea<span शैली = रंग: लाल; |
संदर्भ
- ↑ 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.
- ↑ 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.
- ↑ Shlomi Dolev; Mohammad, Ghanayim; Alexander, Binun; Sergey, Frenkel; Yeali, S. Sun (2017). "मैलवेयर क्लस्टरिंग और ऑनलाइन पहचान में जैककार्ड और संपादन दूरी का संबंध". 16th IEEE International Symposium on Network Computing and Applications: 369–373.
- ↑ 4.0 4.1 4.2 4.3 4.4 Sam's String Metrics - Computational Linguistics and Phonetics
- ↑ 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.
- ↑ Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (2003-08-01). "नाम-मिलान कार्यों के लिए स्ट्रिंग डिस्टेंस मेट्रिक्स की तुलना।": 73–78.
{{cite journal}}: Cite journal requires|journal=(help)
बाहरी संबंध
- String Similarity Metrics for Information Integration A fairly complete overview Archive index at the Wayback Machine
- Carnegie Mellon University open source library
- 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
