LCS问题（最长公共子序列）
上一篇文章
所有代码和markdown在chux0519/algs同步更新。
计算LCS长度
递归解法
LCS问题是具有最优子结构的。
假设长度为m的字符串X[0..m-1]和长度为n的字符串Y[0..n-1]，用L(X[0..m-1], Y[0..n-1]) 来表示它们的LCS长度。则可以得到以下结论：
- 如果X[m-1] = Y[n-1], 那么L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
- 如果X[m-1] != Y[n-1], 那么L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])
用JS描述如下
function lcs (str1, str2, len1, len2) {
if (len1 === 0 || len2 === 0) return 0
if (str1[len1] === str2[len2]) {
return 1 + lcs(str1, str2, len1 - 1, len2 - 1)
} else {
return Math.max(
lcs(str1, str2, len1 - 1, len2),
lcs(str1, str2, len1, len2 - 1)
)
}
}
进一步分析
假设X="AXYT", Y="AYZX"，画出以上代码的调用图，得到：
lcs("AXYT", "AYZX")
/
lcs("AXY", "AYZX") lcs("AXYT", "AYZ")
/ /
lcs("AX", "AYZX") lcs("AXY", "AYZ") lcs("AXY", "AYZ") lcs("AXYT", "AY")
可以看出lcs("AXY", "AYZ")被重复计算了，随着层数的增多，可以分析出，有许多重复子问题会出现，于是，可以利用记忆化或者制表来进行优化算法。
制表解法
// tab
function lcsWithTab (str1, str2, len1, len2) {
var tab = new Array(len1 + 1).fill([])
for (var i = 0; i <= len1; i++) {
for (var j = 0; j <= len2; j++) {
if (i === 0 || j === 0) {
tab[i][j] = 0
} else if (str1[i - 1] === str2[j - 1]) {
tab[i][j] = tab[i - 1][j - 1] + 1
} else {
tab[i][j] = Math.max(
tab[i - 1][j],
tab[i][j - 1]
)
}
}
}
return tab[len1][len2]
}
制表解法，通过定义好基线条件tab[i][j] = 0 where i ==0 || j == 0，自底向上计算出结果，提升速度的同时消除了递归。
回溯LCS
存储回溯数组
在上述算法中，增加一个数组用于存储回溯路径即可，稍作改动如下。
function LCS (str1, str2, len1, len2) {
var tab = []
var back = []
for (var m = 0; m <= len1; m++) {
tab[m] = []
back[m] = []
for (var n = 0; n <= len2; n++) {
tab[m][n] = null
back[m][n] = null
}
}
for (var i = 0; i <= len1; i++) {
for (var j = 0; j <= len2; j++) {
if (i === 0 || j === 0) {
tab[i][j] = 0
back[i][j] = null
} else if (str1[i - 1] === str2[j - 1]) {
tab[i][j] = tab[i - 1][j - 1] + 1
back[i][j] = '↖'
} else if (tab[i - 1][j] > tab[i][j - 1]) {
tab[i][j] = tab[i - 1][j]
back[i][j] = '↑'
} else if (tab[i - 1][j] === tab[i][j - 1]) {
tab[i][j] = tab[i - 1][j]
back[i][j] = '←/↑'
} else {
tab[i][j] = tab[i][j - 1]
back[i][j] = '←'
}
}
}
return { tab: tab, bt: back }
}
运行
var str1 = 'GAC'
var str2 = 'AGCAT'
var result = LCS(str1, str2, str1.length, str2.length)
console.log(result.tab)
console.log(result.bt)
可以得到如下输出：
[ [ 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 1, 1, 1 ],
[ 0, 1, 1, 1, 2, 2 ],
[ 0, 1, 1, 2, 2, 2 ] ]
[ [ null, null, null, null, null, null ],
[ null, '←/↑', '↖', '←', '←', '←' ],
[ null, '↖', '←/↑', '←/↑', '↖', '←' ],
[ null, '↑', '←/↑', '↖', '←/↑', '←/↑' ] ]
tab数组的输出为LCS的长度，�bt数组的内容是回溯的方向，例子取自维基百科。
输出一个LCS
输出LCS结果，需要利用bt数组进行回溯，只输出一个LCS时，可以用以下回溯函数。
function backtrace (bt, str1, str2, i, j) {
if (i === 0 || j === 0) {
return ''
} else if (bt[i][j] === '↖') {
return backtrace(bt, str1, str2, i - 1, j - 1) + str1[i]
} else {
if (bt[i][j] === '←') {
return backtrace(bt, str1, str2, i, j - 1)
} else {
return backtrace(bt, str1, str2, i - 1, j)
}
}
}
console.log(backtrace(result.bt, str1, str2, str1.length, str2.length))
得到输出AC
实际上不用bt数组，直接使用保存LCS长度的tab数组也能直接回溯。稍微修改backtrace的判断条件即可。如下：
function backtraceByTab (tab, str1, str2, i, j) {
if (i === 0 || j === 0) {
return ''
} else if (str1[i - 1] === str2[j - 1]) {
return backtraceByTab(tab, str1, str2, i - 1, j - 1) + str1[i]
} else {
if (tab[i][j - 1] > tab[i - 1][j]) {
return backtraceByTab(tab, str1, str2, i, j - 1)
} else {
return backtraceByTab(tab, str1, str2, i - 1, j)
}
}
}
console.log(backtraceByTab(result.tab, str1, str2, str1.length, str2.length))
得到输出仍旧为AC
20170906 update
输出所有LCS
输出所有LCS结果，在这里使用保存LCS长度的tab数组。
wiki给出的伪代码如下
function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
if i = 0 or j = 0
return {""}
else if X[i] = Y[j]
return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
else
R := {}
if C[i,j-1] ≥ C[i-1,j]
R := R ∪ backtrackAll(C, X, Y, i, j-1)
if C[i-1,j] ≥ C[i,j-1]
R := R ∪ backtrackAll(C, X, Y, i-1, j)
return R
使用JS实现如下
// backtrace all
function backtraceAllByTab (tab, str1, str2, i, j) {
function _backtraceAllByTab (tab, str1, str2, i, j) {
if (i === 0 || j === 0) {
return ['']
} else if (str1[i - 1] === str2[j - 1]) {
return [].map.call(_backtraceAllByTab(tab, str1, str2, i - 1, j - 1), each => each + str1[i - 1])
} else {
var r = []
if (tab[i][j - 1] >= tab[i - 1][j]) {
r = r.concat(_backtraceAllByTab(tab, str1, str2, i, j - 1)) // 本应该求并集，这里直接连接起来，最后去重一次
}
if (tab[i - 1][j] >= tab[i][j - 1]) {
r = r.concat(_backtraceAllByTab(tab, str1, str2, i - 1, j)) // 本应该求并集，这里直接连接起来，最后去重一次
}
return r
}
}
return Array.from(new Set(_backtraceAllByTab(tab, str1, str2, i, j))) // 去重
}
调用
var str1 = 'GAC'
var str2 = 'AGCAT'
console.log(backtraceAllByTab(result.tab, str1, str2, str1.length, str2.length))
输出
[ 'AC', 'GC', 'GA' ]
值得注意的是，输出所有的LCS是不保证时间复杂度为多项式复杂度的，如果两个字符串比较接近，那么可能每一步都会有分枝。
输出diff
这里JS实现完全参考wiki，等号的判定条件放在
>=中，若将其替换为'>'，则diff的输出可能不同。
function printDiff (tab, str1, str2, i, j) {
if (i > 0 && j > 0 && str1[i - 1] === str2[j - 1]) {
printDiff(tab, str1, str2, i - 1, j - 1)
console.log(` ${str1[i - 1]}`)
} else if (j > 0 && tab[i][j - 1] >= tab[i - 1][j]) {
printDiff(tab, str1, str2, i, j - 1)
console.log(`+ ${str2[j - 1]}`)
} else if (i > 0) {
printDiff(tab, str1, str2, i - 1, j)
console.log(`- ${str1[i - 1]}`)
} else {
console.log('')
}
}
调用
var str1 = 'GAC'
var str2 = 'AGCAT'
printDiff(result.tab, str1, str2, str1.length, str2.length)
输出
- G
A
+ G
C
+ A
+ T
思考——算法优化
-
使用trim
在字符串长度很长时，记录LCS的长度的表会非常占用空间，因此如果两个字符串有很多类似的部分，可以对首尾相同的部分进行跳过，从而缩短要进行比较的部分，达到优化的目的。例如wiki中给出的伪代码。
function LCS(X[1..m], Y[1..n]) start := 1 m_end := m n_end := n trim off the matching items at the beginning while start ≤ m_end and start ≤ n_end and X[start] = Y[start] start := start + 1 trim off the matching items at the end while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end] m_end := m_end - 1 n_end := n_end - 1 C = array(start-1..m_end, start-1..n_end) only loop over the items that have changed for i := start..m_end for j := start..n_end the algorithm continues as before ... -
减少比较次数
在上述的算法中，我们进行的比较是逐字符比较的，而实际的应用中，我们通常是采用逐行比较的方式，将每一行看作是一个元素来进行比较，从而到达减少比较次数的目的。
-
缩短字符串长度
在使用了上面的方法后，将每一行（字符串）看作元素，例如在比较源码异同时，通常一行有多余60个的字符，这时利用哈希或是check sum通常可以将长度缩短到8-40个字符。但是，这种做法还是有一些弊端。
- 首先，哈希或是check sum的计算会额外的需要一部分时间。
- 其次，哈希或是check sum的计算会额外的需要一部分空间。
- 上述两点虽说有些耗时，但是比起逐字符比较，这样的代价其实很小。
- 最后一点真正弊端是，字符串的哈希可能导致碰撞（不同的字符串产生相同的哈希），一旦发生碰撞，这会使结果不正确。但是，这样的情况仍是有解决办法的（例如对哈希进行再加密等等）。
-
Hirschberg's算法
这里提一下Hirschberg's algorithm，这个算法可以将节点消耗的内存降低到
min(m,n)+1,但是会相应略微的增加一部分时间复杂度（仍是平方时间复杂度）。 -
使用更高级的算法
LCS的DP解法复杂度时平方时间，理论上应该也不能在高了，但是同样的时间复杂度，在应用中的实际平均耗时是有区别的。这里mark一篇论文，后续可能会继续写相关LCS的文章。
