排序树与索引结构.ppt

《排序树与索引结构.ppt》由会员分享，可在线阅读，更多相关《排序树与索引结构.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Hu JunfengHu JunfengHu JunfengHu Junfeng排序树与文件索引结构排序树与文件索引结构2010/05/06Hu JunfengHu JunfengHu JunfengHu Junfeng本讲主要内容：本讲主要内容：Hash表（续）Web Crawler正则表达式倒排表与倒排索引排序树与AVL树文件的索引结构2Hu JunfengHu JunfengHu JunfengHu Junfeng字典的基本概念字典的基本概念字典字典是一个由数据记录（record）构成的顺序表，其中记录中有一个特殊的字段，称为关键码。关键码。每条记录都有唯一的不重复唯一的不重复的关键码取

2、值。字典中的元素之间能够根据其关键码进行比较与排序，对字典元素的插入、删除和检索等操作一般也以关键码为依据进行。字典可以看成是由关键码值k到数据记录r的一个对应。唯一的关键码取值可以唯一对应一条数据记录。3Hu JunfengHu JunfengHu JunfengHu Junfeng根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据条目。顺序检索、二分检索。衡量一个字典检索算法效率的主要标准是检索过程中对关键码的平均比较次数：字典的检索（字典的检索（searching）4Hu JunfengHu JunfengHu JunfengHu JunfengDictionary表示抽象数据

3、类型字典，DicElement 表示字典元素类型，KeyType 表示元素中关键码的类型，Position 表示字典中元素的位置。Dictionary的的抽象数据类型抽象数据类型ADT DictionaryoperationsDictionary createEmptyDictionary(void)/创建一个空字典。int search(Dictionary dic,KeyType key,Position p)/在字典dic中检索关键码为key的记录的位置p。int insert(Dictionary dic,DicElement ele)/在字典dic中插入记录ele。*int dele

4、te(Dictionary dic,KeyType key)/在字典dic中删除关键码为key的记录。*end ADT Dictionary5Hu JunfengHu JunfengHu JunfengHu Junfeng字典的顺序检索字典的顺序检索字典中的元素可以是无序的，但为了实现的方便，可以把字典中的元素按关键码值排序。从字典的一端开始顺序扫描，将字典中元素的关键码和给定值比较：如果相等，则检索成功；当扫描结束时，还未找到关键码等于给定值的元素，则检索失败。顺序检索算法适用于非排序顺序存储或非关键码字段检索顺序检索的算法复杂度为O(n)，平均比较次数为n/2。6Hu JunfengHu

5、JunfengHu JunfengHu Junfeng字典的二分查找字典的二分查找二分查找(binary search)要求：查找表为有序表，即表中 结点按关键字有序排列，并且采用顺序存储结构。基本思想：1.确定搜索区间的中点位置：2.然后将待查的key值与rangemid.key比较：若相等，则查找成功并返回此位置，否则确定新的查找区间，继续二分查找.7Hu JunfengHu JunfengHu JunfengHu Junfeng二分查找算法（非递归）二分查找算法（非递归）8Hu JunfengHu JunfengHu JunfengHu Junfeng二分法检索每经过一次比较就将检索范围

6、缩小一半，第i次比较可能涉及的元素=2i-1。二分法检索的最大检索长度为：log2(n+1)算法复杂度：log2(n)二分查找性能分析二分查找性能分析9Hu JunfengHu JunfengHu JunfengHu JunfengHash的思想的思想：一种高效的词典结构：一种高效的词典结构将数据集合中的所有对象都唯一对应到一个关键值，然后通过关键值映射到一个表中（哈希表）进行存放，之后可以根据关键值实现迅速查找。其他实现方案：插入速度 检索速度顺序表链表10Hu JunfengHu JunfengHu JunfengHu JunfengHash表的问题：表的问题：空间冗余，多对一（碰撞）空间

7、冗余，多对一（碰撞）确定性问题：关键码分布已知。编码-解码非确定性问题：关键码分布未知且理论上编码空间巨大。（vs 实际问题规模）11Hu JunfengHu JunfengHu JunfengHu Junfeng12Hu JunfengHu JunfengHu JunfengHu Junfeng样例数据：样例数据：33/40关键码？关键码？Value?13Hu JunfengHu JunfengHu JunfengHu Junfeng文件直接存取（文件直接存取（Random File Access）fseek(fileName,offset,origin)file streamFile*fp

8、;14Hu JunfengHu JunfengHu JunfengHu Junfeng文件直接存取函数文件直接存取函数rewind()resets the current position to the start of the filerewind(inFile)fseek()allows the programmer to move to any position in the filefseek(fileName,offset,origin)Origin:SEEK_SET,SEEK_CUR,and SEEK_ENDftell()returns the offset value of th

9、e next character that will be read or writtenftell(inFile);15Hu JunfengHu JunfengHu JunfengHu Junfeng16Hu JunfengHu JunfengHu JunfengHu JunfengHash函数设计：函数设计：观察法：17Hu JunfengHu JunfengHu JunfengHu Junfeng18Hu JunfengHu JunfengHu JunfengHu Junfeng19Hu JunfengHu JunfengHu JunfengHu Junfeng20Hu JunfengH

10、u JunfengHu JunfengHu Junfeng21Hu JunfengHu JunfengHu JunfengHu Junfeng如何处理文件中数据记录的删除？22Hu JunfengHu JunfengHu JunfengHu Junfeng碰撞及解决方案：碰撞及解决方案：23Hu JunfengHu JunfengHu JunfengHu Junfeng00820060 刘艳敏24Hu JunfengHu JunfengHu JunfengHu Junfeng对对hash函数的疑问：函数的疑问：以下是我对hash函数的理解。首先要尽可能的不发生碰撞，同时也要尽可能避免开很大的空

