我想弄清楚如何使用 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)
}
最佳答案
这取决于您的“成本”函数是什么,您的目标是最小化“成本”。
成本函数可能是这样的。这个想法是,“不匹配”比没有任何东西匹配时成本更高,我们称之为“超支”(比成本高两倍)。取 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
}
根据需要制定成本函数,这只是一个示例。然而,假设您有一个成本函数,蛮力算法很容易想出。不过,您可以尝试优化算法 :)。有很多想法。这与具有编辑距离的字符串搜索算法非常相似。维基百科和谷歌有很多结果。
免责声明:所有这些都未经测试 :),但它应该可以帮助您入门
关于arrays - golang中多个整数 slice 的序列对齐,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42445243/