1、信息检索课程结业报告姓 名：学 号：所学专业：报告题目：提交日期：张军卫10S003103语音处理搜索引擎中主题爬虫研究与实现2010 年 11 月 9 日1搜索引擎中主题爬虫研究与实现1 引言像蒸汽机和电的发明一样，互联网的出现和蓬勃发展对人类生活的影响是革命性的，因为它彻底改变了人们获取信息的方式，人们越来越多地通过网络来获取信息，同时它也改变了我们的生活方式。为了使人们能快速、准确地从互联网上获取信息，搜索引擎诞生了，从分类目录检索到全文检索，搜索引擎给人们带来了巨大的便利。它是真正的互联网门户，全球各大著名搜索引擎网站的访问量都居前列。当今，互联网上的数据量呈现出指数级的增长趋势，并且
2、网页不定期地发生变化，这给搜索引擎带来了巨大挑战。最大的搜索引擎也只能覆盖互联网上的部分网页，而且并不能保证建索引的网页和现实网页都是同步的，因此优先采集“重要”网页和制定有效的更新策略成了搜索引擎中的信息采集模块 网络爬虫(web crawler)必须考虑的问题。研究人员在如何评价网页重要度上作了大量研究，这些对网页重要度的评价算法主要基于对网络链接结构的分析，比如著名的PageRank技术。另外，搜索引擎也不能完全满足人们获取个性化主题信息的需求。搜索引擎很难回答诸如“我的竞争对手当当书店网站昨天都有什么新书上架？”这样的问题。为了解决这些问题，就需要一个能在客户端运行的信息采集程序，该程
3、序能满足用户对信息的个性化需求，因此出现了一种称为主题爬虫(topic crawler)的技术。主题爬虫技术在互联网信息检索上是搜索引擎的有力补充，它能完成一些搜索引擎不能完成的信息获取需要。同时主题爬虫技术也会应用在搜索引擎上，比如在类目里面的搜索和特定丰题信息的优先更新等。主题爬虫技术主要研究的是怎样采取一个好的策略( 沿着一条好的“路径”)采集相关度高的网页，同时又能有效地避免不相关的网页，这当中主要用到了数据挖掘、机器学习等理论。它往往结合文本分类、文本聚类、web挖掘等技术，但还远未成熟。在主题爬虫技术方面，fish search算法是最早提出的一个经典算法，该算法体现了主题爬虫技术
4、的基本思想，之后IBM Haifa Research Libratory提出了一个Shark -search算法对其进行了重大改进，引入了文本相似度理论和链接文本分析技术。此后研究者在主题爬虫算法的研究上大量使用了机器学习(主要有增强学习、遗传算法等)和数据挖掘理论( 主要是web挖掘技术，包括文本分类、聚类还有web架构挖掘等技术)。本系统主要是在一般爬虫技术的基础上，加入了一个基于重要度的主题爬虫算法，使爬虫可以爬取比较重要的网页。在本文中详细介绍了该算法的执行过程以及提出该算法的原理。最后通过与一般爬虫提取的网页进行比较，表明加入该算法后网页的重要度得到很大的提高，在文章的最后分析了该系
5、统存在的不足，并提出通过引入相关度来改进系统。2 系统设计2.1 系统结构介绍2该爬虫系统主要可以分为三大模块，分别为主程序运行模块、数据存储模块和用户交互模块，其中主程序运行模块又分为线程分配子模块和网页内容下载及分析处理子模块，数据存储模块又分为线程数据共享区、hash 存储表和队列存储三个子模块。具体结构如图 2-1 所示。图 2-1 系统体系结构图2.2 模块功能介绍a.用户交互模块该模块主要完成系统与用户的交互，用户可以通过系统界面对话框来对系统的各项运行参数如起始 URL、文件存放目录、以及线程的运行数量等进行运行前设置。在运行过程中用户可以随时暂停和终止程序的运行，系统则把爬取的
6、网页情况在界面上进行显示，供用户操作参考。b.主程序运行模块该模块是系统运行的主线。首先启动主线程，然后在主线程中逐个建立各个子线程，子线程通过调用网页内容下载及分析处理模块完成主要的爬取任务。其中网页内容下载及分析处理模块主要负责完成对应 URL 网页的内容下载、分析、内容处理等工作，同时也包含与数据存储模块中线程数据共享区的交互。c.数据存储模块该模块主要完成 URL 信息及线程信息的存储功能。其中线程共享区子模块直接与线程进行交互，提供线程所需要的数据，并保证各个子线程互斥的访问共享数据。队列存储模块是用链表实现的一个简单的队列，实现 URL 的信息的实际存储。hash 存储模块存储 U
7、RL 的部分信息，用 hash 算法比较快速的判定某个 URL 是否已被爬取过。32.3 重要度算法设计与原理采集主题相关的网页，因为时间的限制或需要对重要网页进行更新，而且大范畴主题的网页量也会非常之大，因此我们往往也只能采集一部分主题相关的网页。这时，我们希望采集的是最“重要” 的主题相关网页。通过分析Hits算法和Shark-search算法得出结合网页链出链接数和对该网页URL的结构分析来计算重要度能够较好的表示一个URL的重要度。本系统计算重要度公式如下：网页的重要度=FACTOR*(网页链出链接数MAX LINK NUM) +(1-FACTOR)*(1网页URL 的“ /”数)FA
8、CTOR是两者的权重因子，值在 0到1之间。FACTOR值越大表示网页链接数对网页重要度的计算越起决定作用；FACTOR 值越小，则网页重要度值更多由它的URL 结构信息决定，在实验程序中，该值是可以方便调整的。MAX LINK NUM是为了使网页链接数度量规一化，得到一个01之间的值，该值设置为一个较大的值，对于链接数超过MAXLINK NUM的网页，令相除的值为1，MAX LINK NUM值也是可以方便调整的。根据URL 的“ /”数对URL 重要度的估计是因为URL 的“/”往往代表了该URL在网站中的层次，尤其在结构好的网站中，网页在网站中的层次越高，该网页往往是越重要的。搜索引擎中的
9、web crawler往往采用宽度优先策略，因为它往往要采集所有碰到的网页来建索引。而宽度优先往往也被称为按层次遍历，我们将种子节点称为第1 层，而种子节点链向的网页称为第 2层，以此类推，第 n层网页链向的网页称为第n+1层。这当中有很多网页会同时属于多个层次，为了使问题简单化，我们可以约定这些网页只属于它所在的最低层次。比如第n层某网页a 链向网页b，网页a和网页b又同时链向网页c，那么可以认为网页c既属于第n+1层也属于第n+2层，我们约定网页c只属于第n+1 层。我们以一个网站的主页为种子节点，以严格的宽度优先顺序遍历该网站，也就是只有遍历完第n层的网页才能继续遍历第n+1层的网页，这
10、样就能得到一个网站的层次结构图。该重要度计算公式包含了这样一种假设：层次越高的网页越重要(约定第n层比第n+1层高)，因为URL 中的“/”数目往往隐含了该网页在网站中所处的层次位置，对于结构好的网站尤其如此，URL中包含“/”越多的网页往往越在网站的较低层次，因此本公式中的重要度利“/”数呈反比趋势。高层次网页的链接数也往往比低层次网页的链接数多，因此本公式中的重要度和网页链接数呈正比趋势。当然本公式认为链接数多的网页更重要还因为本算法中希望爬虫能优先找到包含链接数多的相关网页，因为这些网页往往链向很多的相关网页。3 模块详细设计3.1 用户交互模块设计该模块就是本系统的界面模块，与用户进行
11、交互，获取启动的初始参数，并响应用户的操作。主要类和函数说明：41）CProjectDlg 类定义该类的目的：新建工程时显示对话框，方便用户对工程属性进行设定。与其他类的关系：被用户界面线 MainThread 程调用，进行新建的工程一些设置。2）CNetCrawlerDlg 类定义该类的目的：本程序的主窗口，用于新建工程，显示工程进展当前状态。类中函数及功能：void Add(CString 添加下载状态。与其他类的关系：调用 MainThread 类，生成一个工程主要流程图如图 3-1-1 所示。图 3-1-1 用户交互模块流程图3.2 主程序运行模块设计主要类和函数说明：1）MainTh
12、read 类定义该类的目的：储存工程下载信息，每个下载线程共享数据区，包括URL 队列，当前线程数量等等类中函数及功能：virtual BOOL InitInstance(); 重写初始化函数bool TrimString(LPTSTR,UINT 过滤掉网页的 html 语言标签void Run(CString 运行守护线程，启动工作者线程，下载网页与其他类的关系：被 NetCrawlerDlg 类调用，生成一个工程，下载网页；调用 DownloadData 类，生成一个数据共享区；调用 ProjectDlg 类，进行一些工程属5性设置。2）函数名称：UINT DownloadFile(LPV
13、OID pParam) 函数功能描述：全局函数；每个工作线程所要调用的函数；从 URL 任务队列得到一个网址并尝试连接函数的输入参数：LPVOID pParam 主控线程的指针，用于获取共享数据区函数的抽象算法a、试图从 URL 队列中获取一个 URL，若失败则返回(结束线程)b、根据地址向服务器发送请求，若请求失败则返回(结束线程)c、根据网页，提取主要内容，并存一个临时文件，用 FindURL 函数查找链接d、从共享数据区删除线程标签e、结束线程工作者线程(worker thread)的传入函数不能为类中的成员函数，故将传入函数声明为全局函数3）函数名称：FindURL函数功能描述：全局函
14、数；被工作者线程调用，从网页中提取 URL函数调用之前的预备条件：网页已经从网络上下载到本地存为临时文件返回后的处理：删除临时文件函数的输入参数：CString s 临时文件的本地地址MainThread *ptr 用于获得主控线程的共享数据区函数的抽象算法：a、只读方式打开本地文件b、查找连接，若未在共享数据区的 URL 任务队列中出现，则加入队列c、关闭文件函数与其他对象中函数的调用和被调用关系：被每一个工作者线程调用，来从网页中读取链接，工作者线程(worker thread)的传入函数不能为类中的成员函数，故将传入函数声明为全局函数。4）函数名称：TrimString函数功能描述：过滤
15、掉字符串中的 html 语言标签函数的输入参数：LPTSTR pszBuffer 字符串指针指向被处理的字符串，以0结尾UINT 是否 URL 已经存在于队列中bool IsEmpty(); 是否 URL 队列空了（无未处理的 URL）UINT GetMaxThreadnum(); 获得最大线程数目UINT GetCurThread(); 获得当前活动的线程数目bool DeleThread(); 线程结束后，从数据区删除一个线程记录，成功返回 truebool AddThread(); 线程开始，向数据区添加一个线程记录,成功返回 truebool AddURL(CString 向共享数据区
16、 URL 队列尾添加一个 URLbool GetCurURL(CString 从共享数据区 URL 队列头取出一个 URLvoid GetFileName(CString 获得当前本地存储文件的地址bool SetPro(UINT,UINT,CString 根据用户设定起始文件名称，最大线程数量，保存路径与其他类的关系：被用户界面线程 MainThread 调用，生成一个工程的共享数据区，从而实现多线程下载任务。该类中同时会调用 CQueue 类完成对 URL 的存取和信息查询。2）类名称：CQueue定义该类的目的：链表队列类，实现 URL 的实际存储，与一般队列类不同的是，插入元素实现的不
17、是插在队列尾部，而是根据元素的 priority 插入，使其由大到小排列。 类中函数及功能：bool get_el(CString 从队列头部获得元素bool add_el(CString 向队列中按 priority 添加元素bool is_empty(); 判定队列是否为空void add_to_st(s_url * p); 固定存储void del(); 释放所有链表空间bool is_find(CString 在链表中查找是否有某个元素void storetofile(CString ); 存储到文件与其他类的关系：被 DownloadData 调用，存储其得到的 URL；在 is_f
18、ind()中调用 HashTable 类的函数，完成 hash 查找的功能。3）类名称：HashTable定义该类的目的：网页地址表，散列表形式存储 URL 地址及相关信息。类中函数及功能：void insert(const char*); 往散列表加入数据bool is_find(const char*); 查找某个元素是否存在void clear(); 清空网页地址表与其他类的关系：7被 CQueue 类中的成员函数 is_find()调用。ELF hash 算法介绍：ELF hash 是对字符串进行 hash 操作时的常用函数，其原理是将一个字符串的数组中的每个元素依次按前四位与上一个元
19、素的低四位相与，组成一个长整形，如果长整的高四位大于零，那么就将它折回再与长整的低四位相异或，这样最后得到的长整对 HASH 表长取余，得到在 HASH 中的位置。4 系统运行结果分析启动系统运行主界面如图 4-1-1图 4-1-1 运行主界面“新建工程”对话框用来设这运行前参数，见图 4-1-2图 4-1-2 新建工程爬取开始后采集的网页内容存储在以文件 ID 命名的“.txt”文件中，其内容如图 4-1-83。以 http:/ 网页为例，以“主要保留中文”的方式提取内容，可以看到网页的中文主体内容被完整的提取出来，去掉了所有的网页标签，清晰的显示出网页内容。图 4-1-3 采集的网页内容示
20、例在生成的“url.txt”的文件中列出了所有爬取的 URL，下面我们通过比较加入“重要度”算法前后的 URL 列表文件分析该算法的效果。加入算法前URL 列表如图 4-1-4，加入算法后 URL 列表如图 4-1-5。图 4-1-4 加入算法前 URL 列表在加入前爬虫爬取的内容过于深入，持续采集http:/ URL，采集过程中甚至还出现了像9http:/ 这样过于深入而用处不大的 URL，而重要的 URL 却迟迟得不到光顾。在加入“重要度”算法后，爬虫的采集面更广，优先采集更重要的网页，使爬虫的采集效率得到明显提高。5 总结本文以搜索引擎技术研究为背景，开发了一个基于重要度的主题爬虫系统。然后介绍了主题爬虫技术及相关算法，在此基础上提出了一个基于重要度的主题爬虫算法，该算法将网络爬虫技术中网页重要度的结论应用到主题爬虫算法上。最后通过实验证明了该算法能采集相对更重要的网页。本文还可在以下几个方面进行改进：1)本文虽然能够采集“重要”的网页，但还不能采集与主题“相关”的网页，如在计算URL优先级时加入对“相关度”的计算，就能完成真正的主题爬虫了。2)还需多进行对网页更新频率的研究，让爬虫定时的更新网页。
