在列表中查找不同的匹配条目
Find matching entries in list which are different
我有 两个列表。第一个包含条目
- RB 莱比锡 vs SV 达姆施塔特 98
- 柏林赫塔 vs 霍芬海姆
- ..
第二个包含基本相同的条目，但可以用不同的形式编写。例如：
- 柏林赫塔 vs TSG 霍芬海姆
- RB 莱比锡 vs 达姆施塔特 98
- ..
等等。两个列表代表相同的运动项目，但它们可以使用备用球队名称并且不以相同的顺序出现。
我的目标（呵呵双关语）是将两个列表统一为一个并匹配相同的条目并丢弃未出现在两个列表中的条目。
我已经尝试使用 Levensthein distance 和模糊搜索。
我考虑过使用机器学习，但不知道如何开始。
希望得到任何帮助和想法！
您可以使用 BK-tree (I googled C# implementations and found two: 1, 2)。使用 Levenshtein 距离作为度量。或者，从列表中的名称中删除全部大写的子字符串以改进指标（请注意，这不会意外地为名称留下空字符串）。
1. Put the names from the first list in the BK-tree
2. Look up the names from the second list in the BK-tree
a. Assign an integer token to the name pair, stored in a Map<Integer, Tuple<String, String>>
b. Replace each team name with the token
3. Sort each token pair (so [8 vs 4] becomes [4 vs 8])
4. Sort each list by its first token in the token pair,
then by the second token in the token pair (so the list
would look like [[1 vs 2], [1 vs 4], [2 vs 4]])
现在您只需遍历两个列表
int i1 = 0
int i2 = 0
while(i1 < list1.length && i2 < list2.length) {
if(list1[i1].first == list2[i2].first && list1[i1].second == list2[i2].second) {
// match
i1++
i2++
} else if(list1[i1].first < list2[i2].first) {
i1++
} else if(list1[i1].first > list2[i2].first) {
i2++
} else if(list1[i1].second < list2[i2].second {
i1++
} else {
i2++
}
}
您可以使用 Linear Programming combined with the Levenshtein Distance you already mentioned. Linear Programming is a commonly used optimization technique for solving optimization problems, like this one. Check this link to find out an example how to use Solver Foundation in C# 解决此问题。此示例与您遇到的具体问题无关，但它是库如何工作的一个很好的示例。
提示：
您需要在 2 个列表之间的每对 teams/strings 之间建立一个距离矩阵。假设两个列表都有 N 个元素。在矩阵的第 i 行中，您将有 N 个值，第 j 个值将指示第一个列表中的第 i 个元素与第二个列表中的第 j 个元素之间的编辑距离。然后，您需要设置约束。约束将是：
- 每一行的总和需要等于 1
- 每列的总和等于 1
- 每个系数（矩阵项）必须为 0 或 1
几个月前我已经解决了同样的问题，这种方法对我来说非常有效。
代价函数是总和：`
sum(coef[i][j] * dist[i][j] for i in [1, n] and for j in [1, n])
`。你想最小化这个函数，因为你希望映射后 2 组之间的整体 "distance" 尽可能低。
我有 两个列表。第一个包含条目
- RB 莱比锡 vs SV 达姆施塔特 98
- 柏林赫塔 vs 霍芬海姆
- ..
第二个包含基本相同的条目，但可以用不同的形式编写。例如：
- 柏林赫塔 vs TSG 霍芬海姆
- RB 莱比锡 vs 达姆施塔特 98
- ..
等等。两个列表代表相同的运动项目，但它们可以使用备用球队名称并且不以相同的顺序出现。
我的目标（呵呵双关语）是将两个列表统一为一个并匹配相同的条目并丢弃未出现在两个列表中的条目。
我已经尝试使用 Levensthein distance 和模糊搜索。 我考虑过使用机器学习，但不知道如何开始。
希望得到任何帮助和想法！
您可以使用 BK-tree (I googled C# implementations and found two: 1, 2)。使用 Levenshtein 距离作为度量。或者，从列表中的名称中删除全部大写的子字符串以改进指标（请注意，这不会意外地为名称留下空字符串）。
1. Put the names from the first list in the BK-tree
2. Look up the names from the second list in the BK-tree
a. Assign an integer token to the name pair, stored in a Map<Integer, Tuple<String, String>>
b. Replace each team name with the token
3. Sort each token pair (so [8 vs 4] becomes [4 vs 8])
4. Sort each list by its first token in the token pair,
then by the second token in the token pair (so the list
would look like [[1 vs 2], [1 vs 4], [2 vs 4]])
现在您只需遍历两个列表
int i1 = 0
int i2 = 0
while(i1 < list1.length && i2 < list2.length) {
if(list1[i1].first == list2[i2].first && list1[i1].second == list2[i2].second) {
// match
i1++
i2++
} else if(list1[i1].first < list2[i2].first) {
i1++
} else if(list1[i1].first > list2[i2].first) {
i2++
} else if(list1[i1].second < list2[i2].second {
i1++
} else {
i2++
}
}
您可以使用 Linear Programming combined with the Levenshtein Distance you already mentioned. Linear Programming is a commonly used optimization technique for solving optimization problems, like this one. Check this link to find out an example how to use Solver Foundation in C# 解决此问题。此示例与您遇到的具体问题无关，但它是库如何工作的一个很好的示例。
提示： 您需要在 2 个列表之间的每对 teams/strings 之间建立一个距离矩阵。假设两个列表都有 N 个元素。在矩阵的第 i 行中，您将有 N 个值，第 j 个值将指示第一个列表中的第 i 个元素与第二个列表中的第 j 个元素之间的编辑距离。然后，您需要设置约束。约束将是：
- 每一行的总和需要等于 1
- 每列的总和等于 1
- 每个系数（矩阵项）必须为 0 或 1
几个月前我已经解决了同样的问题，这种方法对我来说非常有效。
代价函数是总和：`
sum(coef[i][j] * dist[i][j] for i in [1, n] and for j in [1, n])
`。你想最小化这个函数，因为你希望映射后 2 组之间的整体 "distance" 尽可能低。