中南大学电子商务实验三(共16页)

1、PAGE PAGE 22电子商务应用实验报告项目名称 搜索引擎及SEO实验 专业班级 软件1203 学 号 姓 名 实验成绩：批阅教师：2014年12 月26 日实验(shyn)3搜索引擎及SEO实验(shyn)实验(shyn)学时： 2 实验地点： 二综203 实验日期： 2014/12/26 一、实验目的研究并学习几种常见的搜索引擎算法，包括网络蜘蛛爬行策略、中文分词算法、网页正文提取算法、网页去重算法、PageRank和MapReduce算法，了解它们的基本实现原理；运用所学SEO技术对网页进行优化。二、实验内容和方法1. 研究常用的网络蜘蛛爬行策略，如深度优先策略、广度优先策略、网页选

2、择策略、重访策略和并行策略等，了解其实现原理；2. 研究至少两种中文分词算法，了解其实现原理；3. 研究至少两种网页正文提取算法，了解其实现原理；4. 研究至少两种网页去重算法，了解其实现原理；5. 研究Google的PageRank和MapReduce算法，了解它们的实现原理；6. 使用所学的SEO技术，对实验二所设计的网站静态首页实施SEO，在实施过程中需采用如下技术：(1) 网页标题(title)的优化；(2) 选取合适的关键词并对关键词进行优化；(3) 元标签的优化；(4) 网站结构和URL的优化；(5) 创建robots.txt文件，禁止蜘蛛抓取网站后台页面；(6) 网页内部链接的优

3、化；(7) Heading标签的优化；(8) 图片优化；(9) 网页减肥技术。7. 使用C+、C#和Java等任意一种编程语言，设计并实现一个简单的网络蜘蛛爬行程序，要求在输入关键词、设置爬行深度和初始网页URL之后能够实现网页搜索，输出包含关键词的网页的URL和网页标题。【注：实验7为补充实验，不要求每个同学都完成，感兴趣者可自行实现该程序，不计入实验报告评分。】三、实验(shyn)要求(yoqi)1. 研究几种常用的网络蜘蛛爬行策略，填写相应(xingyng)的表格，表格必须填写完整；2. 研究两种中文分词算法，填写相应的表格，表格必须填写完整；3. 研究两种网页正文提取算法，填写相应的表

4、格，表格必须填写完整；4. 研究两种网页去重算法，填写相应的表格，表格必须填写完整；5. 研究PageRank算法和MapReduce算法，填写相应的表格，表格必须填写完整；6. 提供实施SEO之后的网站静态首页界面和HTML代码，尽量多地使用所学SEO技术；7. 严禁大面积拷贝互联网上已有文字资料，尽量用自己的理解来阐述算法原理，必要时可以通过图形来描述算法；8. 使用任意一种编程语言实现一个简单的网络蜘蛛程序，需提供网络蜘蛛程序完整源代码及实际运行结果。四、实验步骤1. 通过使用搜索引擎并查阅相关资料，研究并整理几种常用的网络蜘蛛爬行策略相关资料，填写相应的表格；2. 通过使用搜索引擎并查

5、阅相关资料，研究并整理两种中文分词算法的基本原理，填写相应的表格；3. 通过使用搜索引擎并查阅相关资料，研究并整理两种网页正文提取算法的基本原理，填写相应的表格；4. 通过使用搜索引擎并查阅相关资料，研究并整理两种网页去重算法的基本原理，填写相应的表格；5. 通过使用搜索引擎并查阅相关资料，研究并整理PageRank算法和MapReduce算法的基本原理，填写相应的表格；6. 对实验二所设计的网站静态首页实施SEO；7. 使用任意一种编程语言，设计并实现一个简单的网络蜘蛛(zh zh)爬行程序。五、实验(shyn)结果1. 研究几种常用(chn yn)的网络蜘蛛爬行策略并填写如下表格：策略名称

6、基本原理参考资料深度优先策略深度优先遍历图的方法是，从图中某顶点v出发：（1）访问顶点v；（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。1百度百科：深度优先搜索/view/288277.htm广度优先策略已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶

7、点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。1百度百科：广度优先搜索/view/288267.htm网页选择策略对搜索引擎而言，要搜索互联网上所有的网页几乎不可能，即使全球知名的搜索引擎google也只能搜索整个Internet网页的30左右。其中的原因主要有两方面，一是抓取技术的瓶颈。网络爬虫无法遍历所有的网页；二是存储技术和处理技术的问题。因此，网络爬虫在抓取网页时。尽量先采集重要的网页，即采用网页优先抓取策略。网页选择策略是给予重要程度、等级较高的Web页以较高的抓取优先级，即Web页越重要，则越应优先抓取。其实质

