導入

ふと、「文字の類似度ってどう計算するんだろう」と思って、調べて実際に作ってみました。

そもそも文字の類似度ってなに？

要は「文字列間がどれくらい似た者同士か？」ということです。

例えば、「りんご」と「ごりら」。

レーベンシュタイン距離に基づく類似度で求めると、

「り」「ん」「ご」
↓
「ご」「り」「ん」
↓
「ご」「り」「ら」

のように2手で変換できます。

以下の公式で求められることから、

類似度　＝　(1　－　レーベンシュタイン距離　÷　長い方の文の文字数)　* 100

結果としては以下になります。

類似度 = (1 - 2 / 3) ≒ 0.333 * 100

「りんご」と「ごりら」は、レーベンシュタイン距離に基づく類似度では「33」となるわけです。（数字が大きければ類似度が高い）

なお、レーベンシュタイン距離については、こちらの記事がわかりやすかったで、ぜひご覧ください。

文字nグラムの特徴ベクトルから求める類似度

レーベンシュタイン距離によって文字列の類似度を求めることができました。

他には、本題の「文字nグラムの特徴ベクトル」からも求めることができます。

どうやらGoogleの検索ロジックもこの方法を応用して検索候補を出しているとか。

詳細な求め方についてはこちらの記事がわかりやすかったので参考にしてみてください。

求め方を簡単に説明すると、

「文字列Aを分割して、分割した文字列を文字列Bと全パターンで比較して、どれくらい合致しているか？」

ということらしいです。

作成したコード

長々と説明しましたが、今回作成したコードは以下になります。

やっていることとしては、PASTAの文字列と

類似している文字列が入力されたら「Yes! パスタ作ったお前」が表示され、
類似しているものがない場合は「Noo.. パスタ作ってない。。。」が返却される、
というだけです。

（Vueを使用していますが、大枠のロジックは他のライブラリでも使用可能です。）

<script setup lang="ts">
type NGram = {
  nGram: string;
  duplicateId: number;
};

const PASTA: string[] = [
  '大親友の彼女の連れ',
  '家庭的な女がタイプの俺',
  '大貧民負けてマジ切れそれ見て',
  '優しい笑顔にまた癒されて',
  '嬉しくて嬉しくて',
  '好きって言いてぇおぼろげな月を',
  '守りたい女って',
  'まじめな顔して',
];

const str = ref('');

const flg = computed(() => chkMadePasta(str.value));

const generateNGram = (input: string): NGram[] => {
  return Array.from({ length: 3 }, (_, length) => length + 1).flatMap(
    (length) =>
      input
        .slice(0, input.length - length + 1)
        .split('')
        .map((_, i) => {
          const nGram = input.slice(i, i + length);
          const duplicateId = input.slice(0, i).split(nGram).length - 1;
          return { nGram, duplicateId };
        })
  );
};
const similarity = (str1: string, str2: string): number => {
  const nGrams1 = generateNGram(str1);
  const nGrams2 = generateNGram(str2);

  const matchCount = nGrams1.filter((item1) =>
    nGrams2.some(
      (item2) =>
        item1.nGram === item2.nGram && item1.duplicateId === item2.duplicateId
    )
  ).length;

  return (matchCount / Math.sqrt(nGrams1.length * nGrams2.length)) * 100;
};
const chkMadePasta = (str: string): boolean => {
  return PASTA.map((tsukutta) => similarity(tsukutta, str)).some(
    (omae) => omae >= 80
  );
};
</script>

<template>
  <div>
    <input type="text" v-model="str" />
    <p>{{ flg ? 'Yes! パスタ作ったお前' : 'Noo.. パスタ作ってない。。。' }}</p>
  </div>
</template>

こちらで動作確認できるので、ぜひよかったら見てみてください。
↓

解説

①文字nグラムを生成

const generateNGram = (input: string): NGram[] => {
  return Array.from({ length: 3 }, (_, length) => length + 1).flatMap(
    (length) =>
      input
        .slice(0, input.length - length + 1)
        .split('')
        .map((_, i) => {
          const nGram = input.slice(i, i + length);
          const duplicateId = input.slice(0, i).split(nGram).length - 1;
          return { nGram, duplicateId };
        })
  );
};

対象文字列を1~3文字で分割して、全パターンの文字列（N-gram）配列を生成しています。

今回は1~3文字分でN-gram配列を作成していますが、より類似度の精度を高めたい場合は分割する文字数を上げる必要があります。
なお、実際に出力される内容としては以下のようなイメージです。

const nGrams = generateNGram("パスタ");

// [["パ"], ["ス"], ["タ"], ["パス"], ["スタ"], ["パスタ"]]

②類似度の計算

const similarity = (str1: string, str2: string): number => {
  const nGrams1 = generateNGram(str1);
  const nGrams2 = generateNGram(str2);

  const matchCount = nGrams1.filter((item1) =>
    nGrams2.some(
      (item2) =>
        item1.nGram === item2.nGram && item1.duplicateId === item2.duplicateId
    )
  ).length;

  return (matchCount / Math.sqrt(nGrams1.length * nGrams2.length)) * 100;
};

こちらのコードで実際に類似度を求めています。

①で定義してある関数（generateNGram）を用いて、比較対象（nGrams1, nGrams2）からN-gram配列を取得してます。
matchCountでは両方のN-gram配列に共通する要素数を取得しています。
最終的には、一致したN-gramの数（matchCount）から、N-gram配列の平方根の積 (Math.sqrt(nGrams1.length * nGrams2.length)) を割って類似度を求めています。

類似度　= 一致したN-gramの数 / N-gram配列の平方根の積 * 100

③入力した文字列と比較したい文字列配列を比較する

const PASTA: string[] = [
  '大親友の彼女の連れ',
  '家庭的な女がタイプの俺',
  '大貧民負けてマジ切れそれ見て',
  '優しい笑顔にまた癒されて',
  '嬉しくて嬉しくて',
  '好きって言いてぇおぼろげな月を',
  '守りたい女って',
  'まじめな顔して',
];

const chkMadePasta = (str: string): boolean => {
  return PASTA.map((tsukutta) => similarity(tsukutta, str)).some(
    (omae) => omae >= 80
  );
};

PASTA配列の中に入力した文字列と類似しているものがないかどうかを判定しています。
今回の場合は、「類似度が80%以上の場合、類似している」という判定で作成しました。
（80%という数字に根拠はありません。）

まとめ

最後まで読んでくださりありがとうございます。
ふと「文字列ってどうやって類似しているかどうかを判定してるんだろう？」って思って調べてみましたが、結構いろいろな求め方があって面白かったです。
もし、文字の類似度をJS側で求めることがありましたが、参考にしてもらえると嬉しいです！

他にもいろいろな記事を投稿しているので、もしよかったら見てみてください！

ではでは！！

導入