골란에서 정수의 여러 슬라이스 시퀀스 정렬

Question

golang을 사용하여 약간 불완전한 이진 조각을 정렬 할 수있는 방법을 찾으려고합니다. 다음 4 개의 슬라이스는 모두 서로 다른 오프셋으로 올바르게 정렬됩니다. 그러나 모든 비트가 동일하지 않으므로 (아래에 표시) 원시 조각을 비교할 수 없습니다. 여기

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

입니다.

비용 함수는 다음과 같을 수 있습니다. 아이디어는 일치하지 않는 것보다 "불일치"가 더 비싸다는 것입니다. 우리는이를 "오버런 (overruns)"이라고 부릅니다. a 및 b에 대한 a[i] != b[i + offset]이 s1, s2, s3, s4과 같고 두 배인 경우의 숫자를 가져옵니다. 그런 다음 각 페어링 (이 경우 4 개 배열에 대해 6 쌍)에 대한 각 offset의 절대 값을 처음에 오버런 수에 추가합니다. 그런 다음 끝에 오버런을 추가하십시오.

샘플 비용 함수 :

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 
} 

그러나 당신이 원하는 당신의 비용 함수를 확인, 이것은 단지 예입니다. 그러나 에 비용 함수가 있다고 가정 할 때, 무차별 대입 알고리즘은 매우 쉽습니다. 알고리즘을 최적화하려고 할 수도 있습니다 :). 많은 아이디어가 있습니다. 이것은 편집 거리가있는 문자열 검색 알고리즘과 매우 유사합니다. Wikipedia와 Google에는 많은 결과가 있습니다.

면책 조항 :이 모든 것은 검증되지 않은 :하지만 당신이 시작할 수 있어야

Answer 2

유사성 편집 거리 일명 Levenshtein 거리를 사용하여 설명 할 수있다 - 문자열을 거쳐야 삽입, 삭제 및 돌연변이의 수 다른 사람이 되라.

이렇게하면 비슷한 정도에 대해 정량적으로 이야기 할 수 있습니다. 예를 들어, 두 문자열 길이 중 더 짧은 길이에 대한 편집 거리의 비율은 합리적인 메트릭 일 수 있습니다. 그러나 이는 정확히 무엇을 의미하는지에 달려 있습니다.

거기에서 비교할 각 쌍의 문자열에서 동일한 하위 문자열의 길이와 수에 대한 하한을 찾을 수 있습니다. 귀하의 경우, 귀하의 예를 시선으로, 4 비트 보이는 당신이 일치하는 것을 고려합니다. IOW, 4 비트 청크를 사용하고 주어진 시퀀스 쌍에 대한 정확한 일치를 확인하는 경우 일치하는 청크의 수가 유사성에 대해 무엇을 말합니까?

작은 하위 문자열에 대한 정확한 비교를 수행하면 차이가 균등하게 배치되어 있어도 몇 가지 일치 항목이 보장됩니다 (클러스터 된 경우 큰 섹션은 정확히 일치하므로 길이가 짧은 문자열을 최대 편집 거리로 나눈 값).

유사점의 위치를 ​​고려한 문자열의 일반적인 근사 일치를위한 정확한 솔루션은 계산 집약적이며 (관련이 있고 잘 연구 된 문제는 가장 긴 공통 하위 시퀀스입니다.) 또한 각 쌍에 대해 적용해야합니다. 비교할 시퀀스. 독립적으로 각 시퀀스가 ​​아닙니다. 대조적으로 적절한 청크 크기를 선택하고 각 문자열을 가능한 하위 문자열로 인덱싱하는 것은 각 문자열을 격리하여 결정하며 대략적인 대답을 제공 할 수 있습니다. 당신은 물론 위치를 기록하고 그것을 제약 할 수 있습니다.

요약하면 문제에 대한 순진한 해결책은 다루기 어려울 수 있습니다. 실제로는 간단한 순서로 문제를 해결 한 다음 순서 정렬과 대략적인 문자열 일치를 수행 한 다음 보다 순진하고 값 비싼 접근 방식.

Rabin 지문은 문자열을 n-gram (슬라이딩 윈도우)보다 하위 문자열로 분할하는보다 복잡한 방법이지만 확률적인 방법이며 가변 크기의 문자열 (결정적 요소)을 생성하기 때문에 경계를 계산하는 것은 조금 더 복잡해졌습니다.