c# - 在列表中查找不同的匹配项

Question

我有两个列表。第一个包含类似的条目

• RB 莱比锡 vs SV 达姆施塔特 98
• 柏林赫塔 vs 霍芬海姆
• ..

第二个包含基本相同的条目，但可以用不同的形式编写。例如:

• 柏林赫塔 vs TSG 霍芬海姆
• RB 莱比锡 vs 达姆施塔特 98
• ..

等等。两个列表代表相同的运动项目，但它们可以使用备用球队名称并且不会以相同的顺序出现。

我的目标(呵呵双关语)是将两个列表统一为一个并匹配相同的条目并丢弃未出现在两个列表中的条目。

我已经尝试使用 Levensthein distance和模糊搜索。我考虑过使用机器学习，但不知道如何开始。

愿意提供任何帮助和想法!

Answer 1

您可以使用 Linear Programming 解决此问题结合您已经提到的 Levenshtein 距离。线性规划是一种常用的优化技术，用于解决优化问题，例如这个问题。查看此链接以了解如何使用 Solver Foundation in C# 的示例.此示例与您遇到的具体问题无关，但它是库如何工作的一个很好的示例。

提示:您需要在 2 个列表之间的每对团队/字符串之间建立一个距离矩阵。假设两个列表都有 N 个元素。在矩阵的第 i 行中，您将有 N 个值，第 j 个值将指示第一个列表中的第 i 个元素与第二个列表中的第 j 个元素之间的编辑距离。然后，您需要设置约束。约束将是:

1. 每一行的总和需要等于1
2. 每列的总和等于1
3. 每个系数(矩阵项)需要为 0 或 1

几个月前我解决了同样的问题，这种方法对我来说非常有效。

代价函数是总和:`

sum(coef[i][j] * dist[i][j] for i in [1, n] and for j in [1, n])

`。你想最小化这个函数，因为你希望映射后 2 个集合之间的整体“距离”尽可能小。