文字列の類似度を計算するアルゴリズムを実装した

レーベンシュタイン距離ではだめなのか

文字列の類似度を計算するアルゴリズムの一つとして、レーベンシュタイン距離がありますが、計算量が O(mn) であるため、文字数が増えると計算量が加速度的に増えてしまいます。
ですので、計算量が少ないものを求めたところ、以下のサイトにあるものが参考になりましたので、Javascript(Typescript)で実装してみることにしました。

N-gramを求める

1-gramから3-gram(unigramとかtrigramとかいうらしい)を求めて、

{[n-gram]:[そのn-gramが出た回数]}

を返す関数が都合がよさそうです。
以下のように実装しました。

const getToNgram = (text: string, n: number = 3) => {
  let ret: { [key: string]: number } = {};
  for (var m = 0; m < n; m++) {
    for (var i = 0; i < text.length - m; i++) {
      const c = text.substring(i, i + m + 1);
      ret[c] = ret[c] ? ret[c] + 1 : 1;
    }
  }
  return ret;
};

まんま実装しただけなので、特記することはないです。

余弦を求める

余弦を求めるには、内積/長さの積を求めれば良いようなので、求めてみました。

// valueが数値のobjectの数値の和を求める関数。
const getValuesSum = (object: { [key: string]: number }) => {
  return Object.values(object).reduce((prev, current) => prev + current, 0);
};

const calculate =  (a: string, b: string) => {
  const aGram = getToNgram(a);
  const bGram = getToNgram(b);
  const keyOfAGram = Object.keys(aGram);
  const keyOfBGram = Object.keys(bGram);
  // aGramとbGramに共通するN-gramのkeyの配列
  const abKey = keyOfAGram.filter((n) => keyOfBGram.includes(n));

  // aGramとbGramの内積(0と1の掛け算のため、小さいほうの値を足し算すれば終わる。)
  let dot = abKey.reduce(
    (prev, key) => prev + Math.min(aGram[key], bGram[key]),
    0
  );

  // 長さの積(平方根の積は積の平方根)
  const abLengthMul = Math.sqrt(getValuesSum(aGram) * getValuesSum(bGram));
  return dot / abLengthMul;
};

完成

See the Pen 文字列の類似度 by ajiken4610 (@ajiken4610) on CodePen.

以上。