目次

この記事の目的
実行環境
用語説明
実装例
コードの解説
なぜ途中の計算結果を利用できるか
最終的な計算結果
動的計画法の使用例
感想
参考文献

この記事の目的

動的計画法は言葉や考え方を知っていたが
実際にどのような処理をするかは理解していませんでした。
そのため、自分自身が理解し技術力を上げる
ために本記事を作成しました。

本記事は

動的計画法という言葉は知っているが、
具体的な内容を理解しきれていない方
ちょっと難しめのアルゴリズムを知りたい方
向けの記事となっています

この記事を読むことで
動的計画法の考え方やアルゴリズムがどのように動くかを
理解できるようになります。

実行環境

実装環境はGoogle Colaboratory,paiza.ioを使用しました。
paiza.ioはすぐにコードを書いて
実行結果を確認できるのでお勧めです

用語説明

【レーベンシュタイン距離】

2つの文字列の類似度（どれだけ異なるか）を表す値です。
追加、削除、置換の最小回数で定義されます。

【動的計画法】

途中までの計算結果を利用し最終的な答えを求める手法です
すでに求めた結果を利用して、より大きな問題を効率的に解く
というのが動的計画法の基本的な考え方です。

実装例

次は具体的な実装例を見ていきます
雑誌の方ではPythonの方で書かれていましたが
技術力を上げるためJavaScriptでも実装してみました
Pythonのコードに比べて難しい文法は使っておらず、
直感的に読めるため
JavaScriptの方がコードが見やすいと思います。

今回はsprinterとsplitのレーベンシュタイン距離を求めます

Pythonでの実装例（クリックで開く）

Pythonでの実装例

# レーベンシュタイン距離を動的計画法を使用して計算
def levenshtein(s1, s2):
    n = len(s1)
    m = len(s2)

    # DP テーブルの初期化
    table = [[0] * (m + 1) for _ in range(n + 1)]

    # 初期条件：空文字列との距離
    for i in range(n + 1):
        table[i][0] = i  # 削除の回数
    for j in range(m + 1):
        table[0][j] = j  # 追加の回数

    # DP の計算
    for i in range(1, n + 1):
        for j in range(1, m + 1):

            # 左のマス +1（追加）
            a = table[i][j - 1] + 1

            # 上のマス +1（削除）
            b = table[i - 1][j] + 1

            # 左上のマス + cost（置換 or 一致）
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            c = table[i - 1][j - 1] + cost

            # 最小値を採用
            table[i][j] = min(a, b, c)

    # DP テーブルの表示（確認用）
    print(*table, sep="\n")

    return table[n][m]
# 実行例
print(levenshtein('sprinter', 'split'))

Python実行結果

[0, 1, 2, 3, 4, 5]
[1, 0, 1, 2, 3, 4]
[2, 1, 0, 1, 2, 3]
[3, 2, 1, 1, 2, 3]
[4, 3, 2, 2, 1, 2]
[5, 4, 3, 3, 2, 2]
[6, 5, 4, 4, 3, 2]
[7, 6, 5, 5, 4, 3]
[8, 7, 6, 6, 5, 4]
4

JavaScriptでの実装例（クリックで開く）

JavaScriptでの実装例

// レーベンシュタイン距離を動的計画法で計算する関数
function levenshtein(s1, s2) {
    let n = s1.length;
    let m = s2.length;

    // DP テーブルの初期化
    let table = new Array(n + 1);
    for (let i = 0; i <= n; i++) {
        table[i] = new Array(m + 1).fill(0);
    }

    // 初期条件：空文字列との距離
    for (let i = 0; i <= n; i++) {
        table[i][0] = i; // 削除の回数
    }
    for (let j = 0; j <= m; j++) {
        table[0][j] = j; // 追加の回数
    }

    // DP の計算
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {

            // 左のマス +1（追加）
            let a = table[i][j - 1] + 1;

            // 上のマス +1（削除）
            let b = table[i - 1][j] + 1;

            // 左上のマス + cost（置換 or 一致）
            let cost;
            if (s1[i - 1] === s2[j - 1]) {
                cost = 0;   // 文字が一致 → 置換コストなし
            } else {
                cost = 1;   // 文字が不一致 → 置換コスト1
            }

            let c = table[i - 1][j - 1] + cost;
            // 最小値を採用
            table[i][j] = Math.min(a, b, c);
        }
    }
    for(let i=0;i<table.length;i++){
        // DP テーブルの表示（確認用）
        console.log(table[i])
    }
    return table[n][m];
}
// 実行例
console.log(levenshtein('sprinter', 'split'));

