두 문자열 사이의 유사성을 측정하기 위한 metric

주어진 문자열을 다른 문자열로 변환하는 데 필요한 최소 작업 수와 동일하다.

세 가지 유형의 작업

• 치환
• 삽입
• 삭제

LD의 경우, 대체 비용은 2단위이고 다른 2개의 작업에 대한 비용은 1단위

ex) 두 문자열 s="bitcoin"과 t="altcoin"을 예로 들어보자.

st에서 시작하려면 문자 "B"와 "i"를 문자 "A"와 "1"로 두 개 대체해야 한다.

따라서 LD(t, s) = 2이다.

스팸 필터링, 컴퓨터 생물학, 엘라스틱 검색 등 LD에 대한 많은 사용 사례가 있다.

정보검색에서 다뤘다.

EditDistance(str1[i],str2[j])
	if(str1[i] == str2[j])        //행과 열의 문자가 같은 경우 
		then m[i,j] = m[i-1][j-1];  //왼쪽 위 대각선에서 그대로 가져온다.
		else                        //문자가 다른경우
				m[i,j] = min(m[i-1][j], m[i-1][j-1], m[i][j-1]) + 1; 
																//인접한 칸들 중 제일 작은 값에 1을 더한다.

ex) fast → cats

• ← : delete
• ↑ : insert
• ↖: replace

방법은 3가지가 있다.

• replace → delete → insert:
• replace → replace → replace
• replace → insert → delete