두 문자열의 유사성을 어떻게 측정 할 수 있습니까?

두 문자열의 유사성을 어떻게 측정 할 수 있습니까?

---

두 개의 문자열이 주어 text1지고text2

public SOMEUSABLERETURNTYPE Compare(string text1, string text2)
{
     // DO SOMETHING HERE TO COMPARE
}

예 :

1. 첫 번째 문자열 : StackOverflow

   두 번째 문자열 : StaqOverflow

   귀국 : 유사성은 91 %입니다.

   수익은 % 또는 그와 비슷한 것일 수 있습니다.

2. 첫 번째 문자열 : 간단한 텍스트 테스트

   두 번째 문자열 : 복잡한 텍스트 테스트

   반환 : 값이 동일한 것으로 간주 될 수 있습니다.

어떤 아이디어? 이를 수행하는 가장 좋은 방법은 무엇입니까?

---

이를 수행하는 다양한 방법이 있습니다. 알고리즘이있는 다른 페이지에 대한 링크 는 Wikipedia "문자열 유사성 측정"페이지 를 참조하십시오 .

나는 이러한 알고리즘 중 어떤 것도 소리를 고려 하지 않는다고 생각 합니다. 그래서 "staq overflow"는 발음면에서 더 유사 함에도 불구하고 "stack overflow"만큼 "stack overflow"와 유사 할 것입니다.

좀 더 많은 옵션을 제공하는 다른 페이지 를 방금 찾았 습니다. 특히 Soundex 알고리즘 ( Wikipedia )이 당신이 추구 하는 것에 더 가까울 수 있습니다.

---

Levenshtein 거리는 아마도 당신이 찾고있는 것입니다.

---

다음은 내가 작업중인 프로젝트를 위해 작성한 코드입니다. 문자열의 유사성 비율과 문자열의 단어를 기반으로 한 유사성 비율을 알아야합니다. 마지막으로, 가장 작은 문자열의 단어 유사성 비율 (따라서 모든 단어가 존재하고 큰 문자열에서 일치하면 결과는 100 %가 됨)과 더 큰 문자열의 단어 유사성 비율 (RealWordsRatio라고 부릅니다)을 모두 알고 싶습니다. ). Levenshtein 알고리즘을 사용하여 거리를 찾습니다. 지금까지 코드는 최적화되지 않았지만 예상대로 작동합니다. 도움이 되셨기를 바랍니다.

