《杨氏矩阵查找,倒排索引关键词Hash编码》由会员分享，可在线阅读，更多相关《杨氏矩阵查找,倒排索引关键词Hash编码（22页珍藏版）》请在金锄头文库上搜索。
1、杨氏矩阵查找，倒排索引关键词 Hash 编码分类： 11.TAOPP（编程艺术） 13.TAOPP array 29.Recommend&Search2011-12-19 21:23 45208 人阅读 评论(38)收藏 举报编程算法数据结构文档 null目录 (?)+第二十三、四章：杨氏矩阵查找，倒排索引关键词 Hash 不重复编码实践作者：July 、yansha。编程艺术室出品。出处：结构之法算法之道。前言本文阐述两个问题，第二十三章是杨氏矩阵查找问题，第二十四章是有关倒排索引中关键词 Hash 编码的问题，主要要解决不重复以及追加的功能，同时也是经典算法研究系列十一、从头到尾彻底解析H
2、ash 表算法之续。OK，有任何问题，也欢迎随时交流或批评指正。谢谢。第二十三章、杨氏矩阵查找杨氏矩阵查找先看一个来自算法导论习题里 6-3 与剑指 offer 的一道编程题（也被经常用作面试题，本人此前去搜狗二面时便遇到了）：在一个 m 行 n 列二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字 6，则返回 true；如果查找数字 5，由于数组不含有该数字，则返回 false。 本 Young 问题解法有二（如查找
3、数字 6）：1、分治法，分为四个矩形，配以二分查找，如果要找的数是 6 介于对角线上相邻的两个数 4、10，可以排除掉左上和右下的两个矩形，而递归在左下和右上的两个矩形继续找，如下图所示：2、定位法，时间复杂度 O（m+n）。首先直接定位到最右上角的元素，再配以二分查找，比要找的数（6）大就往左走，比要找数（6）的小就往下走，直到找到要找的数字（6）为止，如下图所示：上述方法二的关键代码+程序运行如下图所示： 试问，上述算法复杂么？不复杂，只要稍微动点脑筋便能想到，还可以参看友人老梦的文章，Young氏矩阵：http:/ IT 练兵场的：http:/ offer中也收集了此题，感兴趣的朋友也可
4、以去看看。第二十四章、经典算法十一 Hash 表算法（续）、倒排索引关键词不重复 Hash 编码 本章要介绍这样一个问题，对倒排索引中的关键词进行编码。那么，这个问题将分为两个个步骤：1. 首先，要提取倒排索引内词典文件中的关键词；2. 对提取出来的关键词进行编码。本章采取 hash 编码的方式。既然要用 hash 编码，那么最重要的就是要解决 hash 冲突的问题，下文会详细介绍。 有一点必须提醒读者的是，倒排索引包含词典和倒排记录表两个部分，词典一般有词项（或称为关键词）和词项频率（即这个词项或关键词出现的次数），倒排记录表则记录着上述词项（或关键词）所出现的位置，或出现的文档及网页 ID
5、 等相关信息。24.1、正排索引与倒排索引 咱们先来看什么是倒排索引，以及倒排索引与正排索引之间的区别：我们知道，搜索引擎的关键步骤就是建立倒排索引，所谓倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页的查找。接下来，阐述下正排索引与倒排索引的区别：一般索引（正排索引） 正排表是以文档的 ID 为关键字，表中记录文档中每个字的位置信息，查找时扫描表中每个
6、文档中字的信息直到找出所有包含查询关键字的文档。正排表结构如图 1 所示，这种组织方法在建立索引的时候结构比较简单，建立比较方便且易于维护;因为索引是基于文档建立的，若是有新的文档假如，直接为该文档建立一个新的索引块，挂接在原来索引文件的后面。若是有文档删除，则直接找到该文档号文档对因的索引信息，将其直接删除。但是在查询的时候需对所有的文档进行扫描以确保没有遗漏，这样就使得检索时间大大延长，检索效率低下。 尽管正排表的工作原理非常的简单，但是由于其检索效率太低，除非在特定情况下，否则实用性价值不大。 倒排索引 倒排表以字或词为关键字进行索引，表中关键字所对应的记录表项记录了出现这个字或词的所有
7、文档，一个表项就是一个字表段，它记录该文档的 ID 和字符在该文档中出现的位置情况。由于每个字或词对应的文档数量在动态变化，所以倒排表的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字所对应的所有文档，所以效率高于正排表。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，尽管效率相对低一些，但不会影响整个搜索引擎的效率。倒排表的结构图如图 2： 倒排表的索引信息保存的是字或词后继数组模型、互关联后继数组模型条在文档内的位置，在同一篇文档内相邻的字或词条的前后关系没有被保存到索引文件内。24.2、倒排索引中提取关键词倒排索引是搜索引擎之基石。建成了倒排索
8、引后，用户要查找某个 query，如在搜索框输入某个关键词：“结构之法”后，搜索引擎不会再次使用爬虫又一个一个去抓取每一个网页，从上到下扫描网页，看这个网页有没有出现这个关键词，而是会在它预先生成的倒排索引文件中查找和匹配包含这个关键词“结构之法”的所有网页。找到了之后，再按相关性度排序，最终把排序后的结果显示给用户。 如下，即是一个倒排索引文件（不全），我们把它取名为 big_index， 文件中每一较短的，不包含有“#”符号的便是某个关键词，及这个关键词的出现次数。现在要从这个大索引文件中提取出这些关键词，-Firelf-，-11，-Winter-，.，007，007：天降杀机，02Cha
9、n.如何做到呢？一行一行的扫描整个索引文件么？何意？之前已经说过：倒排索引包含词典和倒排记录表两个部分，词典一般有词项（或称为关键词）和词项频率（即这个词项或关键词出现的次数），倒排记录表则记录着上述词项（或关键词）所出现的位置，或出现的文档及网页 ID 等相关信息。最简单的讲，就是要提取词典中的词项（关键词）：-Firelf-，-11，-Winter-，.，007，007：天降杀机，02Chan.。-Firelf-（关键词） 8（出现次数）我们可以试着这么解决：通过查找#便可判断某一行出现的词是不是关键词，但如果这样做的话，便要扫描整个索引文件的每一行，代价实在巨大。如何提高速度呢？对了，关
10、键词后面的那个出现次数为我们问题的解决起到了很好的作用，如下注释所示：/ 本身没有# 的行判定为关键词行，后跟这个关键词的行数 N（即词项频率）/ 接下来，截取关键词-Firelf-，然后读取后面关键词的行数 N/ 再跳过 N 行（滤过和避免扫描中间的倒排记录表信息）/ 读取下一个关键词.有朋友指出，上述方法虽然减少了扫描的行数，但并没有减少 I0 开销。读者是否有更好地办法？欢迎随时交流。24.2、为提取出来的关键词编码爱思考的朋友可能会问，上述从倒排索引文件中提取出那些关键词（词项）的操作是为了什么呢？其实如我个人微博上 12 月 12 日所述的 Hash 词典编码：词典文件的编码：1、词
11、典怎么生成（存储和构造词典）；2、如何运用 hash 对输入的汉字进行编码；3、如何更好的解决冲突，即不重复以及追加功能。具体例子为：事先构造好词典文件后，输入一个词，要求找到这个词的编码，然后将其编码输出。且要有不断能添加词的功能，不得重复。步骤应该是如下：1、读索引文件；2、提取索引中的词出来；3、词典怎么生成，存储和构造词典；4、词典文件的编码：不重复与追加功能。编码比如，输入中国，他的编码可以为 10001，然后输入银行，他的编码可以为 10002。只要实现不断添加词功能，以及不重复即可，词典类的大文件，hash 最重要的是怎样避免冲突。也就是说，现在我要对上述提取出来后的关键词进行编
12、码，采取何种方式编码呢？暂时用 hash 函数编码。编码之后的效果将是每一个关键词都有一个特定的编码，如下图所示（与上文 big_index 文件比较一下便知）：-Firelf- 对应编码为：135942-11 对应编码为：106101. 但细心的朋友一看上图便知，其中第 3439 行显示，有重复的编码，那么如何解决这个不重复编码的问题呢？用 hash 表编码？但其极易产生冲突碰撞，为什么？请看：哈希表是一种查找效率极高的数据结构，很多语言都在内部实现了哈希表。PHP 中的哈希表是一种极为重要的数据结构，不但用于表示 Array 数据类型，还在 Zend 虚拟机内部用于存储上下文环境信息（执行
13、上下文的变量及函数均使用哈希表结构存储）。理想情况下哈希表插入和查找操作的时间复杂度均为 O(1)，任何一个数据项可以在一个与哈希表长度无关的时间内计算出一个哈希值（key），然后在常量时间内定位到一个桶（术语 bucket，表示哈希表中的一个位置）。当然这是理想情况下，因为任何哈希表的长度都是有限的，所以一定存在不同的数据项具有相同哈希值的情况，此时不同数据项被定为到同一个桶，称为碰撞（collision）。哈希表的实现需要解决碰撞问题，碰撞解决大体有两种思路，1. 第一种是根据某种原则将被碰撞数据定为到其它桶，例如线性探测如果数据在插入时发生了碰撞，则顺序查找这个桶后面的桶，将其放入第一个
14、没有被使用的桶；2. 第二种策略是每个桶不是一个只能容纳单个数据项的位置，而是一个可容纳多个数据的数据结构（例如链表或红黑树），所有碰撞的数据以某种数据结构的形式组织起来。不论使用了哪种碰撞解决策略，都导致插入和查找操作的时间复杂度不再是 O(1)。以查找为例，不能通过 key 定位到桶就结束，必须还要比较原始 key（即未做哈希之前的 key）是否相等，如果不相等，则要使用与插入相同的算法继续查找，直到找到匹配的值或确认数据不在哈希表中。PHP 是使用单链表存储碰撞的数据，因此实际上 PHP 哈希表的平均查找复杂度为 O(L)，其中 L 为桶链表的平均长度；而最坏复杂度为 O(N)，此时所有
15、数据全部碰撞，哈希表退化成单链表。下图 PHP 中正常哈希表和退化哈希表的示意图。哈希表碰撞攻击就是通过精心构造数据，使得所有数据全部碰撞，人为将哈希表变成一个退化的单链表，此时哈希表各种操作的时间均提升了一个数量级，因此会消耗大量 CPU 资源，导致系统无法快速响应请求，从而达到拒绝服务攻击（DoS）的目的。可以看到，进行哈希碰撞攻击的前提是哈希算法特别容易找出碰撞，如果是 MD5 或者 SHA1 那基本就没戏了，幸运的是（也可以说不幸的是）大多数编程语言使用的哈希算法都十分简单（这是为了效率考虑），因此可以不费吹灰之力之力构造出攻击数据.（上述五段文字引自：http:/www.codinglabs.org/html/hash-collisions-attack-on-php.html）。24.4、暴雪的 Hash 算法值得一提的是，在解决 Hash 冲突的时候，搞的焦头烂额，结果今天上午在自己的博客内的一篇文章（ 十一、从头到尾彻底解析 Hash 表算法）内找到了解决办法：网上流传甚广的暴雪的 Hash 算法。 OK，接下来，咱们回顾下暴雪的 hash 表算法：“接下来，咱们来具体分析一下一个最快的 Hash 表算法。我们由一个简单的问题逐步入手：有一个庞大的字符串数组，然后给你一个单独的字符串，让你
