쿠...sal: [컴][알고리즘] Edit distance

fuzzy search / 검색 / 알고 /

Edit distance

edit distance 는 ‘Levenshtein distance’ 를 이야기 한다.

이 edit distance 가 어디에 쓰이냐면, fuzzy search 같은 대략적인 문자열을 매칭할떄 쓰인다.(Approximate string matching - Wikipedia) 이외에도 spell checker 나 OCR 등에서도 쓰인다고 한다.

이 Levenshtein distance 는 두 문자열을 비교해서 얼마나 다른가를 distance 로 표현한다. 이 distance 값은 2개의 문자열을 비교해서 ‘삽입’, ‘삭제’, ‘수정’ 이 얼마나 일어났는지를 확인해서 그 차이를 표현한 것이라 보면 된다.

‘삽입’, ‘삭제’, ‘수정’에 각각 같은 값을 줄 수도 있고, ’삽입’에 더 많은 값을 주거나 하는 등 각각의 비용은 다르게 처리할 수 있다. 예를 들어 ’삽입’ 1번 , ‘수정’ 1번이 필요한 경우, 이것을 각각 1의 비용을 산정해서 distance 2 로 표현할 수 있고, 삽입을 0.5로 비용을 산정해서 1.5 로 표현할 수도 있다.(0.5 + 1)

예시

길이가 같은 문자열 2개를 비교하는 예시를 한번 보자. 여기서는 ‘삽입’, ‘삭제’, ’수정’에 모두 1의 비용(cost) 이 발생한다고 보자.

A: hello my name is Tom B: hello my name is Gom

그럼 다음처럼 비교를 하게 된다.

‘h’ , ‘h’ -> 0
‘e’ , ‘e’ -> 0
‘l’ , ‘l’ -> 0
‘l’ , ‘l’ -> 0
‘o’ , ‘o’ -> 0
’ ’ , ’ ’ -> 0
‘m’ , ‘m’ -> 0
‘y’ , ‘y’ -> 0
’ ’ , ’ ’ -> 0
‘n’ , ‘n’ -> 0
‘a’ , ‘a’ -> 0
‘m’ , ‘m’ -> 0
‘e’ , ‘e’ -> 0
’ ’ , ’ ’ -> 0
‘i’ , ‘i’ -> 0
‘s’ , ‘s’ -> 0
’ ’ , ’ ’ -> 0
‘T’ , ‘G’ -> 1 // 수정
‘o’ , ‘o’ -> 0
‘m’ , ‘d’ -> 1 // 수정

그러면 두문자열에 대한 levenshtein distance 는 2이 된다. 다시말하면, A,B라는 2개의 문자열이 있을 때, A를 기준으로 삼으면, B는 2번의 수정을 거쳐서 A와 같아진다.라고 이야기할 수 있다.

참고로, 다른 길이 문자열은 길이가 다른 부분을 공백(’ ’)등으로 채워주면 된다. 그러면 그 부분에서는 distance 가 추가된다.

matrix

그런데 이것을 전체 string 에 대해서만 비교를 하지 않는다. 모든 case에 대해서 계산해서 행렬(matrix)를 만든다. matrix 가 있으면, backtracking 을 해서 비교대상 string 이 original string 으로 변경하기 위한 계산등을 할 수 있다.

아래 메트릭스를 보자. 이 메트릭스로 sittery 라는 문자열을 kitten으로 바꿀 수 있다.(sittery –> kitten)

가장 오른쪽 아래 cell 에서 시작한다.

현재의 cell 의 character가 다를 때

’위’로 가면, insertion
‘왼쪽’ 으로 가면 ‘deletion’
‘대각선위’로 가면 ’substitution’(교체)

의 의미를 갖는다. 현재 cell 의 character가 같다면 그냥 대각선위로 움직인다.

	“”	s	i	t	t	e	r	y
“”	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	1	2	3
n	6	6	5	4	3	2	2	3

여기서 2가지 방법이 나온다. 오른쪽 아래에서 시작하면, 처음에 ‘대각선위’ 또는 ’왼쪽’으로 갈 수 있다.

여기서 그러면, 어디를 택하는 것이 맞을 것인가.

대체로 substitution 보다는 deletion, insertion 의 비용을 더 적게 잡는 듯 하다. 실제로도 위의 경우 substitution 으로 가면, 계속 character 를 변경해야 하지만, deletion 방향으로 움직이면, 그 후의 값들은 쭉 맞게 된다.

아래 그림에서도 보면, substitution 은 1, deletion, insertion 은 0.5 의 cost 를 준다.

https://en.wikipedia.org/wiki/Levenshtein_distance#/media/File:Levenshtein_distance_animation.gif

Reference

슬래시 / slash / 슬래쉬

url 뒤에 ’/’를 붙이는 nginx 설정

현재 내 nginx 는 다음과 같다.

http://localhost/home : 404 error 가 난다.
http://localhost/home/ : http://localhost/home/index.html 을 호출해준다.

그래서 뒤에 ‘/’ 를 붙이는 설정을 해줘야 했다. 일단 내 경우는 다음의 답변이 적절한 듯 하다.

regex - Add slash to the end of every url (need rewrite rule for nginx) - Stack Overflow

위의 답변에서는 file 일때는 ‘/’을 뒤에 붙이지 않고, file 이 아닌경우에’/’ 를 붙이게 된다.

추가로 http://localhost/home?q=test 의 경우도 ‘/’ 를 붙여서 http://localhost/home/?q=test로 만들어준다.

server {
   # ...
   if (!-f $request_filename) {
     rewrite [^/]$ $uri/ permanent;
   }
   location / {
      # CMS logic, e.g. try_files $uri $uri /index.php$request_uri;
   }
   # ...
}

sed -i ‘s,location / {,# add slash to the end of $uriif (!-f $request_filename) {\n rewrite [^/]$ $uri/ permanent;}location / {,’ /etc/nginx/conf.d/default.conf

References

Levenshtein distance - Wikipedia

쿠...sal

[컴][알고리즘] Edit distance

Edit distance

예시

matrix

관련 다른 알고리즘

Reference

url 뒤에 ’/’를 붙이는 nginx 설정

References

댓글 없음:

댓글 쓰기