文档章节

深入剖析手腾MT2.0基于编辑距离计算的增量更新算法

卢勇福
 卢勇福
发布于 2014/06/17 16:31
字数 1584
阅读 686
收藏 15

<p>&#160;</p> <p>手机腾讯网mt2.0(<a href="http://mt.tencent.com">http://mt.tencent.com</a>)终于发布了,这个版本的增量更新算法基于编辑距离计算,做到了字符级别的增量更新,比之前的chunk算法更加精确,减少了chunk算法带来的一些冗余字符的下载,下面我们就来看看mt是如何利用这个算法来实现增量更新的.<h2>(广告:我们的github:<a href="https://github.com/mtjs/mt">https://github.com/mtjs/mt</a> ,如果觉得不错请给我们star)</h2></p> <p>首先我们来看看什么是Levenshtein Distance (编辑距离),编辑距离即从一个字符串变换到另一个字符串所需要的最少变化操作步骤,是俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。</p> <p>那如何计算编辑距离呢。通常我们修改一个字符串为另外一个字符串的时候有集中方法,删除,替换,插入,其他的字符就是不变了,按照编辑代价算,删除,替换,插入这几种操纵的代价是1,即修改一个字符,不变则是0,表示没有修改,即操作代价是0. 首先定义这样一个函数——edit(i, j),它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。</p> <p>通过动态规划法(dp),我们很容易得到以下公司:</p> <p>· if i == 0 且 j == 0,edit(i, j) = 0</p> <p>· if i == 0 且 j &gt; 0,edit(i, j) = j</p> <p>· if i &gt; 0 且j == 0,edit(i, j) = i</p> <p>· if i ≥ 1&#160; 且 j ≥ 1 edit(i, j) = min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) },当第一个字符串的第i个字符不等于第二个字符串的第j个字符时,f(i, j) = 1;否则,f(i, j) = 0</p> <p>· 我们可以用一个矩阵来纪录这一个过程,以以beauty和batyu为例:</p> <p><a href="http://static.oschina.net/uploads/img/201406/17163153_4dVG.png"><img style="background-image: none; border-bottom: 0px; border-left: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; display: inline; border-top: 0px; border-right: 0px; padding-top: 0px" title="wps_clip_image-31133" border="0" alt="wps_clip_image-31133" src="http://static.oschina.net/uploads/img/201406/17163153_GXgY.png" width="227" height="244" /></a></p> <p>这个矩阵的红色部分就是我们纪录edit(I,j)的编辑距离。我们再通过另外一个矩阵记录一下我们获取以上编辑距离表的每个步骤,0表示未修改, 1表示替换,2表示删除,3表示插入,我们得到以下矩阵。</p> <p><a href="http://static.oschina.net/uploads/img/201406/17163154_3EKY.png"><img style="background-image: none; border-bottom: 0px; border-left: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; display: inline; border-top: 0px; border-right: 0px; padding-top: 0px" title="wps_clip_image-10140" border="0" alt="wps_clip_image-10140" src="http://static.oschina.net/uploads/img/201406/17163154_xoYX.png" width="228" height="244" /></a></p> <p>通过这个矩阵,我们可以知道从batyu修改成beauty,要使代价最小,每一步所进行的操作.通过从矩阵的右下脚处,随着编辑步骤往左上脚遍历,我们就能得到从batyu编辑成beauty每一步进行的操作。如果当前是删除,则往纵坐标减1.如果是替换或者相等,则取对角点,如果是插入,则横坐标减1。以上面矩阵为例,最后一个是arr[6][5]=2说明是删除,纵坐标减1,下一步骤是arr[6][4]为0,说明不变,则横坐标,纵坐标都减1, 下一步为arr[5][3]=0,以此类推,得到如下步骤(绿色框字体)</p> <p><a href="http://static.oschina.net/uploads/img/201406/17163155_Uzjj.png"><img style="background-image: none; border-bottom: 0px; border-left: 0px; padding-left: 0px; padding-right: 0px; display: inline; border-top: 0px; border-right: 0px; padding-top: 0px" title="wps_clip_image-23657" border="0" alt="wps_clip_image-23657" src="http://static.oschina.net/uploads/img/201406/17163155_4Ugw.png" width="224" height="244" /></a></p> <p>于是我们得到从batyu 到beauty得修改代价最小得步骤是</p> <p>0-3-0-3-0-0-2</p> <p>即,第一位不变,第二位插入一个字符,从beauty里取第二个字符’2’,第三位不变,第四位取第四个字符’u’,第四第五位不变,那我们用一个数组这个操作:</p> <p>[ [ 1, 0 ], 'e', [ 2, 0 ], 'u', [ 3, 0 ], [ 4, 0 ] ],其中数组表示不变,字符表示插入或者替换。</p> <p>我们进一步压缩有顺序得数组得到: <br />[ [ 1, 1 ], 'e', [ 2, 1 ], 'u', [ 3, 2 ] ]</p> <p>其中得数组表示,从第几个字符开始n个字符不变,这就是传说中得增量文件。</p> <p>通过这个增量文件数组和源字符串batyu我们很容易得到新字符串:</p> <p>beauty=”batyu”.substr(1-1,1)+’e’+”batyu”.substr(2-1,1)+’u’+”batyu”.substr(3-1,2);</p> <p>这就是我们mt2.0得增量更新算法,啥也不说了,我们上代码:</p>

