>

서브 시퀀스 하위 치환을 유지하는최소 거리 메트릭을 찾고 있습니다. 이를 통해 두 번째 시퀀스의 하위 시퀀스는 서로 다른 표현을 가질 수 있지만 여전히 첫 번째 하위 시퀀스와 동일하다는 것을 의미합니다. 두 시퀀스의 길이는 항상 같습니다. 나는 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
    
    

관련 자료

  • 이전 대문자 및 소문자와 같은 필터에서 여러 항목을 사용할 때 angularjs 필터 문제
  • 다음 c# - flowLayoutPanel에서 맨 위에 자식 고정