arrays - golang中多个整数 slice 的序列对齐

Question

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

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

这取决于您的“成本”函数是什么，您的目标是最小化“成本”。

成本函数可能是这样的。这个想法是，“不匹配”比没有任何东西匹配时成本更高，我们称之为“超支”(比成本高两倍)。取 a[i] != b[i + offset] 对于 a 和 b 等于 s1< 的情况的数量,s2,s3,s4 并加倍。然后添加每个配对的每个 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
}

根据需要制定成本函数，这只是一个示例。然而，假设您有一个成本函数，蛮力算法很容易想出。不过，您可以尝试优化算法 :)。有很多想法。这与具有编辑距离的字符串搜索算法非常相似。维基百科和谷歌有很多结果。

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