허용 오차가있는 문자열 비교

허용 오차가있는 문자열 비교

---

문자열을 문자열 배열과 비교하는 방법을 찾고 있습니다. 물론 정확한 검색을 수행하는 것은 매우 쉽지만 내 프로그램이 철자 오류, 문자열의 일부 누락 등을 허용하기를 원합니다.

그러한 검색을 수행 할 수있는 어떤 종류의 프레임 워크가 있습니까? 검색 알고리즘이 일치 비율 또는 이와 비슷한 몇 가지 결과 순서를 반환한다는 점을 염두에두고 있습니다.

---

Levenshtein Distance 알고리즘을 사용할 수 있습니다 .

"두 문자열 사이의 Levenshtein 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 수로 정의되며 허용 가능한 편집 작업은 단일 문자의 삽입, 삭제 또는 대체입니다." -Wikipedia.com

이것은 dotnetperls.com 에서 가져온 것입니다 .

using System;

/// <summary>
/// Contains approximate string matching
/// </summary>
static class LevenshteinDistance
{
    /// <summary>
    /// Compute the distance between two strings.
    /// </summary>
    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];
    }
}

class Program
{
    static void Main()
    {
        Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant"));
        Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha"));
        Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax"));
    }
}

실제로 Damerau-Levenshtein 거리 알고리즘 을 사용하는 것을 선호 할 수 있습니다.이 알고리즘 은 문자를 전치 할 수도 있습니다. 이는 데이터 입력에서 흔히 발생하는 인적 오류입니다. 여기 에서 C # 구현을 찾을 수 있습니다 .

---

.NET 프레임 워크에는 이러한 기본 제공에 도움이되는 것이 없습니다.

가장 일반적인 철자 오류는 글자가 단어의 적절한 음성 표현이지만 단어의 정확한 철자가 아닌 경우입니다.

예를 들어, 단어 sword와 sord(예, 그것은 단어입니다)가 같은 발음 어근을 가지고 있다고 주장 할 수 있습니다 (당신이 발음 할 때 같은 소리).

즉, 단어 (철자가 틀린 단어도 포함)를 음성 변형으로 번역하는 데 사용할 수있는 알고리즘이 많이 있습니다.

첫 번째는 Soundex 입니다. 구현이 매우 간단하며이 알고리즘 의 .NET 구현이 상당히 많습니다 . 다소 간단하지만 서로 비교할 수있는 실제 값을 제공합니다.

다른 하나는 Metaphone 입니다. Metaphone의 네이티브 .NET 구현을 찾을 수는 없지만 제공된 링크에는 변환 할 수있는 여러 다른 구현에 대한 링크가 있습니다. 변환하기 가장 쉬운 방법은 아마도 Metaphone 알고리즘 의 Java 구현 일 것입니다 .

It should be noted that the Metaphone algorithm has gone through revisions. There is Double Metaphone (which has a .NET implementation) and Metaphone 3. Metaphone 3 is a commercial application, but has a 98% accuracy rate compared to an 89% accuracy rate for the Double Metaphone algorithm when run against a database of common English words. Depending on your need, you might want to look for (in the case of Double Metaphone) or purchase (in the case of Metaphone 3) the source for the algorithm and convert or access it through the P/Invoke layer (there are C++ implementations abound).

Metaphone과 Soundex는 Soundex가 고정 길이 숫자 키를 생성하는 반면 Metaphone은 길이가 다른 키를 생성한다는 점에서 차이가 있으므로 결과가 다릅니다. 결국, 둘 다 동일한 종류의 비교를 수행 할 것입니다. 요구 사항과 리소스 (물론 철자 오류에 대한 편협 수준)를 감안할 때 자신의 요구에 가장 적합한 것을 찾아 내면됩니다.

---

다음은 동일한 결과를 생성하면서 훨씬 적은 메모리를 사용하는 LevenshteinDistance 메서드의 구현입니다. 이 위키피디아 기사 에서 "행렬이 두 개인 반복"제목 아래 에있는 의사 코드를 C #으로 수정 한 것입니다 .

public static int LevenshteinDistance(string source, string target)
{
    // degenerate cases
    if (source == target) return 0;
    if (source.Length == 0) return target.Length;
    if (target.Length == 0) return source.Length;

    // create two work vectors of integer distances
    int[] v0 = new int[target.Length + 1];
    int[] v1 = new int[target.Length + 1];

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for (int i = 0; i < v0.Length; i++)
        v0[i] = i;

    for (int i = 0; i < source.Length; i++)
    {
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i+1][0]
        //   edit distance is delete (i+1) chars from s to match empty t
        v1[0] = i + 1;

        // use formula to fill in the rest of the row
        for (int j = 0; j < target.Length; j++)
        {
            var cost = (source[i] == target[j]) ? 0 : 1;
            v1[j + 1] = Math.Min(v1[j] + 1, Math.Min(v0[j + 1] + 1, v0[j] + cost));
        }

        // copy v1 (current row) to v0 (previous row) for next iteration
        for (int j = 0; j < v0.Length; j++)
            v0[j] = v1[j];
    }

    return v1[target.Length];
}

다음은 유사성 비율을 제공하는 함수입니다.

/// <summary>
/// Calculate percentage similarity of two strings
/// <param name="source">Source String to Compare with</param>
/// <param name="target">Targeted String to Compare</param>
/// <returns>Return Similarity between two strings from 0 to 1.0</returns>
/// </summary>
public static double CalculateSimilarity(string source, string target)
{
    if ((source == null) || (target == null)) return 0.0;
    if ((source.Length == 0) || (target.Length == 0)) return 0.0;
    if (source == target) return 1.0;

    int stepsToSame = LevenshteinDistance(source, target);
    return (1.0 - ((double)stepsToSame / (double)Math.Max(source.Length, target.Length)));
}

---

Your other option is to compare phonetically using Soundex or Metaphone. I just completed an article that presents C# code for both algorithms. You can view it at http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex.

---

Here are two methods that calculate the Levenshtein Distance between strings.

The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.

Once you have the result, you'll need to define what value you want to use as a threshold for a match or not. Run the function on a bunch of sample data to get a good idea of how it works to help decide on your particular threshold.

    /// <summary>
    /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second.
    /// </summary>
    /// <param name="first">The first string, used as a source.</param>
    /// <param name="second">The second string, used as a target.</param>
    /// <returns>The number of changes that need to be made to convert the first string to the second.</returns>
    /// <remarks>
    /// From http://www.merriampark.com/ldcsharp.htm
    /// </remarks>
    public static int LevenshteinDistance(string first, string second)
    {
        if (first == null)
        {
            throw new ArgumentNullException("first");
        }
        if (second == null)
        {
            throw new ArgumentNullException("second");
        }

        int n = first.Length;
        int m = second.Length;
        var d = new int[n + 1, m + 1]; // matrix

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

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

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

        for (int i = 1; i <= n; i++)
        {

            for (int j = 1; j <= m; j++)
            {
                int cost = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // cost
                d[i, j] = Math.Min(
                    Math.Min(
                        d[i - 1, j] + 1,
                        d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }

        return d[n, m];
    }

---

You can find implementations of soundex and the levenshtein distance algorithms in the open source CommonLibrary.NET project.

참고URL : https://stackoverflow.com/questions/2344320/comparing-strings-with-tolerance