图6-14Bloomfilter算法原理
利用Bloomfilter算法可以更加经济地利用好散列表中的比特位，使得更加经济灵活地使用内存。通过’图6-14来进一步理解，对于一个字符串独立地使用m散列函数计算，然后将它位映射到散列表的m槽上。如果这m个槽都置1，说明谅字符串已经在历史上出现过；否则说明该字符串是第1次出现，将w个槽都置1。
在抓取到www.sohu.com时，假设执行3吹独立的不同的散列函数（散列1、散列2和散列3）运算。映射到散列表的3个槽上。假定是1、4和7槽位。接下来，如果爬虫又抓取到了www.sina.com，经过同样的3次散列函数运算。假定计算的结果是1、4和6。很明显可以看出槽6是之前没有被置位的，也就是说www.sina.com没有被抓取过。成功抓取www.sina.com后，将槽位6置1。Bloomfilter算法一方面提髙了散列数组的利用效率，并被证明适宜于应用在大规模集合査找计算中。同时在网络应用中也被大量采用。
不重复抓取策略的使用
在抓取过程中，可以使用多个爬虫来合作抓取，这样可以进一步降低每个爬虫的用于记录历史抓取情况的散列表大小。如果有《个爬虫；则可将散列表继续压缩到原有大小的《分之一。如果〃个爬虫分别运行在不同的机器上，那么每个机器被散列表占用的内存用量将非常少；通常保持抓取历史记录所需要的内存在百兆字节左右是恰当的。
通过不重复抓取的方法初步解决了死循环的问题，即抓过的不再抓。然而实际操作中还有这样的一个问题，如果任意两个网页存在链接，则链接它们的最短路径值为17。这样，爬虫无论用何种遍历方法都不能保证一定会按照最佳路径抓取每一个网页，因为任何一个网页都可能从多个种子站点开始广度优先被遍历到。
为了防止爬虫无限制的广度优先抓取，必须在某个深度上进行限制。到达这个深度后就应该停止抓取，这个深度的取值就是万维网直径长度。当在最大深度上停止时，那些深度过大的未抓网页，总是期望可以从其他种子站点更加经济地到达。例如，种子站点B和C在抓取到深度为17的时候，立即停止抓取，把抓取剩余网页的机会留给从种子站点A出发的进行抓取工作的爬虫。此外，深度优先策略和广度优先策略的组合可以有效地保证抓取过程中的封闭性。即在抓取过程（遍历路径）中总是在抓取相同域名下的网页，而很少出现其他域名下的网页。
网页抓取优先策略
网页抓取优先策略也称为”页面选择问题“，通常是尽可能地首先抓取重要性的网页，这样保证在有限的资源内尽可能地照顾到那些重要性高的网页。重要性度量由链接欢迎度、链接重要度和平均链接深度这3个方面决定。
链接欢迎度
链接欢迎度IB主要由反向链接的数目和质量决定。对于数目，一个网页有越多的链接指向它（反向链接数多），那么表示其他网页对其的认可度就越高，同时这个网页被访问的机会就大。这样推测出网页的重要性也就越髙。对于质量，这个网页如果被很多重要性髙的网页所指向，那么其童要性也就越髙。如果不考虑质量，就会出现局部最优，而不是全局最优的问题。最典型的就是作弊网页，人为地在一些网页中设置了大量反向链接指向其自身的网页，以提髙该网页的重要性。如果不考虑链接质量，就会被这些作弊者所利用。
链接重要度
链接重要度IUP）是一个关于URL字符串的函数，考査的是字符串本身。链接重要度主要通过一些模式来确认，如认为包含”。com“或者”home“的URL重要度高，以及具有较少斜杠的URL重要度髙等。
平均链接深度
平均链接深度为ID（P〉，表示在一个种子站点集合中，每个种子站点如果存在一条链路（广度优先遍历规则）到达该网页，那么平均链接深度就是一个重要性指标。因为距离种子站点越近，说明被访问的机会越多，因此重要性越高。可以认为种子站点是那些重要性最髙的网页，离种子站点越远，重要性越低。事实上，按照广度优先的遍历规则即可满足这种重要性髙的网页被优先抓取的需要。
网页重要性的度量为KP），它由以上两个量化值线性决定，即/=a-IB+/?-IL平均链接深度由广度优先的遍历规则保证，因此不作为重要性评价的指标。在抓取能力有限的情况下，如果能够把重要性高的网页尽可能地抓完，是合理科学的，最终被用户査询到的网页也往往是那些重要性高的网页。
除此之外，还要考虑到万维网随时间而动态变化的一面。例如，如何抓取那些新增的网页，如何重访那些被修改了的网页，如何发现那些被删除了的网页。因此，为了保持和万维网网页的同步变化，就必须有网页重访策略。通过该策略可以识别增加、修改及删除网页变化的情况。
网页重访策略
网络爬虫的任务就是不断地下载各种各样的网页，但是，网页是在不断地变化中，刚刚下载的网页有可能变化了。因此爬虫不得不周期性地刷新，重访那些已经下载的网页。通过重访以使得这些网页能够与万维网的变化一致。目前网页重访策略大致可以归为以下两类。
统一的重访策略
网络爬虫用同样的频率重访那些已经抓取的全部网页，以获得统一的更新机会，所有的网页不加区别地按照同样的频率被爬虫重访。
个体的重访策略
不同网页的改变频率不同，爬虫根据其更新频率来决定重访该个体页面的频率。即对每一个页面都量身定做一个爬虫重访频率，并且网页的变化频率与重访频率的比率对任何个体网页来说都是相等的。即对于任意网页P,，其固有的更新频率为A,（次数/单位时间）。爬虫对其重访的频率为/,，则A,//，为一个常数。即对于网页P,和P;，有关j）。那些更新髙的网页，重访频率就髙，更新频率低的网页，重访频率就低。
研究表明，网页的更新过程符合泊松过程、网页更新时间间隔符合指数分布。因此，可以对不同类型的网页采用不同的更新策略。
所谓泊松分布，是一种统计与概率学里常见到的离散机率分布，由法国数学家西莫恩？德尼？泊松（Sinton-DenisPoisson）在1838年时发表。泊松分布的概率密度函数为P（X^k）=e——A——々=0，1，2,…
其中A>0是常数，则称X服从参数为A的泊松分布。泊松分布的参数A是单位时间（或单位面积）内随机事件的平均发生率。泊松分布适合于描述单位时间内随机事件发生的次数。如某一服务设施在一定时间内到达的人数，电话交换机接到呼叫的次数，汽车站台的候客人数，机器出现的故障数，自然灾害发生的次数等。
网页抓取提速策略
网页抓取提速策略又称为合作抓取策略，通常可以采用下面几种方法。
①提髙抓取单个网页的速度。
②尽可能减少不必要的抓取任务。
③增加同时工作的爬虫数量。
对于第①种方法，单个网页的抓取速度受到下载带宽的限制，
宁波seo优化在现有技术条件下很难提高。对于第②种方法难度比较大，由于需要和万维网的变化保持紧密同步，如果要减少不必要的抓取，将会导致网页重访不及时，这样就不能快速同歩目标网页的变化。第③种方法通过增加爬虫数量而提速，目前广泛使用的是这种方法。
在多个爬虫抓取的情况下，就要解决一个网页交给哪一个爬虫抓取？如果分工不明，很可能多个爬虫抓取了相同的网页，从而引人额外的开销。通常采用以下两种方法来进行抓取任务的分解。
通过Web主机的IP地址来分解，使某个爬虫仅抓取某个地址的网页。
通过网页的域名来分解，使某个爬虫仅抓取某个域名段的网页。
对于大型网站来说，通常采用负载均衡的IP组技术，即一个域名对应于多个IP地址技术；对于小型网站来说，通常采用多个域名对应一个IP地址的技术。鉴于多域名对应相同IP和同域名对应多IP的情况，通常的做法是按照域名分解任即只要保证不重复抓取大型网站的网页，小型网站即便重复抓取也可以接受的策略分&任务。这种分配方法将不同的域名分配给不同的爬虫抓取，某一个爬虫只抓取”指定“的一个域名集合下的网页。
为了使按照域名分解的策略更加合理，在下载系统中，按照域名分解抓取任务（网页集合）的工作由一个称为”调度员“的模块来处理，通过域名分解将不同的网页调度给不同的爬虫进行抓取。因此，下载系统主要由爬虫和调度员构成。
形式化的调度分配方式如下。
首先假定有n个爬虫可以并行工作，并且定义一个可以提取URL域名的函数domain。具体过程为：
①対于任意的URL，利用domain函数提取URL的域名；②用MD5签名函数签名域名，MD5（dOmain）；③将MD5签名值对w取模這算，intspider_no=MD5（domain）%n；④该URL分配给编号为spider^no的爬虫进行抓取。
Robots协议
Robots协议是Web站点和搜索引擎爬虫交互的一种方式，robots,txt是存放在站点根目录下的一个纯文本文件。该文件可以指定搜索引擎爬虫只抓取指定的内容，或者是禁止搜索引擎爬虫抓取网站的部分或全部内容。当一个搜索引擎爬虫访问一个站点时，它会首先检査该站点根目录下是否存在robots,txt，如果存在，搜索引擎爬虫就会按照该文件中的内容来确定访问的范围，如果该文件不存在，那么搜索引擎爬虫就沿着链接抓取。
另外，robots,txt必须放置在一个站点的根目录下，而且文件名必须全部小写。
如果搜索引擎爬虫要访问的网站地址是http：//www.w3.org/，那么robots,txt文件必须能够通过http：//www.w3.org/robots,txt打开并看到里面的内容。
井robots,txtforhttp://www.w3.org/
井$Id-robots.txt,v1.482007/10/1605：31：15geraldExp$井
材Forusebysearch.w3.org
User-agent:W3C-gsa
Disallow：/Out-Of-Date
User-agent:W3TSE
Disallow：/Out-Of-Date
User-agent：Mozilla/4.0（compatible；MSIE6.0；WindowsNT；MSSearch4.0Robot）Disallow：/
#W3CLinkchecker
User-agent:W3C-checklinkDisallow：
井excludesomeaccess-controlledareasUser-agent：*Disallow：/TeamDisallow：/ProjectDisallow：/WebDisallow:/SystemsDisallow；/HistoryDisallow；/Out-Of-DateDisallow：/People/all/
Disallow；/2005/11/Translations/Query
Disallow：/2000/06/webdata/xslt
Disallow；/2000/09/webdata/xslt
Disallow：/2005/08/online_xslt/xslt
Disallow；/Search/Mail/Public/
Disallow./2006/02/chartergen
具体使用格式如下。
User-agent
用于描述搜索引擎爬虫的名字，在”robots,txt“文件中，如果有多条User-agent记录说明有多个搜索引擎爬虫会受到该协议的限制，对该文件来说，至少要有一条User-agent记录。如果该项的值设为*，则该协议对任何搜索引擎爬虫均有效，在”robots,txt“文件中，”User-agent:*“迭样的记录另能有一条。
Disallow
用于描述不希望被访问到的一个URL，这个URL可以是一条完整的路径，也可以是部分的，任何以Disallow:开头的URL均不会被机器人访问到。
下面举例来说明robots,txt的具体用法。
例1通过”/robots,txt“禁止所有搜索引擎爬虫抓取”/bin/cgi/“目录，以及”Amp/“目录和/foo.html文件，设置方法如下：
User-agent：*
Disallow：/bin/cgi/
Disallow：/trap/
Disallow：/foo.html
例2通过”/robots,txt“只允许某个搜索引擎抓取，而禁止其他的搜索引擎抓取。如只允许名为”slurp“的搜索引擎爬虫抓取，而拒绝其他的搜索引擎爬虫抓取”/cgi/“目录下的内容，设置方法如下：
User-agent：*
Disallow：/cgi/
User-agent:slurp
Disallow：
例3禁止任何搜索引擎抓取我的网站，设置方法如下：
User-agent：*
Disallow：/
例4只禁止某个搜索引擎抓取我的网站。如只禁止名为”slurp“的搜索引擎爬虫抓取，设置方法如下：
User-agent:slurp
Disallow：/
搜索引擎爬虫必须要遵守Robots协议并执行Web站点的要求。因此搜索引擎爬虫需要有一个分析Robots协议的模块，并严格按照Robots协议的规定抓取Web主机允许访问的目录和网页。
当然，robots,txt只是一个协议，如果搜索引擎爬虫的设计者不遵循这个协议，网站管理员也无法阻止搜索引擎爬虫对于某些页面的访问，但一般的搜索引擎爬虫都会遵循这些协议，而且网站管理员还可以通过其他方式来拒绝网络爬虫对某些网页的抓取。
搜索引擎爬虫在下载网页的时候，会去识别网页的HTML代码，在其代码的部分，会有META标识。通过这些标识，可以告诉搜索引擎爬虫本网页是否需要被抓取，还可以告诉搜索引擎爬虫本网页中的链接是否需要被继续跟踪。例如，表示本网页不需要被抓取，但是网页内的链接需要被跟踪。
现在一般的网站都希望搜索引擎能更全面地抓取自己网站的网页，因为这样可以让更多的访向者能通过搜索引擎找到此网站。为了让本网站的网页更全面被抓取到，网站管理员可以建立一个网站地图，即SiteMap。许多搜索引擎爬虫会把sitemap.htm文件作为一个网站网页爬取的人口，网站管理员可以把网站内部所有网页的链接放在这个文件里面，那么搜索引擎爬虫可以很方便地把整个网站抓取下来，避免遗漏某些网页，也会减小対网站服务器的负担。
网页内容提取技术
搜索引擎建立网页索引，处理的对象是文本文件。对于搜索引擎爬虫来说，抓取下来的网页包括各种格式，包括HTML、图片、DOC、PDF、多媒体、动态网页及其他格式等。这些文件抓取下来后，需要把这些文件中的文本信息提取出来。准确提取这些文档的信息，一方面对搜索引擎的搜索淮确性有重要作用，另一方面对于搜索引擎爬虫正确跟踪其他链接有一定影响。
对于DOC、PDF等这种由专业厂商提供的软件生成的文档，厂商都会提供相应的文本提取接口。搜索引擎爬虫只需要调用这些插件的接口，就可以轻松地提取文档中的文本信息和文件其他相关的信息。
HTML等文档则不一样，HTML有一套自己的语法，通过不同的命令标识符来表示不同的字体、颜色、位置、版式等，提取文本信息时需要把这些标识符都过滤掉。过滤标识符并非难事，因为这些标识符都有一定的规则，只要按照不同的标识符取得相应的信息即可。但在识别这些信息的时候，需要同步记录许多版式信息，例如文字的字体大小、是否是标题、是否是加粗显示、是否是页面的关键词等，这些信息有助于计算单词在网页中的重要程度。同时，对于HTML网页来说，除了标题和正文以外，会有许多广告链接以及公共的频道链接，这些链接与文本正文一点关系也没有，在提取网页内審的时候，也需要过滤这些无用的链接。例如某个网站有”产品介绍“频道，因为导航条在网站内每个网页都有，若不过滤导航条链接，在搜索”产品介绍“的时候，则网站内每个网页都会捜索到，无疑会带来大量垃圾信息。过滤这些无效链接需要统计大量的网页结构规律，抽取一些共性，统一过滤；对于一些重要而结果特殊的网站，还需要个别处理。这就需要搜索引擎爬虫的设计有一定的扩展性。
对于多媒体、图片等文件，一般是通过链接的锚文本（即链接文本）和相关的文件注释来判断这些文件的内容。例如有一个链接文字为”故宫的照片“，其链接指向一张bmp格式的图片，那么搜索引擎爬虫就知道这张图片的内容是”故宫的照片“。这样，在搜索”故宫“和”照片“的时候都能让搜索引擎找到这张图片。另外，许多多媒体文件中有文件属性，考虑这些属性也可以更好地了解文件的内容。
动态网页一直是网络爬虫面临的难题。所谓动态网页，是相对于静态网页而言，是由程序自动生成的页面，这样的好处是可以快速统一更改网页风格，也可以减少网页所占服务器的空间，但同样给网络爬虫的抓取带来一些麻烦。由于开发语言不断的增多，动态网页的类型也越来越多，如aSp、jsp、php等。这些类型的网页对于搜索引擎爬虫来说，可能还稍微容易一些。搜索引擎爬虫比较难于处理的是一些脚本语言（如VBScript和JavaScript）生成的网页，如果要完善地处理好这些网页，网络爬虫需要有自己的脚本解释程序。对于许多数据是放在数据库的网站，需要通过本网站的数据库搜索才能获得信息，这些给网络爬虫的抓取带来很大的困难。对于这类网站，如果网站设计者希望这些数据能被搜索引擎搜索，则需要提供一种可以遍历整个数据库内容的方法。
对于网页内容的提取，一直是搜索引擎爬虫中重要的技术。整个系统一般采用插件的形式，通过一个插件管理服务程序，遇到不同格式的网页采用不同的插件处理。这种方式的好处在于扩充性好，以后每发现一种新的类型，就可以把其处理方式做成一个插件补充到插件管理服务程序之中。
由于网站的内容经常在变化，因此搜索引擎爬虫也须不断地更新其抓取网页的内容，这就需要搜索引擎爬虫按照一定的周期去扫描网站，査看哪些页面是需要更新的页面，哪些页面是新增页面，哪些页面是已经过期的死链接。
搜索引擎的更新周期对搜索引擎捜索的查全率有很大影响。如果更新周期太长，则总会有一部分新生成的网页搜索不到；周期过短，技术实现会有一定难度，而旦会対带宽、服务器的资源都有浪费。搜索引擎爬虫并不是所有的网站都采用同一个周期进行更新，对于一些重要的更新量大的网站，更新的周期短，如有些新闻网站，几个小时就更新一次；相反对于一些不重要的网站，更新的周期就长，可能一两个月才更新一次。
一般来说，搜索引擎爬虫在更新网站内容的时候，不用把网站网页重新抓取一遍，对于大部分的网页，只需要判断网页的属性（主要是日期），把得到的属性和上次抓取的属性相比较，如果一样则不用更新。
山掩
搜索引擎的基本结构
搜索引擎的工作包括如下3个过程：一是在互联网中发现、搜集网页信息；二是对所搜集的信息进行提取和组织，并建立索引库；三是由检索程序根据用户输入的査询关键词，在索引库中快速检出相关文档，进行文档与査询内容的相关度比较，对检出的结果进行排序，并将査询结果返回给用户。
搜索引擎通常由网页搜集模块、网页索引模块、査询模块和用户界面组成。根据检索结构的不同，可以将搜索引擎分为集中式结构和分布式结构。
搜索引擎的主要指标有响应时间、招回率、准确率、受欢迎程度、建立索引的方法和相关度等。
搜索引擎的数据结构
搜索引擎的存储结构主要有顺序存储、链接存储、索引存储和散列存储。搜索引擎的信息库包含每个网页的HTML文档，每个页面都通过Zlib算法进行压缩。文本索引需要按照一定的次序来保存每个文档的信息，以便于信息的查找。不同搜索引擎采用的词典不一样，现在的词典全部存放在内存中以便快速地查找。文档中的每个词对应一个采样，采样包含该词在该文档中的位置、字体和大小写信前向索引是文档到词的索引，在处理文档的时候以文档为单位建立这种索引比较方便。1后向索引是词到文档的索引，主要目的是为了提高文档检索的速度。
搜索引擎爬虫
网络爬虫，也称为蜘蛛程序。网络爬虫是一个自动提取网页的程序，是搜索引擎的重要组成部分。爬虫的作用是为搜索引擎抓取大量的数据，抓取的对象是整个互联网上的网页。爬虫程序不可能抓取所有的网页，因为在抓取的同时，Web的规模也在增大，所以一个好的爬虫程序一般能够在短时间内抓取更多的网页。
网络爬虫采取的抓取策略主要有：深度优先策略、广度优先策略、不重复抓取策略、网页抓取优先策略、网页重访策略和网页抓取提速策略。
Robots协议是Web站点和搜索引擎爬虫交互的一种方式，robots,txt是存放在站点根目录下的一个纯文本文件。该文件可以指定搜索引擎爬虫只抓取指定的内容，或者是禁止搜索引擎爬虫抓取网站的部分或全部内容。
思考救
简述搜索引擎的主要指标及特点。
简述搜索引擎的工作原理及组成部分的特点。
简述布隆过滤器的基本工作原理。
编写robots,txt文件，禁止所有搜索引擎爬虫抓取”/main/“目录，以及”/www/“目录下的index,html文件。
比较深度优先和广度优先策略的优缺点，阐述你自己的观点。
多媒体检索概述
多媒体信息捡索是指根据用户的需求，对文字、图像、声音、动画等多媒体信息进行识别并获取所需信息的技术。主要分为两类：一是以全文检索作为基本和主要的手段，在文字和其他媒体之间建立连接，非文字媒体的检索通过全文检索实现；二是根据各种媒体本身的特征进行检索。多媒体信息检索技术主要包括各种媒体的获取、压缩、存取（本地存取和网络存取）和输出（显示和打印）。本章主要介绍多媒体的基本概念、多媒体检索的分类、多媒体搜索引擎以及多媒体检索的发展。
多媒体信息
多媒体技术通常侧重于音频、图像、视频等信息及相关处理技术，它是传统文本处理技术的一种扩展。下面简单对多媒体信息中最重要、最有代表性的信息：音频、图像、视频进行简单的介绍，同时对它们各自的特性和有关的检索特征进行简单的分析。
多媒体及多媒体技术
媒体
媒体，又称媒介、媒质，是承载信息的载体。
多媒体技木
多媒体技术是指能对多种载体（媒介）上的信息和多种存储体（媒质）上的信息进行处理的技术。也就是一知把文字、图形、图像、视频、动画和声音等表现信息的媒体结合在一起，并通过计算机进行综合处理和控制，将多媒体各个要素进行有机组合，完成一系列随机性交互式操作的技术。
媒体的分类
国际电信联盟电信标准部（ITU-TSS）对多媒体进行了定义，并制定了ITU-TI.374建议。在该建议中，将日常生活中媒体的第一个涵义定义为感觉媒体，第二个涵义定义为存储媒体。此外，在ITU-TI.374建议中，把媒体分为以下5大类。
①感知媒体：指能够直接刺激人的感觉器官，使人产生直观感觉的各种媒体。或者说，人类感觉器官能够感觉到的所有刺激都是感知媒体。比如，人的耳染能够听到的话音、音乐、噪声等各种声音；人的眼睛能够感受到的光线、颜色、文字、图片、图像等各种有形有色的物体等。感知媒体包罗万象，存在于人类感觉到的整个世界。
②显示媒体：指感知媒体与电磁信号之间的转换媒体。显示媒体分为输人显示媒体和输出显示媒体。输人显示媒体主要负责将感觉媒体转換成电磁信号，比如话筒、键盘、光笔、扫描仪、摄像机等。输出显示媒体主要负责将电磁信号转换成感觉媒体，比如显示器、打印机、投影仪、音响等。
③表示媒体：对感知媒体的抽象描述形成表示媒体，比如声音编码、图像编码等。通过表示媒体，人类的感知媒体转换成能够利用计算机进行处理、保存、传输的信息载体形式。因此，对表示媒体的研究是多媒体技木的重要内窖。
④存储媒体：指存储表示媒体的物理设备，比如磁盘、光盘、磁带等。
⑤传输媒体：指传输表示媒体的物理介质，比如电缆、光缆、电磁波等都是传输媒体。
根据获得媒体的途径，可将媒体分为视觉媒体、听觉媒体、触觉媒体、嗅觉媒体等。其中视觉媒体包括位图图像、矢量图形、动态图像和文字等；听觉媒体包括声响、语音和音乐；触觉媒体包括振动、运动等。获得媒体的途径如图7-1所示。
图7-1获得媒体的途径
多媒体的关键特性
①多样性：一方面指信息表现媒体类型的多样性，同时也指媒体输人、传播、再现和展示手段的多样性。多媒体技术的引人将计算机所能处理的信息空间扩展和放大，使人们的思维表达不再局限于顺序的、单调的、狭小的范围内，而有了更充分更自由的表现余地。
②集成性：多媒体技术将各类媒体的设备集成在一起，同时也将多媒体信息或表现形?1AQ.
本文转载自
宁波seo优化www.leseo.net
补充词条：
宁波seo排名
宁波谷歌优化
宁波网站seo优化
宁波网站优化推广
宁波seo优化公司
