距離を求めるプログラムを書こう（３）

2019-01-21データサイエンス

こんにちは。前回残ってしまったレーベンシュタイン距離のプログラムです。相変わらずPythonで書きます。

1. レーベンシュタイン距離を求めるプログラム（１）【単純に再帰で書いた場合】
2. 動的計画法とは
3. レーベンシュタイン距離を求めるプログラム（２）【再帰＋メモ化で書いた場合】
4. レーベンシュタイン距離を求めるプログラム（３）【出題された疑似コードに近いプログラム】
5. 勝手な予想

レーベンシュタイン距離を求めるプログラム（１）【単純に再帰で書いた場合】

レーベンシュタイン距離とは、ある文字列に対して「文字の挿入」・「文字の削除」・「文字の置換」のいずれかの操作を行って別の文字列にするための操作回数のことでした。

レーベンシュタイン距離を求めるには、次の操作で求めることができることが知られています。

２つの文字列Ａ，Ｂに対して、２つの文字列のレーベンシュタイン距離を\( d(A,B) \)と表すこととします。また、２つの文字列Ａ，Ｂの末尾の文字をそれぞれａ，ｂとし、末尾の文字を取り除いた文字列をそれぞれＡ’，Ｂ’とすると、次の４つのいずれかの最小値が\( d(A,B) \)となります。

２つの末尾の文字ａ，ｂが同じである場合、末尾の文字を考えなくてもレーベンシュタイン距離は等しいので、\( d(A,B) = d(A’,B’)+0 \)
末尾の文字ａを文字ｂに置換する必要がある場合、\( d(A’,B’) \)よりも距離が1増えるので、\( d(A,B) = d(A’,B’)+1 \)
文字列Ｂ’に末尾の文字ｂを挿入することが必要な場合、\( d(A,B’) \)よりも距離が1増えるので、\( d(A,B) = d(A,B’)+1 \)
文字列Ａの末尾の文字ａを削除することが必要な場合、\( d(A’,B) \)よりも距離が1増えるので、\( d(A,B) = d(A’,B)+1 \)

このうち、１つ目と２つ目の項目は＋０と＋１の違いだけなので、まとめることができます。

また、文字列Ａと文字数が０である空文字列とのレーベンシュタイン距離は、文字列Ａの文字数と同じことは自明です。空文字列と文字列Ｂとのレーベンシュタイン距離についても同様です。

ここまで整理したことを、プログラムとして表現すると次のようになります。

def levenshtein( A, B ):
	print( '【{}】　と　【{}】'.format( A, B ) )
	if len(A)==0:
		return len(B)

	if len(B)==0:
		return len(A)

	cost = 0 if A[-1] == B[-1] else 1				# Aの末尾の文字とBの末尾の文字が同じなら置換する必要はない
	dist = min( levenshtein(A[:-1],B[:-1]) + cost,	# Aの末尾の文字とBの末尾の文字を置換する場合
				levenshtein(A     ,B[:-1]) + 1,		# B'に文字bを挿入する場合
				levenshtein(A[:-1],B     ) + 1 )	# Aの末尾の文字を削除する場合
	return dist


if __name__ == '__main__':
	print( levenshtein( 'かながわ', 'かがわ' ) )

途中経過がわかるように、関数が呼ばれるたびに受け取った引数を表示しています。関数がどのように呼ばれているかも含めて、結果を示します。よく見ると、このプログラムはとても無駄が多くあります。最初の「かながわ」と「かがわ」の場合、引数が「【か】と【か】」になっている回数に着目してみてください。

【かながわ】　と　【かがわ】
【かなが】　と　【かが】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かなが】　と　【か】
【かな】　と　【】
【かなが】　と　【】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【かが】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【】　と　【かが】
【かながわ】　と　【かが】
【かなが】　と　【か】
【かな】　と　【】
【かなが】　と　【】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かながわ】　と　【か】
【かなが】　と　【】
【かながわ】　と　【】
【かなが】　と　【か】
【かな】　と　【】
【かなが】　と　【】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かなが】　と　【かが】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かなが】　と　【か】
【かな】　と　【】
【かなが】　と　【】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【かが】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【】　と　【かが】
【かなが】　と　【かがわ】
【かな】　と　【かが】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【】　と　【かが】
【かなが】　と　【かが】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かなが】　と　【か】
【かな】　と　【】
【かなが】　と　【】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【かが】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【】　と　【かが】
【かな】　と　【かがわ】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【】　と　【かが】
【かな】　と　【かが】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【】　と　【かが】
【か】　と　【かがわ】
【】　と　【かが】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【】　と　【かが】
【】　と　【かがわ】
1

