《基于实时爬取的提醒服务.doc》由会员分享，可在线阅读，更多相关《基于实时爬取的提醒服务.doc（7页珍藏版）》请在三一文库上搜索。
1、精品论文基于实时爬取的提醒服务杨同峰 ，马军 山东大学计算机科学与技术学院，济南250101 摘要：随着互联网信息的爆炸性增长和人们对互联网依赖的日益加强，传统的通过用户主动浏 览网页获取信息的模式，很难满足用户对信息的实时性和完整性的需求。文中提出了一个通知 服务：首先由用户指定需要从中获取信息的普通网页，系统半自动的生成提取信息的模板，并 构建用户配置文件。系统对配置中的网页实时监控，发现新的信息后，根据用户指定的方式， 将更新的信息推送给用户。该系统支持邮件，短信，客户端等多种推送方式，允许用户随时随地获取最新的信息。最后，本文对该系统的实时性进行了评测。关键词：信息检索;实时爬取;信息
2、抽取中图分类号： TP301.6A Notification Service Based on Real-timeCrawlingYANG Tong-Feng , MA JunDepartment of Computer Science & Technology, Shandong University, Jinan 250101Abstract: With the explosive growth of the Internet information and the increasing dependence of people on web, the traditional model
3、that user browsing web pages actively can not satisfy the real-time and full demand on information. In this paper, we propose a notification system: user specifies the web page whose information need to be obtained at first, then the system semi-automatically creates the extraction template, and add
4、 to user configuration, then the system monitors all the pages that users specified, sends message to users by the way they want to. This system support many notification methods such as email, sms, mobile application. The real-time performance of the system is evaluated at last.Key words: Informati
5、on Retrieval;Real-time crawling;Information Extraction0 引言随着互联网的发展，互联网上的信息量以指数形式上涨。同时，随着计算机的应用遍及人 们生活的方方面面，人们对计算机，对互联网的依赖也越来越重。大量的信息和过度的依赖导 致人们在关注和查找信息方面花费的时间也越来越多。目前Web 上信息传播方式主要是，用基金项目： 本研究得到国家自然基金(61272240,60970047, 61103151), 教育部博士点基金(20110131110028) 和山东省自 然基金(ZR2012FM037) 的资助。作者简介： 杨同峰（1985-），男
6、，博士研究生，主要研究方向：图像标注。马军（1959-），男，教授，博士生导师，主要研究方向：信息检索。- 7 -户主动查找，服务器返回信息。也有一些应用提供推送信息服务。但这些应用在整个互联网中所占的比例非常的少（不到1%)，推送到内容也仅仅与其应用场景相关。所以，用户就需要一 种将被动拉取的信息转化为主动推送的通用的推送服务。对于一个通用的推送服务，有效地对用户指定的网页进行信息抽取就是一个关键问题。传 统的信息抽取技术，往往采用给特定类型网页，人工编写匹配模板的方式。这种方式对人力的 消耗较大，而且对网页格式变动适应性较差。文献1, 2给出了近年来信息抽取技术的综述，其 中算法大多使用自
7、然语言处理，和机器学习的方式来实现，这些算法往往需要一个比较完善的 语料库进行学习，而且通用性较差。本文提出的信息抽取算法，首先对目标网页进行格式分 析，找到用户可能感兴趣的链接集合，并通过与用户的简单交互，自动生成最终的抽取模板。 与传统互联网上相比，现在互联网上的信息越来越强调实时性。现有的试试爬取算法往往 采用在用户查看或者提交查询时实时的爬取目标并将从目标中得到的结果和现有数据结合的方 法来实现，不同之处仅在于数据存储方式和结果合并执行的时机。文献3, 4使用数据库存储 数据;文献5不适用任何缓存数据，在用户检索的时候才去目标查询;文献6 使用缓存来存储数 据;文献7使用索引缓存数据库
8、。上述文献中皆采用在服务端合并结果的方法，文献8采用在浏览器端合并的方式。这些方法总体来说都是基于用户的驱动。在用户提交检索时实时爬取， 这种方式适合于传统的拉取方式浏览信息，而推送服务则无法使用类似的方法，所以只能采用 预测的方式来达到实时性。本文给出的系统设计了一种实时爬取算法，以便在数据集规模增大 时，仍能具有较好的实时性能。在一个目标网页被加入实时爬取库中以后，系统会给予一个初 始的爬取时间间隔。并按时对其进行爬取，爬取后使用抽取模板对目标内容进行抽取，并得出 其是否改变的信息。一个网页被爬取后，以往所有爬取记录中其是否改变的信息都被用于计算 其下一次爬取的间隔。近年来，以智能手机为代
9、表的个人终端得到了空前的发展。人们对信息的获取的实时性有 了设备基础。本文给出的推送服务除了支持传统的邮件提醒外，还支持短信，手机客户端提醒 等方式。使得用户能更灵活的获取通知信息。文章最后，对通知服务的实时性和信息抽取的准确性进行了评测。1 半自动信息抽取信息抽取服务可以表示为:用户指定一个网页p作为输入，算法输出为N = n|n = (t, l)， 其中n为网页中的一个被关心的数据，t为该数据的文本，l为该数据对应的页面。设计一个完备的通用型自动信息抽取算法具有很多难点，而作为消息通知服务的一个部分，则可以做出一定的简化:如果用户关注一个页面是否变化，那么系统不需要做信息抽取， 仅仅对该页
10、面求hash值并保存。如果用户关注的是一个索引页，那么系统只需要关注链接集合 的变化即可。对于一个给定的网页，系统首先得到该网页所有的链接，并根据链接的URL进行聚类。 URL的主要特点是他具有树形的目录结构。同一个网站的链接倾向于同一个类，同一个目录 下的文件更倾向于属于同一类。对于动态网页，带有不同参数的同一个动态页面的链接更倾向于从属于同一个类。对于同一目录下的静态化的页面，文件名前缀相同的更倾向于从属于同一类。所以，对于链接的聚类，就是根据URL的主机名，目录名，文件名，参数，前缀来实现。 依次根据上述参数来进行聚类，由用户来决定聚类的粒度，然后系统生成提取模板。见算法1算法 1 信息
11、抽取模板自动生成算法输入:网页网址m;输出:抽取模板M1: 获取页面m的源代码p;2: 根据p生成DOM树，并提取链接集合L = l|l = (t, u)3: 提取L中每个元素l的链接u的主机h和目录d。4: if 页面m是动态网页 then5: 提取网页的文件名n,参数集合r6: else7: for li , lj L do8: 最大匹配li 和lj 文件名的前缀，将两个前缀加入前缀集合P。9: end for10: end if11: 构建集合V = (h, d, n, r, P )。12: for v V do13: V = V v14: 将v根据目录划分为若干链接类的集合Lv 15:
12、 将每个集合中前10项的链接的文本展示给用户，让用户选择其中一个链接。16: if 用户结束此选择 then17: return V 18: end if19: end for2 实时爬取实时获取目标网页的变化是消息提醒服务的关键。本文提供的实时爬取算法使用以下策 略：(1)根据页面在以往爬取时有无变化的信息预测下一次爬取的时间。(2)当爬虫空闲时，选 择下一个需要爬取的目标网页进行爬取，虽然它的预测爬取时间还没到。因为在实时系统中， 实时性比命中率更重要。设x = xi |i 1, n为网页p的在历史爬取中是否变化的记录向量。如果变化，则xi = 1,否则xi = 0 ，记录页面上次被爬取的
13、次序即为s,记录当前爬虫爬取网页的次数为w,总页面数量为n,当前,则页面第m次和第m + 1次爬取的时间间隔:其中，t0 为初始时间间隔。算法 2 实时爬取输入:m (12xi ) wstn+1 = t0 2i=0n(1)目标网址集合U = u = (l, t, h)，其中l为网页地址，t为下一次爬取的时间间隔，h为上一 次爬取时信息的hash码1: for u U do2: u.t = t03: end for4: while TRUE do5: for 按u.t递增顺序,依次选择u U do6: 爬取网页u.l的网页内容7: 抽取信息8: 计算信息的hash码h9: if u.h = h
14、then10: 发送通知11: end if12: u.h = h13: 根据公式1计算u.t14: U = U u15: end for16: U = U 17: end while3 消息推送为了让用户更便捷的获取消息，消息服务提供多种消息推送方式，包括：(1)邮件推 送(2)SMS推送(3)手机应用推送(4)MSN推送。 而SMS则需要通过发送短信接口，系统中使 用SinaAppEngine提供的短信接口实现。(1) 邮件推送：邮件推送是比较传统的推送方式，在某个目标页面有更新时，给监控这个页 面的所有用户依次发邮件。(2) 短信提醒：系统使用SinaAppEngine提供的短信接口，在
15、有更新消息是给监控这个页面的 所有用户依次发短信。图 1: 系统框架表 1: 半自动信息抽取实验数据抽取消息数召回率准确率新浪新闻22993.0%100.0%新浪军事17394.7%100.0%学校通知78100.0%100.0%(3) 手机应用推送：目前智能手机已成为手机主流，基于手机平台的手机应用满足了用户方方面面的需求，本文给出的服务同样提供了基于android系统的手机应用。应用按一定时 间间隔轮询服务的web接口，消息内容以JSON格式表示，应用如果发现更新，则将本地 数据库，并使用手机中的通知功能提示用户。(4) 即时消息推送：因为谷歌的GTalk和微软的MSN通讯协议比较开放，所
16、以，使得通过这 两者即时消息工具推送消息成为可能。腾讯公司的QQ因为协议封闭，且更改频繁，暂不 能支持。4 实验此部分主要对通知服务的半自动信息提取和实时爬取两个方面进行评测。使用新浪新闻， 新浪军事，学校网站为测试数据源，实验结果见表1，使用召回率和准确率作为评测标准。实 验表明，该信息提取算法可以达到抽取的信息没有错误，但有时会遗漏一些消息。其主要原因 在于，对于同一类消息，有不同URL格式的情况出现。与大规模通用性爬虫相比，实时性爬虫更重视爬取的实时性。所以，我们使用平均爬取延 迟来描述爬取的实时性。设n为总的爬取次数，fi 为该次爬取的时间，ci 为被爬取页面的最后表 2: 实时提醒服
17、务的平均延迟网页数量平均延迟(单位s)1005.14100038.6710000284.21更新时间，则实时性可以表述为平均延迟：1t =nn(fi ci ) (2)i=1因为人工建立大量的测试用户并指定大量目标页面并不现实，而如果测试量太小，实验结果 又没有足够的说服力，所以使用matlab 对爬取算法进行了模拟。假设有n个页面，每个页面 的每次更新的间隔时间（单位为s）服从正态分布。这些正态分布的均值服从3600, 360000之 间的均匀分布，标准差服从1000 5000之间的的均匀分布，同时设爬取每一页面需要的时间 为0.1s。实际中爬取一个页面的平均耗时在多线程情况下可以远小于0.1
18、s，进而其消息提醒的 平均延迟会远小于模拟实验给出的结果。实验中分别取n 为100,1000,1000 时的平均延迟做了 评测,结果见表2。5 结论本文给出了一种基于实时爬取技术的通知服务：使用与用户的简单交互完成信息抽取模板 的构建，然后设计了一个爬取算法，以期达到较高的实时性。对于更新的网页，结合现在人们 生活的习惯，使用多种方式推送给用户。实验表明，本文给出的信息抽取算法具有极高的准确 率和较高的召回率，实时性也比较好，可以基本满足用户对实时消息的要求，在存在10000个 目标页面时，平均延迟不到5分钟，即用户在出现消息5分钟之内即可得到通知。参考文献（References）1 邓尚民,
19、孙玉伟. 信息抽取系统的研究现状J. 现代图书情报技术. 2006(03):55-58 2 李向阳,苗壮. 自由文本信息抽取技术J. 情报科学. 2004(07) :816-8213 陈彤兵，汪保友，胡金化等:一个实时搜索引擎的设计J. 小型微型计算机系统，2003，25(5):855-8584 吴 伟 忠,崔 建 英. 基 于 时 效 性 的 垂 直 搜 索 及 其 应 用J. 暨 南 大 学 学 报(自 然 科 学 版).2007(03):255-2585 马家宇,阳小华,刘振宇等:基于弱实时系统的元搜索引擎合成策略J. 计算技术与自动化.2004(02): 22-246 周佳庆,吴羽,江锦华,陈刚,董轶. 实时垂直搜索引擎对象缓存优化策略J. 浙江大学学报(工学版). 2011(01):14-197 陈飞. 实时垂直搜索引擎的爬虫技术研究D. 大连:大连理工大学,20118 郭 浩,陆 余 良,刘 金 红. 一 种 基 于 状 态 转 换 图 的Ajax爬 行 算 法J. 计 算 机 应 用 研 究.2009(11):4266-4269