8、上是一种使网络爬虫在一定条件下较快地锁定互联网中被用户普遍关注的重要信息资源的方法。而实现该策略的前提是正确评测Web页的重要程度bJ，目前评测的主要指标有PageRank值、平均链接深度等。1李志义. 网络爬虫的优化策略探略.现代情报. 2011,31(10)重访策略1)依据Web站点的更新频率确定重访频率此法符合实际情况，能够更有效地管理和利用网络爬虫。例如，门户网站通常每天要不断地更新信息和添加新的信息，重访的频率则以天或小时为周期进行网页的重访。(2)不关心Web站点的更新频率问题，而是间隔一段时间重访已被抓取的冈页。其弊端是重复抓取的概率大，容易造成不必要的资源浪费。(3)根据搜索引

9、擎开发商对网页的主观评价，提供个性化的服务网页的重访需要搜索引擎开发商对主要的站点进行网页更新频率的主观评价，可以根据需求提供个性化的服务。1李志义. 网络爬虫的优化策略探略.现代情报. 2011,31(10)并行策略实施并行策略的核心是在增加协同工作的爬虫数量的同时，科学合理地分配每个爬虫的任务，尽量避免不同的爬虫做相同的Web信息抓取。一般通过两种方法来分配抓取任务，一是按照Web站点所对应的m地址划分任务，一个爬虫只需遍历某一组地址所包含Web页即可；另一种方法是依据Web站点的域名动态分配爬行任务，每个爬虫完成某个或某些域名段内Web信息的搜集。1李志义. 网络爬虫的优化策略探略.现代

10、情报. 2011,31(10)注：参考资料格式(g shi)如下：1 developerWorks中国(zhn u)：Java 设计模式. /developerworks/cn/java/design/.2 阎宏. Java与模式. 北京(bi jn): 电子工业出版社, 2004.3 于满泉, 陈铁睿, 许洪波. 基于分块的网页信息解析器的研究与设计. 计算机应用, 2005, 25(4).2. 研究两种中文分词算法并填写如下表格：算法名称基本原理参考资料基于词典的方法定义:按照一定策略将待分析的汉字串与一个“大机器词典”中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。按照扫描方向的

11、不同：正向匹配和逆向匹配按照长度的不同：最大匹配和最小匹配1 中文分词算法笔记 - abstractwind - 博客园: /lvpei/archive/2010/08/04/1792409.html基于统计的分词（无字典分词）主要思想：上下文中，相邻的字同时出现的次数越多，就越可能构成一个词。因此字与字相邻出现的概率或频率能较好的反映词的可信度。主要统计模型为：N元文法模型（N-gram）、隐马尔科夫模型(Hidden Markov Model, HMM)1 中文分词算法笔记 - abstractwind - 博客园: /lvpei/archive/2010/08/04/1792409.ht

12、ml3. 研究两种网页正文(zhngwn)提取算法(sun f)并填写如下(rxi)表格：算法名称基本原理参考资料算法一基于相似度的中文网页正文提取算法正文文本在HTML源文件中有两种修饰方式：有标签提示和无标签提示。有标签文本中标签的作用一般包含分块信息、表格信息、或者文本的字体颜色信息等。这种文本采用基于分块的方法能有不错的效果。而无标签信息的正文文本处理之后不在分块中，也不在表格内。采用先分块后提取放入网页正文提取方法，无法达到理想的精度。本文提出根据相似度来提取网页正文的算法。算法分为两个步骤：首先取出网页中包含中文最多的行，然后利用鉴于此余弦相似度匹配和标签相似度来提取网页正文。该算

13、法最大的特点是避免了上述的分块步骤。1熊子奇，张晖林，茂松(西南科技大学计算机科学与技术学院四川绵阳621010)基于相似度的中文网页正文提取算法基于FFT的网页正文提取算法研究与实现给定一个底层网页的HTML源文件，求解最佳的正文区问。对于任何字符串区间(b,e),(O6ess为源文件的长度S为源文件)，都有一个评价值，问题转化为求评价函数的最大解。1李蕾，王劲林，白鹤，胡晶晶.基于FFT的网页正文提取算法研究与实现4. 研究两种网页去重算法并填写如下表格：算法名称基本原理参考资料基于正文结构和长旬提取的网页去重算法首先对网页进行必要的去噪处理；其次将网页正文通过正文结构树生成算法表示成一棵