JavaScript実行結果

[ 0, 1, 2, 3, 4, 5 ]
[ 1, 0, 1, 2, 3, 4 ]
[ 2, 1, 0, 1, 2, 3 ]
[ 3, 2, 1, 1, 2, 3 ]
[ 4, 3, 2, 2, 1, 2 ]
[ 5, 4, 3, 3, 2, 2 ]
[ 6, 5, 4, 4, 3, 2 ]
[ 7, 6, 5, 5, 4, 3 ]
[ 8, 7, 6, 6, 5, 4 ]
4

コードの解説

1.テーブルの初期化

Python,JavaScriptのテーブル初期化（クリックで開く）

Python

def levenshtein(s1, s2):
    n = len(s1)
    m = len(s2)

    # DP テーブルの初期化
    table = [[0] * (m + 1) for _ in range(n + 1)]

JavaScript

function levenshtein(s1, s2) {
    let n = s1.length;
    let m = s2.length;

    // DP テーブルの初期化
    let table = new Array(n + 1);
    for (let i = 0; i <= n; i++) {
        table[i] = new Array(m + 1).fill(0);
    }

n,mで文字列の長さを取得します。
その長さをもとに動的計画法の途中結果を保存する表（DPテーブル）を作ります
長さはn+1列、m+1行です。
文字が何もない状態を保存するため+1ずつ多く作成します。
Pythonの table = [[0] * (m + 1) for _ in range(n + 1)]は
JavaScriptの//DP テーブルの初期化の部分と同じ結果を得られます。

JavaScriptの方ではまず一次元配列のtableをn+1の長さで作成します。
その後要素番号0~nまで一つずつ長さm+1の配列を初期値0で入れるという処理です。

作成する二次元配列

i＼j	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	0	0	0	0	0
2	0	0	0	0	0	0
3	0	0	0	0	0	0
4	0	0	0	0	0	0
5	0	0	0	0	0	0
6	0	0	0	0	0	0
7	0	0	0	0	0	0
8	0	0	0	0	0	0

2.テーブルの初期条件

Python,JavaScriptのテーブル初期化（クリックで開く）

Python

  # 初期条件：空文字列との距離
    for i in range(n + 1):
        table[i][0] = i  # 削除の回数
    for j in range(m + 1):
        table[0][j] = j  # 追加の回数

JavaScript

    // 初期条件：空文字列との距離
    for (let i = 0; i <= n; i++) {
        table[i][0] = i; // 削除の回数
    }
    for (let j = 0; j <= m; j++) {
        table[0][j] = j; // 追加の回数
    }

この DP テーブルでは、行番号 i と列番号 j が次の意味を持ちます。

i：元の文字列 s1（sprinter）の「先頭から i 文字」を使った文字列
j：変換先の文字列 s2（split）の「先頭から j 文字」を使った文字列

つまり、
table[i][j] は「s1 の先頭 i 文字」→「s2 の先頭 j 文字」への
レーベンシュタイン距離を表します。

DPテーブル（初期化直後）

i＼j	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	0	0	0	0	0
2	2	0	0	0	0	0
3	3	0	0	0	0	0
4	4	0	0	0	0	0
5	5	0	0	0	0	0
6	6	0	0	0	0	0
7	7	0	0	0	0	0
8	8	0	0	0	0	0

この表は「初期化部分のみ」を示しており、
左端の列は 削除回数
(例えばi=0、j=2なら"sp"=>""なので距離は2)、
上端の行は 追加回数を表しています。
(例えばi=3、j=0なら""=>"spl"なので距離は3)

3.テーブルの遷移

Python：遷移部分（クリックで開く）

# DP の計算
    for i in range(1, n + 1):
        for j in range(1, m + 1):

            # 左のマス +1（追加）
            a = table[i][j - 1] + 1

            # 上のマス +1（削除）
            b = table[i - 1][j] + 1

            # 左上のマス + cost（置換 or 一致）
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            c = table[i - 1][j - 1] + cost

            # 最小値を採用
            table[i][j] = min(a, b, c)

    # DP テーブルの表示（確認用）
    print(*table, sep="\n")

JavaScript：遷移部分（クリックで開く）

JavaScript

// DP の計算
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {

            // 左のマス +1（追加）
            let a = table[i][j - 1] + 1;

            // 上のマス +1（削除）
            let b = table[i - 1][j] + 1;

            // 左上のマス + cost（置換 or 一致）
            let cost;
            if (s1[i - 1] === s2[j - 1]) {
                cost = 0;   // 文字が一致 → 置換コストなし
            } else {
                cost = 1;   // 文字が不一致 → 置換コスト1
            }

            let c = table[i - 1][j - 1] + cost;

            // 最小値を採用
            table[i][j] = Math.min(a, b, c);
        }
       
    }
    for(let i=0;i<table.length;i++){
        // DP テーブルの表示（確認用）
        console.log(table[i])
    }

