版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
搜索引擎技术主讲教师：王旭博士深圳大学计算机与软件学院未来媒体技术与计算研究所Email:wangxu@1模块一：商用搜索引擎架构与原理搜索引擎基础网页抓取技术网页信息预处理技术信息索引技术信息查询与评价技术参考书籍：袁津生，李群编著，《搜索引擎基础教程》，清华大学出版社其他文献/互联网资料深圳大学未来媒体技术与计算研究所2Scrapy:基于Python的爬虫框架Scrapy是使用Python开发的一个速度快、效率高的web和屏幕数据抓取的框架,多用于抓取web站点并从结构复杂的Web页面中提取出结构化的数据。Scrapy的用途非常广泛,可以用于自动化测试、监测、数据挖掘等任务。Scrapy的底层是基于Twisted网络引擎,用户只需要开发其中的几个模块就可以实现一个功能相当复杂的web爬虫,可以用来进行网页信息抽取和抓取网站上的图片等。使用Scrapy的优势是开发相对简单,信息抽取以后还可以利用Python丰富的第三方库进行后续数据处理和展示。官方网站：/安装指南：/en/latest/intro/install.htmlWiKi:/scrapy/scrapy/wiki/moin/BeginnersGuide/NonProgrammers/zh_CN/latest/intro/overview.htmlScrapy:基于Python的爬虫框架Built-insupportforselectingandextractingdatafromHTML/XMLsourcesusingextendedCSSselectorsandXPathexpressions,withhelpermethodstoextractusingregularexpressions.Aninteractiveshellconsole(IPythonaware)fortryingouttheCSSandXPathexpressionstoscrapedata,veryusefulwhenwritingordebuggingyourspiders.Built-insupportforgeneratingfeedexportsinmultipleformats(JSON,CSV,XML)andstoringtheminmultiplebackends(FTP,S3,localfilesystem)Robustencodingsupportandauto-detection,fordealingwithforeign,non-standardandbrokenencodingdeclarations.Strongextensibilitysupport,allowingyoutopluginyourownfunctionalityusingsignalsandawell-definedAPI(middlewares,extensions,andpipelines).Widerangeofbuilt-inextensionsandmiddlewaresforhandling:–cookiesandsessionhandling–HTTPfeatureslikecompression,authentication,caching–user-agentspoofing–robots.txt–crawldepthrestrictionScrapy:基于Python的爬虫框架库Windows下的Scrapy安装和环境搭建检查PlatformspecificinstallationnotesPython
2.7pip
and
setuptools
Pythonpackages.Nowadays
pip
requiresandinstalls
setuptools
ifnotinstalled.lxml.MostLinuxdistributionsshipsprepackagedversionsoflxml.Otherwiserefertohttp://lxml.de/installation.htmlOpenSSL.Thiscomespreinstalledinalloperatingsystems,exceptWindowswherethePythoninstallershipsitbundled.具体步骤安装Python2.7:
/downloads/在命令行下，添加环境变量：
c:\python27\python.exec:\python27\tools\scripts\win_add2path.py
测试python版本
python--version安装pywin32:/projects/pywin32/安装pip:https://pip.pypa.io/en/latest/installing.htmlpip–version安装IPython安装scrapypipinstallScrapyScrapy使用：基本教程新建一个新的scrapy工程建议需要提取的item对象写一个spider抓取相关的网站和提取items写一个ItemPipeline存储提取的itemsScrapy基本教程：新建工程打开命令行窗口，转到指定路径下输入：scrapystartprojecttutorialScrapy基本教程：定义Item修改文件:item.pyScrapy基本教程：新建spider在“spiders”文件夹下新建一个文件:tutorial.pyScrapy基本教程：新建spider进入到当前文件夹cd<path>在命令行下键入以下命令scrapycrawltutorial结果在文件中查看Scrapy基本教程：提取网页中的数据Selectors类：从网页中提取数据Scrapy基于Xpath(XMLPathLanguage)和CSS/html/head/title选择包含在<head>中的<title>信息/html/head/title/text()选择文本信息//td选择所有的<td>//div[@class=“mine”]选择所有clase=“mine”的divScrapy基本教程：提取网页中的数据在命令行中键入下列命令scrapyshell/Computers/Programming/Languages/Python/Books/可以查看的对象Scrapy基本教程：提取网页中的数据查看数据，例子response.xpath('//title')response.xpath('//title').extract()response.xpath('//title/text()')response.xpath('//title/text()').extract()退出控制台命令：exit()Scrapy基本教程：提取网页中的数据在“spiders”文件夹下新建dmoz.pyScrapy基本教程：保存数据保存数据scrapycrawldmoz-oitems.json具体例子参考：/scrapy/dirbot作业一（选择一）编程实践作业：基于Scrapy框架，学习如何抓取一个网页或者网站，并完成实验报告截止日期：2015.10.25相似度要求：50%以上相似，不合格；增加两点以上的功能，功能越多，分数越高实验报告+源程序基础分15分(报告完整，代码可执行)，总分：20分作业一（选择二）实践作业：基于搜索引擎和个人兴趣，调研社交搜索或者垂直搜索，完成一份行业调研和综述报告。截止日期：2015.10.251、字数：3000字2、相似度要求：大于30%以上不合格；3、基础分15分，总分20分4、OralPresentation加5分模块一：商用搜索引擎架构与原理搜索引擎基础网页抓取技术网页信息预处理技术信息索引技术信息查询与评价技术参考书籍：袁津生，李群编著，《搜索引擎基础教程》，清华大学出版社其他文献/互联网资料深圳大学未来媒体技术与计算研究所20深圳大学未来媒体技术与计算研究所网页信息预处理4.1网页信息结构化4.2文本处理4.3PageRank算法21深圳大学未来媒体技术与计算研究所网页信息预处理技术对于信息预处理系统来说，最主要的工作就是从抓取的网页中提取有价值的，能够代表网页的属性（如网页的URL、编码类型、标题、正文、关键词等），并将这些属性组成一个网页的对象。然后根据一定的相关度算法进行大量复杂的计算，得到每一个网页针对页面内容及链接每一个关键词的相关度，并用这些信息建立索引数据库。从网页中提取关键词，至少要作两部分的工作：一是将网页的源代码整理成一个可以有层次的、利于分析的、包含原始网页中的各种属性的网页对象，即DOM树；二是从整理出来的网页对象中提取文本内容，将这些文本内容切分成以词为单位的集合。22深圳大学未来媒体技术与计算研究所网页信息结构化结构化数据是指被标签定义了其内容、意义和用法的数据。结构化数据除了包含数据本身之外，一般还包含对数据的描述信息，而且其中的数据与描述信息都按照严格的规则进行组织。语法上不具有层次特点的数据称为非结构化数据。介于结构化数据和非结构化数据之间的数据称为半结构化数据。结构化的数据模型可以用二维表（关系型）来表示，半结构化数据模型可以用树和图来表示，非结构化数据没有数据模型。结构化数据的特点是先有结构、再有数据，半结构化数据的特点是先有数据，再有结构。典型的结构化数据的格式有：XML、XHTML、INI等，半结构化数据的格式有：HTML。23深圳大学未来媒体技术与计算研究所网页结构化的目标网页结构化的目标是根据搜索的需要，将半结构化的HTML网页中的数据按照约定的基本属性组合成一个网页的对象。一个网页对象至少有5个属性：（1）锚文本（anchortext）（2）标题（title）（3）正文标题（contenttitle）（4）正文（content）（5）正向链接（link）24深圳大学未来媒体技术与计算研究所建立一个简单的HTML文件，文件名为：index.html。<html><head><metahttp-equiv="Content-Type"content="text/html;charset=gb2312"><title>搜索引擎基础教程</title></head><body><table><tr><td>搜索引擎基础教程：第1章</td></tr><tr><td>搜索引擎基础教程：第2章</td></tr><tr><td>搜索引擎基础教程：第3章</td></tr></table></body></html>25深圳大学未来媒体技术与计算研究所26深圳大学未来媒体技术与计算研究所建立DOM树DOM的全称是DocumentObjectModel，也即文档对象模型。我们在使用过程中，首先要将HTML网页转换成XML格式，然后使用XML分析器将一个XML文档转换成一个对象模型的集合（通常称DOM树）。应用程序正是通过对这个对象模型的操作，来实现对XML文档数据的操作。通过DOM接口，应用程序可以在任何时候访问XML文档中的任何一部分数据，因此，这种利用DOM接口的机制也被称作随机访问机制。/xml
27深圳大学未来媒体技术与计算研究所1．网页内容的DOM树表示28深圳大学未来媒体技术与计算研究所2．DOM树的建立过程HTML语法中，各种标签都是成对出现的，这样我们可以分析一个标记的始末。因此，在解析网页的过程中需要一个标签分析栈的数据结构。栈结构是一种先进后出的线性表结构，栈结构的这种特性为分析工作提供了可能。具体步骤如下：（1）建立标签分析栈（2）顺序读取网页标签并依次入栈（3）文本结点不入栈（4）成对标签同时退栈DOM树建立以后，遍历树中的每个结点，将其中的文本送到分词模块进行处理。29深圳大学未来媒体技术与计算研究所网页内容的获取1．正文分块正文具有分块保存的特性，因此我们引入文本块的概念，对于那些诸如<P></P>等标签间的文本认为是一个文本块。例如<TD>搜索引擎基础教程：第1章</TD>称为一个文本块。一般来说，网页会出现3种类型的文本块。（1）主题型文本块主题型文本块是大段文字的文本块，如：“<TD>搜索引擎基础教程：第1章</TD>”（2）目录型文本块目录型文本块是描述链接的文本块，如：“<ahref=””>搜索引擎基础教程：第1章</a>”（3）图片型文本块 图片型文本块是描述图片的文本块，如：“<imgsrc=””>搜索引擎基础教程：第1章</img>”30深圳大学未来媒体技术与计算研究所网页内容的获取2．投票算法目录型文本块和图片型文本块相对容易被区分；而主题型文本块中可能包含广告等其他内容，必须与正文相区别。判断哪个文本块是正文采用称为”投票算法”的计算方法，这种方法在搜索引擎中特别常用。投票算法的过程是：首先定义一系列规则，然后通过这些规则为每一个文本块打分。得分最高的被认是正文的可能性足够大，并且可以接受。31深圳大学未来媒体技术与计算研究所网页内容的获取3．提取正文打分之后的工作就是将一个个文本块组织成一个正文。深度优先遍历DOM树并依次记录主题类型的文本块，即可得到该网页的正文。如图4-2所示，按照深度优先，我们可以依次提取文本块并按照顺序组织成正文“搜索引擎基础教程：第1章搜索引擎基础教程：第2章搜索引擎基础教程：第3章”。32深圳大学未来媒体技术与计算研究所4.2文本处理文本预处理文本词法分析中文分词33深圳大学未来媒体技术与计算研究所文本预处理的过程（1）文本的词法分析，它主要是对文本中的数字、连接符、标点符号和字符的大小写进行处理；（2）无用词汇的删除，它主要是过滤掉那些对于信息获取过程来说区分能力低的词汇；（3）词干提取，它主要是去除词缀（前缀和后缀），这样可以允许所获取的文档包含一些查询词条的变换形式；（4）索引词条/词干的选择，在选择的时候通常按照单词的习惯用法，实际上名词往往要比形容词、副词和动词包含更多的语义；（5）构造词条的分类结构，例如词典或者结构抽取，利用它可以进行查询的扩展。34深圳大学未来媒体技术与计算研究所文本的词法分析词法分析的过程是将字符串（文档中的文本）转换成词条的过程，这些词条可能被用来作为索引词条。因此词法分析的主要目的就是识别文本中的词条。在对英文进行分词的过程中，除了空格分隔符，还有几种特殊的情况要处理：数字、连字符、标点符号和字母的大小写。数字一般不适合用作索引词条，因为对于数字来说，如果不参考上下文，它就没有明确的含义。35深圳大学未来媒体技术与计算研究所文本的词法分析连字符的处理，目前常用的是首先采用一定的规则选出那些对词义有影响的连字符号，然后将其他的连字符都过滤掉。文本中标点符号的处理，在词法分析过程中将被全部去除。但是，对于那些成为单词中一部分的标点符号来说，一般不可以去除。字母的大小写处理，可以将文本中的所有词条都转换成大写或者小写。但是在某些特殊情况下，也需要对大小写进行区分。36深圳大学未来媒体技术与计算研究所中文分词技术所谓分词，指的就是将一个完整的句子划分为一个个词条的过程。这种词条应当满足某种语言规则，以便于为其建立索引。1．中文分词的方法单字切分：就是按照中文一个字、一个字地进行分词。二分法：就是指每两个字进行一次切分。词库分词：就是用一个已经建立好的词的集合去匹配目标，当遇上集合中已经存在的词时，就将之切分出来。37深圳大学未来媒体技术与计算研究所中文分词技术2．中文分词的系统评价用户相应度：主要指用户对这项技术的满意度。兼容性：能在不同的系统中都可以毫无障碍地使用，而且能给各行各业都带来方便。准确率：是分词系统性能的核心指标，系统的准确率越高越好。准确率（p）=切分结果中正确分词数/切分结果中所有分词数*100%38深圳大学未来媒体技术与计算研究所中文分词技术运行效率：在分词系统中分词的工作消耗的时间应尽量少，使用户没有等待的感觉。适用性：好的分词系统具有良好的适用性，可以方便地集成在各种各样的汉语信息处理系统中。通用性：中文分词系统必须具有很好的通用性。中文分词系统应支持不同地区的汉语处理；应能适应不同地区的不同用字、用词，不同的语言风格。39深圳大学未来媒体技术与计算研究所中文分词技术3．中文分词算法中文分词的算法主要有：正向最大匹配、逆向最大匹配、双向最大匹配、最佳匹配法、最少分词法、词网格算法、逐词遍历法、设立切分法、有穷多层次列举法、二次扫描法、邻接约束法、邻接知识约束法和专家系统法等等。现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。40深圳大学未来媒体技术与计算研究所基于字符串匹配的分词方法这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。41深圳大学未来媒体技术与计算研究所基于字符串匹配的分词方法①最大匹配法（ForwardMaximumMatchingmethod，FMM）FMM算法是正向最大匹配算法，它是基于字符串匹配的一种分词方法，其主要的算法思想是，选取包含6~8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从左向右。42深圳大学未来媒体技术与计算研究所基于字符串匹配的分词方法②逆向最大匹配法（BackwardMaximumMatchingmethod，BMM）基于字符串匹配的一种分词方法，基本算法和正向最大匹配法相似，只是匹配的方向是从左到右，它的算法比FMM的精确度高一些。③双向匹配法（Bi-directionMatchingmethod，BM）对FMM法和BMM法结合起来的算法称为双向匹配法，这种速算法通过比较两者的切分结果，来决定正确的切分，而且可以识别出分词中的交叉歧义。43深圳大学未来媒体技术与计算研究所基于字符串匹配的分词方法④最少匹配算法（FewestWordsMatching，FWM）实现的分词结果中含词数最少，它和在有向图中搜索最短路径很相似。控制首先要对所选的语料进行分段，然后逐段计算最短路径，得到若干个分词结果，最后进行统计排歧，确定最理想的分词结果。44深圳大学未来媒体技术与计算研究所基于字符串匹配的分词方法⑤网格分词算法基于统计性的一种分词算法，它的算法思想是：首先构造候选词网格，利用词典匹配，列举输入句子所有可能的切分词语，并且以词网格形式保存；然后计算词网格中的每一条路径的权值，权值通过计算图中每一结点得一元统计概率和结点之间的二元统计概率的相关信息；最后根据搜索算法在图中找到一条权值最大的路径，作为最后的分词结果。45深圳大学未来媒体技术与计算研究所基于理解的分词方法这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。46深圳大学未来媒体技术与计算研究所基于统计的分词方法从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。47深圳大学未来媒体技术与计算研究所分词中的难题在中文分词过程中，有两大难题。（1）歧义识别歧义是指同样的一句话，可能有两种或者更多的切分方法。（2）新词识别新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但又确实能称为词的那些词。48深圳大学未来媒体技术与计算研究所无用词汇的删除在信息库的文档中太频繁出现的单词将不会成为具有良好区分能力的词汇。实际上，如果一个单词出现在信息库中80％的文档中，该单词对于信息获取过程来说根本没用，这些词统称为无用词汇。在选择索引词条的时候，这些词条常常被过滤掉。删除无用词汇对于信息获取来说具有重要意义，它可以大大缩小索引空间的大小，而且空间的缩小一般可以在40％左右。49深圳大学未来媒体技术与计算研究所词干提取技术在用户查询过程中，经常会发生如下情况：用户输入词汇是信息库中某个相关文档中词汇的一种变形，词汇的变形可以是该词的复数、动名词或过去分词形式等。所谓词干是单词的一部分，是去除词的前缀和后缀后剩下的部分。词干提取技术可以分为4种：词缀删除、表格查询、后续变形和N个字符列。50深圳大学未来媒体技术与计算研究所索引词条的选择在全文索引中，对所有的词条都要建立索引。但是，对有些无用词条建立索引将浪费系统的索引空间，而且影响系统的检索性能，因此并不一定对文档中出现的所有词条都建立索引，而是选择一些比较重要的词条来建立索引。句子一般是由名词、代词、冠词、动词、形容词、副词、介词和连词构成。在这些词中，主要是由名词表达句子的语义的，因此选择句子中的名词来作为索引词条是一种可行的方法。51深圳大学未来媒体技术与计算研究所词典词典是用来根据词汇找到对应词汇信息的数据汇编。词典的主要作用是：（1）提供索引和搜索的标准词汇；（2）帮助用户使用合适的查询词汇；（3）提供分类层次结构，这样可以根据用户的需求来扩大或者缩小查询请求。词典的主要组成部分是索引词、词语之间的关系以及编排的方式。52深圳大学未来媒体技术与计算研究所词典索引词是词典的索引单元。通常来说，词典中的一个词语表示一个概念，它是表达观点的基本语义单元。词语可以使一个单词、一组词和短语。一个词语相关索引词的集合是由同义词和近义词组成的，另外还可以包含相关索引词之间的关系。利用词典对用户的查询进行适当的扩展53深圳大学未来媒体技术与计算研究所4.3PageRank算法54深圳大学未来媒体技术与计算研究所PageRankPageRank是Google的创始人LarryPage发明的一种网页级别的算法。Google的PageRank根据网站的外部链接和内部链接的数量和质量来衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。55深圳大学未来媒体技术与计算研究所PageRank一个网页多次被引用，则可能是很重要的；如果一个网页没有被多次引用，但是如果被重要的网页引用，也有可能是重要的网页。一个网页的重要性被平均地传递到它所引用的网页上，这种网页称为权威（Authoritive）网页。网页重要性的评价主要有三种：（1）认可度越高的网页越重要，即反向链接越多的网页越重要。（2）反向链接的源网页质量越高，被这些高质量网页的链接指向的网页越重要。（3）链接数越少的网页越重要。56深圳大学未来媒体技术与计算研究所PagePank的算法1．PageRank算法1其中：PRn(A)是网页A的PageRank值，PRn-1（Ti）是指网页Ti存在指向A的链接，并且网页在上一次迭代时的PageRank值，C（Ti）是指网页Ti的外链数量。可见，首先，PageRank并不是将整个网站排等级，而是以单个页面计算的。其次，页面A的PageRank值取决于那些连接到A的页面的PageRank的递归值。57深圳大学未来媒体技术与计算研究所
PageRank示例58深圳大学未来媒体技术与计算研究所PagePank的算法2．PageRank算法2假定用户一开始随机地访问网页集合中的一个网页，以后跟随网页的向外链接向前浏览网页，而不回退浏览，浏览下一个网页的概率就是被浏览网页的PageRank值。基于以上的原理，算法1可改进为以下的公式：59深圳大学未来媒体技术与计算研究所PageRank的特性假定存在如图所示简单的网页链接关系。假
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论