基于SharkSearch算法的主题网络爬虫搜索工具的设计与实现
基于SharkSearch算法的主题网络爬虫搜索工具的设计与实现[20191207151544]
摘要
随着web2.0的日趋成熟，互联网上的信息每天以爆炸式的速度疯狂增长，这一方面给人们提供了越来越丰富多彩的信息，而另一方面人们通过传统搜索引擎获取某一专业领域有用信息却越来越难。主题搜索引擎应运而生，它提供了更加精确更加专业的搜索结果，而主题网络爬虫则是主题搜索引擎的核心。近期“棱镜门”的爆料人斯诺登表示其就是通过主题爬虫获取了近20万份的最高机密文件，这充分展示出了主题爬虫的强大力量。
本文所实现的主题网络爬虫采用了SharkSearch算法对URL的potential值进行计算，然后使用Berkeley DB对URL进行大容量的内存高速数据存储，而且在Berkeley DB的基础上实现了以potential值来衡量的优先队列。采用MySQL数据库来存储已爬取的网页的信息。同时为了更加高效的判断已访问的URL地址，实现了可固化的布隆过滤器。最后通过使用SVM构造一个分类器来测试软件爬取的性能。
关键字:互联网主题爬虫数据挖掘SharkSearchBerkeleyDBMySQL 6.1获取关键词 33 A）Fish-Search算法,于1994年由DeBra等人在2004年提出,它是最早的网络爬虫系统之一,该算法用一组初始设定好的关键词与页面文本进行相关性比较从而判定是否把该页面上的链接加入到待爬行队列。该算法的优点是简单易用,同时无法找到最优的子URL进行爬取是其最大的缺点。 其中d（0
目 录
1.绪论 1
1.1课题研究的目的及意义 1
1.2国内外相关技术发展现状 1
1.3本文主要内容 2
1.4论文组织结构 3
2.网络爬虫以及相关研究 4
2.1搜索引擎技术 4
2.1.1 搜索引擎的发展 4
2.1.2搜索引擎的基本结构 5
2.2 通用网络爬虫 6
2.3主题爬虫 8
2.4网络爬虫抓取策略 9
2.4.1深度优先爬行算法 9
2.4.2 广度优先爬行算法 9
2.4.3 最佳优先算法 9
3.主题爬虫关键技术及算法 10
3.1主题表示方法 10
3.2 主题相关性判断 10
3.3 主题爬虫算法 10
3.3.1 基于页面分析 10
3.3.2 基于链接分析 13
3.4 爬虫队列 13
4.基于SharkSearch算法的主题爬虫的设计与实现 16
4.1 主题爬虫总体设计 16
4.2 爬虫队列的设计 17
4.2.1已访问URL队列 17
4.2.2未访问URL队列 18
4.3 网页爬取模块 20
4.3.1 爬取页面 20
4.3.2 网页编码问题 20
4.3.3 多线程 21
4.4 SharkSearch算法实现 23
4.4.1 子链接及锚文本的获得 23
4.4.2 文本分词 24
4.4.3 主题的输入及表示 25
4.4.4 SharkSearch算法 25
4.5 界面设计相关问题 26
5.评价主题爬虫 28
5.1 主题爬虫评价指标 28
5.2 使用SVM进行分类 28
5.2.1如何分类 28
5.2.2 学习算法 28
5.2.3 对偶问题 30
5.2.4 处理噪声 30
5.2.5 算法实现 31
6.运行与测试 33
6.2获取种子URL 33
6.3爬行 34
6.4评价 35
7.总结与展望 36
8.参考文献 37
9.致谢 38
1.绪论
1.1课题研究的目的及意义
随着近几年互联网的爆炸式发展，网络中的各种类型的数据更是让人眼花缭乱，IDC的报告显示，至2020年全世界数据总量将达到40ZB（1ZB≈1E15 GB）。而人所能接受的信息是有限的，iProspect的调查表明56.6%的搜索引擎用户只会看前3页的搜索结果。人们获取的信息越来越单一化，对于一些细分的专业领域的搜索结果并不能让人满意，主题搜索引擎应运而生，它提供了更加精确更加专业的搜索结果，而主题搜索引擎的技术核心就是主题网络爬虫。近期“棱镜门”的爆料人斯诺登表示其就是通过主题爬虫获取了近20万份的最高机密文件，这充分展示出了主题爬虫的强大潜力。
1.2国内外相关技术发展现状
各种不同主题网络爬虫的差异主要体现在URL链接的搜索策略上，比较经典的主要有基于内容的搜索策略和基于链接的搜索策略两大类。
（1）基于内容的搜索策略：主要根据网页内容或者链接周围的锚文本的信息来判断该页面或者下一层的链接与所要求的主题的相关程度来判定是否要爬取该链接的内容。主要的算法有以下几种。
B）Shark-Search算法，于1998年由Haifa实验室的Herseovic提出，该算法对Fish-Shearch进行了改进，依据链接周围锚文本的价值和从父URL 继承的价值来决定链接优先级和爬取深度。该算法的优点是可以优先爬取最优的URL从而提高了在有限时间内的搜索性能 。
（2）基于链接的搜索策略：该类算法基于来自文献计量学引文分析理论的web图搜索策略，在计算链接优先级的时候考虑了大量相关网页相互链接的信息。主要算法有以下几种。
A）PageRank算法，于1998年由google的创始人L.Page,S.Brin提出，PageRank算法不仅仅依赖于入链数量，如果某个高权值的页面链接到另外一个页面，那么这个网页的权值也较高，因此一个页面的的权值由其他页面的权值递归计算得到。其公式为
B)HITS算法，于1999年由Jon Kleinberg提出，HITS算法计算出每个页面的Authority和Hub值，这两个值的关系为：越多高Hub值的页面指向某页面P那么P的Authority值就越大，而若某页面P指向越多高Authority值的页面则P的Hub值越高。HITS算法的长处在于它能更好地描绘互联网的组织结构，因为它只是对互联网中的一个很小的子集进行分析，所以其需要的迭代次数更少，收敛速度更快，时间复杂度更小。但HITS算法也存在如下缺点：中心网页之间的相互引用以增加其网页评价，当一个网站上的多篇网页指向一个相同的链接，或者一个网页指向另一个网站上的多个文件时会引起评分的不正常增加，这会导致易受“垃圾链接”的影响；网页中存在自动生成的链接；主题漂移，在邻接图中经常包括一些和搜索主题无关的链接，如果这些链接自身也是中心网页或权威网页就会引起主题漂移；对于每个不同的查询算法都需要重新运行一次来获取结果。这使得它不可能用于实时系统，因为对于上千万次的并发查询这样的开销实在太大 。
（3）目前的研究者在设计和改进主题爬虫时运用了大量人工智能和机器学习理论。
A）“智能爬行”算法，由2001年由Aggarwal等人提出，它应用预先给定的网页分类器来指导主题爬虫不断学习和优化，用URL优先级队列进行反馈，在爬行过程中不断修正各种参数，以达到提高性能的目的 。
B)“加速主题爬虫”，于2002年由Chakrabarti提出，该爬虫使用两个分类器Critic和Apprentice。两个分类器相互协助，不断反馈修正，从而优化其爬行策略。
1.3本文主要内容
1.4论文组织结构
本文以构造一个JAVA编写的主题爬虫为基础，在设计和实现的过程中全方位地学习和研究了主题爬虫的技术，本文的结构如下：
第一章为绪论，这一章介绍了课题研究的目的和意义、国内外相关技术发展现状和本文的主要内容。
第二章介绍了现有通用网络爬虫的基本原理和工作流程，对不同的爬虫抓取策略进行介绍，然后介绍了搜索引擎技术和主题爬虫。
第三章以主题爬虫算法为核心，介绍了主题爬虫的技术原理、主题表示技术和主题相关性判断方法。
第四章详细介绍本文所构造的主题爬虫的设计与实现，主要包括爬虫队列的设计、网页爬取模块的设计、SharkSearch算法的实现和Swing界面的设计。
第五章介绍了爬虫性能的评价相关知识，并使用机器学习方法构造了一个SVM分类器对本文所实现的主题爬虫进行评价。
第六章是本文所实现主题网络爬虫的运行与测试。
2.网络爬虫以及相关研究
根据CNNIC所做的《2013 年中国网民搜索行为研究报告》，2013年下半年中国网民综合搜索网站的使用比例高达98.0% 。而藏在搜索引擎迅速而精确外表之下的关键技术就是网络爬虫，它是搜索引擎的重要组成部分之一。网络爬虫是一个能够自动下载处理页面内容的程序，网络爬虫所要做的工作就是按照网页的权重更新时间不断地扫描整个或者部分特定互联网中的网页，由于网络上信息的不断更迭，网络爬虫必须时时刻刻不断运行，而且由于网络信息量巨大所以分布式计算和存储、并行计算等技术都广泛地运用于网络爬虫。
2.1搜索引擎技术
搜索引擎（search engine）是一个通过自身庞大的数据库为用户提供信息检索功能的大型程序，以google、baidu为代表的搜索引擎利用网络爬虫在图状的网络中根据超链接的指引下载互联网上几乎全部的网页，然后对获得的数据进行分析和计算，最后根据文档中特征词来建立索引并存储到分布式数据库中，最终使用户能够快捷地得到搜索结果。
2.1.1 搜索引擎的发展
通常人们所公认的第一个搜索引擎是Archie，它是由加拿大蒙特利尔大学的Alan Emtage、Peter Deutsch、Bill Wheelan于1990年发明的。当时的互联网不像现在那样有天文数字一般的网站量，互联网分享信息和文件主要是靠ftp，Archie利用一个基于脚本的文件名称收集器来为用户提供一种根据文件名称查询文件所在的ftp地址的服务。
1994年4月斯坦福大学的David Filo和Jerry Yang创办了Yahoo。Yahoo起初并不是我们现在所使用的真正的搜索引擎，而是一种人工编辑的模式，把网站链接按照分类放在Yahoo的不同目录中来使用户快速地到达自己想要去的网站找寻想要的信息。
1998年9月Google成立，它是由斯坦福的Larry Page和Sergey Brin创立的，Google以网页作为自己的基本数据单元，运用多种高新能的算法例如著名的PageRank算法 ，来使搜索结果的准确率大大提高。Google的爬虫利用GFS 文件系统和BigTable 来存取数据，采用MapReduce 技术来分布式处理各种数据运算
而近两年来，随着开放链接数据（Linked Open Data）等项目的全面展开，语义万维网数据源的数量激增，大量RDF（Resource Description Framework）数据被发布。互联网正在从仅包含网页和网页之间超链接的文档万维网转变成包含大量描述各种实体和实体之间丰富关系的数据万维网（Web of Data）。国内外互联网搜索引擎公司纷纷以此为基础构建知识图谱，如Google知识图谱（Google Knowledge Graph），百度“知心”和搜狗的“知立方”，以此来改进搜索质量，从而拉开了语义搜索的序幕。
2.1.2搜索引擎的基本结构
一般认为搜索引擎的主要由4个部分组成：搜索器、索引器、检索器和用户接口。其基本结构图如下：
图2-1 搜索引擎基本结构图
搜索器即网络爬虫，它的任务是采集和解析互联网众多网页的信息，在剔除掉无关信息之后存储到本地为下一步的分析工作打下基础。由于互联网信息更迭迅速，所以网络爬虫必须不停运转，更加高效更加迅速的爬取各类信息，同时也要注意之前信息的定期更新。动态静态网页、图片、文档等都是网络爬虫的信息搜集目标。
索引器指对网络爬虫所得到网页信息进行处理和分析的模块，它的主要任务是对网页内容以及网络拓扑链接结构使用特定算法进行计算，得到网页中每一个词的相关度信息，并据此建立数据库。而由于中文是用“词”而不是单个的“字”来表达意思，所以中文网页的处理比英文语系的网页处理稍稍复杂一点，得到的网页内容必须先经过分词这一步。中文的分词主要有两大类方法 ：基于词典和规则、基于数据统计。基于词典和规则的具有代表性算法有正向最大匹配算法、逆向最大匹配算法、双向最大匹配法，基于数据统计的代表性算法有朴素贝叶斯方法、隐马可夫链方法。
2.2 通用网络爬虫
摘要
随着web2.0的日趋成熟，互联网上的信息每天以爆炸式的速度疯狂增长，这一方面给人们提供了越来越丰富多彩的信息，而另一方面人们通过传统搜索引擎获取某一专业领域有用信息却越来越难。主题搜索引擎应运而生，它提供了更加精确更加专业的搜索结果，而主题网络爬虫则是主题搜索引擎的核心。近期“棱镜门”的爆料人斯诺登表示其就是通过主题爬虫获取了近20万份的最高机密文件，这充分展示出了主题爬虫的强大力量。
本文所实现的主题网络爬虫采用了SharkSearch算法对URL的potential值进行计算，然后使用Berkeley DB对URL进行大容量的内存高速数据存储，而且在Berkeley DB的基础上实现了以potential值来衡量的优先队列。采用MySQL数据库来存储已爬取的网页的信息。同时为了更加高效的判断已访问的URL地址，实现了可固化的布隆过滤器。最后通过使用SVM构造一个分类器来测试软件爬取的性能。
关键字:互联网主题爬虫数据挖掘SharkSearchBerkeleyDBMySQL 6.1获取关键词 33 A）Fish-Search算法,于1994年由DeBra等人在2004年提出,它是最早的网络爬虫系统之一,该算法用一组初始设定好的关键词与页面文本进行相关性比较从而判定是否把该页面上的链接加入到待爬行队列。该算法的优点是简单易用,同时无法找到最优的子URL进行爬取是其最大的缺点。 其中d（0
目 录
1.绪论 1
1.1课题研究的目的及意义 1
1.2国内外相关技术发展现状 1
1.3本文主要内容 2
1.4论文组织结构 3
2.网络爬虫以及相关研究 4
2.1搜索引擎技术 4
2.1.1 搜索引擎的发展 4
2.1.2搜索引擎的基本结构 5
2.2 通用网络爬虫 6
2.3主题爬虫 8
2.4网络爬虫抓取策略 9
2.4.1深度优先爬行算法 9
2.4.2 广度优先爬行算法 9
2.4.3 最佳优先算法 9
3.主题爬虫关键技术及算法 10
3.1主题表示方法 10
3.2 主题相关性判断 10
3.3 主题爬虫算法 10
3.3.1 基于页面分析 10
3.3.2 基于链接分析 13
3.4 爬虫队列 13
4.基于SharkSearch算法的主题爬虫的设计与实现 16
4.1 主题爬虫总体设计 16
4.2 爬虫队列的设计 17
4.2.1已访问URL队列 17
4.2.2未访问URL队列 18
4.3 网页爬取模块 20
4.3.1 爬取页面 20
4.3.2 网页编码问题 20
4.3.3 多线程 21
4.4 SharkSearch算法实现 23
4.4.1 子链接及锚文本的获得 23
4.4.2 文本分词 24
4.4.3 主题的输入及表示 25
4.4.4 SharkSearch算法 25
4.5 界面设计相关问题 26
5.评价主题爬虫 28
5.1 主题爬虫评价指标 28
5.2 使用SVM进行分类 28
5.2.1如何分类 28
5.2.2 学习算法 28
5.2.3 对偶问题 30
5.2.4 处理噪声 30
5.2.5 算法实现 31
6.运行与测试 33
6.2获取种子URL 33
6.3爬行 34
6.4评价 35
7.总结与展望 36
8.参考文献 37
9.致谢 38
1.绪论
1.1课题研究的目的及意义
随着近几年互联网的爆炸式发展，网络中的各种类型的数据更是让人眼花缭乱，IDC的报告显示，至2020年全世界数据总量将达到40ZB（1ZB≈1E15 GB）。而人所能接受的信息是有限的，iProspect的调查表明56.6%的搜索引擎用户只会看前3页的搜索结果。人们获取的信息越来越单一化，对于一些细分的专业领域的搜索结果并不能让人满意，主题搜索引擎应运而生，它提供了更加精确更加专业的搜索结果，而主题搜索引擎的技术核心就是主题网络爬虫。近期“棱镜门”的爆料人斯诺登表示其就是通过主题爬虫获取了近20万份的最高机密文件，这充分展示出了主题爬虫的强大潜力。
1.2国内外相关技术发展现状
各种不同主题网络爬虫的差异主要体现在URL链接的搜索策略上，比较经典的主要有基于内容的搜索策略和基于链接的搜索策略两大类。
（1）基于内容的搜索策略：主要根据网页内容或者链接周围的锚文本的信息来判断该页面或者下一层的链接与所要求的主题的相关程度来判定是否要爬取该链接的内容。主要的算法有以下几种。
B）Shark-Search算法，于1998年由Haifa实验室的Herseovic提出，该算法对Fish-Shearch进行了改进，依据链接周围锚文本的价值和从父URL 继承的价值来决定链接优先级和爬取深度。该算法的优点是可以优先爬取最优的URL从而提高了在有限时间内的搜索性能 。
（2）基于链接的搜索策略：该类算法基于来自文献计量学引文分析理论的web图搜索策略，在计算链接优先级的时候考虑了大量相关网页相互链接的信息。主要算法有以下几种。
A）PageRank算法，于1998年由google的创始人L.Page,S.Brin提出，PageRank算法不仅仅依赖于入链数量，如果某个高权值的页面链接到另外一个页面，那么这个网页的权值也较高，因此一个页面的的权值由其他页面的权值递归计算得到。其公式为
B)HITS算法，于1999年由Jon Kleinberg提出，HITS算法计算出每个页面的Authority和Hub值，这两个值的关系为：越多高Hub值的页面指向某页面P那么P的Authority值就越大，而若某页面P指向越多高Authority值的页面则P的Hub值越高。HITS算法的长处在于它能更好地描绘互联网的组织结构，因为它只是对互联网中的一个很小的子集进行分析，所以其需要的迭代次数更少，收敛速度更快，时间复杂度更小。但HITS算法也存在如下缺点：中心网页之间的相互引用以增加其网页评价，当一个网站上的多篇网页指向一个相同的链接，或者一个网页指向另一个网站上的多个文件时会引起评分的不正常增加，这会导致易受“垃圾链接”的影响；网页中存在自动生成的链接；主题漂移，在邻接图中经常包括一些和搜索主题无关的链接，如果这些链接自身也是中心网页或权威网页就会引起主题漂移；对于每个不同的查询算法都需要重新运行一次来获取结果。这使得它不可能用于实时系统，因为对于上千万次的并发查询这样的开销实在太大 。
（3）目前的研究者在设计和改进主题爬虫时运用了大量人工智能和机器学习理论。
A）“智能爬行”算法，由2001年由Aggarwal等人提出，它应用预先给定的网页分类器来指导主题爬虫不断学习和优化，用URL优先级队列进行反馈，在爬行过程中不断修正各种参数，以达到提高性能的目的 。
B)“加速主题爬虫”，于2002年由Chakrabarti提出，该爬虫使用两个分类器Critic和Apprentice。两个分类器相互协助，不断反馈修正，从而优化其爬行策略。
1.3本文主要内容
1.4论文组织结构
本文以构造一个JAVA编写的主题爬虫为基础，在设计和实现的过程中全方位地学习和研究了主题爬虫的技术，本文的结构如下：
第一章为绪论，这一章介绍了课题研究的目的和意义、国内外相关技术发展现状和本文的主要内容。
第二章介绍了现有通用网络爬虫的基本原理和工作流程，对不同的爬虫抓取策略进行介绍，然后介绍了搜索引擎技术和主题爬虫。
第三章以主题爬虫算法为核心，介绍了主题爬虫的技术原理、主题表示技术和主题相关性判断方法。
第四章详细介绍本文所构造的主题爬虫的设计与实现，主要包括爬虫队列的设计、网页爬取模块的设计、SharkSearch算法的实现和Swing界面的设计。
第五章介绍了爬虫性能的评价相关知识，并使用机器学习方法构造了一个SVM分类器对本文所实现的主题爬虫进行评价。
第六章是本文所实现主题网络爬虫的运行与测试。
2.网络爬虫以及相关研究
根据CNNIC所做的《2013 年中国网民搜索行为研究报告》，2013年下半年中国网民综合搜索网站的使用比例高达98.0% 。而藏在搜索引擎迅速而精确外表之下的关键技术就是网络爬虫，它是搜索引擎的重要组成部分之一。网络爬虫是一个能够自动下载处理页面内容的程序，网络爬虫所要做的工作就是按照网页的权重更新时间不断地扫描整个或者部分特定互联网中的网页，由于网络上信息的不断更迭，网络爬虫必须时时刻刻不断运行，而且由于网络信息量巨大所以分布式计算和存储、并行计算等技术都广泛地运用于网络爬虫。
2.1搜索引擎技术
搜索引擎（search engine）是一个通过自身庞大的数据库为用户提供信息检索功能的大型程序，以google、baidu为代表的搜索引擎利用网络爬虫在图状的网络中根据超链接的指引下载互联网上几乎全部的网页，然后对获得的数据进行分析和计算，最后根据文档中特征词来建立索引并存储到分布式数据库中，最终使用户能够快捷地得到搜索结果。
2.1.1 搜索引擎的发展
通常人们所公认的第一个搜索引擎是Archie，它是由加拿大蒙特利尔大学的Alan Emtage、Peter Deutsch、Bill Wheelan于1990年发明的。当时的互联网不像现在那样有天文数字一般的网站量，互联网分享信息和文件主要是靠ftp，Archie利用一个基于脚本的文件名称收集器来为用户提供一种根据文件名称查询文件所在的ftp地址的服务。
1994年4月斯坦福大学的David Filo和Jerry Yang创办了Yahoo。Yahoo起初并不是我们现在所使用的真正的搜索引擎，而是一种人工编辑的模式，把网站链接按照分类放在Yahoo的不同目录中来使用户快速地到达自己想要去的网站找寻想要的信息。
1998年9月Google成立，它是由斯坦福的Larry Page和Sergey Brin创立的，Google以网页作为自己的基本数据单元，运用多种高新能的算法例如著名的PageRank算法 ，来使搜索结果的准确率大大提高。Google的爬虫利用GFS 文件系统和BigTable 来存取数据，采用MapReduce 技术来分布式处理各种数据运算
而近两年来，随着开放链接数据（Linked Open Data）等项目的全面展开，语义万维网数据源的数量激增，大量RDF（Resource Description Framework）数据被发布。互联网正在从仅包含网页和网页之间超链接的文档万维网转变成包含大量描述各种实体和实体之间丰富关系的数据万维网（Web of Data）。国内外互联网搜索引擎公司纷纷以此为基础构建知识图谱，如Google知识图谱（Google Knowledge Graph），百度“知心”和搜狗的“知立方”，以此来改进搜索质量，从而拉开了语义搜索的序幕。
2.1.2搜索引擎的基本结构
一般认为搜索引擎的主要由4个部分组成：搜索器、索引器、检索器和用户接口。其基本结构图如下：
图2-1 搜索引擎基本结构图
搜索器即网络爬虫，它的任务是采集和解析互联网众多网页的信息，在剔除掉无关信息之后存储到本地为下一步的分析工作打下基础。由于互联网信息更迭迅速，所以网络爬虫必须不停运转，更加高效更加迅速的爬取各类信息，同时也要注意之前信息的定期更新。动态静态网页、图片、文档等都是网络爬虫的信息搜集目标。
索引器指对网络爬虫所得到网页信息进行处理和分析的模块，它的主要任务是对网页内容以及网络拓扑链接结构使用特定算法进行计算，得到网页中每一个词的相关度信息，并据此建立数据库。而由于中文是用“词”而不是单个的“字”来表达意思，所以中文网页的处理比英文语系的网页处理稍稍复杂一点，得到的网页内容必须先经过分词这一步。中文的分词主要有两大类方法 ：基于词典和规则、基于数据统计。基于词典和规则的具有代表性算法有正向最大匹配算法、逆向最大匹配算法、双向最大匹配法，基于数据统计的代表性算法有朴素贝叶斯方法、隐马可夫链方法。
2.2 通用网络爬虫
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/qrs/165.html
