实现文本diff比较与展示

作为编程人员，文本diff比较与展示应该不陌生，最常见的是在Git中使用git diff命令，可以查看代码修改前后的对比。在git中diff比较与展示的最小单位是行，因为代码修改涉及的改动一般较多，以行为单位显示出来的效果，美观且容易阅读。

自己最近在某个项目中遇到与一个git diff类似的需求：“一段普通长度的文本经过修改后，希望向阅读者展示修改所带来的前后差异”，本文就讲述这个需求自己是如何实现的。

分析需求

需求是针对一段普通长度文本展示修改前后的diff，因文本内容较短，所以不选择编码中常见的行作为比较单位，而是以字符为最小单位。进一步分析，可以发现问题的核心是寻找文本修改前后的相同部分，然后再将前后内容与相同部分进行比较，得到差异内容进行可视化呈现。

寻找前后文本中的相同部分，这个描述并不准确，应该是寻找前后文本中长度最长的共同子序列，这个问题的专业名称是“最长公共子序列”，最佳求解方法是使用动态规划求解，具体算法推导详询Google、百度。

假设原文本(before)-“你今天吃饭了吗？”，修改后(after)-“今天你吃饭了吗？”，在这个简单的例子中我们不需要计算也可以看出最长公共子序列(lcs)是：“今天吃饭了吗？”。

接着我们拿before与lcs进行比较，发现差异字符是"你"，而after与lcs进行比较得到的差异字符也是"你"，但前者表示删除后者则是插入，所以最终我们的diff可以表示为：["你(delete)", "今天", "你(insert)", "吃饭了吗？"]，用这个数组做可视化展示，也就是diff的展示。

最长公共子序列求解

前面的例子由于before与after长度太短，肉眼能看出最长公共子序列，实际中我们则需要用算法与代码实现这部分，思路是先求长度再反推内容，自己用js按算法写了如下实现代码：

function lcs(x, y) {
    x = x ? x.split('') : [];
    y = y ? y.split('') : [];

    let mark = [];
    for (let i = 0; i < x.length; i++) {
        mark[i] = [];

        for (let j = 0; j < y.length; j++) {
            if (x[i] === y[j]) {
                mark[i][j] = (i === 0 ? 0 : (mark[i - 1][j - 1] || 0)) + 1;
                continue;
            }

            mark[i][j] = Math.max(mark[i][j - 1] || 0, i === 0 ? 0 : mark[i - 1][j]);
        }
    }

    let i = x.length - 1;
    let j = y.length - 1;
    let result = [];

    while (i >= 0 && j >= 0) {
        if (x[i] === y[j]) {
            result.unshift(x[i]);
            i--;
            j--;
            continue;
        }

        if (i !== 0 && mark[i][j] === mark[i - 1][j]) {
            i--;
            continue;
        }

        if (j !== 0 && mark[i][j] === mark[i][j - 1]) {
            j--;
            continue;
        }

        break;
    }

    return result.join('');
}

// lcs('今天你吃饭了吗？', '你今天吃饭了吗？') = '今天吃饭了吗？';
// lcs('我今天去你家吃饭，你在家吗？', '你在家吗？我打算今天去你家吃饭') = '我今天去你家吃饭';

对比差异

得到两个字符串的最长公共子序列之后，接着我们需要计算前后字符串与公共子序列的差异并合并到一个结构当中，最终用这个合并的结构做可视化展示。

这部分不需要啥特殊方法求解，以求before与lcs的diff为例：

let before = '今天你吃饭了吗？'.split('');
let lcs = '今天吃饭了吗？'.split('');

let beforeDiff = [];
let chunk = '';
let flag = before[0] === lcs[0];

for (let i = 0, j = 0; i < before.length; i++) {
    if (flag === (before[i] === lcs[j])) {
        chunk += before[i];
        j += flag ? 1 : 0;
        continue;
    }

    beforeDiff.push({
        text: chunk,
        isCommon: flag // lcs中存在
    });

    chunk = before[i];
    flag = !flag;

    if (before[i] === lcs[j]) {
        j++;
    }
}

beforeDiff.push({
    text: chunk,
    isCommon: flag
});

上述代码得到的beforeDiff是原文本before与lcs的diff，可用来展示修改中被删除的内容，而用同样方法可以得到afterDiff，用于展示修改后插入的内容。

通过beforeDiff与afterDiff可以分别展示修改的删除与插入，但要在一个结构中同时体现两者，则需要进行合并，其思路是：“通过diff(before、after)与lcs对比，确定差异字符串在lcs中的index，再将diff内容插入到lcs的这些index位置中”，代码如下：

// _ is lodash
let result = [];

let len = 0;
beforeDiff = _.map(beforeDiff, item => {
    if (item.isCommon) {
        len += item.text.length;
        return item;
    }

    item.type = 'delete';
    item.index = len;
    return item;
});

len = 0;
afterDiff = _.map(afterDiff, item => {
    if (item.isCommon) {
        len += item.text.length;
        return item;
    }

    item.type = 'insert';
    item.index = len;
    return item;
});

let diffItems = _.filter(beforeDiff.concat(afterDiff), item => {
    return item.type === 'insert' || item.type === 'delete';
});

diffItems = _.sortBy(diffItems, 'index');

let index = 0;
_.each(diffItems, item => {
    if (item.index !== 0) {
        result.push({
            text: lcs.substring(index, item.index),
            type: 'origin'
        });
        index = item.index;
    }

    result.push({
        text: item.text,
        type: item.type
    });
});

if (lcs.length > cursor) {
    result.push({
        text: lcs.substring(index, lcs.length),
        type: 'origin'
    });
}

经上诉代码合并得到的result就是最终用来呈现diff的结构，结构为：[{text: 'string', type: 'string, origin|delete|insert'}]

可视化

能得到diff的数据表示结构，做可视化相对容易，展示一下小程序的做法：

<!-- wxml -->
<view class="diff">
    <text wx:for="{{diff}}" wx:key="{{index}}" class="{{item.type}}" space="ensp">{{item.text}}</text>
</view>

上面wx:for之中的diff变量是最终得到的diff表示结构，而样式控制则在不同的class中体现。