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