14、正文结构树，然后动态地、层次地从树中抽取段落作为长句提取算法的输入得到层次指纹；最后通过层次指纹的相似度计算算法得到网页的相似度，从而实现镜像网页和近似镜像网页的检测。动态地、分层地对正文进行特征抽取和层次指纹计算，保证了去重算法的效率；通过长句提取算法得到节点指纹，保证了算法的鲁棒性。1 黄仁，冯胜，杨吉云，刘宇，敖民. 基于正文结构和长旬提取的网页去重算法. 计算机应用研究. 2010,27(7)基于MD5的网页去重算法的设计与研究(1)剔除大文本块中网页编辑中产生的噪音，如空格等标点符号，得到结果字符串。提取网页中所有的文本块，每一个文本块形成一个(Pa，doclD)二元组，并对二元组按

15、照Pa进行排序，即从大到小进行排序，抽取排序结果中的前i个文本块，若该网页文档数不足i个，则取该网页文档的全部分块。将抽取出的二元组中的Pa算出MD5摘要，将产生的(PaMD5，doclD)存储到MD5DocID文件当中。(2)将MD5DoclD文件按照二元组(PaMD5，doclD)中的第一个元素PaMD5进行一次排序。(3)遍历排序后的MD5DoclD文件，如果MD5是一个具体的摘要，文档di、dj是doclD，假如排序后的MD5DoclD文件中出现(MD5，di)(MD5，dj)，那么将会产生二元组(di，dj)，并追加到文件doclD中去，这将说明文档di和dj中有一个MD5是相同的。

16、(4)对doclD进行排序，以便使相同的(di，dj)出现在一起。统计doclD，如果(di，aj)在文件doclD中出现的次数大于一定的阈值数T，则认为文档di和文档dj互为镜像。(5)提取结果字符串的MD5指纹值作为该网页的指纹。比较两个网页的MD5指纹值，如果相同则认为这两个网页为相似网页，可进行去重处理。1 闫俊伢. 基于MD5的网页去重算法的设计与研究. 实验室研究与探索. 2013, 32(12)5. 研究(ynji)PageRank算法(sun f)和MapReduce算法(sun f)并填写如下表格：算法名称基本原理参考资料PageRank一个页面的“得票数”由所有链向它的页面

17、的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（“链 入页面”）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级.1 百度百科PageRank： /link?url=YMuU0fOL7Jq_Ps8rGpPPRpiHjdf4xKpHGd_t074VGMNV9hBWxLdlJGfatM9MlFJSbKa-3NYVO7CQxoQer9m23Cj94UMumduALNOorfZAIlntCN1LFnJ0Lb2uslTL2H6lTTIBdMJ70sLF_P0HKcAFcq#2MapRed

18、uce1.MapReduce库先把user program的输入文件划分为M份（M为用户定义），每一份通常有16MB到64MB，如图左方所示分成了split04；然后使用fork将用户进程拷贝到集群内其它机器上。2.user program的副本中有一个称为master，其余称为worker，master是负责调度的，为空闲worker分配作业（Map作业或者Reduce作业），worker的数量也是可以由用户指定的。3.被分配了Map作业的worker，开始读取对应分片的输入数据，Map作业数量是由M决定的，和split一一对应；Map作业从输入数据中抽取出键值对，每一个键值对都作为参数传递

19、给map函数，map函数产生的中间键值对被缓存在内存中。4.缓存的中间键值对会被定期写入本地磁盘，而且被分为R个区，R的大小是由用户定义的，将来每个区会对应一个Reduce作业；这些中间键值对的位置会被通报给master，master负责将信息转发给Reduce worker。5.master通知分配了Reduce作业的worker它负责的分区在什么位置（肯定不止一个地方，每个Map作业产生的中间键值对都可能映射到所有R个不同分区），当Reduce worker把所有它负责的中间键值对都读过来后，先对它们进行排序，使得相同键的键值对聚集在一起。因为不同的键可能会映射到同一个分区也就是同一个Re

20、duce作业（谁让分区少呢），所以排序是必须的。6.reduce worker遍历排序后的中间键值对，对于每个唯一的键，都将键与关联的值传递给reduce函数，reduce函数产生的输出会添加到这个分区的输出文件中。7.当所有的Map和Reduce作业都完成了，master唤醒正版的user program，MapReduce函数调用返回user program的代码。1 百度百科MapReduce： /link?url=AV23qA-ivHn3MVHNU5WOPS11xJd9yjWldrwZMWJVo8zvwTwcKnRwUoLeaf-VPUND9Dc8MR9sSMwbElHtEzkWuK6. 提供通过SEO优化之后的网站首页静态(jngti)效果图和完整的HTML源代码。http：/www.boxuebookstore/onlinebookstore/index.html博学图书城_网上书店_图书 博学图书城图书搜索: 著作名按作