📂アルゴリズム

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-グラム）は、「오마」、「마이」、そして、「이갓」になる。これら二つの概念を利用すると、与えられた二つの文字列の類似度を具体的な数値で表すことができる。ここで、$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)