[R] 문자열 편집 거리 (edit distance between two strings of characters) : R stringdist package

지난번 포스팅에서는 범주형 특성 데이터, 텍스트 문서의 거리를 측정하는 지표 중에서 

 - 자카드 거리 (Jaccard distance)

 - 코사인 거리 (Cosine distance)

에 대해서 알아보았습니다. 

이번 포스팅에서는 두 문자열의 거리(distance between two strings of characters), 비유사도(dissimilarity)를 측정하는데 사용하는 편집 거리(edit distance), 혹은 다른 이름으로 Levenshtein metric 에 대해서 알아보겠습니다. 

편집거리(edit distance)는 데이터 항목이 놓인 순서(order)가 중요한 문자열(strings of characters, 예: 주소, 전화번화, 이름 스펠링)이나 서열(sequence, 예 : 염색체 염기서열)의 (비)유사도를 측정하는데 유용하게 사용할 수 있습니다. 

편집거리 (edit distance, Levenshtein metric) 는 두 문자열에서 하나의 문자열을 다른 문자열과 똑같게 만들기 위해서 최소로 필요로 하는 편집 회수(문자 추가, 제거, 위치 변경)를 계산합니다. 

아래에 간단한 예를 들어서 설명해보겠습니다. 

[ 편집 거리 예시 (example of edit distance, Levenshtein Metric) ]

아래처럼 사람 이름을 입력한 두 개의 문자열이 있다고 가정해보겠습니다. 

• 문자열 1 (character string 1): Shawn Henry
• 문자열 2 (character string 2): Shan Hennyy

'문자열 2'를 편집해서 '문자열 1'로 변환할 때 필요한 최소한의 조치를 생각해보면, 

(편집 조치 1) '문자열 2'의 4번째 위치에 'w'를 추가 (insert a 'w')

(편집 조치 2) '문자열 2'의 8번째 위치에 'n'을 'r'로 교체 (replace an 'n' with a 'r')

(편집 조치 3) '문자열 2'의 10번째 위치에 있는 'y'를 삭제 (delete the last 'y')

와 같이 3번의 편집 조치가 필요합니다.  따라서 '문자열 1'과 '문자열 2'의 편집 거리는 3입니다. 

'문자열 1'을 편집해서 '문자열 2'로 변환할 때 필요한 최소한의 조치를 생각해보면, 

(편집 조치 1) '문자열 1'의 4번째 위치의 'w'를 삭제 (delete a 'w')

(편집 조치 2) '문자열 1'의 9번째 위치의 'r'을 'n'으로 교체 (replace a 'r' with an 'n')

(편집 조치 3) '문자열 1'의 11번째 위치에 'y'를 추가 (insert an 'y')

이므로, 이렇게 계산해도 역시 '문자열 1'과 '문자열 2'의 편집 거리는 3입니다. 

---

이제 R 의 stringdist package를 사용해서 편집 거리 (edit distance, Levenshtein metric)를 계산해보겠습니다. 

(1) stringdist 패키지 설치 및 불러오기

# installing and loading of stringdist package install.packages("stringdist") library(stringdist)

(2) 문자열 편집 거리(edit distance, Levenshtein metric) 계산: stringdist()

문자열 "shawn henry"와 "shan hennyy", "show hurry" 문자열 간의 편집거리를 각각 계산해보겠습니다. 

> # to compute string edit distances > # default method is 'osa', which is Optimal string alignment, (restricted Damerau-Levenshtein distance) > stringdist(c("shawn henry"), c("shan hennyy", "show hurry")) [1] 3 4

"shawn henry"와 "show hurry"의 편집거리를 계산하기 위해, 'show hurry'를 'shawn henry'로 변환하기 위한 최소 편집 조치를 살펴보면

(편집 조치 1) 'o'를 'a'로 변경 =>  shaw hurry

(편집 조치 2) 'n'을 추가   => shawn hurry

(편집 조치 3) 'u'를 'e'로 변경 => shawn herry

(편집 조치 4) 'r'을 'n'으로 변경 => shawn henry  (끝)

이므로, 편집거리는 4가 됩니다. 

(3) 여러개의 문자열 간의 편집 거리 (edit distance) 계산 결과를 행렬로 만들기: stringdistmatrix()

R stringdist 패키지에 들어있는 간단한 예제를 인용해서 예를 들어보겠습니다. 

> # to compute a dist object of class dist > # => can be used by clustering algorithms such as stats::hclust > stringdistmatrix(c("foo","bar","boo","baz"))   1 2 3 2 3     3 1 2   4 3 1 2 >  > str_dist_mat <- as.matrix(stringdistmatrix(c("foo","bar","boo","baz"))) > str_dist_mat   1 2 3 4 1 0 3 1 3 2 3 0 2 1 3 1 2 0 2 4 3 1 2 0

(4) 가장 유사한 문자열의 위치 찾기: amatch()

stringdist 패키지에는 'hello' 문자열과 편집 거리(edit distance, Levenshtein metric)가 가장 짧은 문자열의 위치를 찾아주는 amatch() 함수가 있습니다.  아래 예처럼 maxDist=2 라고 설정하면 편집 거리가 2를 넘어서는 문자열은 무시하게 됩니다.  동일 최소 편집거리 문자열이 여러개 있으면 앞에 위치한 문자열의 위치를 제시해줍니다. 

> # Approximate string matching > # amatch returns the position of the closest match of x in table > # by default, the OSA algorithm is used  > # : Optimal string aligment (restricted Damerau-Levenshtein distance) > amatch(c("hello"),c("hillu","hala","hallo", "hi"),maxDist=2) [1] 3

- 'hello' 문자열과 'hillu' 문자열 간 편집 거리는 2 ('i'를 'e'로 교체, 'u'를 'o'로 교체), 

- 'hello' 문자열과 'hala' 문자열 간의 편집 거리는 3 ('a'를 'e'로 교체, 'l' 추가, 'a'를 'o'로 교체, 단, maxDist=2 이므로 고려 대상에서 제외됨), 

- 'hello' 문자열과 'hallo' 문자열 간의 편집 거리는 1 ('a'를 'e'로 교체)

이므로 편집 거리가 가장 짧은 'hallo' 의 위치인 3 을 반환합니다. 

* reference: stringdist package manual ( https://cran.r-project.org/web/packages/stringdist/stringdist.pdf)

많은 도움이 되었기를 바랍니다. 

이번 포스팅이 도움이 되었다면 아래의 '공감~'를 꾸욱 눌러주세요. ^^