为反向字符串组合实现 Levenshtein 距离？

Question

我的应用程序中有一个员工列表。每个员工都有名字和姓氏，所以我有一个元素列表，如：

["Jim Carry", "Uma Turman", "Bill Gates", "John Skeet"]

我希望我的客户能够使用模糊搜索算法按姓名搜索员工。例如，如果用户输入 "Yuma Turmon"，最接近的元素 - "Uma Turman" 将是 return。我使用 Levenshtein 距离算法，我发现 here.

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];
    }
}

我在员工姓名列表上重复用户输入（全名）并比较距离。例如，如果低于 3，我 return 找到了员工。

现在我希望允许用户通过颠倒的名字进行搜索 - 例如，如果用户输入 "Turmon Uma" 它将 return "Uma Turman"，因为实际距离是 1，因为名字Last name 与 Last name 和 First name 相同。我的算法现在将它算作不同的字符串，距离很远。我如何修改它，以便无论顺序如何都能找到名称？

Answer 1

您可以使用 LINQ 创建员工姓名的反转版本。例如，如果您有一个员工列表，例如

x = ["Jim Carry", "Uma Turman", "Bill Gates", "John Skeet"]

你可以编写如下代码：

var reversedNames = x.Select(p=> $"{p.Split(' ')[1] p.Split(' ')[0]}");

它将return反转版本，如：

xReversed = ["Carry Jim", "Turman Uma", "Gates Bill", "Skeet John"]

然后用这个数据重复你的算法。

Answer 2

一些想法，因为这是一个可能很复杂的问题：

将每个员工姓名拆分为一个字符串列表。就个人而言，我可能会丢弃任何包含 2 个或更少字母的内容，除非这就是名称的全部组成部分。这应该有助于像 "De La Cruz" 这样的姓氏，它可能会被搜索为 "dela cruz"。将每个员工的姓名列表存储在指向该员工的字典中。
按照您在列表中拆分名称的方式拆分搜索词。对于每个搜索词，找到具有最小 Levenshtein 距离的姓名，然后对于每个人，从最小的开始，用其余搜索词针对该员工的其他姓名重复搜索。对查询中的每个词重复此步骤。例如，如果查询是 John Smith，找到 John 的最佳单个单词名称匹配，然后匹配 Smith 上 "best match" 名员工的剩余名称，并得到总和的距离。然后找到 Smith 的最佳匹配项并匹配 John 上的剩余名称，然后对距离求和。最佳匹配是总距离最小的匹配。您可以通过 return 前 10 个（例如，按总距离排序）来提供最佳匹配列表。数据库中的名称或搜索词采用哪种方式并不重要。事实上，它们可能完全失灵，但这无关紧要。
考虑如何处理带连字符的名称。我可能会将它们分开，就好像它们没有连字符一样。
考虑 upper/lower 个大小写字符，如果您还没有的话。您应该将查找存储在一种情况下，并在比较之前将搜索词转换为相同的情况。
注意重音字母，很多人的名字里都有，比如á。您的算法无法与它们一起正常工作。如果您希望有 non-alpha 个双字节字符，请更加小心，例如。中文、日文、阿拉伯文等

拆分每个员工的姓名还有两个好处：

"Unused" 名字不计入总数，所以如果我只使用姓氏搜索，它不会影响我找到最短距离。
按照同样的思路，您可以应用一些额外的规则来帮助查找 non-standard 名称。例如，带连字符的名称可以存储为连字符（例如 Wells-Harvey）、复合名称（WellsHarvey）和个人名称（Wells 和 Harvey 分开），所有这些都反对同一个员工。任何一个名字的 low-distance 匹配是雇员的 low-distance 匹配，额外的名字不计入总数。

下面是一些似乎有效的基本代码，但它只真正考虑了第 1、2 和 4 点：

using System;
using System.Collections.Generic;
using System.Linq;

namespace EmployeeSearch
{
    static class Program
    {
        static List<string> EmployeesList = new List<string>() { "Jim Carrey", "Uma Thurman", "Bill Gates", "Jon Skeet" };
        static Dictionary<int, List<string>> employeesById = new Dictionary<int, List<string>>();
        static Dictionary<string, List<int>> employeeIdsByName = new Dictionary<string, List<int>>();

        static void Main()
        {
            Init();
            var results = FindEmployeeByNameFuzzy("Umaa Thurrmin");
            // Returns:
            // (1) Uma Thurman  Distance: 3
            // (0) Jim Carrey  Distance: 10
            // (3) Jon Skeet  Distance: 11
            // (2) Bill Gates  Distance: 12
            Console.WriteLine(string.Join("\r\n", results.Select(r => $"({r.Id}) {r.Name}  Distance: {r.Distance}")));

            var results = FindEmployeeByNameFuzzy("Tormin Oma");
            // Returns:
            // (1) Uma Thurman  Distance: 4
            // (3) Jon Skeet  Distance: 7
            // (0) Jim Carrey  Distance: 8
            // (2) Bill Gates  Distance: 9
            Console.WriteLine(string.Join("\r\n", results.Select(r => $"({r.Id}) {r.Name}  Distance: {r.Distance}")));


            Console.Read();
        }

        private static void Init() // prepare our lists
        {
            for (int i = 0; i < EmployeesList.Count; i++)
            {
                // Preparing the list of names for each employee - add special cases such as hyphenation here as well
                var names = EmployeesList[i].ToLower().Split(new char[] { ' ' }).ToList();
                employeesById.Add(i, names);

                // This is not used here, but could come in handy if you want a unique index of names pointing to employee ids for optimisation:
                foreach (var name in names)
                {
                    if (employeeIdsByName.ContainsKey(name))
                    {
                        employeeIdsByName[name].Add(i);
                    }
                    else
                    {
                        employeeIdsByName.Add(name, new List<int>() { i });
                    }
                }
            }

        }

        private static List<SearchResult> FindEmployeeByNameFuzzy(string query)
        {
            var results = new List<SearchResult>();

            // Notice we're splitting the search terms the same way as we split the employee names above (could be refactored out into a helper method)
            var searchterms = query.ToLower().Split(new char[] { ' ' });

            // Comparison with each employee
            for (int i = 0; i < employeesById.Count; i++)
            {
                var r = new SearchResult() { Id = i, Name = EmployeesList[i] };
                var employeenames = employeesById[i];
                foreach (var searchterm in searchterms)
                {
                    int min = searchterm.Length;

                    // for each search term get the min distance for all names for this employee
                    foreach (var name in employeenames)
                    {
                        var distance = LevenshteinDistance.Compute(searchterm, name);
                        min = Math.Min(min, distance);
                    }

                    // Sum the minimums for all search terms
                    r.Distance += min;
                }
                results.Add(r);
            }

            // Order by lowest distance first
            return results.OrderBy(e => e.Distance).ToList();
        }
    }

    public class SearchResult
    {
        public int Distance { get; set; }
        public int Id { get; set; }
        public string Name { get; set; }
    }

    public 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];
        }
    }
}

开始时直接调用Init()，然后调用

var results = FindEmployeeByNameFuzzy(userquery);

到return最佳匹配的有序列表。

免责声明：此代码不是最佳代码，仅经过简单测试，不检查空值，可能会爆炸并杀死一只小猫，等等。如果您有大量员工，那么这可能会非常慢。可以进行多项改进，例如，当循环 Levenshtein 算法时，如果距离超过当前最小距离，您可以退出。

为反向字符串组合实现 Levenshtein 距离？

Implementing Levenstein distance for reversed string combination?

c#

search

levenshtein-distance