📂알고리즘

n-그램과 자카드 계수

정의

• n-그램^n-gram이란 어떠한 문자열을 n개씩 끊어서 자른 것을 말한다.
• 자카드 계수^{jaccard Coefficient}란 두 집합이 얼마나 비슷한지에 대한 척도로써 $0$ 부터 $1$ 사이의 값을 가진다. 수식으로 표현하면 다음과 같다. $$ JC(A,B) = {{| A \cap B|} \over {| A \cup B| }} = {{| A \cap B|} \over { |A|+ |B| -| A \cap B| }} $$

예시

예를 들어 ‘오마이갓’이라는 문자열의 바이그램(2-gram)이라면 ‘오마’, ‘마이’, ‘이갓’ 이 된다. 이러한 두 개념을 이용하면 주어진 두 문자열의 유사도를 구체적인 수로 나타낼 수 있다. 여기서 $n$ 을 어떻게 줘야 적당한지, 자카드 계수가 어느정도부터 비슷하다고 할지는 개발자의 재량이다.

‘oh my god’과 ‘oh my girl’를 바이그램으로 자른 후 구한 자카드 계수는 $0.5454545$ 다. $0.5$ 를 기준으로 이보다 높을 때 두 문자열을 비슷한 것으로 판단한다면 ‘oh my god’과 ‘oh my girl’은 유사한 문자열이다.

코드

JC<-function(A,B,k=2)
{
  subA<-character()
  subB<-character()
  for(i in 1:(nchar(A)-k+1))
  {
    subA<-c(subA,substring(A,i,i+k-1))
  }
  subB<-character()
  for(i in 1:(nchar(B)-k+1))
  {
    subB<-c(subB,substring(B,i,i+k-1))
  }
  
  return(length(intersect(subA,subB))/(length(subA)+length(subB)-length(intersect(subA,subB))))
}
 
JC("oh my god",'oh my girl',2)