基于网络爬虫和改进的LCS算法的网站更新监测

周孝锞 郭克华，2

1(中南大学信息科学与工程学院 湖南 长沙 410000)

基于网络爬虫和改进的LCS算法的网站更新监测

周孝锞1郭克华1，2

1(中南大学信息科学与工程学院 湖南 长沙 410000)

2(高维信息智能感知与系统教育部重点实验室 江苏 南京 210094)

互联网时代，信息爆炸式增长，用户需要方便及时地获取自己所需的信息。传统的搜索引擎和以RSS为代表的订阅具有一些缺陷，难以满足用户高质量需求。在此基础上，利用网络爬虫和文本对比，提出一种新型网站更新监测与订阅的通用方法。该方法将先后抓取的网页内容分析处理后，进行文本对比，检测更新内容，将结果以结构化形式返回给用户查看。实验表明，该方法解决了RSS订阅受订阅源限制的缺点，实现了用户添加任意网站，在高校、企业、新闻、电影、博客、论坛等网站的监测方面具有较好的效果。

网络爬虫 网页去噪 网站订阅 文本对比 更新监测

0 引 言

随着互联网的迅猛发展，社会进入全面信息时代，网站数据不断增多，截至2011年底，中国网民规模达到4.85亿，位居世界首位，网页数量达到600亿以上[1]。这些网页都处在不断的变化更新中，近乎40%的网页一周内会更新，而以.com为域名的网页则有23%每天都在变化[2]。因此，从浩瀚信息海洋中获取最需、最新内容，成为研究热点。搜索引擎和RSS订阅的发明，在一定程度上解决了获取信息的难题，但二者的弊端也随着用户需求的扩大而愈加凸显：搜索引擎需要手动输入，准确度不够；RSS订阅则由于订阅源的限制，而影响了其订阅范围[3]。因此，面向任意网站的通用订阅方法及相关技术应运而生。

RSS订阅在本世纪初被广泛关注，不仅在新闻、博客、论坛等网站得到实施，也有在化学[4]、开源项目[5]、管理系统等领域得到应用，产生了多种试图给任意网站产生RSS Feed的系统和网站。如日本的Nanno等[6]开发的系统，在分析HTML文档特征的基础上实现为含有时间序列项的网站自动生成RSS Feed。不过，该系统所分析的网站必须要有日期描述，由时间序列项构成。此外，业界其他网站提供了生成RSS Feed的功能，如page2rss.com/、feed43.com、feedity.com、feedyes.com、www.ponyfish.com 等，但它们都有各自的局限和缺点：page2rsss解析的目标网站内容不能太多，有些网站难以得到更新内容，即使生成了RSS 种子，格式也不适用于大部分RSS 阅读器；feed43仅能满足大部分一般布局的网站；feedity和feedyes收费；ponyfish已经关闭服务。可实现大规模网站订阅的Google Reader，也随着2013年7月1日Google Reader的关闭而不复存在。

为解决以上问题，人们从爬虫入手，试图利用网站更新检测的技术，获取网站最新内容，并推送给相关用户(订阅用户)。文献[7]试图优化RSS阅读器的信息重复和面向用户个性化不足等缺陷；文献[8]利用网络爬虫和TF-IDF算法对抓取的网页分类，得到高校网站中某一类别的信息，再以RSS订阅的形式推送给用户，它的局限性在于只是针对某个类别的信息获取，未能推广到各类网站的全面内容更新监测及推送。市场上的许多RSS订阅的替代品，如国内的鲜果、抓虾、今日头条以及国外的ZAKER等。这些产品利用网络爬虫抓取目标网页的内容，如果整合起来，供用户订阅，就比较方便，但是这些产品的一个共同缺点，即用户无法自主添加订阅网站。

本文为解决以上问题，找到一个通用的网站订阅方案，提出了一个基于网络爬虫、网页去噪和文本对比，用户可自主添加订阅的网站更新监测和订阅系统。主要采取去除所有网页标签和链接，提取所有文本值作为字符串对比输入的方案。该方法解决了RSS订阅受订阅源限制的缺点，实现了用户任意添加网站，在高校、企业、新闻、电影、博客、论坛等网站的监测方面具有较好的效果。

