📂Algorithm

n-Gram and Jaccard Coefficient

Definition

• An n-gram refers to a string cut into pieces of $n$ characters each.
• The jaccard coefficient is a measure of how similar two sets are, taking a value between $0$ and $1$. Expressed as a formula, it is as follows. $$ JC(A,B) = {{| A \cap B|} \over {| A \cup B| }} = {{| A \cap B|} \over { |A|+ |B| -| A \cap B| }} $$

Example

For example, the bigrams (2-grams) of the string ‘오마이갓’ would be ‘오마’, ‘마이’, and ‘이갓’. Using these two concepts, one can express the similarity between two given strings as a concrete number. Here, how to choose $n$ appropriately and from what value of the Jaccard coefficient two strings are considered similar is up to the developer.

The Jaccard coefficient calculated after cutting ‘oh my god’ and ‘oh my girl’ into bigrams is $0.5454545$. If we take $0.5$ as the criterion and judge two strings to be similar when the value is higher than this, then ‘oh my god’ and ‘oh my girl’ are similar strings.

Code

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)