Design and Implement a Web News Retri System (中文翻译版).doc

设计和实现一个网络新闻检索系统James N.K. Liu, Weidong Luo, and Edmond M.C. Chan香港理工大学，计算机系csnkliu,.hk, .hk摘要：我们展示了“Ai-Times”系统的设计和实现，这是一个基于网络的新闻检索系同时，我们也详细地描述了爬虫模型，新闻提取模型和自动摘要模型。1 简介通过因特网能够轻松获取到的在线信息量正在呈现爆炸式的发展，这是一个不争的事实。当可用信息增加的时候，处理、分析和使用如此大量信息的能力不足也变得越来越明显。在线的新闻信息也存在着这样的问题。而且，目前可用的搜索引擎也效率低下。例如，不能满足用户根据他们指定的目录和时间片获取信息的功能，也不能根据需求的频率来提供在线的新闻信息。我们描述的“Ai-Times”系统（包括设计和实现），是一个基于网络的新闻检索系统，而它的目标就是精确地获取和组织网络上的新闻信息。同样，我们也详细地描述了爬虫模型，新闻提取模型和自动摘要模型。我们相信许多现有的新闻检索系统已经用到了这些技术中的一部分，但是却很少有关于关于这些技术的科学性研究。这篇论文的剩余部分是这样组织的：在第二部分，我们回顾了在新闻检索系统方面的相关工作；在第三部分，我们定义了关键的部分，并且描述了“Ai-Times”系统的运作，包括优化的网络爬虫算法，新闻内容提取模型和自动摘要模型；在第四部分，我们给出了实验结果；最后一个部分是我们的结论。2 相关工作新闻信息检索已经被大量的研究过了1,2,3,4,5。很多研究是在新闻信息检索的一般结构上完成的。例如，引用 Yasuo Ariki, Yoshiaki Sugiyama.A TV News Retrieval System with Interactive QueryFunction. Proceedings of the Second IFCIS International Conference on Cooperative InformationSystems(1997)184-192.展现了一个利用关键字自动分类电视新闻文章的系统；引用 Steve Renals, Dave Abberley, David Kirby and Tony Robinson .The THISL system for indexingand retrieval of broadcast news. IEEE Signal Processing Society 1999 Workshop onMultimedia Signal Processing September 13-15, 1999, Copenhagen, Denmark(1999) 77-82.描述了“THISL”，一个维护BBC广播和电视新闻记录文档的新闻信息检索系统；引用 Sudhir Aggarwal, Fuyung Hung. WIRE - A WWW-based Information Retrieval and ExtractionSystem. Proc. of the 9th International Workshop on Database and Expert Systems Applications(DEXA98), Vienna, Austria.(1998)887-892.介绍了基于万维网信息检索和提取系统；引用 M. Sanderson & C.J. van Rijsbergen. NRT - News Retrieval Tool. Electronic Publishing,EP-odd, Vol. 4, Num. 4(1991) 205-217展示了一个基于一些报纸（例如：Times）的现有数据库的新闻检索工具的设计。上述的论文对新闻信息检索的总体结构有很大的贡献。然而，他们中没有一个详细地描述了核心模块，例如爬虫模块，新闻提取模块和自动摘要模块。也存在着一些研究长串提取算法和网络爬虫算法的文章。例如，引用 Saikat Mukherjee, Guizhen Yang, Wenfang Tan, I. V. Ramakrishnan. Automatic Discoveryof Semantic Structures in HTML Documents. ICDAR (2003) 245-249.描述了一个将HTML文档自动转化成树形语义结构的算法，同时也展示了其隐含的意义。然而，当被用于新闻提取的时候，它并不能对所有种类的HTML页面进行合理的分析。引用 Li, J.J.Research and Implementation of A Domain-Unconstrained Chinese Automatic AbstractingSystem.Phd dissertation, Dept. of Computer Science, Harbin Institute of Technology.1996.介绍了怎样实现一个有效的网络爬虫。然而，当直接用于新闻检索的问题时，性能一般的网络爬虫的表现还是相对会差一点。3 “Ai-Times”的结构和算法这个部分我们描述了“Ai-Times”的基本框架。同时，也详细地讲了爬虫模块，新闻提取模块和摘要模块的算法。3.1 结构图1展示了“Ai-Times”系统的结构，包括几个经典的基于WEB信息检索系统的模块：网络爬虫，自动分类模块，索引引擎，搜索模块和自动摘要模块。“Ai-Times”的特殊在于：“Ai-Times”系统只需要非常少的人工操作，就能够自动提取出新闻的标题，文本内容和图片信息；同时，它也通过优化网络爬虫算法的方法，节省了爬取和更新的时间；当然，“Ai-Times”也能够提供新闻的摘要。我们会在3.2节到3.4节之间，详细地介绍网络爬虫模块，新闻提取模块和自动摘要模块。图1. “Ai-Times”新闻检索系统的结构3.2 网络爬虫新闻信息检索系统的一个基础而重要的组件是网络爬虫，它能够自动地搜集网络文本。这个领域已经有了很多的研究，例如：Cobweb6就是一个典型的网络爬虫。“Ai-Times”专注于从一些预先定义的新闻网站上搜集信息，所以“Ai-Times”的网络爬虫算法不同于经典的网络爬虫算法。经典的网络爬虫算法已经在论文中讨论过了 Cho, Junghoo, Garcia-Molina, Hector. Effective Page Refresh Policies for Web Crawlers,ACM Trans. Database System. 28(4) (2003) 390-426.，但我们展示了一个使用与新闻网络爬虫的优化算法。下面给出一些定义，包括无价值的网络文本，包含新闻的网络文本，索引等：没有价值的网络文本：那些对新闻信息检索没有价值的网络文本，例如：广告网页。包含新闻的网络文本：主要指包括新闻文本、新闻图片和其他的一些媒体资源的网页。目录或者文本列表：主要指包含一些链接的网页，这些链接指向的则是包含新闻内容的或相关主题的网页；通常，主题就是新闻的题目。算法一：优化的爬虫算法BeginLet I be a list of initial URLs of the news website;Let F be a queue;For each URL i in IEnqueue(i,F);EndWhile F is not emptyu=Dequeue(F);if u has not been processedGet (u);Case us type:Valueless web document:Skip u.News content web document:Store u;Index or list page:Extract the hyperlinks and relevant caption;Let U be the set of hyperlinks extracted;For each hyperlink u in UEnqueue(u,F);EndElseu has already been processedCase us typeValueless web document:Skip u;News content web document:Skip u;Index or list web document:Update checkingEndEndEnd要判断一个网页文件是否被改过或被更新过通常是一件非常耗时的工作。一般情况下，爬虫会经常浏览所有的网站和网页来进行更新检测。有时，爬虫向WEB服务器发送请求，并分析得到的应答报文以得到网页文件的最新修改时间。然后，爬虫会决定重新下载网页文件。然而，即使爬虫能够从HTTP头中得到最新的修改时间，但请求时间和系统资源仍然会浪费很多时间。尽管如此，许多HTTP服务器不会在HTTP头中提供最新的修改时间。因此，最通用的更新策略之一是重新访问所有的WEB文件来找到更新信息，虽然这样是非常耗时的。另一个更新策略是重新访问一些重要的网页，但这种方法经常丢失信息。通常，一个新闻网站中超过90%网页文件是包含新闻内容的，并且这些文件很少或者重来不会被修改或者更新。然而，索引或者WEB文件的列表会被很频繁地更新。通过定义这三种WEB文件，“Ai-Times”的网络爬虫不需要在更新期间请求所有的WEB文件。正如我们从算法一中看到的，我们的爬虫会忽略没有价值的文件和包含新闻内容的文件，而只重新访问会有更新可能的包含索引和目录的文件。这种方法会很省时间，并且使更新间隔很短。3.3 新闻提取在这个部分，我们会介绍一个新的概念“keen tags”。我们也会讲怎样通过使用“keen tags”提取新闻文本内容。调查了大量的新闻网站后，我们发现在大多数的新闻WEB文件中，被HTML标记分开的新闻文本内容会集中在一块，从HTML源代码上看。为了使用一个单一目的的提取器，而不是不同网站相关的提取器进行新闻内容的提取，我们会介绍“keen tags”。“keen tag”是一种总是出现在新闻文本内容的里面或周围的标签。图2展示了一个例子。图2 “keen tag”的例子 正如我们从图2中所看到的，新闻内容的字符串在HTML源文件中非常集中，并且总伴随着标签“”和“”。通常，诸如“”，“”，“”，“”，“”之类的标签就是一个网站的“keen tags”。我们定义一个“keen tags”列表：, , , , , , , , , , , , 。通过定义“keen tags”，我们将WEB网页源文件的字符串分成三种类型：1. “keen tags”；2. 不属于“keen tags”的HTML标签；3. 不是HTML标签的字符串。算法二：新闻提取算法1. 根据上述的第二种标签将HTML源文件分成很多部分；因此，每个部分只包含上述的第一种和第三种字符串。如下所示：2. 为每个部分进行评分，评分公式如下：其中，i是这个部分的序号；ni是当前部分中的第三种标签的总数；k是当前部分中第三种标签的序号。3. 选择得分最大的那个部分作为“data-rich”；4. 评价这个被选择的部分，看它是否是一个包含新闻内容的WEB文件：Score就是评分得到的分数，hrenum是在这个部分中，含有HTML超链接的个数。N是预定义的新闻内容的长度。任何新闻内容长度小于N的新闻文件不会被作为一个有用的新闻WEB文件。T是预定义的在一个新闻内容中链接标签总数的上限。任何包含链接标签数超过T的新闻文件不会被当作一个有用的新闻WEB文件。5. 如果evaluate()=1，这个文件能够被当作一个包含新闻内容的WEB文件；并且，被选择的“data-rich”会被作为新闻文本内容被提取出来。把前面得到的摘要作为这个新闻的标题；把当前时间作为下载这则消息的时间。除了我们之前定义的普通“keen tags”，还有一些我们能从训练阶段提取出来的网站相关的“keen tags”。在训练阶段，定义过的新闻WEB文件会被输入，系统会基于一些预定义的规则分析这些文件，最后输出这些网站相关的“keen tags”。3.4 自动的新闻摘要模块这个部分，我们会描述“Ai-Times”系统的自动摘要模块。这个模块的处理过程由以下三部分组成：关键字的生成，句子权重的生成和摘要的生成。接下来的三个小节，我们将会分别讲解这三个过程。3.4.1 关键字生成关键字是依靠分词算法和基于统计和概率的关键字权重等式生成的。在新闻WEB文件中的单词将根据他们在文件中的重要性和出现频率被赋予不同的权重。具有最大权重的单词将被提取作为关键字。摘要算法通过遍历一个新闻WEB文件，并根据接下来的等式找出其中合适的单词：其中，w是从句子中提取出来的中文单词；F(w)是w出现的次数；L(w)是w的长度；numdoc是包含w的文件个数；totalnumdoc是总的文件个数；D是w的最小长度；c是中文汉字序列长度的影响因子。关键字只能用于检索相关的网页，它们并没有真正的语义。3.4.2 句子权重到目前为止，我们已经描述了怎样产生关键字。接下来，摘要算法的第二步就是句子权重的计算。句子被赋予的这个权重，将显示出它们在一个新闻WEB文件中的重要性。权重值越大，重要性越大。最大的权重将被赋予能体现出新闻网页中最重要概念的句子。重要句子有如下特点：句子中有较多的关键字；关键字有更高的权重；句子的长度更短；有较少的子句；有较少的数字性质的词。接下来的等式计算了句子的权重：其中，N是句子中关键字的个数；Ti是句子中第i个关键字的权重；s0是句子中所有单词的总数；s1是句子中所有子句的总数；s2是句子中所有数字性质的单词的总数；m是一个整型变量（通常设置为1）。拥有更多关键字的句子将会有更大的权重；拥有更多子句，单词和数字性质的词，句子的权重将会更小。这就是重要句子提取的过程。3.4.3 摘要生成第三步，是摘要生成。根据接下来的等式，依照由用户要求的特定比率，拥有最大权重的句子将被提取出来以产生关键字。其中，T是新闻WEB文件的长度；