퍼지 (fuzzy) 차이 메트릭을 사용하는 Diff 알고리즘

Question

알파벳 문자 유사성 측정 항목이있는 가장 큰 공통 부분 시퀀스 알고리즘과 유사한 알고리즘을 찾고 있습니다. 제가 알기로 알려진 알고리즘은 알파벳의 모든 문자를 완전히 다르게 취급합니다. 사용 사례는 다른 문자로 쉽게 편집 할 수있는 알파벳 문자를 가지고 있기 때문에 diffing 알고리즘으로 유사하게 취급해야합니다.

사용 예제로 일부 줄이 다른 줄과 더 비슷한 텍스트 줄에서 diffing 알고리즘을 사용하는 경우가 있습니다.

용지 An O(ND) Difference Algorithm and Its Variations (페이지 4) 모든 가장자리에 무게 또는 비용을 추가하는 것이 좋습니다. 대각선 가장자리 가중치 0과 비 대각선 가장자리 가중치 1을 부여하십시오.. [0;1] 간격의 모든 가중치를 할당하는 옵션이 필요합니다.

Answer 1

LCS (Lightsest Common Subsequence) 문제는 대개 동적 프로그래밍 방법으로 계산되며 기존 방법을 조정하여 사용 사례에 적용 할 수 있습니다. (위키 백과에서) 어떻게 LCS 작품 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Example 설명이 예에서

, 당신은 알고리즘을 조정 생각해야 같은 것을 : j = i +1에 대한

score_j = socre_i + 1 (즉, 추가,라고하는 것입니다 : 대신 점수의

1 새 항목을 찾을 때) LCS에 새 항목이 추가되면 점수를 받아야합니다 :

score_j = F(score_i, p(letter_i, letter_j)) 무엇이든간에.

• p(letter_i, letter_j) is the probability to change from letter_i to letter_j (즉이다 weight [0, 1] 당신에 대해 얘기했다)
• F 그 확률 p을 알고 score_j에 score_i에서 이동하기 위해, aggreggation 기능입니다.

예를 들어 F은 operator +으로 정의 할 수 있습니다. 그런 다음 얻을 것이다 : 더 정확하게

score_j = score_i + p(letter_i, letter_j)) 또는 :

score_j = score_i + p(letter_i, letter_j)) x 1

가 (읽기 x 1 of a character 등)

와 즉, 2 개 서브 시퀀스 (문자) 당신에게 최대 유사성을주고 당신이 woud 알고리즘의 끝에서 역 추적으로 찾을 수 있습니다.

자신의 기능 F을 사용하면 더 나은 결과를 얻을 수 있습니다.