关键词搜索排名软件,游戏优化是什么意思?,怎么用cms做网站,平凉崆峒建设局网站【摘抄】基于线性表的检索一、检索的基本概念和算法分类1、检索概念#xff1a; 可以形式化地定义基于关键码的检索。假定k1、k2…kn是互不相同的关键码值#xff0c;有一个包含n条记录的集合C#xff0c;形式如下#xff1a; (k1, R1)#xff0c;(k2, R2)#xff0c;…【摘抄】基于线性表的检索一、检索的基本概念和算法分类1、检索概念 可以形式化地定义基于关键码的检索。假定k1、k2…kn是互不相同的关键码值有一个包含n条记录的集合C形式如下 (k1, R1)(k2, R2)…(kn, Rn) 其中Rj是与关键码kj相关联的信息。给定某个关键码值K检索问题( search problem )就是在C中定位记录(kj, Rj) 使得kj K。检索( searching )就是定位关键码值kj K的记录的系统过程。2、检索算法分类(1) 基于线性表的检索。例如顺序检索、二分检索。(2) 根据关键码值直接访问。例如根据数组下标的直接检索、散列检索。(3) 树索引方法。例如二叉搜索树、字符树、B树。(4) 基于属性的检索。例如倒排表、倒排文件。 二、衡量检索算法 评价一个检索算法的效率需要在时间和空间两方面进行权衡。检索运算的主要操作是关键码值的比较我们通常把检索过程中对关键码需要执行的平均比较次数称为平均检索长度(Average Search Length)它是衡量检索算法优劣的时间标准。显然平均检索长度是存储结构中对象总数n的函数其定义为 其中Pi为检索第i个元素即给定值K与存储结构中第i个元素的关键码值相等的概率Ci为找到第i个元素所需的关键码值与给定值的比较次数。假设线性表为a, b, c检索a、b、c的概率分别为0.4、0.1、0.5则顺序检索算法的平均检索长度为0.4×10.1×20.5×3 2.1即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素。此外我们还需要考虑不成功的检索。 “检索第i个元素的概率P”可理解为在很多次的检索中找第i个元素的次数占总次数的比例为P。显然若已知各个元素检索概率的分布情况则ASL可准确地反映检索算法的平均时间性能。 另外衡量一个检索算法还要考虑算法所需的存储量、算法的复杂性等因素。三、顺序检索 顺序检索的算法思想是针对线性表里的所有记录逐个进行关键码和给定值的比较若某个记录的关键码和给定值比较相等则检索成功找到所查记录反之检索失败。表中各数据元素之间不必拥有逻辑关系即它们在表中可以任意排列。 与其它检索方法相比顺序检索对表的特性没有要求数据元素可以任意排列。插入元素可以直接加到表尾时间代价为Θ(1)。这是其主要优点。但顺序检索的平均检索长度较大在平均和最差的情况下的时间代价都是Θ(n)。当数据规模较大时检索效率比较低。 四、二分检索和分治算法 二分检索是针对有序表的检索。所谓有序表是指线性表中的所有数据元素按关键码值的某种次序进行递增或递降的排列。二分检索法的基本思想是每次将待查区间中间位置上的数据元素的关键码值与给定值K比较若不等则缩小检索区间并在新的区间内重复上述过程直到检索成功或检索区间长度为0检索不成功为止。 二分检索法的效率可以通过二分检索的决策树进行衡量。其平均检索长度与最大检索长度相近效率较高。但它要求被检索序列事先按关键码的次序递增或递减排列而排序本身是一种很费时的运算另外二分检索只适用于顺序存储结构而在顺序结构中插入和删除都比较困难。因此二分检索特别适用于那种一经建立就很少改动、而又需要经常检索的线性表。 现以有序表151718223551608893为例说明用二分检索算法查找K18的过程这里假定表中各元素只含关键码。首先取整个有序表为检索区间这通过分别置low、high为1、9来完成。 因区间长度大于0取区间中间位置mid (19)/2 5将mid位置上元素的关键码值35与K18比较。因1835将区间缩小为[14]。注意此新区间与原区间[19]的差别仅在于上界不同修改区间的工作可通过修改上界high mid151完成。 由于循环终止条件未满足重复上述过程。这时区间中点为mid(14)/22比较结果1817表明区间应改为[34]这一修改由下界的修改low mid121完成。 再次进行比较时区间中点为mid(34)/23比较结果表明dataList[mid]正是待查元素检索成功返回结果为mid3。(如下图所示二分法检索演示图图分治法思想 一般而言计算机求解问题的规模越小所需的计算时间也越少。对于规模为N的问题分治策略将其分解为kk 2, 3, 4, …一般取k2个相同类型的子问题每个子问题的规模相对较小且相互独立递归地求解这些子问题并将所得结果合并而求出原来问题的解。这就是分治策略的基本思想。 分治策略算法通常分为三个部分:分割、求解、合并。五、分块检索 分块检索又称为索引检索性能介于顺序检索和二分检索之间。它把线性表分成若干块在每一块中结点的存放是任意的但是块与块之间必须保持关键码值递增或者递减的顺序。把每块中最大的关键码值块的起始位置这样的二元组构成一个索引表。由于表是分块有序的所以索引表是一个递增递减有序表。检索时首先用待检索的关键码在索引中查找确定如果满足条件的结点存在时它应在哪一块中在索引中检索的方法既可以采用二分法、也可以采用顺序检索然后再到相应的块中顺序检索便可以得到检索的结果。 分块检索的主要代价是增加一个辅助索引数组的存储空间和将初始线性表分块排序的运算。另外当大量的插入删除运算使块中结点数分布很不均匀时检索速度将会下降。 分块检索的优点是在线性表中插入或删除一个结点时只要找到该结点应属于的块然后在块内进行插入和删除运算。由于块内结点的存放是任意的所以插入或删除比较容易不需要移动大量的结点。插入可以在块尾进行如果待删除的记录不是块中最后一个记录时可以将本块内最后一个记录移入被删除记录的位置。 总体来说顺序检索效率最低但限制最少。二分检索效率最高但限制多。而分块检索则介于上述二者之间在实际应用中可根据表的具体情况进行选择需要综合考虑检索效率、插入删除频率等。 集合的检索一、集合特性 集合是由若干个确定的、相异的对象构成的。这些对象称元素一个集合中不包含两个完全相同的元素。在问题求解中集合是十分有用的工具。 元素个数为零的集合称为“空集”一般用φ来表示。 最基本的关系是成员关系若x是集合A的元素则称“x属于A”记作x∈A。 设有两个集合A和B如果集合A的每个元素也都是集合B的元素称集合A被集合B包含也称A是B的子集或称B是A的“超集”(superset)。如果A、B两个集合互相包含则称这两个集合相等记作AB。集合A是集合B的一个真子集(或真超集)必须满足A是B的子集并且A≠B。 集合最基本的运算是并、交、差。由至少属于集合A和集合B之一的一切元素组成的集合称为A和B的并集记作A∪B。由集合A和集合B的所有共同元素所组成的集合称为A和B的交集记作A∩B。由所有属于A但不属于B的元素的全体所组成的集合称为A和B的差集记作A-B。 计算机所支持的集合的基类型basetype一般是有限、顺序类型。被定义的集合类型称为与基类型相联系的集合类型。集合类型的值集是其基类型值集的幂集。集合类型的每个值是其基类型值集的一个子集。 与集合有关的运算可以定义为 二、位图检索 要判断某一元素是否在数组中即集合中的“IN”运算是在一组记录中检索关键码的一种特殊情况。本书所讨论的所有检索方法都可以完成这个任务。 在关键码值范围有限的情况下可以采用一种简单的技术这就是存储一个位数组(bit arrary)为每一个可能的元素分配一个比特位位置。如果元素确实包含在实际集合中就把它对应的位设置为1如果元素不包含在集合中就把它对应的位设置为0。Pascal语言能够直接支持集合类型其集合类型就是用一个位数组来实现的。 例如对于字符型集合为小写字母[a..z]而集合型变量chset [a,c,h,i,j,m,n,t,v,w,y]那么对应于变量chset的位数组为图 这种表示方法很省空间而且对于“属于”、“并”、“交”和“差”“IN”、“”、“*”和“-”操作十分方便。集合比数组的操作更加便捷。例如对于数组的插入和删除都有大量的数据移动而集合类型的“并”、“交”和“差”运算只需要在修改相应的比特位标记。要确定某个元素是否在集合中只需要直接检查对应的位标志。这种表示方法称为位向量( bit vector )或者位图( bitmap )。 如果集合大小在计算机的一个字长范围内而且高级语言支持按位操作就可以通过逻辑的位操作而完成集合的并、交、差运算。例如在C 语言中集合A和B的并运算就是“A | B”按位或集合的交运算就是“A B”按位与集合A与B的差运算可以使用表达式“A ~ B”( ~是非运算的符号)实现。例如如果要计算数字0到数字15之间奇素数集合只需要计算表达式 0011010100010100 0101010101010101 得到结果“0001010100010100”表示0到15之间的奇素数集合为{3571113}。 总结在信息检索( document retrieval )中有一种签名文件( signature file )技术就是根据位向量来计算待检索的文档集合的。 散列方法 前面我们所介绍的检索基本上都是基于关键码比较的检索。例如顺序检索和分块检索依赖于“等于”“”或者“不等于”“!”的判断而二分检索和树型检索BSTB树等依赖于 “大于”“”、“等于”“”“”、“小于” “”这三种判断。这些检索方法的平均检索长度都与n有关。检索是直接面向用户的操作当问题规模n很大时上述检索的时间效率可能使得用户无法忍受。 最理想的情况是根据关键码值直接找到记录的存储地址而不需要把待查关键码与候选记录集合的某些记录进行逐个比较。 计算机科学家发明了散列的方法。本节则主要讨论散列检索技术包括各种散列函数和解决散列冲突的方法等。 一、散列基本概念 散列方法的主要思想是根据结点的关键码值来确定其存储地址以关键码值K为自变量通过一定的函数关系h(K)(称为散列函数)计算出对应的函数值来把这个值解释为结点的存储地址将结点存入到此存储单元中。检索时用同样的方法计算地址然后到相应的单元里去取要找的结点。通过散列方法可以对结点进行快速检索。散列hash也称“哈希”是一种重要的存储方式也是一种常见的检索方法。 按散列存储方式构造的存储结构称为散列表hash table。散列表中的一个位置称为槽(slot)。散列技术的核心是散列函数(hash function)。 对任意给定的动态查找表DL如果选定了某个“理想的”散列函数h及相应的散列表HT则对DL中的每个数据元素X。函数值 hX.key就是X在散列表HT中的存储位置。插入或建表时数据元素X将被安置在该位置上并且检索X时也到该位置上去查找。由散列函数决定的存储位置称为散列地址。 因此散列的核心就是由散列函数决定关键码值(X.key)与散列地址h(X.key)之间的对应关系通过这种关系来实现组织存储并进行检索。 一般情况下散列表的存储空间是一个一维数组HT[M]散列地址是数组的下标。设计散列方法的目标就是设计某个散列函数h0h( K ) M对于关键码值K得到HT[i] K。 在一般情况下散列表的空间必须比结点的集合大此时虽然浪费了一定的空间但换取的是检索效率。设散列表的空间大小为M填入表中的结点数为N则称 为散列表的负载因子load factor也有人翻译为“装填因子”。建立散列表时若关键码与散列地址是一对一的关系则在检索时只需根据散列函数对给定值进行某种运算即可得到待查结点的存储位置。但是散列函数可能对于不相等的关键码计算出相同的散列地址我们称该现象为冲突collision发生冲突的两个关键码称为该散列函数的同义词。在实际应用中很少存在不产生冲突的散列函数我们必须考虑在冲突发生时的处理办法。 因此采用散列技术时需要考虑的两个首要问题是 1如何构造(选择)使结点“分布均匀”的散列函数 2一旦发生冲突用什么方法来解决 当然还需考虑散列表本身的组织方法。下面分别加以讨论。二、散列函数 本节讨论几种散列函数。在以下的讨论中我们假设处理的是值为整型的关键码否则我们总可以建立一种关键码与正整数之间的一一对应关系从而把该关键码的检索转化为对与其对应的正整数的检索同时进一步假定散列函数的值落在0到M1之间。散列函数的选取原则是运算尽可能简单函数的值域必须在散列表的范围内尽可能使得结点均匀分布也就是尽量让不同的关键码具有不同的散列函数值。需要考虑各种因素关键码长度、散列表大小、关键码分布情况、记录的检索频率等等。下面我们介绍几种常用的散列函数。 1、除余法顾名思义除余法就是用关键码x除以M往往取散列表长度并取余数作为散列地址。除余法几乎是最简单的散列方法散列函数为 h(x) x mod M。 2、乘余取整法使用此方法时先让关键码key乘上一个常数A (0 A 1)提取乘积的小数部分。然后再用整数n乘以这个值对结果向下取整把它做为散列的地址。散列函数为 hash ( key ) _LOW( n × ( A × key % 1 ) )。其中“A × key % 1”表示取 A × key 小数部分即 A × key % 1 A × key - _LOW(A × key), 而_LOW(X)是表示对X取下整。 3、平方取中法由于整数相除的运行速度通常比相乘要慢所以有意识地避免使用除余法运算可以提高散列算法的运行时间。平方取中法的具体实现是先通过求关键码的平方值从而扩大相近数的差别然后根据表长度取中间的几位数往往取二进制的比特位作为散列函数值。因为一个乘积的中间几位数与乘数的每一数位都相关所以由此产生的散列地址较为均匀。 4、数字分析法设有 n 个 d 位数每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同可能在某些位上分布均匀些每种符号出现的几率均等; 在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选取其中各种符号分布均匀的若干位作为散列地址。 5、基数转换法将关键码值看成另一种进制的数再转换成原来进制的数然后选其中几位作为散列地址。 6、折叠法有时关键码所含的位数很多采用平方取中法计算太复杂则可将关键码分割成位数相同的几部分最后一部分的位数可以不同然后取这几部分的叠加和舍去进位作为散列地址这方法称为折叠法。 7、ELFhash字符串散列函数ELFhash函数在UNIX系统V 版本4中的“可执行链接格式”( Executable and Linking Format即ELF )中会用到ELF文件格式用于存储可执行文件与目标文件。ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效字符串中每个字符都有同样的作用它巧妙地对字符的ASCII编码值进行计算ELFhash函数对于能够比较均匀地把字符串分布在散列表中。 三、冲突解决策略 尽管散列函数的目标是使得冲突最少但实际上冲突是无法避免的。因此我们必须研究冲突解决策略。 冲突解决技术可以分为两类开散列方法( open hashing也称为拉链法separate chaining )和闭散列方法( closed hashing也称为开地址方法open addressing )。这两种方法的不同之处在于开散列法把发生冲突的关键码存储在散列表主表之外而闭散列法把发生冲突的关键码存储在表中另一个槽内。1、开散列方法。冲突解决策略/开散列方法 1、拉链法 开散列方法的一种简单形式是把散列表中的每个槽定义为一个链表的表头。散列到一个特定槽的所有记录都放到这个槽的链表中。图9-5说明了一个开散列的散列表这个表中每一个槽存储一个记录和一个指向链表其余部分的指针。这7个数存储在有11个槽的散列表中使用的散列函数是h(K) K mod 11。数的插入顺序是77、7、110、95、14、75和62。有2个值散列到第0个槽1个值散列到第3个槽3个值散列到第7个槽1个值散列到第 9个槽。 2、桶式散列 桶式散列方法的基本思想是把一个文件的记录分为若干存储桶每个存储桶包含一个或多个页块一个存储桶内的各页块用指针连接起来每个页块包含若干记录。散列函数h把关键码值K转换为存储桶号即h(K)表示具有关键码值K的记录所在的存储桶号。 图9-6表示了一个具有B个存储桶的散列文件组织。有一个存储桶目录表存放B个指针每个存储桶一个每个指针就是所对应存储桶的第一个页块的地址。 有些存储桶仅仅由一个页块组成如下图中的1号存储桶。有的存储桶由多个页块组成每一个页块的块头上有一个指向下一个页块的指针例如如下图中的第B-1号存储桶由b4b5b6三个页块组成每个存储桶中最后一个页块的头上为空指针。2、闭散列方法。 冲突解决策略/闭散列方法 闭散列方法把所有记录直接存储在散列表中。每个记录关键码key有一个由散列函数计算出来的基位置即h(key)。如果要插入一个关键码而另一个记录已经占据了R的基位置(发生碰撞)那么就把R存储在表中的其它地址内由冲突解决策略确定是哪个地址。 闭散列表解决冲突的基本思想是当冲突发生时使用某种方法为关键码K生成一个散列地址序列d0d1d2... di ...dm-1。其中d0hK称为K的基地址地置( home position )所有di(0 i m)是后继散列地址。当插入K时若基地址上的结点已被别的数据元素占用则按上述地址序列依次探查将找到的第一个开放的空闲位置di作为K的存储位置若所有后继散列地址都不空闲说明该闭散列表已满报告溢出。相应地检索K时将按同值的后继地址序列依次查找检索成功时返回该位置di 如果沿着探查序列检索时遇到了开放的空闲地址则说明表中没有待查的关键码。删除K时也按同值的后继地址序列依次查找查找到某个位置di具有该K 值则删除该位置di上的数据元素删除操作实际上只是对该结点加以删除标记如果遇到了开放的空闲地址则说明表中没有待删除的关键码。因此对于闭散列表来说构造后继散列地址序列的方法也就是处理冲突的方法。 形成探查的方法不同所得到的解决冲突的方法也不同。下面是几种常见的构造方法。 1、线性探查法 将散列表看成是一个环形表若在基地址d即h(K)d发生冲突则依次探查下述地址单元d1d2......M- 101......d-1直到找到一个空闲地址或查找到关键码为key的结点为止。当然若沿着该探查序列检索一遍之后又回到了地址d则无论是做插入操作还是做检索操作都意味着失败。 用于简单线性探查的探查函数是 p(Ki) i 例9.7 已知一组关键码为2636413844156812065125散列表长度M 15用线性探查法解决冲突构造这组关键码的散列表。 因为n11利用除余法构造散列函数选取小于的最大质数P13则散列函数为h(key) key%13。按顺序插入各个结点 26: h(26) 036: h(36) 10 41: h(41) 238: h(38) 12 44: h(44) 5。 插入15时其散列地址为2由于2已被关键码为41的元素占用故需进行探查。按顺序探查法显然3为开放的空闲地址故可将其放在3单元。类似地68和12可分别放在4和13单元中下图显示了插入15和68时的过程。 2、二次探查法 二次探查法的基本思想是生成的后继散列地址不是连续的而是跳跃式的以便为后续数据元素留下空间从而减少聚集。二次探查法的探查序列依次为12-1222 -22...等也就是说发生冲突时将同义词来回散列在第一个地址的两端。求下一个开放地址的公式为 3、随机探查法 理想的探查函数应当在探查序列中随机地从未访问过的槽中选择下一个位置即探查序列应当是散列表位置的一个随机排列。但是我们实际上不能随机地从探查序列中选择一个位置因为在检索关键码的时候不能建立起同样的探查序列。然而我们可以做一些类似于伪随机探查( pseudo-random probing )的事情。在伪随机探查中探查序列中的第i个槽是(h(K) ri) mod M其中ri是1到M - 1之间数的“随机”数序列。所有插入和检索都使用相同的“随机”数。探查函数将是 p(Ki) perm[i - 1]这里perm是一个长度为M - 1的数组它包含值从1到M – 1的随机序列。 4、双散列探查法 伪随机探查和二次探查都能消除基本聚集——即基地址不同的关键码其探查序列的某些段重叠在一起——的问题。然而如果两个关键码散列到同一个基地址那么采用这两种方法还是得到同样的探查序列仍然会产生聚集。这是因为伪随机探查和二次探查产生的探查序列只是基地址的函数而不是原来关键码值的函数。这个问题称为二级聚集( secondary clustering )。 为了避免二级聚集我们需要使得探查序列是原来关键码值的函数而不是基位置的函数。双散列探查法利用第二个散列函数作为常数每次跳过常数项做线性探查。 四、散列检索效率分析 我们可以根据完成一次操作即插入、删除和检索操作所需要的记录访问次数来衡量散列方法的性能。由于散列表的插入和删除操作都是基于检索进行的在删除一条记录之前必须先找到该记录因此删除一条记录之前需要的访问数等于成功检索到它需要的访问数而插入一条记录时必须找到探查序列的尾部对于不考虑删除的情况是尾部的空槽对于考虑删除的情况也要找到尾部才能确定是否有重复记录这等于对这条记录进行一次不成功的检索。因此散列表的效率实质上还是平均检索长度而且我们需要区别对待成功的检索与不成功的检索。 当散列表比较空的时候所插入的记录比较容易插入到其空闲的基地址。如果散列表中的记录比较多插入记录时很可能要靠冲突解决策略来寻找探查序列中合适的另一个槽。而且检索记录时很多时候需要沿着探查序列逐个查找。随着散列表记录不断增加越来越多的记录有可能放到离其基地址更远的地方。 根据这些讨论我们可以看到散列方法预期的代价与负载因子α N/M有关。其中M是散列表存储空间大小N是表中当前的记录数目。 从图9-8可以看出开散列方法的效率最好实际系统中使用的散列大多都是开散列。开散列方法非常简单、易于实现它不会产生聚集现象聚集导致更大的平均检索长度删除也极为方便。大部分数据结构教材用比较多的篇幅来讨论闭散列方法是因为闭散列需要考虑的因素更多因而更需要精心设计闭散列在某些受限制的系统中例如不能使用堆栈分配新空间有独到的用途。并且经过精心设计的闭散列的效率比开散列稳定。 总结:散列法的平均检索长度不随表目数量的增加而增加而是随负载因子的增大而增加。如果安排得好平均检索长度可以小于1.5。正是由于这个特性散列法成为一种很受欢迎的高效检索方法。例如搜索引擎中关键词字典、域名服务器DNS中域名与IP地址的对应例如db.pku.edu.cn与 162.105.203.98www.google.com与216.239.53.99、操作系统中命令路径下的所有可执行程序名、编译系统中的符号表等都采用了散列技术以提高查找速度。 来源http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/chapter9/01/t01_jj.html转载于:https://www.cnblogs.com/GoGoagg/archive/2011/03/08/1977361.html
