3

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

由于我要完成的工作与计算字符串编辑距离非常相似，因此我认为它可能被称为无序字符串编辑距离，或者只是设置编辑距离。然而，谷歌并没有用这些搜索词出现任何东西，所以我很想知道这个问题是否有其他名字？

为了澄清，问题将通过以下方式解决

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。不幸的是，排列的数量增长得非常快，即使对于中等大小的输入也不实用。

编辑更清楚地表明操作与不同的成本相关联。

4

4 回答 4

1

虽然你的观察是正确的，但你实际上是让一个简单的问题变得更复杂。

由于来源可以是原始来源的任何排列，您首先需要检查字符级别的差异。

有两个映射，每个映射计算目标和源字符串中单个字符的数量：

例如：a：2 c：1 d：100

现在比较两张地图，如果你缺少任何字符当然需要插入它，如果你有多余的字符则删除它。而已。

于 2014-03-12T09:20:52.907 回答
1

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

于 2014-03-12T09:17:30.127 回答
1

让我们暂时忽略替换。

现在，确定仅在第一组中的元素（将被视为删除）和仅在第二组中的元素（将被视为插入）成为一个相当微不足道的问题。这可以通过以下任一方式轻松完成：

  • 对集合进行排序并同时遍历两者，或者
  • 将第一个集合中的每个元素插入到哈希表中，然后从哈希表中删除第二个集合中的每个元素，每个未找到的元素都是插入，并且在我们完成删除后保留在哈希表中的每个元素

现在，要包括替换，剩下的就是找到插入元素与删除元素的最佳配对。这其实是稳定的婚姻问题：

稳定婚姻问题 (SMP) 是在给定每个元素的一组偏好的情况下，在两组元素之间找到稳定匹配的问题。匹配是从一组元素到另一组元素的映射。只要两者都不是，则匹配是稳定的：

  1. 第一个匹配集合的某个给定元素 A 比 A 已经匹配的元素更喜欢第二个匹配集合的某个给定元素 B，并且
  2. B 也更喜欢 A 而不是 B 已经匹配的元素

这可以用Gale-Shapley 算法解决：

Gale-Shapley 算法涉及许多“轮”（或“迭代”）。在第一轮中，首先 a) 每个未订婚的男人向他最喜欢的女人求婚，然后 b) 每个女人对她最喜欢的追求者回答“也许”，对所有其他追求者回答“不”。然后她与她目前最喜欢的追求者暂时“订婚”，而那个追求者同样与她暂时订婚。在随后的每一轮中，首先 a) 每个未订婚的男人向他尚未求婚的最喜欢的女人求婚（无论该女人是否已经订婚），然后 b) 每个女人对她的追求者回答“也许”她最喜欢（无论是她现有的临时伴侣还是其他人）并拒绝其余的（再次，也许包括她当前的临时伴侣）。

我们只需要正确计算成本。要将插入和删除配对，使其成为替换，我们将失去插入和删除的成本，并获得替换的成本，因此配对的净成本为substitutionCost - insertionCost - deletionCost。

现在上面的算法保证了所有的插入或删除都是配对的——我们不一定想要这个，但是有一个简单的解决方法——只需创建一堆“保持原样”元素（在插入和删除端）——任何与“保持原样”元素配对的插入或删除都将花费 0，并导致它保持插入或删除状态，并且两个“保持原样”元素最终配对不会发生任何事情。

于 2014-03-12T11:56:44.017 回答
0

关键观察：您只关心字符串中有多少 'a's、'b's、...、'z' 或其他字母字符，因为您可以重新排序每个字符串中的所有字符。

因此，问题归结为以下几点：具有s['a']字符'a'，s['b']字符'b'，...，s['z']字符'z'，将它们转换为t['a']字符'a'，t['b']字符'b'，...，t['z']字符'z '。如果您的字母表很短，s[]并且t[]可以是数组；通常，它们是从字母表到整数的映射，例如map <char, int>在 C++、dictPython 等中。

现在，对于每个字符c，您知道s[c]和t[c]。如果s[c] > t[c]，则必须从第一个无序字符串 ( )中删除s[c] - t[c]字符。如果，则必须将字符添加到第二个无序字符串 ( )。css[c] < t[c]t[c] - s[c]ct

取，所有这样X的总和，您将获得总共必须删除的字符数。取，所有这样的总和，您将获得总共必须删除的字符数。s[c] - t[c]cs[c] > t[c]sYt[c] - s[c]cs[c] < t[c]t

现在，让Z = min (X, Y). 我们可以进行Z替换，剩下的就是X - Z插入和Y - Z删除。因此，操作的总数是Z + (X - Z) + (Y - Z)或X + Y - min (X, Y)。

于 2014-03-12T09:18:28.193 回答