<!-- lang: js -->
function lcsDiff(source,target){
var SAME= 0,REPLACE= 1,DELETE= 2,INSERT=3;
var sourceArr=source.split('');
//var sLength=sourceArr.length;
var targetArr=target.split('');
//var tLength=targetArr.length;
//编辑距离矩阵
var disMatrix=[];
//步骤矩阵
var stepMatrix=[];
//生成一个空矩阵,二维数组
for(var i=0;i<=sourceArr.length;i++){
    disMatrix[i]=[];
    stepMatrix[i]=[];
    for(var j=0;j<=targetArr.length;j++){
        disMatrix[i][j]=0;
        stepMatrix[i][j]=0;
    }
}

 console.log(disMatrix);
 console.log(stepMatrix);
for(var i=0;i<=sourceArr.length;i++){
    for(var j=0;j<=targetArr.length;j++){
        // console.log(i+" "+j);
        //在第0步,由于都是空,所以是0
        if(i==0&&j==0){
            disMatrix[i][j]=0;
            stepMatrix[i][j]=SAME;
        }
        else if(i==0&&j>0){
            disMatrix[i][j]=j;
            stepMatrix[i][j]=INSERT;
        }
        else if(j==0&&i>0){
            disMatrix[i][j]=i;
            stepMatrix[i][j]=DELETE;
        }
        else if(i>0&&j>0){
            var sameStep=(sourceArr[i-1]===targetArr[j-1]),
                delStep=disMatrix[i-1][j]+1,
                insertStep=disMatrix[i][j-1]+1,
                replaceStep=disMatrix[i-1][j-1]+(sameStep?0:1);
            //console.log(i+' '+j+":"+replaceStep+' '+delStep+' '+insertStep+" v:"+sourceArr[i-1]+' '+targetArr[j-1]);
            //console.log(i+' '+j+":"+replaceStep+' '+delStep+' '+insertStep);
            disMatrix[i][j]=Math.min(replaceStep,delStep,insertStep);
            var stepAct=disMatrix[i][j];
            switch(stepAct){
                case replaceStep:
                    stepMatrix[i][j]=sameStep?SAME:REPLACE;
                    break;
                case insertStep:
                    stepMatrix[i][j]=INSERT;
                    break;
                case delStep:
                    stepMatrix[i][j]=DELETE;
                    break;
            }
            // console.log(i+' '+j+":"+replaceStep+' '+delStep+' '+insertStep+' act :'+stepMatrix[i][j]);
        }
    }
}
console.log("disMatrix:");
console.log(disMatrix);
console.log("stepMatrix:");
console.log(stepMatrix);
var diff=[];
for(i=sourceArr.length,j=targetArr.length;i>0&&j>0;){
    var step=stepMatrix[i][j];
    console.log('=========================='+i+' '+j+':'+step);
    switch(step){
        case SAME:
            diff[j-1]=[i,SAME];
            i--;j--;
            break;
        case REPLACE:
            diff[j-1]=targetArr[j-1];
            i--;j--;
            break;
        case DELETE:
            diff[j-1]=DELETE;
            i--;
            break;
        case INSERT:
            diff[j-1]=targetArr[j-1];
            j--;
            break;

    }


}

console.log(diff);
var preItem,tempStr='',tempArr,reArr=[];
for(i=0;i<diff.length;i++){
    var item=diff[i];
    if(i==0){
        if(typeof(item)=='string'){
            tempStr=item;
        }
        else{
            tempArr=item;
            tempArr[1]=1;
        }
        //continue;
    }
    else{
        if(typeof(item)=='string'){
            tempStr=tempStr+item;
            if(typeof(preItem)=='object'){
                reArr.push(tempArr);
            }
        }
        else{

            if(typeof(preItem)=='string'){
                tempArr=item;
                tempArr[1]=tempArr[1]+1;
                reArr.push(tempStr);
                tempStr='';
            }
            else{
                if(preItem[0]==(item[0]-1)){
                    tempArr[1]=tempArr[1]+1;
                }
                else{
                    reArr.push(tempArr);
                    tempArr=item;
                    tempArr[1]=tempArr[1]+1;
                }
            }
        }
    }
    preItem=item;
}
if(typeof(preItem)=='string'){
    reArr.push(tempStr);
}
else{
    reArr.push(tempArr);
}
return reArr;
}
function mergeLcs(src,diff){
var strBuffer='';
for(var i=0;i<diff.length;i++){
    var item=diff[i];
    if(typeof(item)=='string'){
        strBuffer=strBuffer+item;
    }
    else{
        strBuffer=strBuffer+src.substr(item[0]-1,item[1]);
    }
}
return strBuffer;

}


