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

手机腾讯网mt2.0（http://mt.tencent.com）终于发布了，这个版本的增量更新算法基于编辑距离计算，做到了字符级别的增量更新，比之前的chunk算法更加精确，减少了chunk算法带来的一些冗余字符的下载，下面我们就来看看mt是如何利用这个算法来实现增量更新的.**(广告:我们的github:https://github.com/mtjs/mt ,如果觉得不错请给我们star)**

首先我们来看看什么是Levenshtein Distance (编辑距离)，编辑距离即从一个字符串变换到另一个字符串所需要的最少变化操作步骤，是俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

那如何计算编辑距离呢。通常我们修改一个字符串为另外一个字符串的时候有集中方法，删除，替换，插入，其他的字符就是不变了，按照编辑代价算，删除，替换，插入这几种操纵的代价是1，即修改一个字符，不变则是0，表示没有修改，即操作代价是0. 首先定义这样一个函数——edit(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。

通过动态规划法（dp）,我们很容易得到以下公司：

· if i == 0 且 j == 0，edit(i, j) = 0

· if i == 0 且 j > 0，edit(i, j) = j

· if i > 0 且j == 0，edit(i, j) = i

· if i ≥ 1  且 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

· 我们可以用一个矩阵来纪录这一个过程，以以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得修改代价最小得步骤是

0-3-0-3-0-0-2

即，第一位不变，第二位插入一个字符，从beauty里取第二个字符’2’,第三位不变，第四位取第四个字符’u’,第四第五位不变，那我们用一个数组这个操作：

[ [ 1, 0 ], 'e', [ 2, 0 ], 'u', [ 3, 0 ], [ 4, 0 ] ]，其中数组表示不变，字符表示插入或者替换。

我们进一步压缩有顺序得数组得到： 
[ [ 1, 1 ], 'e', [ 2, 1 ], 'u', [ 3, 2 ] ]

其中得数组表示，从第几个字符开始n个字符不变，这就是传说中得增量文件。

通过这个增量文件数组和源字符串batyu我们很容易得到新字符串：

beauty＝”batyu”.substr(1-1,1)+’e’+”batyu”.substr(2-1,1)+’u’+”batyu”.substr(3-1,2);

这就是我们mt2.0得增量更新算法，啥也不说了，我们上代码：

view source

 

print?

001	function lcsDiff(source,target){

002	var SAME= 0,REPLACE= 1,DELETE= 2,INSERT=3;

003	var sourceArr=source.split('');

004	//var sLength=sourceArr.length;

005	var targetArr=target.split('');

006	//var tLength=targetArr.length;

007

//编辑距离矩阵

008	var disMatrix=[];

009

//步骤矩阵

010	var stepMatrix=[];

011	//生成一个空矩阵，二维数组

012	for(var i=0;i<=sourceArr.length;i++){

013	disMatrix[i]=[];

014	stepMatrix[i]=[];

015	for(var j=0;j<=targetArr.length;j++){

016	disMatrix[i][j]=0;

017	stepMatrix[i][j]=0;

018

}

019

}

020

021	console.log(disMatrix);

022	console.log(stepMatrix);

023	for(var i=0;i<=sourceArr.length;i++){

024	for(var j=0;j<=targetArr.length;j++){

025	// console.log(i+" "+j);

026	//在第0步，由于都是空，所以是0

027	if(i==0&&j==0){

028	disMatrix[i][j]=0;

029	stepMatrix[i][j]=SAME;

030

}

031	else if(i==0&&j>0){

032	disMatrix[i][j]=j;

033	stepMatrix[i][j]=INSERT;

034

}

035	else if(j==0&&i>0){

036	disMatrix[i][j]=i;

037	stepMatrix[i][j]=DELETE;

038

}

039	else if(i>0&&j>0){

040	var sameStep=(sourceArr[i-1]===targetArr[j-1]),

041	delStep=disMatrix[i-1][j]+1,

042	insertStep=disMatrix[i][j-1]+1,

043	replaceStep=disMatrix[i-1][j-1]+(sameStep?0:1);

044	//console.log(i+' '+j+":"+replaceStep+' '+delStep+' '+insertStep+" v:"+sourceArr[i-1]+' '+targetArr[j-1]);

045	//console.log(i+' '+j+":"+replaceStep+' '+delStep+' '+insertStep);

046	disMatrix[i][j]=Math.min(replaceStep,delStep,insertStep);

047	var stepAct=disMatrix[i][j];

048	switch(stepAct){

049	case replaceStep:

050	stepMatrix[i][j]=sameStep?SAME:REPLACE;

051

break;

052	case insertStep:

053	stepMatrix[i][j]=INSERT;

054

break;

055	case delStep:

056	stepMatrix[i][j]=DELETE;

057

break;

058

}

059	// console.log(i+' '+j+":"+replaceStep+' '+delStep+' '+insertStep+' act :'+stepMatrix[i][j]);

060

}

061

}

062

}

063	console.log("disMatrix:");

064	console.log(disMatrix);

065	console.log("stepMatrix:");

066	console.log(stepMatrix);

067	var diff=[];

068	for(i=sourceArr.length,j=targetArr.length;i>0&&j>0;){

069	var step=stepMatrix[i][j];

070	console.log('=========================='+i+' '+j+':'+step);

071	switch(step){

072	case SAME:

073	diff[j-1]=[i,SAME];

074

i--;j--;

075

break;

076	case REPLACE:

077	diff[j-1]=targetArr[j-1];

078

i--;j--;

079

break;

080	case DELETE:

081	diff[j-1]=DELETE;

082

i--;

083

break;

084	case INSERT:

085	diff[j-1]=targetArr[j-1];

086

j--;

087

break;

088

089

}

090

091

092

}

093

094	console.log(diff);

095	var preItem,tempStr='',tempArr,reArr=[];

096	for(i=0;i<diff.length;i++){

097	var item=diff[i];

098

if(i==0){

099	if(typeof(item)=='string'){

100	tempStr=item;

101

}

102

else{

103	tempArr=item;

104	tempArr[1]=1;

105

}

106	//continue;

107

}

108

else{

109	if(typeof(item)=='string'){

110	tempStr=tempStr+item;

111	if(typeof(preItem)=='object'){

112	reArr.push(tempArr);

113

}

114

}

115

else{

116

117	if(typeof(preItem)=='string'){

118	tempArr=item;

119	tempArr[1]=tempArr[1]+1;

120	reArr.push(tempStr);

121	tempStr='';

122

}

123

else{

124	if(preItem[0]==(item[0]-1)){

125	tempArr[1]=tempArr[1]+1;

126

}

127

else{

128	reArr.push(tempArr);

129	tempArr=item;

130	tempArr[1]=tempArr[1]+1;

131

}

132

}

133

}

134

}

135	preItem=item;

136

}

137	if(typeof(preItem)=='string'){

138	reArr.push(tempStr);

139

}

140

else{

141	reArr.push(tempArr);

142

}

143	return reArr;

144

}

145	function mergeLcs(src,diff){

146	var strBuffer='';

147	for(var i=0;i<diff.length;i++){

148	var item=diff[i];

149	if(typeof(item)=='string'){

150	strBuffer=strBuffer+item;

151

}

152

else{

153	strBuffer=strBuffer+src.substr(item[0]-1,item[1]);

154

}

155

}

156	return strBuffer;

157

158

}

159

160

161	var src="batyu";

162

163	var target="beauty";

164

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

166

167	var diffArray=lcsDiff(src,target);

168

169	console.log(diffArray);

170

171	var merStr=mergeLcs(src,diffArray);

172

173	console.log(merStr==target);

174

175	console.log(merStr);