レーベンシュタイン距離によるサジェストUI改善の取り組み

はじめに

こんにちは。イタンジ株式会社賃貸仲介支援事業プロダクト開発の稲垣です。

今回は、レーベンシュタイン距離を導入してwebサービスのUI/UXを向上させた事例について紹介します。

レーベンシュタイン距離とは

レーベンシュタイン距離（Levenshtein distance）は、2つの文字列間の差異を測定するための指標です。この距離は、ある文字列を別の文字列に変換するために、文字を最小で何回入れ替えればよいかという数として定義されます。 (文字の追加・削除は""(空文字)と入れ替えとみなして1カウント)

詳しいアルゴリズムについてはここでは記載しませんが、実際に以下のようなコードでレーベンシュタイン距離を計算しています。

const levenshteinDistance = (source: string, target: string): number => {
  const distanceMatrix: number[][] = Array.from(
    { length: source.length + 1 },
    () => Array<number>(target.length + 1).fill(0),
  );

  // 最初の行と列を初期化
  for (let sourceIndex = 0; sourceIndex <= source.length; sourceIndex += 1) {
    distanceMatrix[sourceIndex][0] = sourceIndex;
  }
  for (let targetIndex = 0; targetIndex <= target.length; targetIndex += 1) {
    distanceMatrix[0][targetIndex] = targetIndex;
  }

  // レーベンシュタイン距離を計算
  for (let sourceIndex = 1; sourceIndex <= source.length; sourceIndex += 1) {
    for (let targetIndex = 1; targetIndex <= target.length; targetIndex += 1) {
      const substitutionCost =
        source[sourceIndex - 1] === target[targetIndex - 1] ? 0 : 1;
      distanceMatrix[sourceIndex][targetIndex] = Math.min(
        distanceMatrix[sourceIndex - 1][targetIndex] + 1, // 削除
        distanceMatrix[sourceIndex][targetIndex - 1] + 1, // 挿入
        distanceMatrix[sourceIndex - 1][targetIndex - 1] + substitutionCost, // 置換
      );
    }
  }

  return distanceMatrix[source.length][target.length];
};

このように数行のコードで計算でき、事前に学習などが必要ないため簡単に導入することができます。

レーベンシュタイン距離の応用例

タグのサジェスト機能

弊社のCRMツール（ノマドクラウド）では、顧客へのタグ付け機能があります。

しかし、ユーザーがタグ付け機能を利用する際、似たようなタグが多数作成される事例が頻発していました。

例えば、

イタンジ(株)
イタンジ（株）
イタンジ_2024
イタンジ2024

といった具合です。

この問題を解決するために、タグの入力時に既存のタグをサジェストする機能を設けました。ただし、サジェストするタグをシンプルに前方一致や部分一致で検索してしまうと、上記のようなタグの差異を検出できず解決にはなりません。そこで、レーベンシュタイン距離を用いて入力されたタグと既存のタグの差異を計算し、差異が小さいタグをサジェストすることでユーザーが似たタグを作成することを防ぐことができました。

分析条件の検索機能

タグのサジェスト機能の他に、分析条件の検索機能にもレーベンシュタイン距離を活用しています。弊社のCRMツールにはデータ分析の画面が存在し、分析条件に名前をつけて保存することができます。

この名前はある程度長く、日付などの数字や記号が入り全角と半角文字が入り交じることが予想できたため、レーベンシュタイン距離を用いて簡易的なあいまい検索として実装しました。

具体的にはシンプルな部分一致検索とOR条件として、レーベンシュタイン距離による判定を加えました。

// あいまい検索の実装例
partialMatch(searchText, name) || levenshteinDistance(searchText, name) <= 1

許容するレーベンシュタイン距離を1以下と短めに設定することで、半角と全角の違いを吸収しつつも入力したテキストにマッチする検索結果のみを表示することができました。

レーベンシュタイン距離の注意点

このように非常に便利なレーベンシュタイン距離ですが、いくつか注意点があります。

一つは計算量の問題で、計算量がO(n²)となるため、文字列の長さが大きい場合には計算時間がかかることがあります。ただし、今回のようなタグや名前といった程度なら全く問題ありません。計算はクライアントサイドで実行していますが、体感できるほどの遅延はありません。

また、今回のようなタグのサジェスト機能として利用する場合には、タグをすべて事前に読み込んでおく必要があります。ページネーションを利用している場合、全てのタグを読み込むことができないため、サジェスト機能を利用することができません。

この点についてはMySQLのStored Functionを利用して、データベース側でレーベンシュタイン距離を計算することできるらしく、将来のタスクとして導入を検討しています。

まとめ

レーベンシュタイン距離は、文字列間の差異を定量的に評価するための強力なツールです。この距離を計算することで、サジェストやあいまい検索などの様々な機能に応用することができ、簡易的ながらも効果的な機能を効率的に提供することができます。

この記事を書いた人

ITANDI株式会社でエンジニアをやっている稲垣です。前職では工場作ってました。