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가 같다면 그냥 대각선위로
움직인다.
| “” |
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 를 준다.
관련 다른 알고리즘
Reference
- Edit
Distance. The Dynamic and The Recursive Approach | by Deboparna Banerjee
| Medium
- 비슷한
명령어 추천은 어떻게 하는걸까?
슬래시 / slash / 슬래쉬
url 뒤에 ’/’를 붙이는 nginx
설정
현재 내 nginx 는 다음과 같다.
http://localhost/home : 404 error 가 난다.http://localhost/home/ :
http://localhost/home/index.html 을 호출해준다.
그래서 뒤에 ‘/’ 를 붙이는 설정을 해줘야 했다. 일단 내 경우는 다음의
답변이 적절한 듯 하다.
위의 답변에서는 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
