本文主要是介绍Sweet Snippet 之 字符串编辑距离,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
字符串编辑距离的简单实现
字符串编辑距离应该是动态规划中的代表问题了:
给定两个字符串 a a a 与 b b b,求解将 a a a 编辑至 b b b 的操作步数(距离),编辑包含以下两种操作:
- 删除某一字符
- 增加某一字符
(这里我们不允许变更某一字符,注意一下)
求解方法则是根据子问题的结果"递推"出原问题的结果:
设字符串 a a a 的长度为 m m m, 字符串 b b b 的长度为 n n n, 我们定义问题 C ( i , j ) C(i, j) C(i,j)
C ( i , j ) C(i, j) C(i,j) : a a a 的(前缀)子串(长度为 i i i) 与 b b b 的(前缀)子串(长度为 j j j) 的字符串编辑距离.
接着就是 C ( i , j ) C(i, j) C(i,j) 的递推公式了(这里就不做细节的讲述了,不熟悉的朋友可以参考进一步的资料)
C ( i , j ) = { i , i f j = 0 j , i f i = 0 C ( i − 1 , j − 1 ) , i f a [ i ] = b [ j ] m i n ( C ( i − 1 , j ) , C ( i , j − 1 ) ) + 1 , o t h e r w i s e C(i, j) = \left\{ \begin{aligned} % & 0, & if \ i = 0\ and\ j = 0 \\ & i, & if \ j = 0 \\ & j, & if \ i = 0 \\ & C(i - 1, j - 1), & if\ a[i] = b[j] \\ & min(C(i - 1, j), C(i, j - 1)) + 1, & otherwise \end{aligned} \right. C(i,j)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧i,j,C(i−1,j−1),min(C(i−1,j),C(i,j−1))+1,if j=0if i=0if a[i]=b[j]otherwise
下面简单列份实现(Lua):
-- get key from two index
function get_key(m, n)return m .. "_" .. n
endfunction edit_dist_iter(a, b, m, n)local edit_dist_buffer = {}edit_dist_buffer[get_key(0, 0)] = 0for i = 1, m doedit_dist_buffer[get_key(i, 0)] = iendfor i = 1, n doedit_dist_buffer[get_key(0, i)] = iendfor i = 1, m dofor j = 1, n dolocal ac = a:sub(i, i)local bc = b:sub(j, j)if ac == bc thenedit_dist_buffer[get_key(i, j)] = edit_dist_buffer[get_key(i - 1, j - 1)]elselocal d1 = edit_dist_buffer[get_key(i - 1, j)]local d2 = edit_dist_buffer[get_key(i, j - 1)]edit_dist_buffer[get_key(i, j)] = math.min(d1, d2) + 1endendendreturn edit_dist_buffer[get_key(m, n)]
endfunction edit_dist(a, b)return edit_dist_iter(a, b, #a, #b)
end
以上的代码使用了迭代形式,我们也可以用递归形式(来编写代码),只是递归会引起不少的重复计算,所以(工程)实现上,我们需要使用缓存来记录计算过的子问题结果(迭代版本也使用了缓存,作用上和递归版本其实也是一致的,记录的也是子问题的结果):
-- get key from two index
function get_key(m, n)return m .. "_" .. n
endfunction edit_dist_recur(a, b, m, n, buffer)if m <= 0 then-- result is trivial, do not need bufferreturn nelseif n <= 0 then-- result is trivial, do not need bufferreturn melselocal ac = a:sub(m, m)local bc = b:sub(n, n)if ac == bc thenlocal d = buffer[get_key(m - 1, n - 1)]if d thenbuffer[get_key(m, n)] = dreturn delselocal d = edit_dist_recur(a, b, m - 1, n - 1, buffer)buffer[get_key(m, n)] = dreturn dendelselocal d1 = buffer[get_key(m - 1, n)]if not d1 thend1 = edit_dist_recur(a, b, m - 1, n, buffer)endlocal d2 = buffer[get_key(m, n - 1)]if not d2 thend2 = edit_dist_recur(a, b, m, n - 1, buffer)endlocal d = math.min(d1, d2) + 1buffer[get_key(m, n)] = dreturn dendend
endfunction edit_dist(a, b)-- create bufferlocal edit_dist_buffer = {}return edit_dist_recur(a, b, #a, #b, edit_dist_buffer)
end
另外还看到一种基于编辑图(Edit Graph)的实现方式,不过思路上仍然和之前的讲述是一致的,实现上则会更复杂些,在此就不列代码了~
更多资料
- 编辑距离 (Edit distance)
- 编辑距离算法(Edit Distance)
- wiki
这篇关于Sweet Snippet 之 字符串编辑距离的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!