这几天接了大佬的一道题，计算两个数组的相似度，菜鸡如我思来想去终于有点眉目了。首先对于相似度是一个非常具有主观性的东西，“相似”应基于什么标准。 我没有大费周章地去查资料，只问了度娘什么是相似度，度娘的百科告诉我我猜对了——这就是一个非常主观的东西，很多算法也都是基于一定程度的主观定义而出发的。 我从简到繁地来分析一下，假设字符串序列A和字符串序列B我们说它们‘有点像’，我们说的像应该指什么。朴素地来说比如说它们有共同的字、它们之间某段顺序相同这两点是最常见的‘相似性’判断，更深晦地比如说它们都遵从某种规律。 用几种场景来说明。首先比如比较两个人的简历，简历上我们只比较学历、工作经验、个人信息是否相同而不在乎这几项的排列顺序是否也对应相同；又比如说比较两个同学的英语试卷来判断有没有抄袭的迹象。英语试卷大部分都是选择题，而对于ABCD答案的排列顺序就尤其重要；又比如是毕业论文查重，查重软件会把你的论文跟收集的论文库里的范本进行比较，而比较的重点就在于字符的重复性和排列性等。 更艰深的比如判断歌曲作品之间的抄袭，但我们现在讨论的相似性只讨论字符串序列之间的重复和排列层次的相似，至于‘共同规律’不做探究，虽然对于曲谱这类字符序列其规律性非常重要，但本人能力尚不足，先从较为简单的出发。 我们通常描述一个事物跟另一个事物相似，会通过“只要这样这样再这样它两就一模一样了”，用更书面的说法就是‘让A序列经过一系列操作与B相同’，那么这个‘操作’越复杂A就越不像B，越简单A就越像B。 我们好像摸到了门道，但是相对应的还有‘B序列经过一系列操作与A相同’的操作，谁也没说过A像B那B就对称地一定像A，或者更准确地说A像B的度是否严格等于B像A的度。这是一个重要的问题。 生活中，如果我们描述一对父子很相像，有没有这种‘儿子像老爸比老爸像儿子更像’的说法？这种说法我们可能会觉得比较奇怪，我们可以接受相爱的两个人说的‘我爱你比你爱我爱得更深’，但是‘爱’替换成‘像’就...... 如果拿整体跟自身局部进行比较可能就更直观一点，比如一张世界地图跟一张中国地图作比较。中国地图像世界地图，但是还有更多的地方它是不像的，中国地图需要把除中国以外的所有国国家都绘制完才跟世界地图一样。反观世界地图，它不需要做重新绘制这种麻烦操作，只需要遮住其它地方就跟中国地图一样。请注意这里我是认为‘遮住’的操作比‘绘制’的操作更简单，因为我认为的是‘存在性是第一原则’。比如拿亚洲地图跟欧洲地图比较，我们可以认为他们相似度为0，因为它们完全没有交集，也就是重复存在性是完全没有。 根据以上分析，我们拿操作简单度（或操作复杂度）来描述相似度。‘这个孩子只要鼻子再大点就跟他老爸一模一样了’、‘这幅画只要修改这部分就跟那幅画一模一样了’，我们用这样增加、删除、移动等操作来描述字符序列之间的操作简单度也就是相似性。 我们如何去定义操作简单度？现在我们只考虑增加字符、删减字符和移动字符这三种操作，每多一种操作其复杂度就增加一些。那么每种操作增加的复杂度是一样的吗？这个谁都没有说过。首先我们必须建立一个原子假设，假设同种操作增加的复杂度是一样的（这个基本假设很重要，它的合理性仅仅在于我们的直观感受）。如果不同种操作之间单位操作的复杂度增量是相同的，对于这种假设我称为一致性模型或者简单模型，如果认为不相同则称为区分性模型。下一篇将进行一致性模型的分析和描述。
切尔西爱吃鱼
