TOC
前段时间公司里有需求需要一个文本对比工具，我在网上也收集到了一些资料，找到了一些对比 DEMO，仔细考虑之后恍然大悟，这东西不就是最长公共子序列算法吗？
所谓的 diff，就是寻找两个文本中的最长公共子序列，子序列的任意部分都是正确的部分，而在这个序列之外的字符就是错误字符，抱着这个思路我开发了一个基于 Web 的校对工具，当然虽然可能有些粗糙，但还是非常宝贵的实践体验啊，因为这是我学习一些算法来第一次真正意义上的用到，并且如果不知道这个算法的话，可能真的写不出来这个工具（只能用循环判断来进行对比，一但某个字符错误，接下来全错）
在这里放出核心的代码。
const LCS_TABLE = (s1, s2) => {
s1 = s1.slice()
s2 = s2.slice()
let x = s1.length
let y = s2.length
// 需要保证表格的便利与数组的访问同意 也就是从1 开始
// 所以需要在前面将数组踮起 并且为了避免越界 需要在获取长度之后进行
s1.unshift(null)
s2.unshift(null)
// 以下两个循环都是为了打出一个边界 也就是表格的最顶层和最左层都是0
let table = []
for (let i = 0; i <= x; i++) {
table[i] = []
table[i][0] = {
val: 0
}
}
for (let i = 0; i <= y; i++) {
table[0][i] = {
val: 0
}
}
// 正式开始
for (let i = 1; i <= x; i++) {
for (let j = 1; j <= y; j++) {
// 找到匹配 填入左上箭头
if (s1[i] === s2[j]) {
table[i][j] = {
val: table[i - 1][j - 1].val + 1,
lt: true,
t2Index: j - 1
}
} else if (table[i - 1][j].val >= table[i][j - 1].val) {
table[i][j] = {
val: table[i - 1][j].val,
top: true,
t2Index: j - 1
}
} else {
table[i][j] = {
left: true,
val: table[i][j - 1].val,
t2Index: j - 1
}
}
}
}
return table
}
const printLCS = (table, X, i, j) => {
if (i === 0 || j === 0) return
if (table[i][j].lt) {
return printLCS(table, X, i - 1, j - 1)
}
if (table[i][j].top) {
return printLCS(table, X, i - 1, j)
}
return printLCS(table, X, i, j - 1)
}
// 返回一个包含 text2Index 下标的数组
// 所有匹配的文本
const processTextLCSDiff = table => {
let i = table.length - 1
let j = table[0].length - 1
function _inner(table, i, j) {
if (i === 0 || j === 0) return []
if (table[i][j].lt) {
return [table[i][j].t2Index].concat(_inner(table, i - 1, j - 1))
}
if (table[i][j].top) {
return [].concat(_inner(table, i - 1, j))
}
return [].concat(_inner(table, i, j - 1))
}
return _inner(table, i, j)
}
const getDiffTextArray = (diffIndexArray, textArray) => {
return textArray.map((v, i) => {
// 检测该字符是否匹配
let findex = diffIndexArray.findIndex(v => v === i)
if (findex > -1) {
return {
mathed: true,
val: v
}
}
return {
mathed: false,
val: v
}
})
}
// 接收主文本和副文本 返回已副文本为基准的一个数组，其内部为对象，标记该单个字符和正确情况。
function textDiffCore(mainText, assistantText) {
mainText = mainText.split('')
assistantText = assistantText.split('')
console.time('search')
const table = LCS_TABLE(mainText, assistantText)
console.timeEnd('search')
console.time('LCS')
const LCSArray = processTextLCSDiff(table)
console.timeEnd('LCS')
return getDiffTextArray(LCSArray, assistantText)
}
// 接收两段文本 和一个元素以便插入结果
function startDiff(text1, text2, content) {
// 已1为基准 进行前置处理
// 文本处理的内容是用正则删除所有空格换行 业务需要
text1 = textProcess(text1)
text2 = textProcess(text2)
let diffResult = textDiffCore(text1, text2)
let htmlText = diffResult.map(v => {
return (
'<span ' +
(v.mathed ? 'class="corrent" ' : 'class="fail" ') +
'>' +
v.val +
'</span>'
)
})
content.html(htmlText)
}
求最长公共子序列是一个NPHard问题，她的效率是O(n ^ 2),还是比较慢的，还有一点我这个东西因为业务需要是删除所有换行的，这样的话所有文本都处于一行上。
如果能分行对比，性能会有大幅度的提升。