| 【关于MT】 MT是手机腾讯网前端团队开发维护的一个专注于移动端的、带有增量更新特色的JavaScript模块管理框架。MT提供了简单友好的模块定义规范、简单易用的打包管理工具和强大的JavaScript增量更新代理服务。本文主要是介绍了MT 2.0版本中基于编辑距离计算的增量更新方案。 关于MT，更多内容可访问页面。 手机腾讯网开源项目MT 2.0版本，一个主要特点是增量更新算法基于编辑距离计算，做到了字符级别的增量更新，比之前的chunk算法更加精确，减少了chunk算法带来的一些冗余字符的下载。下面我们就来看看MT是如何利用这个算法来实现增量更新的。 首先我们来看看什么是Levenshtein Distance（编辑距离），编辑距离即从一个字符串变换到另一个字符串所需要的最少变化操作步骤，该概念由俄罗斯科学家Vladimir Levenshtein在1965年提出的。 那如何计算编辑距离呢？通常我们修改一个字符串为另外一个字符串的时候有几种方法，删除、替换、插入，其他的字符就是不变了。按照编辑代价算，删除、替换、插入这几种操纵的代价是1，即修改一个字符，不变则是 0，表示没有修改，即操作代价是 0。 首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为 i 的子串到第二个字符串的长度为 j 的子串的编辑距离。通过动态规划法（dp）,我们很容易得到以下公式：
我们可以用一个矩阵来纪录这一个过程，以 beauty 和 batyu 为例：
这个矩阵的红色部分就是我们纪录 edit(I,j) 的编辑距离。我们再通过另外一个矩阵记录一下我们获取以上编辑距离表的每个步骤，0 表示未修改、1 表示替换、2 表示删除、3 表示插入，我们得到以下矩阵：
通过这个矩阵，我们可以知道从 batyu 修改成 beauty，要使代价最小而每一步所进行的操作。通过从矩阵的右下脚处，随着编辑步骤往左上脚遍历，我们就能得到从 batyu 编辑成 beauty 每一步进行的操作。如果当前是删除，则往纵坐标减 1；如果是替换或者相等，则取对角点；如果是插入，则横坐标减 1。以上面矩阵为例，最后一个是 arr[6][5]=2 说明是删除，纵坐标减 1,下一步骤是 arr[6][4] 为 0，说明不变，则横坐标，纵坐标都减 1, 下一步为 arr[5][3]=0，以此类推，得到如下步骤（绿色框字体）：
于是我们得到从 batyu 到 beauty 得修改代价最小得步骤是：
即，第一位不变，第二位插入一个字符，从 beauty 里取第二个字符 2，第三位不变，第四位取第四个字符 u，第四第五位不变，那我们用一个数组这个操作：
我们进一步压缩有顺序得数组得到：[ [ 1, 1 ], 'e', [ 2, 1 ], 'u', [ 3, 2 ] ]。其中得数组表示，从第几个字符开始 n 个字符不变，这就是传说中得增量文件。通过这个增量文件数组和源字符串 batyu 我们很容易得到新字符串：
以上就是对MT 2.0基于编辑距离计算的增量更新方案的详细介绍。 |
