Soundex 기법 정리하면서... - from __future__ import dreamfrom __future_

예전에 spell correction을 하기위해 edit distance를 사용할 수 있다는 이야기를 했다. 물론 포탈이나
여러곳을 가보니 다 이런 방식으로 거의 다 적용이 되어 있더라. 사실 그 당시는 잘 몰랐기도 했거니와 내 나름대로 고민하고
생각해서 올려본것인데 이미 다른 사람들도 같은 생각을 하고 있더라.

이번의 기법은 이 역시 robust한 검색 시스템을 만들기 위해 soundex를 사용하면 어떨까 하고 올려본다.

soundex 기법은 사실 Programming Perls라는 책을 보다가 나온 개념이다. 물론 이 책의 번역서가 생각하는 프로그래밍이라는 책으로 나와있다.

알고리즘은 간단하다 “발음이 비슷하게 나오는 단어는 동일한 코드가 나오도록 부호화”하는 개념이다. 책에서는 저장 용량과 search 복잡도, 그리고 문제에 대한 정확한 이해의 측면에서 접근을 하고 있는거 같다.

사실 이 개념을 이용하면 edit distance의 개념과 비슷한 용도로 쓸수 있다. 두 단어가 얼마나 비슷하냐… 정확한
매칭의 개념이 아니라 얼마나 비슷하느냐이다. 이것은 문서중복에서도 같은 개념이 나온다. exact dup.과 near dup.

정확한 매칭에 대한 개념은 문서의 경우 md5의 개념, 그리고 string의 경우 brute-force,
Boyer-Moore 같은 알고리즘을 이용한 알고리즘이 있다면 이와 다른면의 near matching쪽에는 Soundex와
edit distance가 있다. edit distance는 Levenshtein알고리즘하고 같은걸로 알고 있다.(비슷하던가… ?? 같던가??)
문서의 경우는 shingle, i-match 그리고 올해 구글이 특허를 낸 Similarity Engine이라는 것이 있겠다. simility engine은 내가 봤을땐, shingle과 i-match의 개념이 합쳐진거라고 생각하는데 정확한건지는 잘 모르겠다. 그닥 새로운 개념도 아닌듯 한데, 특허를 내버렸더군.

움…. 그럼 Soundex를 어디에다가 써먹을까? 이것도 역시 spell correction에 쓸수 있지 않을까 한다.
아니면 외래어의 발음인경우 쿼리 확장하는데도 쓰여도 될거 같다. 예를들어 ‘타이레놀’과 ‘타이래놀’처럼…

그럼 영어의 경우 어떻게 적용이 되는지 알고리즘을 따져보자.

1. 첫번째 문자는 문자 그대로 복사한다.
2. 그 다음에 오는 문자는 모두 다 아래의 코드로 바꾼다.
bfpv -> “1”, cgjkqsxz -> “2”, dt -> “3”, l -> “4”, mn ->”5″, r -> “6”
3. 다른 문자는 무시하고 반복되는 문자는 그중 하나만을 사용한다.
4. 코드길이가 4가 되면 부호화를 마치고, 길이가 모자랄때는 0으로 채운다.

아래는 D language로 구현한 소스이다. 물론 내가 구현한건 아니구. std.string
라이브러리 소스에서 따왔다. 굉장히 직관적인 소스라서 구현해볼 필요나 세심하게 볼 필요는 없을듯하다. 다만 이 소스보고 D
language의 input parameter와 return value에 대한 evaluation을 하는 부분을 보는 행운을
얻었다. 바로 contract programming 방법을 D language에서는 언어단에서 지원을 한다는걸 알았다.(이야기가 옆으로 세나가기 시작하는군.. ㅜㅜ)

아래는구현 코드다.

[CODE C]
char[] soundex(char[] string, char[] buffer = null)
in //input인자의 유효성을 판단한다. 4 char이상을 포함할수 있는지 확인…
{
   assert(!buffer || buffer.length >= 4);
}
out (result) // return 되는 값의 유효성을 판단한다. 반드시 코드길이는 4가 되어야 한다.
{
   if (result)
   {
   assert(result.length == 4);
   assert(result[0] >= ‘A’ && result[0] <= ‘Z’);
   foreach (char c; result[1 .. 4])
   assert(c >= ‘0’ && c <= ‘6’);
   }
}
body //실제 함수의 본문이다. 이하 부분은 일상적인 코드다.
{
   static char[26] dex =
   // ABCDEFGHIJKLMNOPQRSTUVWXYZ
   “01230120022455012623010202”;

   int b = 0;
   char lastc;
   foreach (char c; string)
   {
   if (c >= ‘a’ && c <= ‘z’)
   c -= ‘a’ – ‘A’; //대문자로 norm 한다.
   else if (c >= ‘A’ && c <= ‘Z’)
   {
   ;
   }
   else
   { lastc = lastc.init;
   continue;
   }
   if (b == 0)
   {
   if (!buffer)
   buffer = new char[4];
   buffer[0] = c;
   b++;
   lastc = dex

;
   }
   else
   {
   if (c == ‘H’ || c == ‘W’)
   continue;
   if (c == ‘A’ || c == ‘E’ || c == ‘I’ || c == ‘O’ || c == ‘U’)
   lastc = lastc.init;
   c = dex

;
   if (c != ‘0’ && c != lastc)
   {
   buffer[b] = c;
   b++;
   lastc = c;
   }
   }
   if (b == 4)
   goto Lret;
   }
   if (b == 0)
   buffer = null;
   else
   buffer[b .. 4] = ‘0’;
Lret:
   return buffer;
}
[/CODE]

이번 포스팅은 여러가지 혼재되어서 설명이 된듯하다. 역시나 뭐든 파고들면 끝이 없다. ^^;
그리고 다른 오픈소스 코드들을 리뷰하는것을 게을리 하면 안되겠다는 생각이 다시하번 들었다.

지금 만들고 있는 spam server가 가끔 core dump를 떨어뜨리는데 아마도 만든 모든 함수들의 input, output을 이런 방식으로 evaluation 해봐야 겠다.

일단 영어는 저렇구 다음으로는 한글 soundex룰을 찾아봐야 겠군.

from future import dream

당신의 나의 뜨거운 감자!

Soundex 기법 정리하면서…

관련