n-gramで文字列の類似度を測定する

2020/02/272020/10/06

「レーベンシュタイン距離で文字列の類似度を高速に取得する」の続きです。文字列の類似度の別方法としてn-gramについて考慮します。

利点と欠点

レーベンシュタイン距離
- 処理速度が遅い
  - 一致度が低い場合、高速化しても遅い
- 位置の異なるキーワードに弱い
- 完全一致を判定できる
- 文字列同士の編集距離である
n-gram
- 処理が早い
- 位置の異なるキーワードに強い
- nより小さい文字列に一致できない
- 完全一致を判定できない
- 集団の中で何個が一致するかの数値である

※利用目的が、ブログタイトルの類似度から関連記事を算出することであるため、高速であり、位置の異なるキーワードに強い点でn-gramの方が理想的です

コード

ngramify.js// N-gram化する
const ngramify = function(text, set, n, padding) {
  n = n != null ? n : 3;
  if (text.length < n) {
    padding = padding != null ? padding : ' ';
    text = text + Array(n-text.length+1).join(padding);
  }

  if (n == 1 && !set) {
    set = new Set(text);
  } else {
    set = set || new Set();
    for (let i=text.length-n+1; i--; ) {
      set.add(text.substring(i, i+n));
    }
  }
  return set;
};

trigramify.js// 3文字づつに分解する
const trigramify = function(text, set) {
  text = '  '+text.toLowerCase()+'  ';
  set = set || new Set();
  for (let i=text.length-2; i--; ) {
    set.add(text.substring(i, i+3));
  }
  return set;
  // trigramify("太郎さんへのgiftです。");
  // ["。  ", "す。 ", "です。", "tです", "ftで", "ift", "gif", "のgi", "へのg", "んへの", "さんへ", "郎さん", "太郎さ", " 太郎", "  太"]
};

engramify.js// 英語（半角スペース区切り文字）を分割 + 全角文字3文字づつ分解する
// see https://www.bugbugnow.net/2020/02/English-simple-separation.html
const engramify = function(text, set) {
  set = set || new Set();
  const re = /[A-Z]+[a-z]*|[A-Z]*[a-z]+|'[A-Z]*[a-z]*|[0-9]+|[^A-Za-z0-9'"!\?\-:;,\.\s]+/g;
  let m;
  while ((m=re.exec(text)) !== null) {
    if (m[0].charCodeAt(0) <= 0xFE) {
      set.add(m[0].toLowerCase());
    } else {
      trigramify(m[0], set);
    }
  }
  return set;
  // engramify("It's a GiftCode for Mr. 太郎. 太郎のGIFTCodeです。");
  // ["it", "'s", "a", "gift", "code", "for", "mr", "郎  ", "太郎 ", " 太郎", "  太", "の  ", "への ", "んへの", "さんへ", "郎さん", "giftcode", "。  ", "す。", "です。", " です", "  で"]
};

relevance.js// ngramify, trigram, engramifyの関連度を計算する
const relevance = function(set1, set2) {
  let count = 0;
  set2.forEach(function(value) {
    if (set1.has(value)) {
      count = count + 1;
    }
  });
  return count / (set1.size + set2.size - count);
  // count: 一致数
  // set1.size + set2.size - count: チェック数
  // return: 0-1 (0: 不一致, 1:一致(完全一致とは限らない))
  // 第二引数が小さい方が高速に動作する(set1.size > set2.size)
};

使用例

var set1 = trigramify('Windows10のエクスプローラで遅い緑のバーの解決方法');
var set2 = trigramify('Windows10でウェブページの汚いフォントを置換える');
var set3 = trigramify('WSH(JScript)でコードを書いてみる');
var set4 = trigramify('ソースコードのライセンスの書き方');
console.log(relevance(set1, set2));   // 0.17307692307692307
console.log(relevance(set1, set3));   // 0.018518518518518517
console.log(relevance(set1, set4));   // 0