文字列の類似度計算：レーベンシュタイン距離をPython, Goで実装する

Aru

レーベンシュタイン距離（Levenshtein distance）は、２つの文字列間での変換に必要な最小の編集回数（挿入、削除、置換）を示す数値です。この方法は、文字列の類似度や違いを測定する際に非常に有用です。特に、競技プログラミングや自然言語処理の分野では頻繁に利用されます。本記事では、PythonとGoの２つの言語を使用して、レーベンシュタイン距離を計算する実装方法を説明します

Contents

レーベンシュタイン距離
アルゴリズム
まとめ

レーベンシュタイン距離

レーベンシュタイン距離（Levenshtein distance）は、２つの文字列間の違いを数値（距離）として示す手法のひとつです。この手法は「編集距離」とも呼ばれ、文字列の類似度や違いを測るために広く利用されています。

レーベンシュタイン距離は、具体的には、どちらか一方の文字列に対して「挿入・置換・削除」のいずれかの操作を行い、もう一方の文字列と一致させるために必要な操作回数の最小値を求めるものです。この最小回数が、２つの文字列の「距離」として表されます。

例えば、文字列 “temperature” の “m” を “n” にTYPOした場合、文字列 “tenperature” とのレーベンシュタイン距離は1になります。これは、”m” を “n” に置換する操作が1回必要だからです。

この計算方法は、自然言語処理など、文字列データを扱うさまざまな分野で役立ちます。また、競技プログラミングにおいても、文字列の一致度を測るための重要なツールとして使用されます。

アルゴリズム

アルゴリズム解説

レーベンシュタイン距離の計算には、動的計画法（Dynamic Programming）が利用されます。このアルゴリズムは効率的で、計算量を大幅に削減することができます。

レーベンシュタイン距離を計算するためには、文字列 s と t の長さをそれぞれ m と n としたとき、(m+1) × (n+1) のテーブル dp[m+1][n+1] を作成します。このテーブルを使って、動的に距離を計算していきます。

具体的には、次のような手順で進めます

テーブル dp[i][j] には、文字列 s の最初の i 文字と、文字列 t の最初の j 文字のレーベンシュタイン距離を格納します。

s[i] == t[j] であれば、編集距離は dp[i-1][j-1] と同じ値となります（文字が一致するため、変換は必要ありません）。
一致しない場合、編集距離は dp[i-1][j-1]（置換）、dp[i][j-1]（挿入）、dp[i-1][j]（削除）の３つの値の中で最小の値に 1 を加えたものになります。

最終的に、テーブルの dp[m][n] にレーベンシュタイン距離が格納されます。

実例

例として、文字列 “think” と “thank” のレーベンシュタイン距離を計算してみましょう。

オレンジの部分は初期化で計算しておきます。すると１文字目”t”と”t”は同じなので、編集距離はdp[0][0]をコピーして０になります。

“think” と “thank” の場合、最初の文字 t と t は一致するため、距離は 0 になります。次に、h と h も一致し、a と a も一致します。しかし、i と n の場合は置換が必要で、その後、k と k は一致するため、最終的に編集距離は 1 となります。

結果レーベンシュタイン距離は1になります。

	“”	t	h	a	n	k
“”	0	1	2	3	4	5
t	1	0	1	2	3	4
h	2	1	0	1	2	3
i	3	2	1	1	2	3
n	4	3	2	2	1	2
k	5	4	3	3	2	1

処理の流れ

変数の初期化
- m と n に、それぞれ s と t の長さを格納します。
- dp 配列を (m+1)×(n+1) の2次元リストとして初期化（すべて 0）します。
DPテーブルの初期値設定
- dp[i][0] = i として、s[:i] 側の初期化をします（sを削除して空文字列と一致させるコストと考えられます）。
- dp[0][j] = j として、t[:j] 側の初期化をします（tを削除して空文字列と一致させるコストと考えられます）。
動的計画法を適用
- 二重ループ (i=1 から m、j=1 から n) を使って、 dp[i][j] を更新します。
- s[i-1] == t[j-1] の場合、dp[i][j] = dp[i-1][j-1]（変更不要）。
- 違う場合、dp[i][j] は以下の3つの操作の最小値＋1になります。どの操作も+1で同じです。
  1. dp[i-1][j]（削除）
  2. dp[i][j-1]（挿入）
  3. dp[i-1][j-1]（置換）
最小編集距離を返す
- 動的計画法による処理が完了すると、dp[m][n] に s と t のレーベンシュタイン距離が格納されているので、それを返す。

このアルゴリズムの計算量は O(m×n) です。

処理自体は単純で文字列が同じなら修正はせず、それ以外の場合は、一方を削除または挿入するか、置換する操作のうち一番コストが低いものを選択していきます（操作自身は１のコストがかかるので、以前の状態のコストの差で決まります）。

if s[i - 1] == t[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]  # 文字が同じなら変更なし
else:
    dp[i][j] = 1 + min(dp[i - 1][j],    # 削除
                        dp[i][j - 1],    # 挿入
                        dp[i - 1][j - 1]) # 置換

Pythonコード

レーベンシュタイン距離の計算をPythonで書くと以下のようなコードになります。

def leven(s: str, t: str) -> int:
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初期化: dp[i][0] は i (削除), dp[0][j] は j (挿入)
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # DPテーブルの更新
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # 文字が同じなら変更なし
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],    # 削除
                                   dp[i][j - 1],    # 挿入
                                   dp[i - 1][j - 1]) # 置換
    
    return dp[m][n]

Goコード

Go言語の場合は、min()関数が用意されていないのでそちらも作る必要があります。


func min(a, b, c int) int {
    if a < b && a < c {
        return a
    } else if b < c {
        return b
    }
    return c
}

func leven(s, t string) int {
	m, n := len(s), len(t)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// 初期化: dp[i][0] は i (削除), dp[0][j] は j (挿入)
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}

	// DPテーブルの更新
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] {
				dp[i][j] = dp[i-1][j-1] // 文字が同じなら変更なし
			} else {
				dp[i][j] = 1 + min(dp[i-1][j],    // 削除
					dp[i][j-1],    // 挿入
					dp[i-1][j-1])  // 置換
			}
		}
	}

	return dp[m][n]
}