Algorithm

1. Longest Common Subsequences (LCS)

장점: 공통 부분 문자열을 찾을 때 유용

LCS 알고리즘은 두 문자열에서 공통으로 가지고 있는 가장 긴 부분 문자열을 찾는 알고리즘으로, 문자열 처리에서 유용하게 사용됩니다. 예를 들어, 자연어 처리에서 두 문장 간의 유사도를 측정하거나, DNA 서열 분석 등에서 사용됩니다.

(LCS로 두 문자열 input에 대해 일치하는 부분 중 가장 긴 문자열을 찾는 것이 과제)

 

알고리즘 과정

 

 

2. Edit Distance 

문자열 사이의 차이를 계산하는 데 사용되는 개념

 

ex) "kitten" 문자열을 "sitting" 문자열로 변환하는 데 필요한 최소 편집 횟수를 계산하면, 다음과 같은 과정을 거칩니다.
"k"를 "s"로 대체
"e"를 "i"로 대체
"t"와 "t"는 동일하므로 일치
"t"와 "i"를 대체
"e"를 삭제
"n"과 "g"를 삽입

 

2-Row Representation
max 매칭을 찾는게 아닌 매칭되지 않는 나머지를 최소화 하는게 이 알고리즘

Edit distance = min ( #insertions + #deletions + #mismatches )
먼저 대각선을 다 만들어 준다. 그 후 매칭되는 부분의 대각선은 0으로 만들어 준다.
위 아래 이동은 +1 이후 가장 작은 가중치를 가지는 경로를 찾는다.

가로와 세로는 deletions or insertion?