1 系统框架与关键技术

1.1 系统框架

本系统设计有3个模块，分别为订阅模块、更新模块和查看模块。订阅模块是处理用户添加的订阅网站，流程图如图1所示。爬虫访问用户添加的网址，获取网页内容，存入数据库；同时根据需要与否从中提取二级超链接(即页面上的超链接，这由用户选择的更新深度决定)，若需要，再访问二级超链接获取网页内容，存入数据库；同样根据需要与否提取其中的三级超链接，访问三级超链接获取网页内容，只需存入数据库，不用再提取超链接。因为系统设置的可选更新深度最大是3，便于订阅目录型网站[9]。

图1 订阅模块流程图

更新模块是整个系统的核心，流程图如图2所示。该模块独立于系统，后台运行，不受用户干预。为有效地利用资源，及时获得更新，采用一种新型增量式更新算法用于设置更新时间。通过爬虫获取网页内容，经网页去噪后提取每个超链接的文本值，构成新旧字符串数组进行对比，得到新增或修改过的超链接，即网站的Item(通知、新闻、讲座、视频、音乐、帖子等，统称Item)。经过文本对比，若发现两次爬取的页面内容有改变，则提取变化的Item，存入数据库，并更新数据库中存储的页面内容，供下次对比使用；若无改变，只需更新数据库中存储的页面内容。由于文本值以标题为主，重复概率很低，文本值具备唯一性和不变性，所以选择Item的文本值作为对比。

图2 更新模块流程图

查看模块是从数据库中提取所需数据，结构化显示在网页上，便于用户查看，是系统的主要界面。

由于网页内容的杂乱性、动态性、页面结构差异性，经过文本对比，得到最新Item存入数据库后，其实并非都是网站最新的、用户需要查看的Item。本文使用选择性提取数据，提高更新准确性。从数据库表中读取本次更新获得的记录时，跟上次更新获得的记录进行对比，过滤那些在上次更新中也出现过的重复记录。

通过选择性提取数据，把精简、准确的最新Item结构化显示在页面上，供用户查看。一般而言，Item包含标题、链接、发布日期(若没有，则用更新日期替代)，用户点击标题即可链接到Item所在原网站的详细页面，类似RSS订阅器。

1.2 爬虫访问被拒问题

由于系统需要频繁地访问众多网址，难免会出现各种网络错误，比如不断重新连接服务器、服务器拒绝访问、访问频率过高连接崩溃等。对此问题，本系统首先完善访问机制，设置合适最大链接数、重连次数等参数，确保一些低级问题不会发生；其次，合理访问网址，不暴力地持续访问，避免服务器采取阻止爬虫的各类措施；可以通过设置合理的更新周期、多线程的机制和分布式爬虫加以实现；在本机上做出的系统demo，运用了增量式更新和多线程爬取，实现了前两点。

为节省系统的资源，提高爬虫效率，本文采取增量式爬取算法来设置更新周期。增量式爬取算法可以简单地分为三种[8]：(1) 定期地从URL列表中，按先后顺序进行访问；(2) 把网页根据其更新速度简单分为更新快的一类和更新慢的一类，分别设置较短和较长的更新周期；(3) 对URL列表中每个URL所指页面的更新速度进行预测，根据这个预测时间来爬取网页，尽可能满足各种网页的更新频率，最大效率地利用系统资源。本系统采用第三种增量式爬取算法，其中的更新预测算法采用文献[8]中改进的算法。该算法简单描述为：用一个参数A记录“上次监测到更新所用时间”，另一个参数C记录“上次更新至今有多久”，从队列中取出“预测更新时间”已到的网页进行访问，若有更新，说明实际更新时间小于或等于A，根据实践经验，设置为A的80%；若无更新，说明预测的更新时间太小，将预测更新时间变为其本身加上A的一半。算法流程如图3所示。

图3 增量式更新，预测更新时间算法流程图

