golang中多个整数切片的序列对齐

Question

我想弄清楚如何使用 golang 对齐稍微不完美的二进制切片。以下四个切片均使用不同的偏移量正确对齐。然而，并非每一位都是相同的（在下面标记）所以我不能只比较原始块。

func main() {

    // Match all three slices up (ignoring occasional errors)
    s1 := []int16{0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1}
    s2 := []int16{ /*                     */ 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}
    //                                       ^              ^
    s3 := []int16{0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1}
    //               ^
    s4 := []int16{ /*            */ 0, 0, 0, 1, 1, 1, 0, 0}

    slices := make([][]int16, 3)
    slices = append(slices, s1, s2, s3, s4)


    offsets := forgivingSyncHere(slices)
}

这是一个https://play.golang.org/p/zqJ_4qLc8O

Answer 1

这取决于你的 "cost" 函数是什么，你的目标是最小化你的 "cost"。

成本函数可能是这样的。这个想法是 "mismatch" 比没有任何匹配项的成本更高，我们将其称为 "overruns"（比成本高两倍）。取 a[i] != b[i + offset] for a and b 等于 s1,s2,s3,s4 和 double 的情况数它。然后加上每个配对的每个 offset 的绝对值（在本例中为 4 个数组的 6 个配对）作为开始时的超限次数。然后在最后加上超限。

示例成本函数：

func cost(sn [][]int16, offsets [][]int) int {
  // cost accumulator
  c := 0.0

  // the factor of how much more costly a mismatch is than an overrun
  mismatchFactor := 2.0

  // define what you want, but here is an example of what I said above
  for i1:=0;i1<len(sn);i++ {
    for i2:=i1+1;i2<len(sn);i2++ {
      c += mismatchFactor * diff(sn[i1], sn[i2], offsets[i1][i2])
      c += math.Abs(offsets[i1][i2])
      c += math.Abs(len(sn[i1]) + offsets[i1][i2] - len(sn[i2]))
    }
  }
}

// offset of the offset of s1 wrt s2
func diff(s1 []int16, s2 []int16, offset int) int {
  // index, index, diff total
  i1,i2,d := 0,0,0
  if offset >= 0 {
    i1 += offset
  } else {
    i2 -= offset
  }
  while i1<len(s1) && i2<len(s2) {
    if s1[i1] != s2[i2] {
      d++
    }
    i1++
    i2++
  }
  return d
}

随心所欲地制定你的成本函数，这只是一个例子。但是，假设您有成本函数，那么很容易想出蛮力算法。不过，您可以尝试优化算法 :)。有很多想法。这与具有编辑距离的字符串搜索算法非常相似。维基百科和 Google 有很多结果。

免责声明：所有这些都未经测试 :)，但它应该可以帮助您入门

Answer 2

相似性可以使用 Levenshtein 距离来描述，又名编辑距离 - 一个字符串必须经历的插入、删除和突变的次数才能变成另一个。

这使您可以定量地讨论相似度，例如编辑距离与两个字符串长度中较短的长度之比可能是一个合理的指标，但这取决于您所说的相似度到底是什么意思.

从那里您可以找到要比较的每对字符串中相同子字符串的长度和数量的下限。在您的情况下，通过观察您的示例，看起来 4 位就是您认为的匹配项。 IOW，如果你使用 4 位块，并检查给定序列对的精确匹配，匹配块的数量告诉你它们的相似性是多少？

如果您对足够小的子字符串进行精确比较，则至少可以保证有几个匹配项，即使差异是均匀分布的（如果它们聚集在一起，较大的部分将具有精确匹配，因此较短的字符串除以最大编辑距离）。

将相似性位置考虑在内的字符串的一般近似匹配的精确解是计算密集型的（并且相关且经过充分研究的问题是最长公共子序列），而且还必须应用于每一对要比较的序列，而不是独立的每个序列。相反，选择合适的块大小并通过其可能的子字符串对每个字符串进行索引仅取决于孤立的每个字符串，并且可能会提供一个近似的答案。您当然可以记下位置并进一步限制它。

总而言之，针对您所描述的问题的简单解决方案可能很棘手，实际上序列对齐和近似字符串匹配是通过解决一个更简单的问题来完成的，然后仔细检查这些解决方案更 naive/expensive 的方法。

Rabin Fingerprinting 是一种比 n-gram（滑动 window）更复杂的将字符串分解为子字符串的方法，但它是一种随机方法并产生可变大小的字符串（但确定性字符串），所以计算边界有点复杂。

golang中多个整数切片的序列对齐

Sequence alignment of multiple slices of ints in golang

arrays

match

go

slice