Levenshtein (편집) 거리의 정규화의 차이는?

Question

경우 s 및 tL(s,t) 주어진다 두 문자열 사이의 Levenshtein 거리

다음 두 가지 방식의 정규화 결과 휴리스틱에 미치는 영향의 차이는 무엇인가?

(L(s,t)*2)/[length(s) + length(t)]

L(s,t)/max[length(s), length(t)]

L(s,t)/[length(s) + length(t)]

1. 나는 정규화 방법 2가 Levenshtein 거리 위키피디아 페이지가 권장 되나 언급이 접근 방식 1의 이루어지지 않습니다 것으로 나타났습니다. 두 가지 방법 모두 똑같이 유효합니까? 서로를 사용하는 것에 대해 수학적으로 정당성이 있는지 궁금합니다.

   또한 접근 방식 1과 접근 방식 3의 차이점은 무엇입니까? 다음 예에

   :

   s = "Hi, my name is"

   t = "Hello, my name is"

   가

   L(s,t) = 4

   length(s) = 14 (공백 포함)

   length(t) = 17는

   (공백 포함) 상기 세 개의 표준화 알고리즘 주어진 691,363,210

   Levenshtein 거리이다 :

   1. 4/(+ 17 14) = 0.129

   2. 4/(17) = 0.235

   3. (4 * 2)/(14 + 17) = 0.258

Answer 1

두 변종의 효과는 거의 동일해야한다. 두 번째 용어는 영 (문자열은 동일)에서 하나 (완전히 다른)까지의 범위를 다루는 반면 첫 번째 변형의 상위 범위는 문자열의 길이에 따라 다릅니다. 길이가 거의 같으면 상한은 0.5이며 길이 차이가 클수록 커집니다.