其中A表示更新参数，记录上一次共用多久监测到更新；B表示预计下次过多久更新，即系统需要的预测更新时间；C表示累计未更新时间，即上次更新后到现在为止这段时间，如果更新了就清零，初始值赋为0。

1.3 过滤不合适链接

为了多层次监测网站的更新，需要提取某些网站(由用户自己选择)的首页及二级页面上的超链接，由于有些页面结构杂乱、链接众多，有许多非法、无用的不适用链接需要过滤掉，如友情链接、相关导航等。首先，友情和导航链接基本是绝对链接，而页面上正常的用户需要的链接是相对链接，对其进行初步过滤；其次，对于一个链接，可尝试访问，并提取它所指页面的超链接个数，如果超链接个数较多，超过某阈值，则判断为不合用链接而过滤掉，形成二次过滤。另外，一个较大网站难免会有一些相同Item和一些相互指向的链接，对此，把所有链接存入HashMap里面，过滤掉重复值。

1.4 文本对比算法

本系统采用改进的LCS(Longest Common Sequence)算法[10]进行文本对比，LCS指两个字符串的最长公共子序列(不要求连续出现，只要出现顺序一致)。计算LCS(A,B)的方法很多，运用动态规划思想的Needleman-Wunsch算法[11]是较早较基础的，它最早在1970年由Needleman和Wunsch二人提出，用于生物信息学领域的蛋白质序列对比，后来发展为全局最优匹配(Optimal Global Alignment)的常用手段。

算法1 假设待比较的字符串A和B，长度分别是m、n，Needleman-Wunsch算法求两个字符串的LCS分为四步：

Step1 初始化矩阵。构建一个(m+1)×(n+1)的空矩阵F。

Step2 选择计分系统。字符串匹配时每对字符存在三种情况：

(1) 匹配(Math)：两个字符相同；

(2) 不匹配(Mismatch)：两个字符不同；

(3) 缺口(Gap)：一个字符跟缺口相对。

计分系统就是对上述三种情形赋值，赋值规则不同，计分系统就不同。Needleman和Wunsch采取最简单的方式，设定Math计1分，Mismatch计-1分，Gap计-1分。

Step3 填充矩阵。根据计分系统填充矩阵。主要的规则由式(1)决定：

F(i,j)= Max(F(i-1,j-1)+S(Ai,Bj),F(i,j-1)+d,

F(i-1,j)+d) (1≤i≤m,1≤j≤n)

(1)

Step4 回溯路径。根据Step3中的计算，用箭头表示F(i,j)(1≤i≤m,1≤j≤n)的来源，即上单元、左单元和左上角单元。然后根据箭头从矩阵的最右下角一个单元开始，回溯得到最长公共子序列的路径。

实际上，每个单元格的得分表示该单元格的列所代表的字符变为该单元格的行所代表的字符的难易程度，换言之，分数代表字符之间的编辑距离。算法1采用Math=1，Mismatch=-1，Gap=-1的计分系统，得分越高，编辑距离越小，所以式(1)中F(i,j)选取三个方向的最大值。于是计分完成之后，根据得分来源从右下角单元格开始回溯得到路径，是得分最高的路径，也是编辑距离最小的路径，即我们需要的最长公共子序列。这是算法1的核心思想。

由于矩阵是(m+1)×(n+1)，计算每个单元的值在常数时间内完成，整个过程中需要存储每个单元格的值，算法1的时间和空间复杂度都为O(mn)。

然而，该时间和空间复杂度跟被比较的两个字符串长度乘积成正比，当比较的字符串长度很大时，耗费的时间和空间巨大。不少学者对LCS算法进行了改进。已经证明，LCS问题算法的时间复杂度不可能小于O(mlogn)[12],目前几种比较有效的是Hirschberg[13]提出的时间复杂度为O(tn),Nakatsu[10]提出的时间复杂度为O(n(m-t))，以及李欣等人改进的快速算法[14]，时间复杂度为O(t(m-t))，其中m、n、t分别为字符串A的长度、字符串B的长度，二者的LCS长度。

本文采用的算法：Nakatsu提出的时间复杂度为O(n(m-t))，这里称之为算法2。

