作为一个潜在的复杂问题,以下是一些想法需要考虑到:
- 将每个员工的姓名拆分成字符串列表。个人而言,我可能会丢弃任何由2个或更少字母组成的内容,除非整个名字都是由这些字母组成的。这应该有助于像“De La Cruz”这样的姓氏,这些姓氏可能会被搜索为“dela cruz”。将每个员工的名称列表存储在指向该员工的字典中。
- 以与拆分列表中的名称相同的方式拆分搜索术语。对于每个搜索术语,找到具有最低Levenshtein距离的名称,然后对于每个名称,从最低开始,使用其余的搜索术语重复对该员工的其他名称进行搜索。使用查询中的每个单词重复此步骤。例如,如果查询为
John Smith
,则查找John
的最佳单词名称匹配项,然后在那些“最佳匹配”员工中为剩余名称匹配Smith
,并获取距离之和。然后查找Smith
的最佳匹配项,并在John
上匹配剩余名称,并将距离求和。最佳匹配是总距离最小的匹配。您可以通过返回前10个按总距离排序的最佳匹配项列表来提供最佳匹配。而且,数据库或搜索术语中的名称方式并不重要。实际上,它们可以完全无序,也没有关系。
- 考虑如何处理连字符名称。我可能会像没有连字符一样拆分它们。
- 考虑大/小写字符,如果您还没有考虑的话。您应该在一个大小写中存储查找,并在比较之前将搜索术语转换为相同的大小写。
- 小心带重音符号的字母,许多人在他们的名字中使用它们,例如
á
。您的算法将无法正确处理它们。如果您希望有非字母双字节字符(例如中文、日文、阿拉伯文等),则应更加小心。
将每个员工的名字拆分的另外两个好处:
- “未使用”的名字不会计入总数,因此如果我仅使用姓氏进行搜索,则不会对我在查找最短距离时造成影响。
- 沿着同样的思路,您可以应用一些额外的规则来帮助查找非标准名称。例如,连字符名称可以存储为连字符(例如
Wells-Harvey
)、复合名称(WellsHarvey
)和单独的名称(Wells
和Harvey
分开),所有这些都与同一员工相关联。任何一个名称的低距离匹配都是对该员工的低距离匹配,再次提醒,额外的名称不会计入总数。
这里有一些基本代码似乎能够工作,但它只真正考虑了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");
Console.WriteLine(string.Join("\r\n", results.Select(r => $"({r.Id}) {r.Name} Distance: {r.Distance}")));
var results = FindEmployeeByNameFuzzy("Tormin Oma");
Console.WriteLine(string.Join("\r\n", results.Select(r => $"({r.Id}) {r.Name} Distance: {r.Distance}")));
Console.Read();
}
private static void Init()
{
for (int i = 0; i < EmployeesList.Count; i++)
{
var names = EmployeesList[i].ToLower().Split(new char[] { ' ' }).ToList();
employeesById.Add(i, names);
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>();
var searchterms = query.ToLower().Split(new char[] { ' ' });
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;
foreach (var name in employeenames)
{
var distance = LevenshteinDistance.Compute(searchterm, name);
min = Math.Min(min, distance);
}
r.Distance += min;
}
results.Add(r);
}
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
{
public static int Compute(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];
}
}
}
当你开始时,只需调用Init()
,然后调用
var results = FindEmployeeByNameFuzzy(userquery)
返回一个按最佳匹配排序的有序列表。
免责声明: 这段代码不是最优的,只经过简短测试,没有检查null值,可能会出错导致程序崩溃,等等。如果你有大量员工,则可能非常缓慢。有几个改进可以进行,例如在循环Levenshtein算法时,如果距离超过当前最小距离,则可以退出循环。