var src="batyu";

var target="beauty";

console.log(src+" >> "+target);

var diffArray=lcsDiff(src,target);

console.log(diffArray);

var merStr=mergeLcs(src,diffArray);

console.log(merStr==target);

console.log(merStr);

© 著作权归作者所有

共有 人打赏支持
卢勇福

卢勇福

粉丝 39
博文 19
码字总数 22106
作品 9
海淀
高级程序员
腾讯移动前端框架 mt 2.0 发布

MT是手机腾讯网前端团队开发维护的一个专注于移动端的js模块管理框架。 Git:http://git.oschina.net/luyongfugx/mt mt介绍文档:http://mt.tencent.com/mt1index.html 为什么使用MT 无更新不...

oschina
2014/06/11
8.7K
21
手机腾讯网mt框架之mtwebapp示例解析。

手机腾讯网mt2.0框架发布有一段时间,但是经常有朋友问怎么用,其实项目里面是有一个基于jqmobi和ratchet的webapp示例的,这里我们就来分析一下。代码目录在:https://github.com/mtjs/mt/tr...

卢勇福
2014/11/12
0
10
手机腾讯网mt2.0增量更新算法优化小记

手机腾讯网[mt2.0][1]目前已经应用在线上案例,在使用的过程中,为了提高增量更新的效率,我们使用编辑距离算法来替代原来的chunk算法,在这个过程中碰到了一个性能问题,我们这里写一下优化方...

卢勇福
2014/08/13
0
9
手机腾讯网前端框架 MT 2.0.1 发布

手机腾讯网前端框架 MT 2.1.0 发布 ============= 主要更新 ------------------------ 1. 优化编辑距离算法性能,混合使用chunk,lcs两种算法提升性能,并保持增量更新字符级别的精度 2. 更新...

卢勇福
2014/07/28
6K
12
手机腾讯网前端框架 MT 2.2.2 版本发布

手机腾讯网前端框架MT 2.2.2 版本发布 主要更新: 使用偏移算法压缩编辑距离算法计算生成的增量文件,减少增量文件的体积大小。 示例如下: 首先下载mt(假设您已经有nodejs环境)项目,cd到...

卢勇福
2014/11/26
6.2K
17

没有更多内容

加载失败,请刷新页面

加载更多

好用的vue组件

http://elickzhao.github.io/2017/08/vue%E4%B8%80%E4%BA%9B%E7%89%B9%E5%88%AB%E6%9C%89%E7%94%A8%E7%9A%84%E6%8F%92%E4%BB%B6/...

Littlebox
27分钟前
2
0
linux 源码安装mysql8

1.安装依赖 yum -y install wget cmake gcc gcc-c++ ncurses ncurses-devel libaio-devel openssl openssl-devel   2.下载源码包 wget https://cdn.mysql.com//Downloads/MySQL-8.0/mysql-......

苏牧影子
27分钟前
1
0
BeanFactory和FactoryBean

BeanFactory BeanFactory是ioc容器的顶层接口,里面定义了一些容器基本的功能 类似ConfigurableBeanFatory和ApplicationContext就是比较高级的容器,除了基本的方法之外,还实现了很多高级的...

sendo
29分钟前
1
0
Java并发(9)- 从同步容器到并发容器

引言 容器是Java基础类库中使用频率最高的一部分,Java集合包中提供了大量的容器类来帮组我们简化开发,我前面的文章中对Java集合包中的关键容器进行过一个系列的分析,但这些集合类都是非线...

Ala6
33分钟前
3
0
Java定时器Timer学习之一

种类: 接通延时型定时器:接通延时型定时器是各种PLC(可编程控制器)中最常见最基本的定时器,这种定时器在Siemens的PLC中,成为SD型定时器 断开延时型定时器:这种定时器是当输入条件00000为ON时...

王怀楼
35分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部