はじめに
単語同士の「似ている」「似ていない」を判断することはとてもシンプルなようで、実際は非常に難しい問題だと思う。現在業務で利用しているシステムにおいて「過去に類似した案件があったかをどうか」を検索することが多いのだが、なかなか痒い所に手が届くような検索結果が返ってこなく、改善案を思案している所である。
「あいまい検索」と言うとSQLのlike文なんかをイメージする方も多いのではないかと思うのだが、実際は入力されたキーワードが部分的にも「一致」している必要がある。なので少しでも検索にノイズとなるキーワードが含まれると途端にヒットしなくなる。やはりgoogleのようなfuzzyな検索にも耐えられる仕組みが欲しいと思うのだ。
そんなわけで今回は「似ている」「似ていないを」単語間の編集コストで表現する編集距離（レーベンシュタイン距離）について学んだので備忘を残そうと思う。大枠は下記記事を大いに参考にさせて頂いた。要点が分かりやすいので詳細はこっちを見た方が良いと思う、、
本記事は、上記記事で登場する再帰アルゴリズムが何故そのように書けるのかがなかなか理解できなかったポンコツな自分用の、理解に至るための備忘である。
編集距離のベースとなる考え方
本質はとてもシンプル。文字列s, tがあるとき、
- sの現在位置にtの現在位置の文字を挿入（I：Insert）
- sの現在位置の文字を削除（D：Delete）
- sの現在位置の文字を、tの現在位置の文字で置換（R：Replace）
の操作を行ってsをtに一致させる。この編集操作にはコストがかかり、最小コストが編集距離となる。
元となるソースコード
レーベンシュタイン距離
def ld(s: str, t: str) -> int:
'''2つの文字列間のレーベンシュタイン距離を求める'''
# 一方の長さが0の場合、他方の長さが編集距離
if not s:
return len(t)
if not t:
return len(s)
# 1文字目が一致なら2文字目以降の距離を求める
if s[0] == t[0]:
return ld(s[1:], t[1:])
# sの先頭に追加
la = ld(s, t[1:])
# sの先頭を削除
lb = ld(s[1:], t)
# sの先頭を置換
lc = ld(s[1:], t[1:])
return 1 + min(la, lb, lc)
理解に時間がかかったのは、追加・削除・置換の操作のイメージと実際のリスト操作が直感的に一致しなかったため。下記は自分の理解のためにコードにコメントをベタ書きしたもの。
レーベンシュタイン距離(補助コメント有)
def ld(s: str, t: str) -> int:
'''2つの文字列間のレーベンシュタイン距離を求める'''
print('【関数呼出】ld({}, {})'.format(s,t))
# 一方の長さが0の場合、他方の長さが編集距離
if not s:
print('【return len(t)】', len(t))
return len(t)
if not t:
print('【return len(s)】', len(s))
return len(s)
# 1文字目が一致なら2文字目以降の距離を求める
if s[0] == t[0]:
print('【return】ld(s[1:], t[1:])')
return ld(s[1:], t[1:])
###############################################################
# 先頭の文字が異なる
# ->追加・削除・置換の3パターンを考える
# この動作イメージと再帰呼び出しの指定パラメータが感覚的に一致するためには
# ・常に先頭同士の文字比較をするイメージを持つ
# -> ld(s, t)はs[0]とt[0]の関係を検証しているだけ。
# ・sの文字列操作を基準に考える -> sを編集してtに近づけるにはどれだけコストがかかるか?
###############################################################
######################################################################################
# 【sの先頭に追加】
#-----------
# 初期状態
# 0 1 2
#[s] a b c
#[t] b c d
#-----------
# [s]の先頭にbを追加すると次のようになる
#[s] b a b c
#[t] b c d
# ^
#-----------
# 次は^の対応を比較する問題に移行する
#[s] a b c
#[t] c d
# よって sの先頭に追加する行為 -> 次は[sの先頭から]と[tの2番目から]の文字列を比較する問題
# ゆえに ld(s, t[1:])
######################################################################################
print('sの先頭に追加')
la = ld(s, t[1:])
######################################################################################
# 【sの先頭を削除】
#-----------
# 初期状態
# 0 1 2
#[s] a b c
#[t] b c d
#-----------
# [s]の先頭を削除すると次のようになる
#[s] b c
#[t] b c d
# ^
#-----------
# 次は^の対応を比較する問題に移行する
# よって sの先頭を削除する行為 -> 次は[sの2番目から]と[tの先頭]の文字列を比較する問題
# ゆえに ld(s[1:], t)
######################################################################################
print('sの先頭を削除')
lb = ld(s[1:], t)
######################################################################################
# 【sの先頭を置換】
#-----------
# 初期状態
# 0 1 2
#[s] a b c
#[t] b c d
#-----------
# [s]の先頭を置換すると次のようになる
#[s] b b c
#[t] b c d
# ^
#-----------
# 次は^の対応を比較する問題に移行する
#[s] b c
#[t] c d
# よって sの先頭を置換する行為 -> 次は[sの2番目から]と[tの2番目から]の文字列を比較する問題
# ゆえに ld(s[1:], t)
######################################################################################
print('sの先頭を置換')
lc = ld(s[1:], t[1:])
print('【return】{} (1 + min({}, {}, {}))'.format(1 + min(la, lb, lc), la, lb, lc))
# 追加・削除・置換のいずれもコスト1はかかる。
# 残りの文字列の問題についてかかったコストのうち最小値を足すと全体として最小コストが算出される
return 1 + min(la, lb, lc)
ld('ba', 'cab')
再帰呼び出しの中で、
- あくまで個々の呼び出しは先頭文字同士の比較に過ぎない(部分問題)というイメージを持つこと
- 部分問題のコスト総和が全体としてのコスト(=編集距離)になる
ことを意識したらやっと理解できました。配列操作は再帰呼び出しにおいて次の部分問題を作成するために、先頭文字列を揃える操作だとみなせます。
見づらいですがトレース内容を出力してみました。
出力結果
【関数呼出】ld(ba, cab)
sの先頭に追加
【関数呼出】ld(ba, ab)
sの先頭に追加
【関数呼出】ld(ba, b)
【return】ld(s[1:], t[1:])
【関数呼出】ld(a, )
【return len(s)】 1
sの先頭を削除
【関数呼出】ld(a, ab)
【return】ld(s[1:], t[1:])
【関数呼出】ld(, b)
【return len(t)】 1
sの先頭を置換
【関数呼出】ld(a, b)
sの先頭に追加
【関数呼出】ld(a, )
【return len(s)】 1
sの先頭を削除
【関数呼出】ld(, b)
【return len(t)】 1
sの先頭を置換
【関数呼出】ld(, )
【return len(t)】 0
【return】1 (1 + min(1, 1, 0))
【return】2 (1 + min(1, 1, 1))
sの先頭を削除
【関数呼出】ld(a, cab)
sの先頭に追加
【関数呼出】ld(a, ab)
【return】ld(s[1:], t[1:])
【関数呼出】ld(, b)
【return len(t)】 1
sの先頭を削除
【関数呼出】ld(, cab)
【return len(t)】 3
sの先頭を置換
【関数呼出】ld(, ab)
【return len(t)】 2
【return】2 (1 + min(1, 3, 2))
sの先頭を置換
【関数呼出】ld(a, ab)
【return】ld(s[1:], t[1:])
【関数呼出】ld(, b)
【return len(t)】 1
【return】2 (1 + min(2, 2, 1))
手書きトレース
恥ずかしいけど、また見返すとき用に手書きのトレース内容も張っておく。これで理解が捗った。
まとめ
再帰のプログラムは毎回理解に苦戦してしまう。結局手書きでトレースしてようやく理解するに至った。みんなこういうのどうやって理解するんだろ、っていつも思ってしまう。再帰理解のコツがあったら教えて欲しい、、、