【JavaScript】文字列検索の手法

先日、検索の手法でレーベンシュタイン距離というのを知りました。

調べていると、どうやら他にも文字検索の手法があるそうな。

今回はJavaScriptを使用してそれらを実装してみました。

レーベンシュタイン距離

まずはレーベンシュタイン距離から見ていきましょう。

レーベンシュタイン距離の求め方について、
下記のような記述を見つけました。

簡単に言うと、ある文字列Aと別の文字列Bを比較した時に、二つの言葉がどの程度異なっているかを示す尺度です。

もう少し具体的に言うと、文字列Aを文字列Bに変えるために、文字の置換・削除・挿入を何回行う必要があるか？を計算し、その回数がレーベンシュタイン距離となります。

なるほど。
置換等の回数が少ないほど文字列が似ているということですね。

レーベンシュタイン距離の実装

では実際の実装例をみてみましょう。

自力での実装は骨が折れるため、
今回はChatGPTに実装をお願いしました。

function levenshteinDistance(str1, str2) {
  const len1 = str1.length;
  const len2 = str2.length;

  // DPテーブルを作成
  const dp = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(0));

  // 初期化
  for (let i = 0; i <= len1; i++) dp[i][0] = i;
  for (let j = 0; j <= len2; j++) dp[0][j] = j;

  // DPテーブルを埋める
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // 文字が一致する場合
      } else {
        dp[i][j] = Math.min(
          dp[i - 1][j] + 1, // 削除
          dp[i][j - 1] + 1, // 挿入
          dp[i - 1][j - 1] + 1 // 置換
        );
      }
    }
  }

  // 最終的な編集距離を返す
  return dp[len1][len2];
}

function similarity(str1, str2) {
  const distance = levenshteinDistance(str1, str2);
  const maxLength = Math.max(str1.length, str2.length);

  // 最大長が0の場合は100%（両方とも空文字列の場合）
  if (maxLength === 0) return 100;

  // 類似度計算
  const similarityScore = (1 - distance / maxLength) * 100;
  return similarityScore.toFixed(2); // 小数点以下2桁に丸める
}

// 使用例
const str1 = "kitten";
const str2 = "sitting";

const distance = levenshteinDistance(str1, str2);
const similarityScore = similarity(str1, str2);

console.log(`Levenshtein Distance between "${str1}" and "${str2}": ${distance}`);
console.log(`Similarity: ${similarityScore}%`);

str1 str2 にそれぞれ任意の文字列を入力すると
レーベンシュタイン距離、類似度が表示されます。

注意
置換・削除・挿入に対してそれぞれ異なる重みを指定することもあるため、
「編集距離が最小 = レーベンシュタイン距離である」とは限りません。

メリット/デメリット

ジャロ・ウィンクラー距離

ジャロ・ウィンクラー距離は下記のようなものです。

ある文字列と別の文字列で一致する文字数と置換の要不要から距離を計算する。ジャロ・ウィンクラー距離は、距離の取りうる値が0～1であり、距離の数値が大きいほど文字列間の類似度が高いことを表す。そのため、距離が0の時は全く異なる文字列であることを、距離が1の時は完全に一致している文字列であるという意味になる。

今度は距離の数値が大きいほど類似度が高いようです。

ジャロ・ウィンクラー距離の実装

こちらもChatGPTにお願いしました。

