문자열 유사도 알고리즘 Needleman-Wunch, Smith-Waterman

fzf에서 문자열 서치 알고리즘으로 뭘 사용하는지 찾아보다가 정리해둔다.

차이점 위주로

Needleman-Wunch

두 문자열의 전체 유사도

https://en.wikipedia.org/wiki/Needleman–Wunsch_algorithm

padding 전략: 맨 왼쪽 위 값을 0으로 주고 indel 이 발생했다고 가정한다. gap으로 채워지게 됨.

점화식:H[i][j] = max(H[i-1][j-1] + match or mismatch, H[i-1][j] + gap, H[i][j-1] + gap)

trace back 시작점: H[str1.length][str2.length] 그러니까 .. 테이블 오른쪽 맨 아래 셀

Smith-Waterman

두 문자열의 지역 유사도

https://en.wikipedia.org/wiki/Smith–Waterman_algorithm

padding 전략: 모두 0으로 채움 

점화식:H[i][j] = max(H[i-1][j-1] + match or mismatch, H[i-1][j] + gap, H[i][j-1] + gap, 0)

trace back 시작점: high score인 셀

이때 0을 줌으로써 테이블에 음수가 들어가지 않게되고, 이로 인해 지역적으로 high score인 곳이 best match이게 된다.

그래서 smith waterman 에서 high score 값을 구하면 문자열이 얼마나 유사한지 점수화 할 수 있다. 

더 생각해볼만한것

gap, 즉 indel 가중치가 서로 달라질수있다. 이 경우는 가중치를 크게준 쪽이 traceback으로 채택될 가능성이 낮아진다.