[ 알고리즘 ] Dynamic Programming : 근사문자열매칭 ,편집거리

1.근사 문자열 매칭과 거리함수

 

근사 문자열 매칭 : 비슷한 문자열 비교 (엄청 빠른 방법은 없음)

 

거리함수

• 해밍거리 : 두 문자열을 같은 자리를 비교해서 다른 것의 개수를 센다. 밀리는 경우는 체크 못함
• 편집거리 : 해밍거리와 비슷하지만 insert, delete 와 change 존재
• 가중편집거리 : 편집거리와 비슷하지만 문자별로 가중치 존재

 

2. 편집거리

 

편집거리란 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집연산들의 최소 수이다.

편집연산은 삽입, 삭제, 교체가 존재한다. 

 

이를 구하는 방법은 문자열 두개로 표를 만든뒤 각 칸에 편집거리를 계산해주는 것이다 .

편집거리는 아래와 같이 계산한다.

 

편집거리

D(i,j)는 S1의 i번째 인덱스와 S2의 j번째 인덱스를 비교한다는 의미이다.

D(i, j-1) + 1 은 삽입을 의미하고 D(i-1, j) + 1은 삭제, D(i-1, j-1) + diff(i, j)은 같으면 0 다르면 1을 의미한다.

편집거리 계산 예시

이미지 출처:https://javascript.plainenglish.io/a-beginners-guide-to-the-levenshtein-distance-algorithm-part-1-d581fef7588f

 

단점은 문자열이 길어지면 속도가 너무 느려진다는 것과, 덩어리가 삭제된것은 잡지 못한다는 것이다.