algorithm - 将变形字符串列表匹配到它们的正确值

Question

我有两个列表，每个列表包含 50 个名字。

两个列表之间存在 1-1 的对应关系，满足:对于列表 1 中的每个名称 x，列表 2 中的 x 都有一个错误(或正确)的拼写。

如果我有列表 1 并且给出了拼写错误的列表 2，是否有可靠的算法将拼写错误的名称与其正确拼写的对应名称相匹配？

例如，

列表 1:衬套奥巴马特朗普

列表 2:伯特Pbame流浪汉

Answer 1

首先，计算 Levenshtein distance从每个拼错的单词到所有拼写正确的单词。

然后，使用 Gale-Shapley算法，您可以从拼写错误的单词到正确拼写的单词进行最佳配对。

在配对算法中，每个拼错的单词都会优先选择一个距离较近的拼写正确的单词。

注意:总会有解不唯一的情况。