vb.net 在字符串列表中查找与输入字符串最接近的匹配项

Find closest match to input string in a list of strings

提问by dasblinkenlight

I have problems finding an implementation of closest match strings for .net

我在为 .net 找到最接近匹配字符串的实现时遇到问题

I would like to match a list of strings, example:

我想匹配一个字符串列表，例如：

input string: "Publiczna Szko?a Podstawowa im. Boles?awa Chrobrego w W?soszu"

输入字符串：“Publiczna Szko？a Podstawowa im. Boles？awa Chrobrego w W？soszu”

List of strings:

字符串列表：

Publiczna Szko?a Podstawowa im. B. Chrobrego w W?soszu

Publiczna Szko？a Podstawowa im。B. Chrobrego w W?soszu

Szko?a Podstawowa Specjalna

Szko?a Podstawowa Specjalna

Szko?a Podstawowa im.Henryka Sienkiewicza w W?soszu

Szko?a Podstawowa im.Henryka Sienkiewicza w W?soszu

Szko?a Podstawowa im. Romualda Traugutta w W?soszu Górnym

Szko？a Podstawowa im。Romualda Traugutta w W?soszu Górnym

This would clearly need to be matched with "Publiczna Szko?a Podstawowa im. B. Chrobrego w W?soszu".

这显然需要与“Publiczna Szko?a Podstawowa im. B. Chrobrego w W?soszu”相匹配。

What algorithms are there available for .net?

.net 有哪些可用的算法？

回答by paparazzo

Edit distance

编辑距离

Edit distance is a way of quantifying how dissimilar two strings (e.g., words) are to one another by counting the minimum number of operations required to transform one string into the other.

编辑距离是一种通过计算将一个字符串转换为另一个字符串所需的最少操作次数来量化两个字符串（例如，单词）彼此之间的不同程度的方法。

Levenshtein distance

莱文斯坦距离

Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.

非正式地，两个单词之间的 Levenshtein 距离是将一个单词更改为另一个单词所需的最小单字符编辑（即插入、删除或替换）次数。

Fast, memory efficient Levenshtein algorithm

快速、内存高效的 Levenshtein 算法

C# Levenshtein

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"));
    }
}

回答by dasblinkenlight

.NET does not supply anything out of the box - you need to implement a an Edit Distancealgorithm yourself. For example, you can use Levenshtein Distance, like this:

.NET 不提供任何开箱即用的东西 - 您需要自己实现一个编辑距离算法。例如，您可以使用Levenshtein 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];
}

Call LevenshteinDistance(targetString, possible[i])for each i, then pick the string possible[i]for which LevenshteinDistancereturns the smallest value.

调用LevenshteinDistance(targetString, possible[i])每个i，然后选择字符串possible[i]为其LevenshteinDistance返回最小值。