接大招：查重算法实现（二）——一致性模型

接大招：查重算法实现（二）——一致性模型

      接着上一章的分析，对于相似度模型的第一个较为简单的模型称为‘一致性模型’。

模型假设：

1.字符序列的操作对相似度有影响的只包括增加、删减、移动这三个操作；

2.相同操作的单位操作复杂度增量一致相同；

3.增加、删减、移动这三个操作单位操作的复杂度增量一致相同；

4.两序列的相似度与各自操作复杂度线性相关；

5.两序列的对应操作复杂度并不对称相等，它们对整体相似度的影响力各占一半；

6.每个序列的最小操作复杂度可以代表其操作复杂度。

模型解析：

        用C、D、M分别表示增加、删减、移动三操作，操作某元素x，可以表示为C(x)或D(x)或M(x)。再加上位置属性，C(x)[S]表示在S位置添加元素x，D(x)[S]表示删除S位置的元素x，很明显C(x)[S]与D(x)[S]互为逆操作即

公式 1

        M(x)[S,P]表示将元素x从位置S移动到位置P，其满足以下关系

公式 2

        现对某序列进行一系列操作，这操作称为操作系列A。序列m经过操作操作系列变为序列n，数学表达式为A(m) = n。我们再对序列n进行操作，我们容易知道将操作系列A中的操作按相反的操作顺序并对每个操作取逆按照公式1、2可将

        ...没写完，先发了