この部分では現在の文字列に対して追加、削除、置換のどれが最適かを求めて、その結果をDPテーブルに保存しています
例えばi=1,j=1の場合を考えます("s"=>"s")

case-a.追加

a=table[i][j - 1] + 1;は文字を追加する場合を考えます。("s"=>"s*", *はどの1文字でもよい)
今回の場合はtable[1][0]+1がtable[1][1]の候補の一つになります

case-b.削除

b = table[i - 1][j] + 1;は文字を削除する場合を考えます。
("s"=>"")
今回の場合はtable[0][1]+1がtable[1][1]の候補の一つになります

case-c.置換

この部分はPythonとJavaScriptで若干コードが違うので該当部分を以下に記述します。
またわかりやすさのためJavaScriptのコードを基準に説明します

Python,JavaScriptの置換のコード（クリックで開く）

Python

# 左上のマス + cost（置換 or 一致）
cost = 0 if s1[i - 1] == s2[j - 1] else 1
c = table[i - 1][j - 1] + cost

JavaScript

// 左上のマス + cost（置換 or 一致）
let cost;
if (s1[i - 1] === s2[j - 1]) {
     cost = 0;   // 文字が一致 → 置換コストなし
} else {
     cost = 1;   // 文字が不一致 → 置換コスト1
}
let c = table[i - 1][j - 1] + cost;

if文の処理の説明をします。
s1[i-1]とはs1のi-1番目の文字(ただし先頭の文字を0文字目と扱う)
という意味になります。

s1[i - 1] === s2[j - 1]はs1の0文字目（"s"）とs2の0文字目（"s"）を比較するということになります。

一致しているなら回数は変わらない
cost = 0;
一致していないのであれば回数+1
cost = 1;
そしてその結果を
c = table[i - 1][j - 1] + cost;の部分で保存します。
("s"=>"s" or "s"=>"*",*はどの1文字でもよい)

比較した結果、今回の場合は文字が同じなため、
table[0][0]+0がtable[1][1]の候補の一つになります。

judgement-数値決定-

最後にどの値が実際にtable[1][1]に保存されるかを決定します
決定の仕方はa,b,cのうち最も小さい値です。

Python

table[i][j] = min(a, b, c)

JavaScript

table[i][j] = Math.min(a, b, c);

実際に計算してみると今回の場合は

