반응형
string distance
-
The Levenshtein Distance카테고리 없음 2020. 2. 4. 17:40
Levenshtein distance는 2개의 단어 사이의 유사성을 측정하는 알고리즘이다. 이 알고리즘은 similarity를 계산해주고 또는 몇개의 단어를 수정해야 하는지도 계산해준다. 이 알고리즘은 Vladimir Levenshtein(블라디미르 레벤시테인)이 1965년에 개발하였다. Levenshtein distance의 두 개의 문자열 a,b 사이의 수식은 다음과 같다. i, j 는 source와 target 문자열을 비교할때 각 문자를 가르키는 index이다. 1(ai≠bj)는 각 문자 ai, bj가 같으면 0이고 그렇지 않으면 1이다. 이것은 각 문자열을 deletion, insertion, substitution 중 무엇이 가장 최소의 비용이 드는지 계산하기 위해 중요하다. 아래 수식에서 m..
반응형