Levenshtein距離 - taq225's Memo on Algorithms

Levenshtein距離

Abstract

文字列$ S, T間のLevenshtein距離$ d_{\mathrm{L}}(S, T)は動的計画法 (Dynamic Programming)で求まる.

Explanation

TODO まだ.

Implementation

Input

文字列$ S, T

Output

文字列$ S, T間のLevenshtein距離$ d_{\mathrm{L}}(S, T)

Time complexity

$ O(|S| |T|)time.

code:python

def levenshtein_dist(S, T):

'''

Input:

S, T: string

Output:

the Levenshtein distance of S and T

'''

len_S, len_T = len(S), len(T)

dp = [float('inf') * (len_T + 1) for i in range(len_S + 1)]

for i in range(len_S + 1): dpi0 = i

for j in range(len_T + 1): dp0j = j

for i in range(1, len_S + 1):

for j in range(1, len_T + 1):

cost = 0 if Si - 1 == Tj - 1 else 1

dpij = min(dpi - 1j + 1, # insertion

dpij - 1 + 1, # deletion

dpi - 1j - 1 + cost) # replacement (if cost == 1)

Verification

なし

References