홈>2020-02-01 01:19

algorithm - 인코딩 된 시퀀스의 최소 거리 메트릭

서브 시퀀스 하위 치환을 유지하는최소 거리 메트릭을 찾고 있습니다. 이를 통해 두 번째 시퀀스의 하위 시퀀스는 서로 다른 표현을 가질 수 있지만 여전히 첫 번째 하위 시퀀스와 동일하다는 것을 의미합니다. 두 시퀀스의 길이는 항상 같습니다. 나는 Hamming 또는 Levenshtein 거리에 익숙하지만이 경우에는 아마도 쓸모가 없습니다.

이 예제를 고려하십시오 :

AABBAA
CCDDCC

A = C 때문에

의 거리는 0입니다 그리고 B = D (또는 AA = CC 그리고 BB = DD ).

AABBBBBB
CCDDEEEE

A = C 때문에

의 거리는 2입니다 그리고 B = E (또는 AA = CC 또는 BB = EE 또는 BBBB = EEEE ), 그러나 B =/= D (또는 BB =/= DD ).

그러나이 기능은 정확하게 동작하지 않을 수 있습니다.인코딩되지 않은 시퀀스가 반복 측면에서 인코딩 된 시퀀스와 어떻게 비슷한 지 알아야합니다.두 번째 시퀀스가 시저 암호와 같은 것으로 인코딩 된 것으로 가정 할 수 있습니다 (예 : 교대는 시간에 따라 다를 수 있습니다.)

참고 :

또한 LZW 알고리즘으로 두 시퀀스를 압축하고 압축 비율을 비교하는 방법도 생각했습니다. 다른 아이디어?

답변 # 1
처음부터 연속 번호로 시퀀스의 요소를 열거 한 다음 레 벤슈 테인 거리 또는 이와 유사한 것을 사용할 수 있습니다.
```
AACCAABB  --> 11221133  (A->1, C->2, B->3)
CCXXCCYY  --> 11221133  (C->1, X->2, Y->3)
d(AACCAABB, CCXXCCYY) = d(11221133, 11221133) = 0
```

Python2.net

algorithm - 인코딩 된 시퀀스의 최소 거리 메트릭

관련 자료