11、间，所以我们要找一个很巧妙的函数，对吧？那么对于一个已知的输入数据，我们可以分析它的特点，然后制定相应的函数。比如作业题1中给出的那个解决方案，作者考虑到倒数第三位和第一位很特殊，可以直接返回这个两位数。但是在加入了两组捣乱的数据后，这个方案明显出了问题。但我觉得这个因果关系有点颠倒了，如果我们已知了数据，hash函数甚至可以直接用从小到大的对应的次序，这样根本不要费尽心机的找一个函数出来。所以我觉得，一个好的函数，是不是应该在数据还未知的情况下，就能有一定的把握，使碰撞次数很少。如果这样想的话，就要要求这个函数尽可能散，随机的把数据投射到另一个集合，但这样又似乎没法控制hash表的规模。而且

12、保证随机（或者说比较均匀的）也挺麻烦，就像课上说的，平方的话会使一些平方数明显增多，等等。然后我就困惑了，像这次的这个作业题，到底有没有一个比较厉害的函数，能够应对几乎所有的捣乱数据?25Hu JunfengHu JunfengHu JunfengHu Junfeng一般思路：一般思路：号码类字符串类26Hu JunfengHu JunfengHu JunfengHu JunfengHash的用途的用途词典索引用来判重和统计数目27Hu JunfengHu JunfengHu JunfengHu Junfeng字符串处理：字符串处理：28Hu JunfengHu JunfengHu Junfe

13、ngHu Junfengsscanf()29Hu JunfengHu JunfengHu JunfengHu Junfengsscanf()30Hu JunfengHu JunfengHu JunfengHu Junfengsscanf()31Hu JunfengHu JunfengHu JunfengHu Junfengsscanf()32Hu JunfengHu JunfengHu JunfengHu Junfengsscanf()33Hu JunfengHu JunfengHu JunfengHu Junfeng网络爬虫网络爬虫：网络爬虫是什么？怎样爬？整体框架核心算法算法改进34Hu

14、JunfengHu JunfengHu JunfengHu Junfeng怎样搜集怎样搜集?网页为节点网页中的HyperLink为有向边Crawl=图遍历,right?35Hu JunfengHu JunfengHu JunfengHu Junfeng链接是哪些？链接是哪些？36Hu JunfengHu JunfengHu JunfengHu JunfengRefer to HTML 4.01 Specification37Hu JunfengHu JunfengHu JunfengHu JunfengGET Method in HTTPRefer to RFC 2616HTTP Made R

15、eally Easy 38Hu JunfengHu JunfengHu JunfengHu JunfengAgenda网络爬虫是什么？怎样爬？预备知识整体框架核心算法算法改进Distributed Crawling39Hu JunfengHu JunfengHu JunfengHu Junfeng网络爬虫是什么？网络爬虫是什么？系统框图系统框图40Hu JunfengHu JunfengHu JunfengHu Junfeng41Hu JunfengHu JunfengHu JunfengHu Junfeng42Hu JunfengHu JunfengHu JunfengHu Junfeng4

16、3Hu JunfengHu JunfengHu JunfengHu Junfeng还存在什么问题呢？还存在什么问题呢？The real world is not perfect镜像与重复网页 mirrors and duplicationsurl/html syntax error server trapsserver complainslegal issuessystem crash,power brake44Hu JunfengHu JunfengHu JunfengHu JunfengURL不唯一性不唯一性不同url指向的同一个网页IP地址和域名之间的多对多关系大规模网站用于负载平衡的技

17、术：内容镜像“virtual hosting”和“Proxy pass”：不同的主机名映射到同一个IP地址，发布多个逻辑网站的需要（Apache支持）动态网页的参数Session id上一页/下一页45Hu JunfengHu JunfengHu JunfengHu Junfeng“同义同义”地址地址域名与IP对应存在4种情况：一对一，一对多，多对一，多对多。一对一不会造成重复搜集，后三种情况都有可能造成重复搜集。可能是虚拟主机，多个域名共一个IP,内容不同,-162.105.129.12可能是DNS轮转-202.112.8.2， -202.112.8.3可能是一个站点有多个域名对应和等价46

18、Hu JunfengHu JunfengHu JunfengHu Junfengserver traps防止系统异常病态HTML文件例如，有的网页含有68 kB null字符误导Crawler的网站用CGI程序产生无限个网页用软目录创建的很深的路径 JunfengHu JunfengHu JunfengHu Junfeng自动提取所关注领域的网页自动提取所关注领域的网页我觉得可以由用户提供一个关键词名单，每个关键词有一定分值，网页文本中若出现此关键词就得到相应的分数；总分高的网页优先显示。问题：关键词名单如何确定？关键词分值如何确定？如何规避文本内容与所包含的词不一致的问题？预习：网站上“倒排表与向量空间模型”内容。48Hu JunfengHu JunfengHu JunfengHu Junfeng本次作业：本次作业：所有同学继续完上一次内容，9号前务必要提交。尽可能这次把布置的选作题也都作了。可以考虑建一个大的字符串的数组，value值放数组的下标（推荐），也可以尝试用课上讲过的文件直接存取技术存放URL的文件偏移量来进行URL的比对。（提交为第二题，依然assignment0429目录）选作题哦：提取网页（pku主页）中所有超链接显示的文字内容。例如前面例子中：“北大故事”的提取。10号前完成的请发给49