स्ट्रिंग समानता -> लेवेनशेटिन दूरी

Question

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

CONAIR
AIRCON

एल्गोरिथ्म तो 6 अक्षरों के इस शब्द के लिए 6. की दूरी दे देंगे (: समस्या यह है कि एल्गोरिथ्म निम्न उदाहरण समान रूप नहीं मिल रहा है है आप उच्चतम अक्षरों वाले शब्द को देखते हैं), अंतर 100% => समानता 0% है।

मुझे दो स्ट्रिंग के बीच समानताएं खोजने के लिए एक रास्ता खोजने की आवश्यकता है, लेकिन मैंने पहले प्रस्तुत किए गए मामलों जैसे मामलों को भी ध्यान में रखा है।

क्या कोई बेहतर एल्गोरिदम मैं उपयोग कर सकता हूं? या आप लोग मुझे क्या सलाह देते हैं?

संपादित करें: मैंने "डेमरौ-लेवेनशेटिन" एल्गोरिदम में भी देखा है, जो पारदर्शिता जोड़ता है। समस्या यह है कि यह पारदर्शिता केवल आसन्न वर्णों के लिए हैं (और कई पात्रों के लिए नहीं)।

Answer 1

मैं इस शब्द को यूनिग्राम, बिग्राम और ट्रिग्राम में विभाजित करता हूं, फिर कोसाइन समानता की गणना करता हूं।

Answer 2

ऐसा लगता है जैसे आप अक्षर के बजाय अक्षरों या फोनेम का उपयोग करके लेवेनशेटिन दूरी करने का प्रयास करना चाह सकते हैं।

Answer 3

सैद्धांतिक रूप से, जिस दृष्टिकोण का आप उपयोग कर रहे हैं वह उस समस्या के लिए सही है जिसे आप हल करने का प्रयास कर रहे हैं। लेकिन लेवेनस्टीन केवल दो पात्रों के व्यक्तिगत पात्रों पर विचार करेगा।

स्ट्रिंग समानता Longest Common Subsequence विधि का उपयोग करके भी पाई जा सकती है और फिर आप शेष बेजोड़ पर लेवेनस्टीन देख सकते हैं।

यदि आप क्लस्टर्ड दृष्टिकोण करना चाहते हैं, तो the following answer में कुछ विवरण हैं, लेकिन जाहिर है कि इसे कार्यान्वित करना अधिक कठिन है।

Answer 4

शब्दों को सॉर्ट करना और लेवेनशेटिन ढूंढना आपके उदाहरण के लिए 100% मैच देगा लेकिन यह 100% मैच भी देगा, उदाहरण के लिए

CONAIR 
RCIAON 

जो आप चाहते हैं कि हो सकता है कि नहीं हो सकता है।

समानता को परिभाषित करने का दूसरा तरीका 2 तारों के लिए सामान्य सबस्ट्रिंग का पता लगाना होगा। आप Suffix Tree बना सकते हैं और सभी सामान्य सबस्ट्रिंग्स को ढूंढ सकते हैं और यह निर्धारित करने का प्रयास कर सकते हैं कि वे कितने समान हैं। तो आपके उदाहरण के लिए प्रत्यय पेड़ सामान्य सबस्ट्रिंग्स को CON & एआईआर के रूप में देगा जो पूरे शब्द को कवर करता है (आपके 2 तारों के लिए) और इस तरह उन्हें समान रूप से समाप्त करता है। > "Airconaircon -

Answer 5

