お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

距離を求めるプログラムを書こう(3)

データサイエンス

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

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

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

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

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

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

このうち、1つ目と2つ目の項目は+0と+1の違いだけなので、まとめることができます。

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

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

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

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

動的計画法とは

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

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

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

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

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

さて、メモ化を使って前のプログラムを書き直してみます。変数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

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

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

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

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 ):
		# Aの文字列を表示
		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

勝手な予想

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

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

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

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai