algorithm - 加权无序字符串编辑距离

Question

我需要一种有效的方法来计算两个无序符号集合之间的最小编辑距离。与仅适用于序列的 Levenshtein 距离一样，我需要插入、删除和替换具有不同的每个符号成本。我也有兴趣恢复编辑脚本。

因为我要完成的工作与计算字符串编辑距离非常相似，所以我认为它可能被称为无序字符串编辑距离，或者可能只是设置编辑距离。但是，Google 没有使用这些搜索词找到任何结果，所以我很想知道这个问题是否有其他名称？

澄清一下，问题将由

解决

def unordered_edit_distance(target, source):
    return min(edit_distance(target, source_perm) 
               for source_perm in permuations(source))

例如，unordered_edit_distance('abc', 'cba') 将是 0，而 edit_distance('abc', 'cba') 是 2。不幸的是，排列的数量增长非常快，即使对于中等大小的输入也不实用。

编辑 使操作与不同的成本相关联变得更清楚。

Answer 1

对它们进行排序(不是必需的)，然后删除两组中相同(并且数量相等!)的项目。然后，如果集合的大小相等，则需要替换的数量；如果一个更大，那么你还需要一些插入或删除。无论如何，您需要的操作数等于第一阶段后剩余的更大集合的大小。