기본적인 아이디어는 단어를 잘게 자른 조각(그것을 shingle 이라 하자)들을 모은 후, 그 조각들이 많이 비슷하면 비슷할수록 두 단어가 비슷하다는 것이다. 예를 들어 보자. adenophorae radix 와 adenophora 를 비교하는 모습을 살펴 보자. 논의의 편의를 위하여 shingle 의 길이를 2 개로 제한하자.
adenophorae radix --> ad
a
denophorae radix --> de
ad
enophorae radix --> en
aden
ophorae radix --> op
...
adenophorae ra
dix --> di
adenophorae rad
ix --> ix
따라서 adenophorae radix 의 shingle 은 { 'ad', 'de', 'en', ..., 'ix' } 가 된다. 같은 식으로 adenophora 에 대한 shingle도 구할 수 있다. 주어진 단어에 대한 shingle 의 집합을 S라 하자. 즉,
S('adenophorae radix', 2) = { 'ad', 'de', 'en', ..., 'ix' },
S('adenophora', 2) = { 'ad', ..., 'ra' }
가 된다. 쉽게 생각을 해보자. 위와 같이 shingle 을 정의한 상태에서, 두 단어가 '비슷하다'면? 즉, 두 집합이 비슷하다면? 그렇다면 두 집합을 교집합 시킨 것과 합집합 시킨 것이 유사할 것이다. 즉 두 집합 A 와 B에 대하여
n( A ∩ B ) ≒ n( A ∪ B )
일 것이다. 다시 표현하면,
n( A ∩ B ) ÷ n( A ∪ B ) ≒ 1.0
일 것이다. 따라서, 위의 경우에 대하여, resemblance R 을,
R(A,B) = n( A ∩ B ) ÷ n( A ∪ B ) --------------------------------- (1)
로 정의하면, 우리가 생각하는 것을 수학적으로 적절히 표현할 수 있게 된다. 극단적인 경우, R(A,A) = 1.0 인 것이다. 위 식을 C++ 코드로 간단히 표현해 보자.
접기
std::set<std::string> get_shingle(const std::string& str, int size)
{
std::set<std::string> shingle;
int length = (int)(str.size());
int max_pos = length - size;
int i = 0;
for(i = 0; i<=max_pos; i++){
shingle.insert(str.substr(i, size));
}
return shingle;
}
bool get_resemblance(
const std::string& str1,
const std::string& str2,
double *r, double *c1, double *c2)
{
std::set<std::string> s1 = get_shingle(str1, 2);
std::set<std::string> s2 = get_shingle(str2, 2);
if(s1.empty() == true || s2.empty() == true) return false;
std::set<std::string> com;
std::set<std::string> all;
std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::inserter(com, com.begin()));
std::set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::inserter(all, all.begin()));
double com_size = (double)(com.size());
double union_size = (double)(all.size());
*r = com_size/union_size;
*c1 = com_size/s1.size();
*c2 = com_size/s2.size();
return true;
}
(최대한 명시적 코드를 작성하기 위해 성능은 거의 고려하지 않음)
접기
get_shingle 함수는 주어진 단어를 주어진 길이로 자른 조각 집합을 반환해 준다. get_resemblance 함수는 위의 식에 따라 계산한 값들을 반환한다. containment, 즉, 한 단어가 다른 단어에 '포함'되어 있는가 역시 '비슷한' 단어가 포함되어 있는가로 생각해 볼 수 있고, 쉽게 계산할 수 있다. get_resemblance 함수는 containment 까지 반환한다. 위 코드로 adenophorae radix 와 adenophora 의 resemblace 와 containment 를 구해 보면,
resemblance : 0.642857
containment of 'adenophora' in 'adenophorae radix' : 1.0
containment of 'adenophorae radix' in 'adenophora' : 0.642857
가 나온다. 어느 정도 합당한 값으로 보인다.
위의 알고리즘은
Syntactic Clustering of the Web(pdf임)에서 소개된 것으로, 인터넷에서 두 '문서'의 유사도를 계산하기 위하여 제안된 것이다. 위처럼 결과적으로 방법은 간단해도 그것은 어느 정도 수학적으로 뒷받침된다. 본 문서에서는, 두 문서의 유사도를 계산할 때, shingle 을 섞은 후 s 개를 선택해서 위의 식(1)처럼 계산하거나, m 번째 요소를 선택해서 식(1)처럼 계산하면 resemblance 에 대한 unbiased estimator 가 된다는 것이다. 또, shingle 은 자갈, 작은 돌, 로 해석할 수 있겠는데, 문서들을 단어들로 나눠서 단어들이 얼마나 비슷하게 본다는 개념에서 단어들을 '자갈'이라고 표현한 것이다. 하여튼 이와 같은 알고리즘을, 단어의 유사도를 찾기 위하여 나는 위처럼 다소 간단히 적용해 보았다. 음... 저 알고리즘을 적용해야 할 데이터가 결국은 사람이 눈으로 다시 한 번 확인을 해야만 하는 것이라서 대충 구현해도 되기 때문에...