なんと２５回も呼ばれています。たった４文字と３文字のレーベンシュタイン距離を求めるために２５回も呼ばれているのです。その値を求めるために、さらに「【】と【】」、「【か】と【】」、「【】と【か】」の３種類の組を引数として、さらに関数を呼び出します。本当に無駄な呼び出しだらけです。もっと長い文字列どうしでレーベンシュタイン距離を求めると、とんでもないことになりそうです。

動的計画法とは

さて、単なる再帰では無駄が多いことはわかりました。これを解消するための工夫が必要があります。

着目点ですが、「【か】と【か】」のレーベンシュタイン距離を求めるために「【】と【】」、「【か】と【】」、「【】と【か】」を呼び出して「【か】と【か】」のレーベンシュタイン距離を求めています。１回「【か】と【か】」のレーベンシュタイン距離を求めたら、２回目以降は「【】と【】」、「【か】と【】」、「【】と【か】」を呼び出さないようにしましょう。人が手作業で求める場合には、「さっき求めたじゃない！」とメモを見るでしょう。これと同じです。コンピュータ上でメモを取っておき、メモがあればメモを見ましょう！そうすると、「【か】と【か】」を呼び出しているところでも、わざわざ「【か】と【か】」を呼び出さないでメモを見てくれるようになります。全体では、関数呼び出しの回数がかなり減ることが予想されます。このメモを利用する方法が動的計画法のポイントの１つです。

動的計画法の２つ目のポイントは、すでに使われています。大きな問題をそのまま解くのではなく、小さい問題に分割して解くことです。今回のアルゴリズムでは、\( d(A,B) \)を求めるために、\( d(A’,B’) \)，\( d(A,B’) \)，\( d(A’,B) \)の少しだけ小さい３つの問題に分割して解いています。

動的計画法とは『メモ化』と『問題の分割』を行って解決することです。

レーベンシュタイン距離を求めるプログラム（２）【再帰＋メモ化で書いた場合】

さて、メモ化を使って前のプログラムを書き直してみます。変数Xがメモにあたります。

def levenshtein( A, B ):
	global X
	X = [ [-1] * ( len(B)+1 ) for i in range( len(A)+1 ) ]
	return lv( A, B )

def lv( A, B ):
	global X
	print( '【{}】　と　【{}】'.format( A, B ) )

	if X[len(A)][len(B)]>=0:
		return X[len(A)][len(B)]

	if len(A)==0:
		X[0][len(B)] = len(B)
		return len(B)

	if len(B)==0:
		X[len(A)][0] = len(A)
		return len(A)

	cost = 0 if A[-1] == B[-1] else 1		# Aの末尾の文字とBの末尾の文字が同じなら置換する必要はない
	dist = min( lv(A[:-1],B[:-1]) + cost,	# Aの末尾の文字とBの末尾の文字を置換する場合
				lv(A     ,B[:-1]) + 1,		# B'に文字bを挿入する場合
				lv(A[:-1],B     ) + 1 )		# Aの末尾の文字を削除する場合
	X[len(A)][len(B)] = dist
	return dist


if __name__ == '__main__':
	print( levenshtein( 'かながわ', 'かがわ' ) )

先ほどと同じように、引数が「【か】と【か】」になっている回数に着目してみます。出力は次になります。

【かながわ】　と　【かがわ】
【かなが】　と　【かが】
【かな】　と　【か】
【か】　と　【】
【かな】　と　【】
【か】　と　【か】
【】　と　【】
【か】　と　【】
【】　と　【か】
【かなが】　と　【か】
【かな】　と　【】
【かなが】　と　【】
【かな】　と　【か】
【かな】　と　【かが】
【か】　と　【か】
【かな】　と　【か】
【か】　と　【かが】
【】　と　【か】
【か】　と　【か】
【】　と　【かが】
【かながわ】　と　【かが】
【かなが】　と　【か】
【かながわ】　と　【か】
【かなが】　と　【】
【かながわ】　と　【】
【かなが】　と　【か】
【かなが】　と　【かが】
【かなが】　と　【かがわ】
【かな】　と　【かが】
【かなが】　と　【かが】
【かな】　と　【かがわ】
【か】　と　【かが】
【かな】　と　【かが】
【か】　と　【かがわ】
【】　と　【かが】
【か】　と　【かが】
【】　と　【かがわ】
1