a=table[1][0](値は1)+1=2
b=table[0][1](値は1)+1=2
c=table[0][0](値は0)+0=0

になりcが一番小さいためtable[1][1]の値は0になります。

ほかの計算例

i=2,j=1（"sp"=>"s"）の場合以下のようになります

a=table[2][0]+1 ("sp"=>"sp*")
b=table[1][1]+1 ("sp"=>"s")
c=table[1][0]+1 (今回は"p"==="s"ではないため"sp"=>"s*")

よってbが一番小さいためtable[2][1]に1が保存されます

なぜ途中の計算結果を利用できるか

例えば「spli」と「sprint」の距離（table[4][6]）を求めるとき、
現在のセルは、追加・削除・置換の直前の3つの状態を比較します。

種類	対応する状態（部分文字列）	DPセル	値	説明
追加	"spli" と "sprin"	table[4][5]	2	ここまで 2 回操作して "sprin" まで到達済み
削除	"spl" と "sprint"	table[3][6]	4	ここまで 4 回操作して "sprint" まで到達済み
置換	"spl" と "sprin"	table[3][5]	2	ここまで 2 回操作して "sprin" まで到達済み

a = table[4][5] + 1 = 3  
b = table[3][6] + 1 = 5  
c = table[3][5] + 1 = 3

これらの結果をもとに最後の一文字だけ考えて
最小値 3 がtable[4][6]となります。

DPテーブル（計算後)

最終的なDPテーブルを以下に示します

j＼i	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	0	1	2	3	4
2	2	1	0	1	2	3
3	3	2	1	1	2	3
4	4	3	2	2	1	2
5	5	4	3	3	2	2
6	6	5	4	4	3	2
7	7	6	5	5	4	3
8	8	7	6	6	5	4

最終的な計算結果

最終的な答えはtable[n][m]にあります。
Pythonならprint(levenshtein('sprinter', 'split'))
JavaScriptならconsole.log(levenshtein('sprinter', 'split'));
で出力します。
ちなみに文字列の位置を逆にしても答えは変わりません
（DPテーブルは変わります）
試してみてください。

Python,JavaScriptの計算結果表示（クリックで開く）

Python

# DP テーブルの表示（確認用）
  print(*table, sep="\n")
  return table[n][m]
print(levenshtein('sprinter', 'split'))

JavaScript

  for(let i=0;i<table.length;i++){
        // DP テーブルの表示（確認用）
        console.log(table[i])
  }
  return table[n][m]
console.log(levenshtein('sprinter', 'split'));

実行結果はどちらも共通で[]で囲まれている部分がDPテーブルで
一番下の数字がレーベンシュタイン距離（この例では4）です。

実行結果

[0, 1, 2, 3, 4, 5]
[1, 0, 1, 2, 3, 4]
[2, 1, 0, 1, 2, 3]
[3, 2, 1, 1, 2, 3]
[4, 3, 2, 2, 1, 2]
[5, 4, 3, 3, 2, 2]
[6, 5, 4, 4, 3, 2]
[7, 6, 5, 5, 4, 3]
[8, 7, 6, 6, 5, 4]
4

動的計画法の使用例

最後に日常的な使用例を紹介します

スマホの予測変換,検索候補
（レーベンシュタイン距離+動的計画法）
カーナビの最短ルート計算
(実際にはダイクストラ法やA*アルゴリズムが使用されることが多い)
ゲームのAI
（経路探索や最適行動選択で使用）
Excelの最適化ソルバー
（動的計画法を使うナップザック問題等で使用）
などに使用されています。

感想

前回よりは文章が短いですが

でもながすぎ。

これでも前回の記事と比べると３分の１ほどの文字量になっています。
がどうしても長くなってしまいます。
記事を書くのは楽しいですが
長くなればなるほど説明に矛盾ができたりするので改善していきたいです。
前回の記事はこちらです。

参考文献

日経ソフトウェア2023/1
アルゴリズム/Python開発環境比較/NumPy/電子書籍CD+付録冊子p21