📂アルゴリズム

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)