引数が「【か】と【か】」になっている回数はたった３回です。これは\( d(A’,B’) \)，\( d(A,B’) \)，\( d(A’,B) \)の３パターンで使われることによるものです。

レーベンシュタイン距離を求めるプログラム（３）【出題された疑似コードに近いプログラム】

次のプログラムは、出題された疑似コードとほとんど同じです。河合塾「キミのミライ発見」で解説されているので、リンクを貼っておきます。プログラムが少し長いのは、解説にある表を表示するためのプログラム（１９～３５行目）を追加したためです。

慶應義塾大学環境情報学部/2018年情報入試問題解説 - キミのミライ発見

キミのミライ発見大学入試問題研究プロジェクト監修・執筆間辺広樹先生(神奈川県立柏陽高等学校教諭)

https://www.wakuwaku-catch.net/nyushi180902/

def levenshtein( A, B ):
	# 初期化
	m , n = len(A) , len(B)
	X = [ [0] * ( n+1 ) for i in range( m+1 ) ]

	for j in range( 1, n+1 ):
		X[0][j] = j

	for i in range( 1, m+1 ):
		X[i][0] = i
		for j in range( 1, n+1 ):
			cost = 0 if A[i-1] == B[j-1] else 1	# Aの末尾の文字とBの末尾の文字が同じなら置換する必要はない
			X[i][j] = min( X[i-1][j-1] + cost,	# Aの末尾の文字とBの末尾の文字を置換する場合
						   X[ i ][j-1] + 1,		# B'に文字bを挿入する場合
						   X[i-1][ j ] + 1 )	# Aの末尾の文字を削除する場合
	print_table( A, B, X )
	return X[m][n]

def print_table( A, B, X ):
	# Bの文字列を表示
	print( '   | －', end=' ' )
	for j in range( 1, len(B)+1 ) :
		print( B[j-1], end=' ' )
	print()
	print( '-'*(len(B)*3+7))

	for i in range( len(A)+1 ):
		# Ａの文字列を表示
		l = '－' if i==0 else A[i-1]
		print( l, end=' |  ' )

		# X[i][j]を表示
		for j in range( len(B)+1 ):
			print( X[i][j], end='  ' )
		print()


if __name__ == '__main__':
	print( levenshtein( 'かながわ', 'かがわ' ) )
	print( levenshtein( 'さいたま', 'あいち' ) )

それでは、実行結果は次の通りです。

   | － か が わ 
----------------
－ |  0  1  2  3  
か |  1  0  1  2  
な |  2  1  1  2  
が |  3  2  1  2  
わ |  4  3  2  1  
1
   | － あ い ち 
----------------
－ |  0  1  2  3  
さ |  1  1  2  3  
い |  2  2  1  2  
た |  3  3  2  2  
ま |  4  4  3  3  
3

勝手な予想

大学試験で情報を試験に科すことが検討されています。さらに、プログラミングを出題することもいわれています。難易度を上げるには、再帰を出題するという手として使えそうです。さすがに動的計画法は、情報オリンピック本選出場レベルのなのでどうでしょうか？情報オリンピック予選の参加者の裾野がひろがったらあり得るのでしょうか？ある程度様子見になるように思っていますが、今回の慶応ＳＦＣのように誘導をつけて試みる大学もあるような・・・

少なくとも、レーベンシュタイン距離が出題されたからといって、さまざまなアルゴリズムを教えて覚えるような対策は、方向性としてよいものではないと思っています。ifやループの条件を正しく判断できること、細かい手順に分割すること、手順を（疑似コードを含め）コードと対応付けること、というあたりは必要で、それらを組み合わせられるような対策は必要かな。という焦点がはっきり絞れない予想（になっているのか？！）でした。

今回はこれでおしまい。それでは、また。

Posted by 春日井優