文档章节

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

卢勇福
 卢勇福
发布于 2014/06/17 16:31
字数 1584
阅读 683
收藏 15
点赞 0
评论 0

<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发布

MT2.0新增特性 本地存储异常回调 统计回调 combo支持 新增LCS增量算法,将更新粒度精确到字符 什么是MT MT是手机腾讯网前端团队开发维护的一个专注于移动端的js模块管理框架。 github:https:/...

卢勇福 ⋅ 2014/05/30 ⋅ 4

手机腾讯网mt框架之mtwebapp示例解析。

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

卢勇福 ⋅ 2014/11/12 ⋅ 10

腾讯移动前端框架 mt 2.0 发布

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

oschina ⋅ 2014/06/11 ⋅ 21

手机腾讯网mt2.0增量更新算法优化小记

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

卢勇福 ⋅ 2014/08/13 ⋅ 9

手机腾讯网前端框架 MT 2.0.1 发布

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

卢勇福 ⋅ 2014/07/28 ⋅ 12

手机腾讯网前端框架 MT 2.2.2 版本发布

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

卢勇福 ⋅ 2014/11/26 ⋅ 17

编辑距离求解算法分析

编辑距离是一种衡量两个相似字符串相似性的度量方法。距离越大相似度越小。具体地,两个字符串的编辑距离是其中一个字符串要变换为另一个字符串所需要的最小编辑次数。其中编辑操作包含3种:...

dugangabc ⋅ 2016/02/19 ⋅ 0

使用 Levenshtein 寻找彼此相似的字符串对

我们爬来了一些数据,接下来以豆瓣畅销书为例。 爬虫爬来的数据有 而我们系统中原有的数据有 做前端的同志可能一眼就看出来了,两个数组中有三个元素是因为全半角的缘故,是不能全词匹配的,...

xh4n3 ⋅ 2015/08/18 ⋅ 0

从源代码剖析Mahout推荐引擎

从源代码剖析Mahout推荐引擎 Hadoop家族系列文章, 主要介绍Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Zookeeper, Avro, Ambari, Chukwa,新增加的项目包括,...

片刻 ⋅ 2014/06/19 ⋅ 0

机器学习模型

机器学习模型 M. Tim Jones 2018 年 1 月 17 日发布 机器学习中使用的算法大体分为 3 类:监督学习、无监督学习和强化学习。监督学习提供了反馈来表明预测正确与否,而无监督学习没有响应:算...

M. Tim Jones ⋅ 01/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

骰子游戏代码开源地址

因为阿里云现在服务器已经停用了,所以上面的配置已经失效。 服务端开源地址:https://gitee.com/goalya/chat4.git 客户端开源地址:https://gitee.com/goalya/client4.git 具体运行界面请参考...

算法之名 ⋅ 39分钟前 ⋅ 0

设计模式--装饰者模式

装饰者模式 定义 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比生成子类更为灵活。 通用类图 意图 动态地给一个对象添加一些额外的职责。就增加功能来说,装饰模式相比...

gaob2001 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(八)JavaScript的数组

JavaScript零基础入门——(八)JavaScript的数组 欢迎大家回到我们的JavaScript零基础入门,上一节课我们讲了有关JavaScript正则表达式的相关知识点,便于大家更好的对字符串进行处理。这一...

JandenMa ⋅ 今天 ⋅ 0

sbt网络问题解决方案

转自:http://dblab.xmu.edu.cn/blog/maven-network-problem/ cd ~/.sbt/launchers/0.13.9unzip -q ./sbt-launch.jar 修改 vi sbt/sbt.boot.properties 增加一个oschina库地址: [reposit......

狐狸老侠 ⋅ 今天 ⋅ 0

大数据,必须掌握的10项顶级安全技术

我们看到越来越多的数据泄漏事故、勒索软件和其他类型的网络攻击,这使得安全成为一个热门话题。 去年,企业IT面临的威胁仍然处于非常高的水平,每天都会看到媒体报道大量数据泄漏事故和攻击...

p柯西 ⋅ 今天 ⋅ 0

Linux下安装配置Hadoop2.7.6

前提 安装jdk 下载 wget http://mirrors.hust.edu.cn/apache/hadoop/common/hadoop-2.7.6/hadoop-2.7.6.tar.gz 解压 配置 vim /etc/profile # 配置java环境变量 export JAVA_HOME=/opt/jdk1......

晨猫 ⋅ 今天 ⋅ 0

crontab工具介绍

crontab crontab 是一个用于设置周期性被执行的任务工具。 周期性执行的任务列表称为Cron Table crontab(选项)(参数) -e:编辑该用户的计时器设置; -l:列出该用户的计时器设置; -r:删除该...

Linux学习笔记 ⋅ 今天 ⋅ 0

深入Java多线程——Java内存模型深入(2)

5. final域的内存语义 5.1 final域的重排序规则 1.对于final域,编译器和处理器要遵守两个重排序规则: (1)在构造函数内对一个final域的写入,与随后把这个被构造对象的引用赋值给一个引用...

江左煤郎 ⋅ 今天 ⋅ 0

面试-正向代理和反向代理

面试-正向代理和反向代理 Nginx 是一个高性能的反向代理服务器,但同时也支持正向代理方式的配置。

秋日芒草 ⋅ 今天 ⋅ 0

Spring 依赖注入(DI)

1、Setter方法注入: 通过设置方法注入依赖。这种方法既简单又常用。 类中定义set()方法: public class HelloWorldOutput{ HelloWorld helloWorld; public void setHelloWorld...

霍淇滨 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部