Head First Search Engine&1&Web Crawlers&bitmap

Head First Search Engine 1——Web Crawlers——bitmap

搜索引擎中的ADT（Abstract Data Type）及算法是我本科毕业论文所涉及的内容，谈不上研究，只是粗略的涉及了点皮毛，拿Lucene做了套小规模的搜索引擎。本来这个毕业设计是为了考研复试准备的，遗憾的是连初试都没有过。但是这并不影响我再考一年的决心，现在一边工作一边考研，累的时候就上来写点儿东西，将之前学到的东西都记录下来，做个总结，也当是分享吧，如果其中有什么错误，还请见谅，本人水平一般。

这个系列主要想介绍一下搜索引擎的相关知识，以及在搜索引擎中涉及到的ADT及算法。这些ADT将和我们传统的数据结构教学中的ADT做比较。这些内容比较适合对数据结构这门课程的扩展教学。之所以喜欢用ADT，可能是受了清华朱忠涛老师的影响吧，当时在听他课的时候老用ADT(当然我不是清华的)，所以自己也用习惯了。好像严蔚敏老师上课也用的是ADT。

我大致规划了一下，这个系列主要会讲到如下方面：
Head First Search Engine 1——Web Crawlers  bitmap、图算法、哈希表等。
Head First Search Engine 2——analytical system  堆栈。
Head First Search Engine 3——Index System  归并排序。
Head First Search Engine 4——Query System  堆排序。

在这些文章中，我基本会涉及到所有的传统数据结构，就当是为接下来的考研做个复习。在文章列表里有个Algorithms的分类，不再写有关传统ADT了，那里主要会放一些比较精巧的算法，比如协同过滤、多分树存储这些。

下面开始讲述这节的主要内容Bitmap:
在搜索引擎这套系统中，如果按照运行流程来分，可以分为四个子系统，分别是：下载系统、分析系统、索引系统和查询系统。
下载系统：其中有我们熟知的网络爬虫，他主要负责抓取网络当中的页面，并交由分析系统做处理。
分析系统：主要做页面的解析工作，这些解析包括页面中链接的分析、对页面内容进行分词、对网页的内容按照一定的规则进行打分等。
索引系统：主要对处理完的页面建立索引，并做简单的排序工作。
查询系统：直接面向用户，是我们所说的“检索”的门户，主要负责对大规模数据查找和排序，找出符合用户需求的信息。




下面我们模拟这样一个环境：
我们将一个页面当作是图(Graph)中的顶点(Vertex)，将指向其他页面的链接(link)看作是图中的边(edge)。有了这个假设之后，整个互联网就可以看作是一张巨大的有向连通图。假设我们的爬虫从一个导航页面开始对互联网进行遍历，下面问题来了，你怎样保证爬虫所走过的路不会产生环路？或者，怎样保证在同一次抓取过程中，被抓取过的页面不再被重复抓取？

我觉得很容易可以想到用哈希表，或者更直接的说，如果我用Java语言，我可以使用Map或者Set这样去重复的集合来做这件事情。当然也会有人想到用数据库来做帮助，因为那也有唯一主键。是的，我们需要的就是唯一。可是用上述的方法来做，是否会太浪费空间了，如果用数据库了，每次抓取前先遍历一遍数据库，是不是太小题大做了。

我们知道hash表的查找效率是非常高的，为O(1)，在Java中如果我们将链接映射到hash表中，那样的话很容易通过hash code就能找到原纪录是否存在。其核心只要我们能减少存储空间即可。

采用bitmap这种数据结构的好处主要是在不改变查询效率的同时，可以节省空间。
拿java为例，一个Int类型的数占了4个字节(B)，即32位(bit)，如果建立一个存放整型数据且长度为8的hash表，则需要32字节，共256位。如果采用传统的hash表使用方式，长度为8的哈希表，最多只能存放8条互不相同的记录。

