网页版本对比系列四 ——业 务对比逻辑及行内对比

#技术 #算法

上三节,基本完成了对具体的对比算法的描述,而要很好的把算法应用得具体的业务场景,还需要一些 必需的逻辑规则及优化。

如在具体在应用上面的应用对比算法进行字串的对比时,不是简单的就将两串丢人算法入口就OK了, 还需要做一些加速措施及资源控制具体认为比较重要的有以下三点,不细说:

1.  优先求取公共前串与公共后串。
2.  进行简单的子串判定。
3.  进行计算时间,资源利用的控制。

以上的前两点主要是为了尽可能的缩短以diff算法进行计算的字串的长度,以提升性能及资源需求(实际证明提升效果非常显著,因 为采用的diff算法,是一个递归的求解子问题的过程),第三点是为了能够在计算复杂度太高时,还是能够给出一个粗糙的对比结果, 而不是无法给出结果。

下面具体说业务中,完成整个网页对比过程的流程,然后详细说明一些行内对比的细则。

###对比流程

为加速完成对比,实际的网页对比时是先进行段落的对比,再进行行内的的对比,因为在业务场景下,对比的两网页还是具有一定的相似度的。 段落对比开始时,采用了多级流程,这儿只说最后使用的简单的分段方法,即简单的以h2, h3, p, table, ul, ol 等标签对网页进行分段。 如下:

    $old_content = preg_replace('/<\/(h2|h3|p|table|ul|ol)>/', "$0\0", $old_content);
    $a = explode("\0", $old_content);
    $new_content = preg_replace('/<\/(h2|h3|p|table|ul|ol)>/', "$0\0", $new_content);
    $b = explode("\0", $new_content);

在进行上面的切分后,实现上段落间的对比就变成了两数组的对比(可以是切分后的两原串的对比,也可以是md5的处理后的串的对比,不过在业务中 由于各种原因,需要在段落的对比时进行一定程度的脱标签(即需要敏感的标签是要保留的)的对比,以尽可能小的减小标签对最后对比结果的影响。因此采用的是md5的串的对比,同时用md5 做了向原串内容的索引)。这样大体流程可概括为如下:

  • step 1 对输出的html内容进行切分
  • step 2 对切分后的数组进行md5编码,并建立md5码对原内容的索引
  • step 4 对段落对比的内容根据EQUAL, INSERT, DELETE不同对比码,进行不同的结果渲染。
  • step 5 对段落对比结果的REPLACE,进行行内对比
  • step 6 对行内对比结果进行渲染。

在完成段落间的对比后,最为重要的就是处理段内的对比,也及这儿称的行内对比。
###行内对比

对比的内容会根据段落对比的结果的提取出对应的原串的内容进行对比,原串是带全html标签的(即未进行脱标签处理的),因为在进行行内对比时需要尽可能多 的对比出变化的细节(包括格式变化细节),因此,在行内对比不可能做脱标签处理后进行对比的。但是这儿就出现的一个矛盾。就是,不脱标签对比,标签会对对比结果产生非常大的影响 导致对比结果出现非常大的偏差(因为由于历史原因,对比内容的html标签不是统一化的,有很多垃圾的标签夹在其中,但这些标签对于实际的显示效果也不会有影响 但是却是不能却除), 而脱标签对比也不能更多的对比出来行内差异的细节。

在经历了多种方法的尝试后,采取转换标签的处理:即对比对内容来说,不管标签具体是什么,就单单的将其当做一个分隔符,这样,标签在格式上的体现一定程度会得到保留(对于斜体,加粗,连接 这类的标签敏感标签已做特殊处理,不在这儿的说的标签转换范围内,这儿说的标签主要是span, tr, td, ul等对内容本身的表明呈现不那么重要的,它们主要用于分隔内容)并且多个连续的分隔符, 也将它当作一个分隔符进行处理,然后再以分隔符为基础对内容进行切分,然后以段落比较的形式对切分后数组进行比较,对对比那结果,同样分特征码进行不一样的处理,如下步骤示:

  • step 1 对内容按标签进行切分,如以正则/<[^>]+>/is对内容进行切分。
  • step 2 对切分后的两数组进行对比,对比前需要适当建立索引。
  • step 3 对INSERT,EQUAL, DELETE, REPLACE进行不同的处理,假设对于当前对比结果左右下一次的开始位置,即本次的结束位置 分别为eleft, eright, 本次的开始位置为bleft, bright, 则如下: * EQUAL: 分别获取左右两边的(eleft - bleft), (eright-bright)间的串,标记为相等,同时增加左右的bleft, bright (之所以不直接以算法计算结果的相等串标记为最后的相等内容,是因为中间还有一些标签在计算过程 中是被舍弃的,这儿需要进行还原)。 * INSERT: 分别取出insert的串,将其位置定位到原串中,假设为tpos,然后迭代的将tpos与上一次处理后重新 标记的开始位置间的串标记为EQUAL,而将对比结果的insert串,才真正标记为insert,是因为这些insert串间 可能会有一些标签,因此 需要将这些标签还原回来,所以只能将这些标签标记为相等。 * DELETE: 原理同INSERT * REPLACE: 这个逻辑较为复杂,下面详细讨论。
  • step 4 用最后生成的对比结果,替换对应的段落的对比。

下面看一下行内对比时按标签拆分后,对比中结果中REPLACE的处理。 这部分还需要进一步进行字符级的对比,主要的对比步骤如下示:

  • step 1 将左右两边的REPLACE数组,以”\1”, 重新组合成字符串。(之所以以”\1”, 组合是为了保持标签的分隔属性)
  • step 2 将组合后的字符串传入对比算法进行对比,得到字符级的一个对比结果,此时需要如上示对对比结果中的INSERT, EQUAL, DELETE, REPLACE同样分别进行处理。 * INSERT: 以”\1”, 进行分隔,分别在原串中找到insert串进行标记。 * DELETE: 同上 * EQUAL : 通常情况是,不进行任何处理,直接延长处理串,不过在前一个对比结果,与后一个对比结果 是插入或者删除时,且都是基于分隔符”\1”时,则需要特殊的处理逻辑,此时的相等串需要被 标记为替换串,及REPLACE串,因为在前后有插入或者删除分隔符时,通常情况表示,格式有变 化,这种情况特别是在表格中,表现最为突出。 * REPLACE: 这个处理结果实际上是同删除与插入逻辑的,只是在进行标记时,是将其标记为REPLACE。
  • step 3 同样替换上一级的对应的对比结果。

这其中当然还有很多的细节,不过大体流程是如上的。 另上面的对EQUAL判定前后的对比的情况是为了,处理下面这种情况,修改前如下示: edit 修改后: edit 这种修改实际上从内容上来说,是没有改变的,但是分隔位置却是不一致的。 一些其它的情况,慢慢补充。