Virtual DOM中最小编辑距离的实现

参考文章:

深度剖析:如何实现一个 Virtual DOM 算法

最小编辑距离

实现Virtual DOM一般会经历如下步骤:

  • 使用JavaScript模拟dom树
  • 渲染dom树
  • 比较两颗虚拟dom树的差异
  • 应用上一步中找出的不同

模拟和渲染dom树在参考文章中写得非常清楚,实现起来难度也不大。

本文主要学习第三步 比较两颗虚拟dom树的差异 中用到的列文斯坦(Levenshtein)距离计算算法。

在计算开始之前要先对虚拟dom树做如下处理(图片来自深度剖析:如何实现一个 Virtual DOM 算法):

以深度优先的方式遍历虚拟dom,为每个元素加上唯一的key

image

比较同级的元素

image

同级元素寻找最小编辑方案

对于元素来说一般会有以下几种常见的操作:

  • 替换掉原来的节点,例如把上面的div换成了section
  • 移动、删除、新增子节点,例如上面div的子节点,把p和ul顺序互换
  • 修改了节点的属性
  • 对于文本节点,文本内容可能会改变。例如修改上面的文本节点2内容为Virtual DOM 2。

这里面重点关注对子节点的操作,因为对当前节点的操作诸如替换、修改节点属性、修改文本节点内容等操作都能很容易感知到并进行修改;但是对子节点的操作不容易感知——如果只是简单地比较子节点同位置的元素,那么在发生子节点元素发生位置交换的时候,这些子节点元素都会被替换掉,从而产生不必要的性能开销。

比如有元素

<div id='wrap'>
    <p key='A'></p>
    <p key='B'></p>
    <div key='C'></div>
    <p key='D'></p>
    <div key='E'></div>
</div>

变换为

<div id='wrap'>
    <p key='D'></p>
    <p key='A'></p>
    <div key='F'></div>
    <p key='B'></p>
    <div key='C'></div>
</div>

要求得id为wrap的节点的子节点操作步骤,一种是直接使用新的节点替换id为wrap的节点,这种方法简单粗暴但会产生不必要的性能开销;另外一种便是计算出wrap节点的子节点变动的步骤,从而尽可能保留现有的节点。

之前深度优先遍历元素添加唯一key的作用便是通过该key来判断到变动前后的两个元素是否是同一个。有了以上条件,我们可以直接把同层级dom修改的过程抽象成由字符串A变换为字符串B的过程,应用 莱文斯坦距离 来计算出最小编辑距离及最小编辑过程。

因为给每个子元素都加了唯一的key,所以可以把变动前后的节点抽象成两个字符串'ABCDE'和'DAFBC',要做的便是求得由字符串'ABCDE'变成'DAFBC'的最小编辑过程。

最小编辑距离

该算法采用动态规划的思想,请参考 什么是动态规划?动态规划的意义是什么?
就算讲得这么详细我也看不懂╮(╯▽╰)╭
采用矩阵的方式来记录各个操作所需要的代价(操作次数),这样每一步的操作都基于上一次计算得出的结果,可以减少很多不必要的计算。

如图所示,先构建一个初始化矩阵,X轴为字符串AB,Y轴为字符串CD

image.png

定义删除和插入所需要的代价是1,替换所需要的代价是2(即先删除再插入或先插入再删除)。

表格中0表示初始化的代价(也可以看成是一个空字符串变换到另一个空字符串的代价)。

那么表格中1和2表示代价指的便是:空字符串变换到C或A所需的代价是1,空字符串变换到CD或AB所需的代价是2(也可看做字符串C变换到CD的代价是1,因此最后的代价便是1+1=2)。

继续完善矩阵

image.png

灰色格子表示由A变换到C或由C变换到A所需要的最小代价。从以下三个代价中取最小的一个作为灰色格子里的值:

  • 左侧值+1(删除操作)
  • 上方值+1(增加操作)
  • 如果变换的值相同左上角的值+0,如果不同左上角的值+2(说明是替换的操作)

剩余的格子都做类似的操作,以上文所述字符串'ABCDE'变换到'DAFBC'为例:

image.png

灰色格子即为每次做的操作,右下角格子内的数字标识了最小编辑距离。从右下角开始找出当前代价上方、左方、左上方中最小的数字,该数字即是上一次做的操作——如图中灰色格子所示。我们可以根据这个矩阵从左上角开始回溯出变换的流程:

  • 从字符串 ABCDE 开始
  • 向下走一步,插入字符串D 变为 DABCDE
  • 向右下角走一步,因为代价没有发生变化,当前字符串还是 DABCDE
  • 向下走一步,插入字符串F 变为 DAFBCDE
  • 向右下角走一步,因为代价没有发生变化,当前字符串还是 DAFBCDE
  • 向右下角走一步,因为代价没有发生变化,当前字符串还是 DAFBCDE
  • 向右走一步,删除字符串D 变为 DAFBCE
  • 向右走一步,删除字符串E 变为 DAFBC