public static int Compute(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        // Step 1
        if (n == 0)
        {
            return m;
        }

        if (m == 0)
        {
            return n;
        }

        // Step 2
        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        // Step 3
        for (int i = 1; i <= n; i++)
        {
            //Step 4
            for (int j = 1; j <= m; j++)
            {
                // Step 5
                int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                // Step 6
                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        // Step 7
        return d[n, m];
    }

double GetSimilarityRatio(String FullString1, String FullString2, out double WordsRatio, out double RealWordsRatio)
    {
        double theResult = 0;
        String[] Splitted1 = FullString1.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries);
        String[] Splitted2 = FullString2.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries);
        if (Splitted1.Length < Splitted2.Length)
        {
            String[] Temp = Splitted2;
            Splitted2 = Splitted1;
            Splitted1 = Temp;
        }
        int[,] theScores = new int[Splitted1.Length, Splitted2.Length];//Keep the best scores for each word.0 is the best, 1000 is the starting.
        int[] BestWord = new int[Splitted1.Length];//Index to the best word of Splitted2 for the Splitted1.

        for (int loop = 0; loop < Splitted1.Length; loop++) 
        {
            for (int loop1 = 0; loop1 < Splitted2.Length; loop1++) theScores[loop, loop1] = 1000;
            BestWord[loop] = -1;
        }
        int WordsMatched = 0;
        for (int loop = 0; loop < Splitted1.Length; loop++)
        {
            String String1 = Splitted1[loop];
            for (int loop1 = 0; loop1 < Splitted2.Length; loop1++)
            {
                String String2 = Splitted2[loop1];
                int LevenshteinDistance = Compute(String1, String2);
                theScores[loop, loop1] = LevenshteinDistance;
                if (BestWord[loop] == -1 || theScores[loop, BestWord[loop]] > LevenshteinDistance) BestWord[loop] = loop1;
            }
        }

        for (int loop = 0; loop < Splitted1.Length; loop++)
        {
            if (theScores[loop, BestWord[loop]] == 1000) continue;
            for (int loop1 = loop + 1; loop1 < Splitted1.Length; loop1++)
            {
                if (theScores[loop1, BestWord[loop1]] == 1000) continue;//the worst score available, so there are no more words left
                if (BestWord[loop] == BestWord[loop1])//2 words have the same best word
                {
                    //The first in order has the advantage of keeping the word in equality
                    if (theScores[loop, BestWord[loop]] <= theScores[loop1, BestWord[loop1]])
                    {
                        theScores[loop1, BestWord[loop1]] = 1000;
                        int CurrentBest = -1;
                        int CurrentScore = 1000;
                        for (int loop2 = 0; loop2 < Splitted2.Length; loop2++)
                        {
                            //Find next bestword
                            if (CurrentBest == -1 || CurrentScore > theScores[loop1, loop2])
                            {
                                CurrentBest = loop2;
                                CurrentScore = theScores[loop1, loop2];
                            }
                        }
                        BestWord[loop1] = CurrentBest;
                    }
                    else//the latter has a better score
                    {
                        theScores[loop, BestWord[loop]] = 1000;
                        int CurrentBest = -1;
                        int CurrentScore = 1000;
                        for (int loop2 = 0; loop2 < Splitted2.Length; loop2++)
                        {
                            //Find next bestword
                            if (CurrentBest == -1 || CurrentScore > theScores[loop, loop2])
                            {
                                CurrentBest = loop2;
                                CurrentScore = theScores[loop, loop2];
                            }
                        }
                        BestWord[loop] = CurrentBest;
                    }

                    loop = -1;
                    break;//recalculate all
                }
            }
        }
        for (int loop = 0; loop < Splitted1.Length; loop++)
        {
            if (theScores[loop, BestWord[loop]] == 1000) theResult += Splitted1[loop].Length;//All words without a score for best word are max failures
            else
            {
                theResult += theScores[loop, BestWord[loop]];
                if (theScores[loop, BestWord[loop]] == 0) WordsMatched++;
            }
        }
        int theLength = (FullString1.Replace(" ", "").Length > FullString2.Replace(" ", "").Length) ? FullString1.Replace(" ", "").Length : FullString2.Replace(" ", "").Length;
        if(theResult > theLength) theResult = theLength;
        theResult = (1 - (theResult / theLength)) * 100;
        WordsRatio = ((double)WordsMatched / (double)Splitted2.Length) * 100;
        RealWordsRatio = ((double)WordsMatched / (double)Splitted1.Length) * 100;
        return theResult;
    }

---

한동안 C # 으로 Double Metaphone 구현을 작성했습니다 . Soundex 등보다 훨씬 우수하다는 것을 알게 될 것입니다.

Levenshtein distance has also been suggested, and it's a great algorithm for a lot of uses, but phonetic matching is not really what it does; it only seems that way sometimes because phonetically similar words are also usually spelled similarly. I did an analysis of various fuzzy matching algorithms which you might also find useful.

---

To deal with 'sound alikes' you may want to look into encoding using a phonetic algorithm like Double Metaphone or soundex. I don't know if computing Levenshtein distances on phonetic encoded strings would be beneficial or not, but might be a possibility. Alternately, you could use a heuristic like: convert each word in the string to its encoded form and remove any words that occur in both strings and replace them with a single representation before computing the Levenshtein distance.

---

You might look for string "distances", for example the Levenshtein distance.

---

Perl module Text::Phonetic has implementations of various algorithms.

---

Jeff Atwood wrote about looking for a similar solution for determining the authorship of wiki posts which may help you narrow your search.

---

If you're comparing values in a SQL database you can use the SOUNDEX function. If you query Google for SOUNDEX and C#, some people have written a similar function for that and VB.

---

I have to recommend Soundex too, I have used it in the past to process misspelt city names. Here is a good link for usage: http://whitepapers.zdnet.com/abstract.aspx?docid=352953

---

If you want to compare phonetically, check out the Soundex and Metaphone algorithms: http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex

---

Metaphone 3 is the third generation of the Metaphone algorithm. It increases the accuracy of phonetic encoding from the 89% of Double Metaphone to 98%, as tested against a database of the most common English words, and names and non-English words familiar in North America. This produces an extremely reliable phonetic encoding for American pronunciations.

Metaphone 3 was designed and developed by Lawrence Philips, who designed and developed the original Metaphone and Double Metaphone algorithms.

ReferenceURL : https://stackoverflow.com/questions/1034622/how-can-i-measure-the-similarity-between-2-strings