c# - 为反向字符串组合实现莱文斯坦距离?
问题描述
我的应用程序中有一个员工列表。每个员工都有名字和姓氏,所以我有一个元素列表,例如:
["Jim Carry", "Uma Turman", "Bill Gates", "John Skeet"]
我希望我的客户具有使用模糊搜索算法按姓名搜索员工的功能。例如,如果用户输入“Yuma Turmon”,则最接近的元素 - “Uma Turman”将返回。我使用 Levenshtein 距离算法,我在这里找到。
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,我返回找到的员工。
现在我希望允许用户通过反向名称搜索 - 例如,如果用户输入“Turmon Uma”,它将返回“Uma Turman”,因为实际距离是 1,因为名字和姓氏与姓氏和名字相同姓名。我的算法现在将其视为不同的字符串,距离很远。如何修改它以便无论顺序如何都能找到名称?
解决方案
您可以使用 LINQ 创建员工姓名的反转版本。例如,如果您有一个员工列表,例如
x = ["Jim Carry", "Uma Turman", "Bill Gates", "John Skeet"]
您可以编写以下代码:
var reversedNames = x.Select(p=> $"{p.Split(' ')[1] p.Split(' ')[0]}");
它将返回相反的版本,例如:
xReversed = ["Carry Jim", "Turman Uma", "Gates Bill", "Skeet John"]
然后用这个数据重复你的算法。
推荐阅读
- android - 使用两个按钮启动、停止和重新启动 TimerTask
- pandas - Pandas 将列值转换为列
- next.js - 如何在不使用 +150k 静态页面重建应用的情况下添加新页面?
- jquery - 使用 seiyria 的 bootstrap-slider 根据输入值调整范围
- c - C 语言中的 open() 是跨平台的吗?
- c - 如何将我的字符串转换为小写?
- c++ - 从分离的翻译单元混合非终端规则
- javascript - Vue js,axios GET localhost > cors 策略“访问 XMLHttpRequest”
- linux - awk :: 不区分大小写以在 2 个文件中查找常用词
- python - 不和谐.py | 尝试 dm 用户并获取 AttributeError: 'NoneType' 对象没有属性 'send'