我相信写到这里很多人已经想到了，如果我们按位(bit)存储，而不是传统的按字节存储，即用比特(bit)位来区分这些记录，那长度为8的哈希变不就能存放256条互不相同的记录了么？




确实，bitmap就是用这种思路来压缩存储的，这样一来，上面的例子中，一下子节省了1/32的空间。bitmap这种ADT，借助按位与和按位或，以及左移运算(<<)和右移(>>)运算来实现压缩存储信息。下面我们来看具体的实现细节：

public static void testBitmap(int num) {
		int MD5 = num;
		int index_int = MD5 & 31;
		int index_Hash = (MD5 >> 5) & 7;// (34/32)%8=1
		System.out.println(index_Hash);
		if ((Hash_MD5[index_Hash] & (1 << index_int)) != 0) {// 查询某个比特为是否为1
			System.out.println("has been used");
		} else {
				Hash_MD5[index_Hash] = Hash_MD5[index_Hash] | (1 << index_int);
			if ((Hash_MD5[index_Hash] & (1 << index_int)) == 1) {
				System.out.println("successful");
			}
		}
	}

其中：传入的参数num为通过MD5单项函数处理过的链接，这部分内容我会放在下一讲关于hash数据结构中讲述。现在你只要知道，一个URL通过MD5函数转换成了一个整型的数据，及num，然后将num按位存储。

我们对上述细节再做一些描述：
例如一个URL：www.baidu.com经过MD5函数计算后，转换成了数值34，然后，我们将对34做bitmap处理。在这里我们使用长度为8的整型数组做示例，即Hash_MD5[0…7]。
第一步，（34/32）%8==1，即程序中的index_Hash = (MD5 >> 5) & 7，求出这个num应存放在Hash_MD5[1]中。
第二步，34%32==2，即程序中的Hash_MD5[index_Hash] | (1 << index_int)，这样就能确定在Hash_MD5[1]中，低位的第2位被置为1(低位从0开始，二进制编码为：00000000 00000000 00000000 00000100)。所以在Hash_MD5[1]中存放的值为4。

当然，有一种更简单的方法：
直接将34化为二进制形式，即0010 0010，因为每个单元是长度是32bit，所以我们将二进制前后分为001 | 00010，这样一来，前面的值代表存储在数组中的位置(即按字节存，Hash_MD5[1])，后面的值为2，代表了按bit存，将低位第三位置为1。
例如：又有一个URL经过MD5函数转换为45，转化为二进制后即 001 | 00111，这样可知，按bit存，将低位第13位置为1(低位从零开始)。然后将Hash_MD5[1]中原本的4，加上现在的2^13，相加后为：2^13+2^2。

以上算法在实际处理中也会遇到问题：
面对相当庞大的数据集时，很容易造成数据在定位上的冲突，针对这一问题，当然有很多解决办法，比如在数据结构课程中讲到的开放定址法、拉链法等。但是这样做会给查找也带来一定的麻烦。产生这种冲突的主要原因就是bitmap的前期处理——将URL转换成数值的过程。因为这里的处理做的比较简单，只通过一个MD5函数进行转换，所以才增大了冲突的概率。就个人认为，这种概率上的问题并不是由bitmap这种数据结构本身带来的，至于前期如何做处理才能保证没有冲突，那是前期的问题。Bitmap确实是给了我们一种很好的解决问题的办法。

有一种ADT叫Bloom Filter，据说可以解决以上问题。其实Bloom Filter解决问题的原因并不在处理存储的过程上，而是前期对数据的处理。Bloom Filter用了多个哈希函数来确保转换的唯一性。

综上，bitmap很厉害，可以给我们的处理带来很多启发，不论实在查重或者数据压缩上，但是根据bitmap存在的风险，我们需要由哈希函数来解决。所以下一节，将写关于哈希的相关知识。

以上只是一种思路，具体的实现网上应该都有成篇的代码。个人愚见，谢谢观看。

本文原创，转载请指明出处，谢谢。