मैं अपने डेटाबेस में दूषित डेटा खोजने के लिए स्ट्रिंग समानता फ़ंक्शंस का उपयोग करना चाहता हूं।समानता एल्गोरिदम की तुलना करें
मैं:
मैं उनमें से कई पर आया जानना चाहता था कि उनके बीच क्या अंतर है और किस परिस्थितियों में वे सबसे अच्छा काम करते हैं?
इरेटा और noting some of the ground-floor literature on the comparability of algorithms that apply to similar problem spaces, में मेरी विकी-चलने वाली टिप्पणी पर विस्तार करना हम यह निर्धारित करने से पहले इन एल्गोरिदम की प्रयोज्यता का पता लगाएं कि वे संख्यात्मक रूप से तुलनीय हैं या नहीं।
विकिपीडिया से, Jaro-Winkler:
कंप्यूटर विज्ञान और सांख्यिकी में, Jaro-विंकलर दूरी (विंकलर, 1990) दो तार के बीच समानता का एक उपाय है।यह जारो दूरी मीट्रिक (जारो, 1 9 8 9, 1 99 5) और का एक रूप है जो मुख्य रूप से [उद्धरण वांछित] रिकॉर्ड लिंकेज (डुप्लिकेट पहचान) के क्षेत्र में उपयोग किया जाता है। दो तारों के लिए जारो-विंकलर दूरी जितनी अधिक होगी, उतनी ही समान तार हैं। जारो-विंकलर दूरी मीट्रिक डिज़ाइन किया गया है और व्यक्ति के नाम जैसे छोटे तारों के लिए सबसे उपयुक्त है। स्कोर सामान्यीकृत है जैसे कि 0 समानता के बराबर नहीं है और 1 सटीक मिलान है।
सूचना सिद्धांत और कंप्यूटर विज्ञान में, Levenshtein दूरी एक स्ट्रिंग दो दृश्यों के बीच अंतर की राशि को मापने के लिए मीट्रिक है। शब्द संपादित दूरी का प्रयोग अक्सर को लेवेनशेटिन दूरी पर संदर्भित करने के लिए किया जाता है।
दो तार के बीच Levenshtein दूरी स्वीकार्य संचालन संपादित किया जा रहा प्रविष्टि, हटाने या एकल वर्ण के प्रतिस्थापन के साथ, दूसरे में एक स्ट्रिंग को बदलने के लिए आवश्यक संपादन की न्यूनतम संख्या के रूप में परिभाषित किया गया है। यह व्लादिमीर Levenshtein, जो 1965.
गणित में में इस दूरी माना के नाम पर है, इयूक्लिडियन दूरी या इयूक्लिडियन मीट्रिक दो अंक के बीच "साधारण" दूरी है कि एक होगा शासक के साथ मापें, और पाइथागोरियन फॉर्मूला द्वारा दिया जाता है। इस फॉर्मूला को दूरी के रूप में उपयोग करके, यूक्लिडियन स्पेस (या यहां तक कि किसी भी आंतरिक उत्पाद स्थान) एक मीट्रिक स्पेस बन जाता है। संबंधित मानदंड को यूक्लिडियन मानदंड कहा जाता है। पुराना साहित्य मीट्रिक को पायथागोरियन मीट्रिक के रूप में संदर्भित करता है।
कम्प्यूटेशनल भाषाविज्ञान और संभावना के क्षेत्रों में, एक n ग्राम पाठ या भाषण की दी गई अनुक्रम से n मदों की एक सन्निहित अनुक्रम है। प्रश्न में आइटम फोन के अनुसार फोनेम, अक्षरों, अक्षरों, शब्द या आधार जोड़े हो सकते हैं। एन-ग्राम टेक्स्ट या भाषण कॉर्पस से एकत्र किए गए हैं।
दो प्रमुख एन-ग्राम मॉडल की लाभ (और एल्गोरिदम कि उन्हें इस्तेमाल) रिश्तेदार सादगी और ऊपर पैमाने पर करने की क्षमता है - बस बढ़ती na मॉडल के आधार पर एक साथ अधिक संदर्भ स्टोर करने के लिए इस्तेमाल किया जा सकता अच्छी तरह से स्पेस-टाइम ट्रेडऑफ समझा, छोटे प्रयोगों को को बहुत कुशलता से स्केल करने में सक्षम बनाता है।
मुसीबत इन एल्गोरिदम सभी संभव एल्गोरिदम के अंतरिक्ष के भीतर विभिन्न प्रयोज्यता longest common subsequence समस्या को हल करने के लिए है कि आपके डेटा में या एक प्रयोग करने योग्य metric उसके कलम बांधने का काम में, विभिन्न समस्याओं का समाधान है। वास्तव में, ये सभी मीट्रिक भी नहीं हैं, क्योंकि उनमें से कुछ triangle inequality को संतुष्ट नहीं करते हैं।checksums और parity bits अपने डेटा के लिए उपयोग करके:
इसके बजाय अपने रास्ते से बाहर जा रहा डेटा भ्रष्टाचार का पता लगाने के, ठीक से ऐसा करने के एक संदिग्ध योजना को परिभाषित करने की। एक आसान समाधान करने पर एक बहुत कठिन समस्या को हल करने का प्रयास न करें।
यदि आप यह सत्यापित करने का प्रयास कर रहे हैं कि कोई डेटाबेस दूषित हो गया है, तो चेकसम और समानता बिट्स का उपयोग करें। यदि आप यह पता लगाने की कोशिश कर रहे हैं कि कौन सा डेटा दूषित है, तो आपको यह पहचानने की आवश्यकता है कि आप किस प्रकार के भ्रष्टाचार को ठीक करने की कोशिश कर रहे हैं (रिकॉर्ड लिंक, प्रदूषित डेटा, गायब डेटा इत्यादि)। – Daniel
स्ट्रिंग समानता कई अलग-अलग तरीकों से मदद करती है। उदाहरण के लिए
लेकिन जैसा कि एक आकार सभी फिट नहीं है। प्रत्येक स्ट्रिंग समानता एल्गोरिदम एक विशिष्ट उपयोग के लिए डिज़ाइन किया गया है हालांकि उनमें से अधिकतर समान हैं। उदाहरण के लिए Levenshtein_distance इस बारे में है कि आप दो तारों को बराबर बनाने के लिए कितने चार बदलते हैं।
kitten → sitten
यहां दूरी 1 वर्ण परिवर्तन है। आप हटाने, जोड़ और प्रतिस्थापन के लिए अलग-अलग वजन दे सकते हैं। उदाहरण के लिए ओसीआर त्रुटियों और कीबोर्ड त्रुटियों में कुछ बदलावों के लिए कम वजन मिलता है। ओसीआर (कुछ वर्ण दूसरों के समान होते हैं), कीबोर्ड कुछ वर्ण एक-दूसरे के बहुत करीब होते हैं। जैव सूचनात्मक स्ट्रिंग समानता बहुत सम्मिलन की अनुमति देता है।
की "Jaro–Winkler दूरी मीट्रिक बनाया गया है और सबसे अच्छा ऐसे व्यक्ति के नाम के रूप संक्षिप्त स्ट्रिंग के लिए अनुकूल है"
आपका दूसरे उदाहरण इसलिए आप अपनी समस्या के बारे में अपने ध्यान में रखना चाहिए।
मैं अपने डेटाबेस में दूषित डेटा खोजने के लिए स्ट्रिंग समानता फ़ंक्शंस का उपयोग करना चाहता हूं।
आपका डेटा दूषित कैसे हुआ? क्या यह एक उपयोगकर्ता त्रुटि है, कीबोर्ड इनपुट त्रुटि के समान? या यह ओसीआर त्रुटियों के समान है? या पूरी तरह से कुछ और?
Google का * क्या आपका मतलब * स्ट्रिंग समानता का उपयोग करके गणना नहीं की जाती है। इसकी गणना उपयोगकर्ताओं द्वारा गलत टाइप करने और बाद में एक पल फिर से प्रयास करके की जाती है। [स्रोत] (http://stackoverflow.com/a/307344/1720014) – willlma
मैंने कभी "क्यू-ग्राम" के बारे में नहीं सुना है। इसके लिए कोई संदर्भ? –
यह एक ऐसा मामला है जहां विकी-पैदल [है] (http://en.wikipedia.org/wiki/Jaro%E2%80%93 विंकलर_डिस्टेंस) [ईमानदारी से] (http://en.wikipedia.org/wiki/ जारो% ई 2% 80% 93 विंकलर_डिस्टेंस) [सबसे] (http://en.wikipedia.org/wiki/Euclidean_distance) [उचित] (http://en.wikipedia.org/wiki/Q-gram) जल्दी और सुसंगत रूप से अपने प्रश्न का उत्तर दें। इस पर भी विचार करें: [शैनन एंट्रॉपी] (http://en.wikipedia.org/wiki/Shannon_entropy) या [पारस्परिक जानकारी] (http://en.wikipedia.org/wiki/Mutual_information) का उपयोग एक ह्युरिस्टिक के रूप में करते हुए। तुलना समस्या अंतरिक्ष और दक्षता से है, जिसे आप वर्णन और शरीर से प्राप्त कर सकते हैं। – MrGomez
यह एक गैर-तुच्छ गणितीय क्षेत्र है जिसके लिए किताबें लिखी जाती हैं और व्यापक शोध किया जाता है, चर्चा के योग्य जो एक ही SO उत्तर में फिट होना मुश्किल होगा। क्या आपके लिए अधिक विशिष्ट होना संभव होगा? –