🔤

文字列の一致度を測定するレーベンシュタイン距離

2025/03/14に公開

とあるOCR技術の精度を表現するために、文字列の一致度を測定する必要がありました。
文字列の一致度を測定するには様々な指標がありますが、代表的な指標であるレーベンシュタイン距離（編集距離）の実装例について記載します。

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

using System;

// レーベンシュタイン距離を計算する関数
static int LevenshteinDistance(string s, string t)
{
    int m = s.Length;
    int n = t.Length;
    
    int[,] d = new int[m + 1, n + 1];
    
    for (int i = 0; i <= m; i++)
    {
        d[i, 0] = i;
    }
    
    for (int j = 0; j <= n; j++)
    {
        d[0, j] = j;
    }
    
    for (int j = 1; j <= n; j++)
    {
        for (int i = 1; i <= m; i++)
        {
            int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;
            
            d[i, j] = Math.Min(
                Math.Min(d[i - 1, j] + 1,      // 削除
                         d[i, j - 1] + 1),      // 挿入
                d[i - 1, j - 1] + cost);        // 置換
        }
    }
    
    return d[m, n];
}

レーベンシュタイン距離の100点満点への変換

レーベンシュタイン距離は0から1までの値で計算され、2つの文が似ているほど値が小さく（0に近く）、異なっているほど値が大きく（1に近く）なります。
この数値ではお客様相手に説明が難しいので、人間が理解しやすい指標にするには、以下の式で100点満点に変換できます。

類似度スコア = 100 * (1 - レーベンシュタイン距離 / 最大可能距離)

ここで最大可能距離は「より長い方の文字列の長さ」と定義します。

スコアの意味

100点: 完全に一致（距離 = 0）
0点: 全く異なる（距離 = 最大可能距離）
中間値: 部分的に一致

// レーベンシュタイン距離を100点満点のスコアに変換
public static double GetSimilarityScore(string s1, string s2)
{
    int levenshteinDistance = LevenshteinDistance(s1, s2);
    int maxPossibleDistance = Math.Max(s1.Length, s2.Length);
    
    if (maxPossibleDistance == 0) return 100;
    
    double similarityScore = 100 * (1 - (double)levenshteinDistance / maxPossibleDistance);
    return Math.Round(similarityScore, 2);
}

使用例

// 使用例
Console.WriteLine($"kitten → sitting: {GetSimilarityScore("kitten", "sitting")}点");
Console.WriteLine($"book → back: {GetSimilarityScore("book", "back")}点");
Console.WriteLine($"こんにちは → こんばんは: {GetSimilarityScore("こんにちは", "こんばんは")}点");

補足情報

レーベンシュタイン距離のアルゴリズム解説

レーベンシュタイン距離の計算には動的計画法（DP）を使用します：

二次元配列を作成し、各セルには「その位置までの部分文字列の最小編集距離」を格納
初期条件として、配列の端（空文字列との比較）を設定
各セルを左上から右下へ埋めていき、最小の編集コストを計算
右下のセルが最終的なレーベンシュタイン距離

時間複雑度は O(mn)、空間複雑度も O(mn) となります（m, nはそれぞれの文字列の長さ）。

文字列一致度の主要指標と用途に応じた選び方

文字列の一致度を測定する指標には様々なものがあり、用途に応じて使い分けることが重要です：

綴りミスの検出: レーベンシュタイン距離、ジャロ・ウィンクラー
文書の類似性: コサイン類似度、ジャッカード類似度
DNAシーケンスの比較: 最長共通部分列
固定長バイナリ比較: ハミング距離
言語処理: N-gram類似度
音声検索: Soundex、Metaphone

実際のアプリケーション開発では、これらの指標を組み合わせたり、特定のドメインに合わせてカスタマイズすることも多いです。性能要件や使用ケースに応じて適切な指標を選択することが重要です。