मैं यह आसानी से (उदाहरण के लिए" Conair ") और अन्य स्ट्रिंग एक बार खुद के साथ जोड़ दिया तार में से एक पर सबसे लंबे समय तक आम सबस्ट्रिंग/Subsequence एल्गोरिथ्म रोजगार (जैसे" aircon "द्वारा हल किया जा सकता लगता है ")।सी में

नमूना कोड:

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

// Returns the length of the longest common substring (LCS) 
// between two given strings. 
// 
// This recursive implementation can be replaced by a 
// more performant dynamic programming implementation. 
size_t llcs(const char* s1, const char* s2) 
{ 
    size_t len[3]; 

    if (*s1 == '\0' || *s2 == '\0') return 0; 

    len[0] = (*s1 == *s2) + llcs(s1 + 1, s2 + 1); 
    len[1] = llcs(s1 + 1, s2); 
    len[2] = llcs(s1, s2 + 1); 

    if (len[0] < len[1]) len[0] = len[1]; 
    if (len[0] < len[2]) len[0] = len[2]; 

    return len[0]; 
} 

// Returns similarity of two given strings in the range 
// from 0.0 to 1.0 (1.0 for equal strings). 
double similarity(const char* s1, const char* s2) 
{ 
    size_t s1len = strlen(s1); 
    size_t s2len = strlen(s2); 
    double sim; 

    if (s1len == 0 && s2len == 0) 
    { 
    // Two empty strings are equal 
    sim = 1; 
    } 
    else 
    { 
    size_t len; 
    // Append s1 to itself in s1s1 (e.g. "aircon" -> "airconaircon") 
    char* s1s1 = malloc(s1len * 2 + 1); 
    strcpy(s1s1, s1); 
    strcpy(s1s1 + s1len, s1); 

    // Find the length of the LCS between s1s1 and s2 
    // (e.g. between "airconaircon" and "conair") 
    len = llcs(s1s1, s2); 
    // We need it not longer than s1 (e.g. "aircon") 
    // since we're actually comparing s1 and s2 
    if (len > s1len) len = s1len; 

    len *= 2; 

    // Prevent 100% similarity between a string and its 
    // cyclically shifted version (e.g. "aircon" and "conair") 
    if (len == s1len + s2len && strcmp(s1, s2) != 0) len--; 

    // Get the final measure of the similarity 
    sim = (double)len/(s1len + s2len); 

    free(s1s1); 
    } 

    return sim; 
} 

int main(int argc, char** argv) 
{ 
    if (argc == 3) 
    printf("Similarity of \"%s\" and \"%s\" is %.2f%%\n", 
      argv[1], argv[2], 100 * similarity(argv[1], argv[2])); 
    else 
    printf("Usage:\n %s string1 string2\n", 
      argv[0]); 
    return 0; 
} 

नमूना उत्पादन:

Similarity of "123" and "123" is 100.00% 
Similarity of "123" and "1234" is 85.71% 
Similarity of "0123" and "123" is 85.71% 
Similarity of "a" and "aa" is 66.67% 
Similarity of "aa" and "a" is 66.67% 
Similarity of "aaaaaaa" and "aaaaaa" is 92.31% 
Similarity of "aaaaaa" and "aaaaaaa" is 92.31% 
Similarity of "aircon" and "conair" is 91.67% 
Similarity of "spit" and "pits" is 87.50% 
Similarity of "pits" and "spit" is 87.50% 
Similarity of "spits" and "pits" is 88.89% 
Similarity of "pits" and "spits" is 88.89% 

Answer 6

Needleman-Wunsch, या स्मिथ-वाटरमैन एल्गोरिदम को एक नजर डालें। इन्हें डीएनए अनुक्रमों के लिए अनुकूलित संपादन दूरी के माध्यम से स्ट्रिंग मिलान को संभालने के लिए उपयोग किया जाता है, जहां किसी भी प्रकार की प्रविष्टि, रिवर्सल, ट्रांस्पॉन्स किसी भी स्थान पर हो सकती है। यह कहकर, मुझे इसे जोड़ने के लिए पर्याप्त लंबी स्ट्रिंग के लिए कोई इष्टतम समाधान नहीं है। और यह न भूलें कि संपादन लागत एल्गोरिदम (एक अर्थशास्त्र समस्या) के उपयोग-संदर्भ पर निर्भर करती है, जबकि कोई भी एल्गोरिदम हमेशा एक वाक्य रचनात्मक मशीन होता है।

Answer 7

अन्य समानता और jaro_winkler

Sorenson, Jaccard जैसे उपायों का उपयोग करके देखें व्यक्तिगत रूप से मैं के बाद से यह मेरी कई बार उद्देश्य पूरा jaro विंकलर का बहुत बड़ा प्रशंसक हूँ।

from Levenshtein import jaro_winkler 
In [2]: jaro_winkler("conair","aircon") 
Out[2]: 0.8333333333333334