1) 왜이 라인에 1을 더합니까?Levenshtein 거리에 관한 질문
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
if s[i] = t[j] then cost := 0
else cost := 1
가 낮은 단어 길이/삭제 고려해야한다, 또는 내가 뭔가를 놓친 거지 라인?
2) 주석은 상태 삭제 및 삽입을 나타냅니다. 더 낮은 값은 삭제 된 문자를 나타 내기 때문에 두 단어 (삭제 된 문자가 단어의 길이를 나타내는 정수)에서 삭제 된 문자를 확인한다고 생각합니다.
사용되는 코드는 여기(이것은 의사 코드 내가 더 언어 별 문제가 없기 때문에,이 스레드는 모든 언어 범주가 아닌) :
http://www.iterasi.net/openviewer.aspx?sqrlitid=z0cloj7xhk-ce0f72v4cjq
1)이 라인은 거리를 계산 삽입의 경우 삭제의 경우 및 대체의 경우 "비용"을 사용하는 경우 ...
삭제 및 삽입은 거리 계산에서 효과적으로 "1"로 계산되므로 +1.
우리는 문자 따라서 다른 경우에만 대체가 있었다 믿을 수은 "비용 = 0"두 문자가 동일한 경우는 ...
새로운 거리가 이들 3 개 가설 사이의 최소 거리 그래서 당신은 항상 1을 추가하지 않습니다 ...
2) "FooBar"와 "FoBaWhatever"사이의 거리를 계산하는 경우 2) 두 번째 문자열이 첫 번째 문자열보다 길어도 일부 문자 삭제가 발생합니다 ...
물론 두 번째 문자열이 두 번째 문자열보다 짧으면 (FooBar -> F oBa) 나는 일부 삭제를 발견 할 것이다. 그러나 그들이 어디에 있는지 미리 알 수 없다 ...
당신은 http://www.merriampark.com/ld.htm을 읽었 느냐?
한 문자열을 다른 문자열로 변환하는 데 필요한 변환 - 삽입 및 삭제 횟수 -를 계산합니다.
이 "비용"은 두 문자열 간의 거리를 나타냅니다.
교환은 어떻게됩니까? 그 알고리즘은 Damerau–Levenshtein이며 다른 알고리즘입니다. 교환을 포함하여 많은 일이 개선되지는 않습니다.
본질은 두 단어 사이에 행렬을 만들고 각 단어의 각 문자에서 다른 단어의 각 문자까지의 "거리"를 계산합니다. 해당 행렬의 오른쪽 아래 모서리는 모든 문자를 고려한 총 거리입니다.
질문 1)
"위"셀 변경의 이력을 반영하고, 그 행의 문자 (일반적으로)이 상이하므로,이 셀은 그것에 삭제 상대적이다.
"left"셀은 변경 내역을 반영하며 해당 열의 문자는 (일반적으로) 이와 다르므로이 셀은이 셀에 상대적으로 삽입됩니다.
일반적으로 이것이 잘못된 길은 세 자리 문자가있는 단어입니다. 희귀 영어.
행 열 비교는 0 또는 1
최소 "역사 더한 변경 '및 변화의 실제 비용은 해당 비용의 비용을 갖는다.
은 질문 2)
변수 i 및 j 아무것도의 길이 아니다. 그들은 비교 행렬의 입장에 있습니다. "삽입"및 "삭제"는 한 단어를 다른 단어로 변환하는 데 필요한 작업입니다. 삽입/삭제 동작의 수는 단어 사이의 거리입니다.
그래, 실제로 그 링크를 읽었습니다. 좋은 대답. 마지막으로 한 가지 : 최소 기능은 셀에 +1이 있고 셀에 + 비용이 있습니다. 확실히 1과 비용은 비용이 1보다 크지 않고 동일한 값 (1)이며 if 문이 실행될 때 0이 아닌 경우 (비용 == 0 등). 나는이 논리를 이해하지 못합니까? – dotnetdev
아니요. 비용은 항상 1이 아닙니다. 인접한 문자가 일치하지 않는 경우 1보다 훨씬 클 수 있습니다. 처음 시작할 때 n 문자 단어의 마지막 문자는 n 삽입 결과라고 가정합니다. 비용은 처음에는 n이 비교가 될 때까지 적습니다. 왜냐하면 일부 문자가 실제로 일치하기 때문입니다. –