算法2Nakatsu提出的快速LCS算法，基于下面几个基本定理[14]：

字符串A=A[1]A[2]…A[m]和字符串B=B[1]B[2]…B[n]，A(1:i)表示A的连续子序列A[1]A[2]…A[i]，同样B(1:j)表示B的连续子序列B[1]B[2]…B[j]。Li(k)表示所有与字符串A(1：i)有长度为k的LCS的字符串B(1：j)中j的最小值。公式化表示就是Li(k)=Minj(LCS(A(1:i),B(1:j))=k)。

定理1 ∀i∈[1,m]，有Li(1)

定理2 ∀i∈[1,m-1],(t∈[1,m])，有Li+1(k)

定理3 ∀i∈[1,m-1],(t∈[1,m-1])，有Li(k)

以上三个定理都不考虑Li(k)无定义的情况。

定理4Li+1(k)如果存在，那么它的取值必为：

Li+1(k)=Min(j,Li(k))

这里j是满足以下条件的最小整数：A[i+1]=B[j]且j>Li(k-1)。

以上定理的证明请参阅文献[10，13]。定理4递推得到Li(k)。利用此递推关系构建矩阵如图4所示。

图4 求解LCS的矩阵L(p,m)

以上矩阵中的元素L(k,i)=Li(k)，这里(1

设t=Maxk(L(k,m)≠null)，容易证明L矩阵中L(t,m)所在对角线L(1,m-t+1)L(2,m-t+2)…L(t-1,m-1)L(t,m)所对应的子序列B[L(1，m-t+l)]B[L(2，m-t+2)]…B[L(t，m)]即为A和B的LCS(也可能存在特殊情况，对角线所对应的子字符串并非完全是LCS，后文会讨论)，t为该LCS的长度。于是，LCS问题的求解就转化为对Lm(k)矩阵的求解。

举例说明：给定字符串A和B，A=bcdabab，B=cbacbaaba，(m=|A|=7，n=|B|=9)，根据定理4给的推理公式，L矩阵如图5所示。

图5 Nakatsu的快速LCS算法举例

如图5所示，A和B的LCS为B[1][3][5][6][8]=cabab，LCS的长度t=5。

矩阵第一行元素L(1,i)可用L(1,i) =Minj([A]=B[j])得到，其余行元素用定理4递推而出。然而实际上并不需要这么做，无需计算矩阵中每个元素的值，只需按对角线顺序计算L矩阵。先求第一条对角线上的元素L(1,1)L(2,2)…，直至L(i,i)=null,i≤m为止；再求第二条对角线L(1,2)L(2,3)…L(i,i+1)=null,i

算法2的时间复杂度曲线是一条随t增大而减小的直线，如图6所示。可以看出，当t接近m时，它的时间复杂度非常低。算法2适合比较两个文本文件，能够把一行文本作为一个比较单位，从而大大加快计算速度，提升效率。本文正好需要比较两段长文本，二者相异部分很小，LCS长度接近被比较的字符串长度，非常适合采用算法2。

图6 算法2的性能

1.5 文本对比算法改进

本文在利用算法2的基础上，进行如下改进：

算法2的目的在于找出一个LCS(不是所有)，降低计算LCS的时间与空间复杂度，而本文需要找出所有的LCS，排除不符合的LCS，提取变化的内容，保证更新的准确性。

在图5的例子中除了B[1][3][5][6][8]=cabab这个明显的LCS外，还存在其他LCS，如B[2][4][6][8][9]=bcaba等。根据算法2：计算从第一条对角线开始，直到对角线L(1,s)L(2,s+1)…L(u,m)，且L(u,m)≠null为止。这时L(1,s)所在的对角线是最明显直接的一个LCS；在计算的过程中，运用了定理4：Li+1(k)=Min(j,Li(k))，这里j是满足以下条件的最小整数：A[i+1]=B[j]且j>Li(k-1)，如果不存在这样的j满足A[i+1]=B[j]且j>Li(k-1)，那么Li+1(k)=Li(k)，将这样的Li+1(k)标记圆圈以示区别。实际上，该Li+1(k)对应的B[b](b=Li+1(k))是不可能成为LCS一部分，因为B中不存在A[i+l]字符，Li+1(k)的值是由Li(k)替代的，它是个虚假的匹配点，可称之为虚点。如图7所示，路径Ⅰ、Ⅱ、Ⅲ、Ⅲ所在的单元构成四个真实的LCS。

图7 存在多个LCS

因此图5中箭头所在的对角线只能表明LCS的长度为5，而真的LCS是箭头Ⅰ所对应的子字符串B[1][3][5][6][8]=cabab，这就是前文提到的特殊情况。箭头Ⅱ、Ⅲ、Ⅲ也都是LCS，分别对应B[2][3][5][6][8]=babab、B[2][4][5][6][8]=bcbab和B[2][4][6][8][9]=bcaba，四个LCS的匹配情形如图8所示。

图8 四种匹配情形

总结可以发现，所有的LCS是以最后一条对角线(称之为基准线)为基础扩展而来，它只可能位于基准线的左下方，并且遵循如下规则：

(1) 对于L(1,s)(s≤m-t+1)所在的每条对角线，若所包含的不为null的元素个数等于LCS长度t，转(2)；

(2) 对于对角线上元素L(k,i)(k>1,i>1)，若L(k-1,i-1)不为null和虚点，且L(k-1,i-1)

利用上述规则很容易得到所有的LCS，但不同的LCS对应着明显不同的匹配情形，这对于网站更新系统而言，意味着变化的Item不同。而一个网站实际的更新变化只有一种，所以只有一个匹配情形符合网站的真实更新情况，需要排除其余的匹配。

利用算法，获得两个字符串的LCS后，根据匹配情形即可得知差异部分，对应本文网站更新系统的字符串数组匹配，就是变化的字符串。比如图8中，匹配IV的B字符串的B[1]=c、B[3]=a是插入部分，B[5]=b就是修改部分，A[7]=b是被删除的。由于网站新闻标题具有独特性和功能性，标题相同而内容不同的情况是极少的；换言之，经过文本对比匹配之后，得到的插入部分，在被比较网页(称之为旧网页)中是不存在的(跟字符串匹配不同：插入的字符也可能存在被匹配字符串中)。所以，本文采用字符串数组对比，当遇到多个LCS时，只需验证每种匹配情形下插入部分的字符串是否存在被比较的字符串数组中，即可判断该匹配情形是否符合真实情况；若存在，则不是真实情况，排除。

本文利用网络爬虫和文本对比实现网站更新监测与订阅。首先将爬虫获取的新旧HTML内容利用MD5算法判别是否不同；其次，若有不同，将新旧HTML内容进行网页去噪，再进行文本对比。采用Nakatsu等人的LCS算法[10]进行文本对比，并考虑多个LCS存在的情况，进行了改进。

网页去噪的含义广泛，主要指去除与应用目的不相符的干扰因素，毛先领等人[15]对众多的去噪方法进行归纳分类，分为单模型网页去噪和多模型网页去噪，重点有Shingle方法[16]，Cai等人的VIPS算法[17-20]。本系统采用的网页去噪方法简单而实用，提取每个超链接的文本值，构成新旧字符串数组进行对比，满足算法要求的数据输入格式。经过MD5判别和网页去噪，再进行文本对比，降低了对比误差出现的概率，提高了更新检测的准确性。

2 实验结果与分析

2.1 实验设置

为验证本文所提方法的性能。在联想个人PC机上进行实验，配置：CPU:Intel(R) Pentium(R)@2.80 GHz，内存:4.0 GB，操作系统:Win 8.1专业版，32位。

实验以7个不同类型、规模、结构的网站自然情况下的更新作为测试，采用增量式更新和LCS算法获取更新，统计其查准率和查全率。由于大型网站如凤凰网、天涯论坛，一天内更新的内容多而散乱，难以统计某段时间内网站更新的具体新闻数目，不便计算查全率，只能计算出查准率。测试网站的名称、URL、编号如表1所示，与表2中编号相对应。

表1 测试网站编号表

表2 采用改进的LCS算法统计网站更新数据表

续表2

2.2 实验结果

采用本文改进的LCS算法，分别统计7个网站每次更新的查准率、查全率以及5次试验的平均查准率、查全率，如表2所示。可以得知，1、2号网站，是高校内部网站，它们的查准率和查全率非常高接近100%，因为高校内部网站结构简单、更新数量较少，容易全部捕获到。不过，由于更新数量少，若有1～2条更新没有获取，对查准率、查全率影响较大，2号网站正是因此在第4次测试中查准率和查全率较低。3-7号网站，分别是凤凰网、天涯论坛、CSDN博客、中国建设银行、电影天堂，其中6号中国建设银行，监测了3层页面，其表现跟1、2号网站类似，准确率高但易被少量未捕获的更新内容影响；3号凤凰网，其结构严谨、内容单一有规律，每次查准率都在97%以上；其余的3个网站，分别是论坛、博客、电影网站，类型不同，共同点在于网页结构复杂、内容繁多杂乱、变化频繁而不规律、有防爬虫设计，故查准率相对偏低，3个网站的平均查准率是85.9%，比较稳定，受未捕获的少量更新内容影响较小；查全率虽无法统计，但从局部范围内的统计发现，查全率不低于查准率，使得更新内容遗漏很少，保证了更新的覆盖范围。

另外，对同样的上述7个网站，分别采取改进和原始的Nakatsu的LCS算法，进行3次更新监测，统计其平均查准率。具体数据如表3所示，对应的对比如图9所示。

表3 网站更新对比统计表

续表3

图9 网站更新对比图

通过对比可以发现，改进后的LCS算法用于网站更新监测，虽然个别网站的查准率并未提高，但总体上有更高的查准率。因为网站上的Item重复较少，采用LCS算法获取最长公共子序列时不会经常得到多个最长公共子序列，所以改进后的一些网站，其查准率是相同的。但对于4号“天涯论坛”这种大规模大数据网站而言，有许多帖子由于评论内容的增加而导致其在页面上的位置变化，但Item标题其实未变。这导致了后期更新时LCS算法会得到多个最长公共子序列，需要排除。于是本文改进的LCS算法就取得了效果，提高了查准率。查准率对网站更新而言，非常重要，影响到用户查看信息的准确性、全面性，避免遗漏重要通知、信息。

3 结 语

本文提出一种基于网络爬虫和改进的文本对比的网站更新监测新方案，实现了几乎任意网站的更新监测与订阅。实验结果表明，对于结构简单、内容规律的高校、新闻等网站，该方法表现优秀；对于结构复杂、内容繁杂、变化频繁无规律的论坛、博客、视频等网站，该方法表现稍有欠缺。总的来说，所提方法对大规模网站的更新监测，具有一定可行性，为网站更新监测领域提供了一个新的方案。本文提出的改进LCS算法，一定程度上提高了网站更新的查准率，保证了网站更新的准确性、全面性，提高了用户的使用体验和效率。但本实验的测试网站数量较少、实验环境和配置简单、未采取分布式爬虫，对实验结果有一定的影响，这将是进一步的研究方向。

[1] 曹建勋, 刘奕群, 岑荣伟, 等. 基于用户行为的色情网站识别[J]. 计算机研究与发展, 2013, 50(2): 430-436.

[2] Fetterly D, Manasse M, Najork M, et al. A large-scale study of the evolution of Web pages[J]. Software-Practice and Experience, 2004, 34(2): 213-237.

[3] Ma D. Use of RSS feeds to push online content to users[J]. Decision Support Systems, 2012, 54(1):740-749.

[4] Vawter E. Rss explosion in chemistry and science[J]. Searcher, 2006, 14(4): 33-36.

[5] Nagy P, Daly M, Warnock M, et al. Using RSS feeds to track open source radiology informatics projects[C]//Medical Imaging. The International Society for Optics and Photonics, 2005: 282-285.

[6] Nanno T, Okumura M. HTML2RSS: automatic generation of RSS feed based on structure analysis of HTML document[C]//Proceedings of the 15th International Conference on World Wide Web. ACM, 2006: 1075-1076.

[7] 荆明明. 基于Android的个性化RSS订阅系统的设计与实现[D]. 哈尔滨：哈尔滨工业大学, 2011.

[8] 张睿涵. 基于RSS的聚焦网络爬虫在高校网站群中的研究[D]. 南昌：南昌大学, 2012.

[9] 王大伟, 张岩, 曾皓, 等. 一个预测网页变化的增量式更新模型[J]. 微计算机信息, 2009(6): 153-154,130.

[10] Nakatsu N, Kambayashi Y, Yajima S. A longest common subsequence algorithm suitable for similar text strings[J]. Acta Informatica, 1982, 18(2): 171-179.

[11] Needleman S B, Wunsch C D. A general method applicable to the search for similarities in the amino acid sequences of two proteins[J]. Journal of Molecular Biology, 1970, 48: 444-453.

[12] Ullman J D, Aho A V, Hirschberg D S. Bounds on the complexity of the longest common subsequence problem[J]. Journal of the ACM (JACM), 1976, 23(1): 1-12.

[13] Hirschberg D S. Algorithms for the longest common subsequence problem[J]. Journal of the ACM (JACM), 1977, 24(4): 664-675.

[14] 李欣, 舒风笛. 最长公共子序列问题的改进快速算法[J]. 计算机应用研究, 2000, 17(2): 28-30.

[15] 毛先领, 何靖, 闫宏飞, 等. 网页去噪: 研究综述[J]. 计算机研究与发展, 2010, 47(12): 2025-2036.

[16] Gibson D, Punera K, Tomkins A. The volume revolution of Web page templates[C]//Proceedings of the 14th International Conference on World Wide Web. New York: ACM, 2005: 830-839.

[17] Cai D, Yu S, Wen J R, et al. Extracting content structure for web pages based on visual representation[C]//Proceedings of the 5th Asia-Pacific Web Conference on Web Technologies and Applications. Springer, 2003: 406-417.

[18] Song R, Liu H, Wen J R, et al. Learning block importance models for web pages[C]//Proceedings of the 13th International Conference on World Wide Web. ACM, 2004: 203-211.

[19] Cai D, Yu S, Wen J R, et al. VIPS: A vision-based page segmentation algorithm[R]. MSR-TR-2003-79, Microsoft Technical Report, 2003.

[20] Yu S, Cai D, Wen J R, et al. Improving pseudo-relevance feedback in web information retrieval using web page segmentation[C]//Proceedings of the 12th International Conference on World Wide Web. ACM, 2003: 11-18.

WEBSITE UPDATE MONITOR BASED ON WEB CRAWLER AND IMPROVED LCS ALGORITHMS

Zhou Xiaoke1Guo Kehua1,2

1(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410000,Hunan,China)2(HighDimensionalInformationIntellisenseandSystemKeyLaboratoryoftheMinistryofEducation,Nanjing210094,Jiangsu,China)

With the explosive growth of information in Internet era, customers need to get the required information conveniently and timely. Traditional search engine and website subscription represented by RSS couldn’t satisfy the users’ high equality demand due to their disadvantages. Based on this, a new universal method of website update detection and subscription based on web crawler and text contrast is proposed. After analyzing and processing the successive webpage content, the proposed method would contrast the text, update contents and return the structured results to users. Experiment results show that this method conquers the difficult of RSS subscription’s feed limit, and makes it possible to add subscription on one’s own. It also got good performance upon university,enterprise,news,video,blog,forum websites etc.

Web crawler Noise reduction in web pages Website subscription Text contrast Update detection

2015-11-12。国家自然科学基金项目(61202341);高维信息智能感知与系统教育部重点实验室创新基金项目(JYB201502);科技部国家国际科技合作专项项目(2013DFB10070);湖南省创新平台专项项目(2012GK4106);中南大学创新驱动计划；中南大学升华育英计划。周孝锞，硕士生，主研领域：Web推荐，透明计算。郭克华，副教授。

TP391

A

10.3969/j.issn.1000-386x.2017.01.041