以上就是整个变换的流程。

使用代码实现该过程:

  • 以需要变换的两个字符串的长度作为X轴和Y轴的长度来构建矩阵
  • 初始化矩阵,在各个格子中填入相应的值
  • 从右下角开始回溯出操作过程

生成并初始化矩阵

let matrix = [];
const string1 = 'fjasklrfew';
const string2 = 'cvdsjklfqweo';
// 遍历生成填充矩阵
for (let i = 0, len1 = string1.length; i <= len1; i++) {
    // 初始化一维的数据
    matrix[i] = [];
    for (let j = 0, len2 = string2.length; j <= len2; j++) {
        // 如果i或j为0则需要填充数据
        if (i === 0) {
            matrix[i][j] = j;
        } else if (j === 0) {
            matrix[i][j] = i;
        } else {
            /* 否则就按照规则计算出增加、删除、替换操作所需的代价  取出最小的一个作为最终的操作
            *  对于插入和删除来说无论如何都会有1的代价,对于替换来说当两个字符不相同的时候会产生2的代价(即删除+插入) 相同的时候代价为0
            */
            const isDiff = string1[i - 1] !== string2[j - 1];
            // 插入的代价
            const insertCost = matrix[i - 1][j] + 1;
            // 删除的代价
            const deleteCost = matrix[i][j - 1] + 1;
            // 替换的代价
            let replaceCost = isDiff ? 2 : 0;
            replaceCost += matrix[i - 1][j - 1];
            matrix[i][j] = Math.min(insertCost, deleteCost, replaceCost);
        }
    }
}

根据矩阵回溯出操作过程

// 从右下角开始回溯出操作过程
let startX = string1.length,
    startY = string2.length;
// 定义操作对应的code和名字
const operateList = ['删除', '插入', '替换'];
const operateCodeList = ['delete', 'insert', 'replace'];
// 最终的操作结果
let finalOperate = [];
// 根据生成的矩阵回溯出做的操作
backTraceOperate(matrix, startX, startY);
function backTraceOperate(matrix, startX, startY) {
    /*  约定X轴变换为插入操作,Y轴变换为删除操作
    *   因为插入和删除操作的代价都为1,所以要把一个字符串'A'变为字符串'B'
    *   可以先删除A再插入B也可以先插入B再删除A,约定操作是为了回溯操作过程时有统一的标准
    *   如果插入和删除的代价一样则默认选择插入的
    */
    // 取出当前格子上方、左方、左上方的代价得到最小代价即为上一次的操作
    deleteCost = matrix[startX - 1][startY];
    insertCost = matrix[startX][startY - 1];
    replaceCost = matrix[startX - 1][startY - 1];
    // 这里做的一大波步骤只是为了输出信息时的可读性
    const costList = [deleteCost, insertCost, replaceCost];
    const minCost = Math.min(deleteCost, insertCost, replaceCost);
    let minCostIndex = costList.indexOf(minCost);
    minCostIndex = deleteCost === insertCost && minCostIndex <= 1 ? 1 : minCostIndex;
    const calcMinCost = matrix[startX][startY] - minCost;
    console.log(`当前代价 ${matrix[startX][startY]} 最小代价是 ${calcMinCost} 最小代价操作是 ${calcMinCost === 0 ? '不做操作' : operateList[minCostIndex]}`);
    let tempStartX = startX, tempStartY = startY;
    if (operateCodeList[minCostIndex] === 'insert') {
        tempStartY -= 1;
        finalOperate.push(`插入字符 ${string2[tempStartY]}`)
    } else if (operateCodeList[minCostIndex] === 'delete') {
        tempStartX -= 1;
        finalOperate.push(`删除字符 ${string1[tempStartX]}`)
    } else if (operateCodeList[minCostIndex] === 'replace') {
        tempStartX -= 1;
        tempStartY -= 1;
        if (matrix[startX][startY] - minCost === 0) {
            finalOperate.push('不做操作');
        } else {
            finalOperate.push(`将 ${string1[tempStartX]} 替换为 ${string2[tempStartY]}`);
        }
    }
    // 因为是从右下角回溯回去的,得到的顺序是倒序,所以当结束时对操作列表做一次反转
    if (tempStartX === 0 && tempStartY === 0) {
        console.log('回溯结束');
        console.log(matrix);
        console.log(`将 ${string1} 变换为 ${string2} 最小操作距离 ${matrix[string1.length][string2.length]}`);
        console.log(finalOperate.reverse());
    } else {
        arguments.callee(matrix, tempStartX, tempStartY);
    }
}

以上便是最小编辑距离的计算方式。