2

我有一组字符串[S1 S2 S3 ... Sn]，我要计算所有这样的目标字符串T，以便每个字符串S1 S2... Sn都可以T在总共K编辑中转换。
所有字符串都是固定长度L的，这里的编辑是汉明距离。

我所拥有的只是一种蛮力方法。所以，如果我的字母大小是 4，我有 O(4^L) 的样本空间，并且需要 O(L) 时间来检查它们中的每一个。我似乎无法将复杂性从指数降低到某种多边形或伪多边形！有没有办法修剪样本空间以做得更好？

我试图将其可视化为 L 维向量空间。我已经获得了 N 个点，并且必须计算与给定 N 个点的距离之和小于或等于 K 的所有点。
i.e. d1 + d2 + d3 +...+ dN <= K
是否有任何已知的几何算法可以更复杂地解决这个或类似问题？请指出我正确的方向或任何提示表示赞赏。
谢谢

4

2 回答 2

1

您可以使用动态编程有效地做到这一点。

关键思想是您不需要枚举所有可能的目标字符串，您只需要知道 K 编辑可能有多少种目标方式，仅考虑 I 之后的字符串索引。

alphabet = 'abcd'
s = [ 'aabbbb', 'bacaaa', 'dabbbb', 'cabaaa']

# use memoized from http://wiki.python.org/moin/PythonDecoratorLibrary          
@memoized
def count(edits_left, index):
  if index == -1 and edits_left >= 0:
    return 1
  if edits_left < 0:
    return 0
  ret = 0
  for char in alphabet:
    edits_used = 0
    for mutate_str in s:
      if mutate_str[index] != char:
        edits_used += 1
    ret += count(edits_left - edits_used, index - 1)
  return ret
于 2012-02-16T17:00:11.383 回答
0

大声思考，在我看来，这个问题归结为一个组合问题。

一般来说，对于长度为 L 的字符串 S，总共有 C(L,K) 个（二项式系数）位置可以被替换，因此 (ALPHABET_SIZE^K)*C(L,K) 来自 Hamming 的目标字符串 T K 的距离。

使用动态规划和帕斯卡三角可以很容易地计算二项式系数......无需疯狂进入factoriel等......

现在处理了一个字符串大小写，处理多个字符串有点棘手，因为您可能会重复计算目标。直观地说，如果 S1 距离 S2 很远，那么两个字符串都将生成相同的目标集，因此在这种情况下您不会重复计算。这最后一个陈述可能是一个远射，这就是为什么我一定要说“直觉地”:)

希望能帮助到你，

于 2012-02-16T17:30:39.220 回答