接大招：查重算法实现（四）——js代码实现
接大招：查重算法实现（四）——js代码实现
先说重点，如果有人搜到这篇文章请注意在最后会放具体文件，节约时间的直接下载文件用。
首先别问我为什么跳过二跳过三。
第一是因为书面语言太麻烦，其次是因为这个模型部分结论的证明工作以及开发工作耗费了不少时间，现在直接贴代码。
在这段时间里我了解到了部分事实，在PHP中已经提供了现成的相似度计算函数similar_text()以及levenshtein(),这不免让我感到有些灰心。特别地，这个levenshtein()函数计算的是lenvenshtein距离,而所谓的lenvenshtein距离指的是由一个字符串转换到另一个字符串所需要的替换、删除、增加操作的最少次数，这与我的模型可以说是一模一样的，也就是说虽然我的想法不是创造性的但是它至少是走在正确的道路上的。
与已有函数的不同，我考虑过将替换操作加入到基础操作中，但是考虑到替换操作其实等价于一次删除操作和一次添加操作所以我并不太认同levenshtein把替换操作算进去这一做法。而我的基础操作中包括删除操作、移动操作和添加操作。在之后的二、三篇章中你们会了解到我会将删除操作的成本等于无穷小、一次添加操作的成本等于两次移动操作的成本。根据这些结论下面贴代码（js实现）。
rootTree.push([
{
itemNum:1,
selfId:0,
name:amongPoint,
point:sortStrArr2[0][amongPoint].point[0],
topClass:1,
father:false,
sublevel:[],
sublevelPoint:[],
addNode:function(addInfo){
//动作递归传递，这个是重点中的重点中的核心————递归调用，而且必须放在开头
for(var i = 0,son;son = this.sublevel[i++];){
rootTree[this.itemNum][son].addNode(addInfo);
}
//判断大小
for(var j = 0,addPoint;addPoint = addInfo['point'][j++];){
if(addPoint <= this.point) continue;
if(this.sublevelPoint.indexOf(addPoint) > -1) continue;//子级位置已存在的不添加
rootTree[this.itemNum].push({
itemNum:this.itemNum,
selfId:rootTree[this.itemNum].length,
name:addInfo['name'],
point:addPoint,
topClass:this.topClass + 1,
father:this.selfId,
sublevel:[],
sublevelPoint:[],
addNode:this.addNode
});
rootTree[0].nodeCount++;
this.sublevel.push(rootTree[this.itemNum].length - 1);
this.sublevelPoint.push(addPoint);
rootTree[0].maxDepth = (rootTree[0].maxDepth < this.topClass + 1)?this.topClass + 1:rootTree[0].maxDepth;
break;
}
}
}
]);
我知道这样贴代码看着肯定费劲，特别简书的编辑器对写代码特别不友好，以后会把相同的内容发送到知乎等平台。用语言描述一下上面这段代码干了什么吧：
我们在rootTree数组里插入了一个数组元素，使其成为二维数组，其中每一个数组元素就是一棵树，这个数组元素的每个子元素都是对象，每个对象都是树结构的节点；
这里的每颗树储存的都是一种A序列在B序列中的已有排序的情形，举栗子：A序列155235与B序列123456中，A序列在B序列中的排序情形包括比如1235、123、135、125、15...等等等等，其中1235是最大排序情形；
我们在节点对象中用属性信息描述属性之间的关系包括子级、父级、id、字符名、在目标序列的位置、子级元素的位置、以及一个添加函数；
关键的就是这个添加函数addNode，这个方法第一段是一个遍历递归，也就是父节点调用子节点的同名方法，然后子节点调用子节点的子节点同名方法...子子孙孙无穷尽也...这就是递归；
addNode的目的是遍历进行位置比较，而插入新节点。这个递归是根据A序列中的字符在B序列中的位置，把每一个A序列中的字符传递给已有树的所有节点，并与这个节点的位置进行比较，如果合适的便成为它的子节点。
通过递归操作获取深度最深的树的深度，这个深度就是最大排序情形。根据之后的二、三篇的分析，用AB序列交集的长度减去这个最大排序情形的长度就等于最少移动操作次数。
表达无力，关于代码实现先说到这里，下面是下载地址。由于是菜鸡一枚写得比较粗糙，这个算法在浏览器计算大字符串时会内存泄漏，将就着看看，欢迎批评。
