24

.net に最も近い一致文字列の実装を見つけるのに問題があります

文字列のリストを一致させたいと思います。例:

入力文字列: "Publiczna Szkoła Podstawowa im. Bolesława Chrobrego w Wąsoszu"

文字列のリスト:

Publiczna Szkoła Podstawowa im. B. クロブレゴ wąsoszu

Szkoła Podstawowa Specjalna

Szkoła Podstawowa im.Henryka Sienkiewicza w Wąsoszu

Szkoła Podstawowa イム。Romualda Traugutta wąsoszu Górnym

これは明らかに「Publiczna Szkoła Podstawowa im. B. Chrobrego w Wąsoszu」と一致させる必要があります。

.net で使用できるアルゴリズムは何ですか?

4

2 に答える 2

29

距離を編集

編集距離は、1 つの文字列を別の文字列に変換するために必要な操作の最小数を数えることによって、2 つの文字列 (単語など) が互いにどの程度異なるかを定量化する方法です。

レーベンシュタイン距離

非公式に言えば、2 つの単語間のレーベンシュタイン距離は、1 つの単語を別の単語に変更するために必要な 1 文字の編集 (つまり、挿入、削除、または置換) の最小数です。

高速でメモリ効率の高いレーベンシュタイン アルゴリズム

C# レーベンシュタイン

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"));
    }
}
于 2012-12-10T00:56:55.077 に答える
23

.NET はそのままでは何も提供しません。Edit Distanceアルゴリズムを自分で実装する必要があります。たとえば、次のようにレーベンシュタイン距離を使用できます。

// This code is an implementation of the pseudocode from the Wikipedia,
// showing a naive implementation.
// You should research an algorithm with better space complexity.
public static int LevenshteinDistance(string s, string t) {
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];
    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 = (t[j - 1] == s[i - 1]) ? 0 : 1;
            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];
}

LevenshteinDistance(targetString, possible[i])for eachを呼び出し、最小値を返すi文字列を選択します。possible[i]LevenshteinDistance

于 2012-12-10T01:00:24.617 に答える