function jaroWinklerDistance(s1, s2) {
  // 両方の文字列が空の場合、完全一致
  if (!s1 && !s2) return 1.0;

  // 片方が空の場合、類似度は0
  if (!s1 || !s2) return 0.0;

  const len1 = s1.length;
  const len2 = s2.length;

  // 一致範囲（matching window）のサイズを計算
  const matchDistance = Math.floor(Math.max(len1, len2) / 2) - 1;

  let matches = 0; // 一致する文字数
  let transpositions = 0; // 順序が異なる一致の数
  const s1Matches = new Array(len1).fill(false);
  const s2Matches = new Array(len2).fill(false);

  // 一致する文字をカウント
  for (let i = 0; i < len1; i++) {
    const start = Math.max(0, i - matchDistance);
    const end = Math.min(i + matchDistance + 1, len2);

    for (let j = start; j < end; j++) {
      if (s2Matches[j] || s1[i] !== s2[j]) continue;
      s1Matches[i] = true;
      s2Matches[j] = true;
      matches++;
      break;
    }
  }

  // 一致する文字がなければ類似度は0
  if (matches === 0) return 0.0;

  // 転置（順序が異なる一致）のカウント
  let k = 0;
  for (let i = 0; i < len1; i++) {
    if (!s1Matches[i]) continue;
    while (!s2Matches[k]) k++;
    if (s1[i] !== s2[k]) transpositions++;
    k++;
  }
  transpositions /= 2;

  // Jaro 距離を計算
  const jaro = (matches / len1 + matches / len2 + (matches - transpositions) / matches) / 3;

  // Jaro-Winkler 調整
  const prefixLength = Math.min(4, [...s1].findIndex((c, i) => c !== s2[i]) || 4);
  const scalingFactor = 0.1; // 通常 0.1 を使用
  return jaro + prefixLength * scalingFactor * (1 - jaro);
}

// 使用例
const str1 = "MARTHA";
const str2 = "MARHTA";

const similarity = jaroWinklerDistance(str1, str2);
console.log(`Jaro-Winkler Similarity between "${str1}" and "${str2}": ${similarity.toFixed(4)}`);

str1 str2 にそれぞれ任意の文字列を入力すると類似度が表示されます。

注意
Winkler調整によって最初の数文字が一致している場合、スコアが調整されます。
仕様によって、最大4文字で一致しているか設定されています。

N-gram法

N-gramは下記のような手法です。

自然言語処理におけるN-gramとは、「文字列をN個の連続するシンボルで分割していき、その分割した文字列に対し出現頻度やパターンの分析を行う」という手法です。ここで言うシンボルとは文字や形態素など、自由に決めることができます。

N-gram法の実装

function generateNGrams(str, n) {
  const nGrams = [];
  for (let i = 0; i <= str.length - n; i++) {
    nGrams.push(str.slice(i, i + n));
  }
  return nGrams;
}

function nGramSimilarity(str1, str2, n) {
  // N-gramを生成
  const nGrams1 = generateNGrams(str1, n);
  const nGrams2 = generateNGrams(str2, n);

  // 共通N-gramの数を計算
  const set1 = new Set(nGrams1);
  const set2 = new Set(nGrams2);

  const intersection = new Set([...set1].filter((ngram) => set2.has(ngram)));

  // 類似度を計算
  const similarity = (2 * intersection.size) / (set1.size + set2.size);
  return similarity;
}

// 使用例
const str1 = "kitten";
const str2 = "sitting";
const n = 2; // Bi-gram

const similarity = nGramSimilarity(str1, str2, n);
console.log(`N-Gram Similarity (${n}-gram) between "${str1}" and "${str2}": ${(similarity * 100).toFixed(2)}%`);

generateNGrams関数に入力文字列とNを渡すことで、
文字列のリストを生成します。

例のkittenの場合だとn = 2なので
["ki", "it", "tt", "te", "en"]が生成されます。

sittingにも同じ処理を施し、
Setに変換した後共通部分を計算します。

その後、それらの値を使用して類似度の計算を行っています。

Nの選択
Nの値を変更し、異なる精度で比較できます。

小さいN：広範囲なマッチングが可能
大きいN：厳密な一致が必要

比較

それぞれ下記のような場面で使用するのがいいのかなと思います。

アルゴリズム	適した場面	適さない場面
レーベンシュタイン距離	正確な文字列の比較が必要な場合（ファイル名、スペルチェック、短い文字列）。	長い文字列の部分一致や前方一致を重視する場合。
ジャロ・ウィンクラー距離	人名、住所、会社名など、先頭部分が重要でスペルミスを許容したい場合。	長い文字列や部分一致を評価したい場合。
N-gram法	長い文字列、曖昧な一致、部分一致が重要な場合（自然言語処理や曖昧検索）	短い文字列や完全一致に近い評価が必要な場合。

おわりに

いろいろな手法があることを知りました。

それぞれメリット/デメリットが存在するので、
適切に使い分けていきたいです。

それでは。

参考文献