1.근사 문자열 매칭과 거리함수 근사 문자열 매칭 : 비슷한 문자열 비교 (엄청 빠른 방법은 없음) 거리함수 해밍거리 : 두 문자열을 같은 자리를 비교해서 다른 것의 개수를 센다. 밀리는 경우는 체크 못함 편집거리 : 해밍거리와 비슷하지만 insert, delete 와 change 존재 가중편집거리 : 편집거리와 비슷하지만 문자별로 가중치 존재 2. 편집거리 편집거리란 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집연산들의 최소 수이다. 편집연산은 삽입, 삭제, 교체가 존재한다. 이를 구하는 방법은 문자열 두개로 표를 만든뒤 각 칸에 편집거리를 계산해주는 것이다 . 편집거리는 아래와 같이 계산한다. D(i,j)는 S1의 i번째 인덱스와 S2의 j번째 인덱스를 비교한다는 의미이다. D(i, j-1) ..