#3 編集距離との遭遇

日曜技術研究所

※今回競プロの問題を、学習としてChatGPTで解法を学んでいます。ただ、本文は競プロを生成AIを用いて大会等に参加することは推奨していません。あくまで、学習として利用したことを留意してください。
※私自身が初学者のため、下記に誤る可能性があります。


1.遭遇

　プログラミング勉強のために、競プロ問題を解いていた時、以下のような問いに出くわした。問題自体には著作権あると思うので、自作にアレンジしたものが以下の通りとなる。
　「文字列 S に対して 0 回以上 K 回以内で操作（置換・挿入・削除）を行って、文字列 T と一致させられるか判定してください。」
つまり、"abcde"という文字列Sを、値を置き換える（置換）・値を追加する（挿入）・値を削除する（削除）の操作で、"abbef"という文字列Tにするときに、K回以内でSとTを一致させられるか。という問いになります。
　まず、SとTをfor文でループさせることで、一致しているかを判断する方法を考えました。以下のコードがそのコードに当たります。このコードは、一致しているかどうかで判断しています。つまり、不一致であるということは、すなわち置換する必要があるということでカウントアップするという具合です。ただ、このコードの構想段階でコードを書くことなく正しくないことに気づきます。なぜなら、文字列Sと文字列Tの文字数が違えば、すべての値がずれることになるので、すべてを置換する可能性が生じるからです。つまり、挿入・削除の操作を行っていないので、Sをすべて置換することでTへと編集するアルゴリズムが完成してしまったのです。そうそれは、漫画を巻数の昇順で並べているときに、一つ飛ばして入れていることに気づいたときに、すべてをやり直すかごとく無駄な処理です。

func main() {
	var k int
	var s, t string
	fmt.Scanf("%d", &k)
	fmt.Scanf("%s", &s)
	fmt.Scanf("%s", &t)

	start := strings.Split(s, "")
	target := strings.Split(t, "")

	count := 0
	for _, i := range start {
		for _, j := range target {
			if i != j {
				//不一致
				count++
			}
		}
	}

	if k <= count {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

　そこで、私はChatGPTに尋ねました。「文字列Aを文字列Bに変換するのは何回変更が必要かという問いで、abc=>agcは文字列を配列にして一つずつ比較すれば導けるのはわかるのですが、ac=>agcにする時には、文字数が同じではないので比較の仕方がわかりません」（原文ママ）すると、「文字列 A を文字列 B に変換する際に、文字数が異なる場合には、以下の3つの操作が必要になる可能性があります：

  1. 挿入 (Insert): A に文字を挿入して長さを増やす。

  2. 削除 (Delete): A から文字を削除して長さを減らす。

  3. 置換 (Replace): A の文字を別の文字に置き換える。

これらの操作を最小限に抑えるためには、文字列編集距離（Levenshtein Distance）を計算するのが一般的です。」（原文ママ）と、返答がありました。

2.編集距離について

　

二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。

Wikipedia

　つまり、"abc"から、"acc"とするときに、何回操作をすれば変形できるかを、計算した時の最小回数のことです。例えば、"abc"=>"acc"では、"abc"のbを「削除」する。次に、"ac"となったところに、cを間に「挿入」する。この時の操作回数は、２回となるわけです。ただ、この例では、ｂをｃに「置換」すれば、１回の操作で終わることがわかります。この時、最小回数は１となり、編集距離は１となるわけです。
　そして、この編集距離を利用することで、操作回数（＝コスト）を計算することで、今回の問いである「文字列 S に対して 0 回以上 K 回以内で操作（置換・挿入・削除）を行って、文字列 T と一致させられるか判定してください。」の、0 回以上 K 回以内をコストが満たすかを判断すれば、この問いに答えられるというわけです。

3.動的計画法にも遭遇

　さぁ、編集距離という武器を手に入れたので、意気揚々とコードにしてやるぞと思ったのですが、そもそも、文字列Sと文字列Tが文字数に不一致があるならば、その編集距離事態を求められないのではないか？となりました。困りました。ふとChatGPTに目をやると、最後にちゃんと書いてありました。「編集距離を計算するには、動的計画法を用いるのが効果的です。」

　閑話休題：自戒を込めて記述させていただきます。教えを乞うたならば、よく読みましょうと。

　そんなこんなで動的計画法に、遭遇しました。

対象となる問題を帰納的に解く場合にくり返し出現する小さな問題例について、解を表に記録し表を埋めていく形で計算をすすめ、冗長な計算をはぶくアルゴリズムのことをいう。

Wikipedia

　つまり、繰り返し分割した小さな問いの解をまとめていき、帰納的に問い自体に解を出すということです。例えば"abc"=>"acc"では、"a"と"a"を"a"と”ac"を"a"と"acc"をと、文字列Sから、文字列Tへとすべて小さな問いへと分割してその操作回数をテーブルにすることで、編集距離を求められるというわけです。
　この方法であれば、"abc"=>"ac"であるときには、例えば、"a"=>"ac"を考えるとき、"a"に"c"を挿入することを計算できるし、"abc"=>"ac"の時に、"b"を削除することを計算できます。

4.コード

　実際に、動的計画法を利用した、編集距離を作成してみましょう。
　手順は以下の通りです。
　1.二次元配列の作成
　　この二次元配列がいわばテーブルの役目を果たします。
　２．空文字列との比較で削除と挿入コストを入れる
　　この処理で、テーブルを完成させるための基盤を整えます。
　３．文字列の長さ（＝文字数）文のループをして、不一致の時に、置換・削除・挿入の操作で最小の操作回数の操作のコストをテーブルに保存します。
　以上の処理を行うことで、編集距離を計算できます。

// dpテーブルの作成
func editDistance(s, t string, limit int) int {
	//長さ
	sl, tl := len(s), len(t)

	//長さ分のdpテーブルを作成
	//二次元配列
	dp := make([][]int, sl+1)
	for i := range dp {
		dp[i] = make([]int, tl+1)
	}

	//初期条件
	//空文字列との比較で削除と挿入コストを入れる
	//削除
	for i := 0; i <= sl; i++ {
		dp[i][0] = i
	}
	//挿入
	for i := 0; i <= tl; i++ {
		dp[0][i] = i
	}

	//計算
	for i := 1; i <= sl; i++ {
		for j := 1; j <= tl; j++ {
			if s[i-1] == t[j-1] {
				//一致
				//コストなし
				dp[i][j] = dp[i-1][j-1]
			} else {
				//不一致
				dp[i][j] = min(
					//置換
					dp[i-1][j-1]+1,
					//削除
					dp[i-1][j]+1,
					//挿入
					dp[i-1][j-1]+1,
				)
			}
		}
	}

	return db[sl][tl]
}

// 最小値を求める関数
func min(a, b, c int) int {
	return int(math.Min(float64(a), math.Min(float64(b), float64(c))))
}


5.最後に

　動的計画法での編集距離を求めるときには、上記のコードで行うと膨大なメモリと長時間の処理が行われて処理を遅滞させます。なので、この方法はあくまで、編集距離を求めるときに動的計画法をわかりやすく書き起こしたにすぎません。なので、求める際には、現在の行と1つ前の行だけを保持しながらforループを行う方法によってテーブルを二行で行うことができます。この話はまたいつか.…

いいなと思ったら応援しよう！