搜索引擎技术之数据结构

搜索应用技术冲出宇宙2008.111111预备知识如果只是给一个普通项目提供搜索支持，你不需要多少预备知识，可以跳过本节。如果你想把搜索作好，建议你看本节。本节假定读者已经具备计算机专业本科水平。本预备知识包含了搜索引擎一般需要使用的而普通课本上面又没有详细描述的数据结构和压缩算法。1.11.11.11.1数据结构数据结构数据结构数据结构1.1.11.1.11.1.11.1.1HHHHashashashash函数定义：Hash函数把任意范围的key映射到一个相对较小的整数范围内。比如，md5hash算法就是把任意字节数组映射到128位的整数上。Hash函数在很多领域都有应用，比如，模式匹配、密码学。它们都额外的定义了Hash函数的其他特点，如密码学要求Hash函数接近于单向函数。我们这里只讨论Hash函数在Hashtable结构里面的应用。1.1.1.11.1.1.11.1.1.11.1.1.1常用常用常用常用HashHashHashHash函数介绍函数介绍函数介绍函数介绍Hash函数一般会分为2种，即Hashtable用的hash和密码学上面应用的Hash。这里分开介绍。1.1.1.1.11.1.1.1.11.1.1.1.11.1.1.1.1HashHashHashHashtabletabletabletable的HashHashHashHash函数应用在Hashtable上的Hash函数的一个主要特点是输出一般为32或者64位。常见的算法有很多种，有关这些Hash算法的实现代码，可以参考笔者博客上的文章：Hash算法实现。1.1.1.1.21.1.1.1.21.1.1.1.21.1.1.1.2密码学上的HashHashHashHash函数密码学上的Hash函数第一重要的是其伪单向性。故一般其计算都特别复杂，结果位数也很长。我们常见的Hash函数有如下几个：Adler-32：定义在rfc1950里面，是一种乘法Hash算法，结果是32位整数；CRC32：循环冗余码，结果是32位整数；MD系列：md3,md4,md5等，结果都是128位整数；考虑到md5冲突的易构造性，建议不要用它做重要消息签名；搜索应用技术冲出宇宙2008.12RipedMd系列：有128/160/256/320位4种规范，但RipedMd-256/320没有被认真设计，其安全度和128/160这2种规范一样；SHA系列：有160/256/384/512位4种规范；Tiger：192位，专门为64位机器优化；WhirlPool：512位。这里，需要注意的是，美国的国家标准推荐使用如下几个Hash算法：RipedMd系列，SHA系列，Tiger和WhirlPool。具体的说明大家可以去看密码学相关书籍（推荐《密码学基础（英文版）》和《现代密码学理论与研究》）或者学习著名的开源库Crypto++或者参考笔者的博客：Hash散列算法详细解析。1.1.1.21.1.1.21.1.1.21.1.1.2HashHashHashHashtabletabletabletable处理碰撞的技术处理碰撞的技术处理碰撞的技术处理碰撞的技术Openaddressing（closedhashing）：探测方式。通过选择不同的位置来存放数据。线形探测：计算公式为next_pos=(cur_pos+m)modN；其中m为常数，N为Hashtable数组长度；平方探测：常用计算公式为next_pos=(cur_pos+cur_pos^2)modN；二次Hash：常用计算公式为next_pos=(cur_pos+Hash2(key))modN；Hash2表示第二个Hash函数。Chaining：链表方式。即把冲突的key串在一起。以上两种碰撞处理技术很多数据结构书籍都详细描述过，本处不在赘述。下面看看其他的方法：Coalescedhashing：结合了Openaddressing和Chaining方法，把Chaining的链表融合到Hashtable的数组里面，从而减少了空间使用。下面用一个例子说明这种方式。输入key序列为{“qur”,“qrj”,“ofu”,“gcl”,“clq”,“ecd”,“aty”,“rhv”,“qus”}，左边图是基本Chaining方式的结果，右边图是本方式的结果：Null“clq”“qur”Null“dim”“aty”“rhv”“qrj”NullNull“qsu”“ofu”“gcl”“ecd”搜索应用技术冲出宇宙2008.13Coalescedhashing方式的处理方法为：利用线形探测找到一个空位，填入key，然后把这个空位链接到相同映射值组成的链表上面。需要注意的是，Coalescedhashing对定长的key才真正有用。Cuckoohashing：基本思想是使用2个hash函数来处理碰撞，从而每个key都可以对应到2个位置。其具体的处理方式为：如果key对应的2个位置中有一个为空，key就可以插入到那个位置；否则，任选一个位置，key插入，把已经在那个位置的key踢出来；被踢出来的key需要重新插入；直到没有key被踢出为止。显然，这种方式是可能产生无限循环的，当出现无限循环的时候，就需要重新选择hash函数。Cuckoohashing有2个主要的变形：1）增加hash函数的个数；2）每个位置可以放2个key。这2个的目的都是为了增加Hashtable数组的利用率，因为基本的Cuckoohashing只有49%的利用率，而3个Hashtable可以利用91%的空间，每个位置保存2个key可以使利用率达到80%。有人分析Cuckoohashing比Chaining的方式更好。基本CuckooHashing的实现，参考笔者博客文章：CuckooHash介绍。1.1.21.1.21.1.21.1.2TrieTrieTrieTrie树也叫前缀数组，是一种key为字符串的联合数组。下图是一个简单示例：**itoteteatenitoeanTrie树的一个主要特点是查询字符串Key很快。有关Trie树的介绍可以参考一般的数据结构书籍。基本的Trie树占用的内存很大，人们发明了基于数组的Trie结构。双数组Trie树其实是把Trie树中的所有节点拼接在一起，减少占用的空间。以上图来说，这棵树可以用7个（7个节点，从上往下编号）数组表示：Node1[0:256]={null}，Node1[‘t’]=Node2，Node1[‘i’]=Node3，isNodeHasData=falseNode2[0:256]={null}，Node2[‘o’]=Node4，Node2[‘e’]=Node5，isNodeHasData=falseNode3[0:256]={null}，isNodeHasData=true搜索应用技术冲出宇宙2008.14Node4[0:256]={null}，isNodeHasData=trueNode5[0:256]={null}，Node5[‘a’]=Node6，Node5[‘n’]=Node7，isNodeHasData=trueNode6[0:256]={null}，isNodeHasData=trueNode7[0:256]={null}，isNodeHasData=true注意到共有7个256个元素的数组，数组元素表示对应节点的孩子节点对应的数组，数组里面大部分都是Null值，所以如果把它们组合在一起，可以大大减少空间占用。在上面的这个例子中，可以简单的把所有数组混合起来，因为它们没有冲突；也可以把所有数组并排；前者组合后的数组大小为256，后者组合后的数组大小为256*7。实际中，直接混合数组会有很多冲突，而并排所有数组又十分浪费空间，故必须找一个好的办法来避免冲突同时减少空间浪费。文章“Fastandcompactupdatingalgorithmsofadouble-arraystructure”提出了一种基于空余空间链接的混合数组的算法，这是一种贪婪算法，能够较好地减少空间浪费。在实际应用中，我们发现这种算法的构建速度极慢，主要慢在贪婪算法上面。为了加快速度，我们在贪婪算法的基础上，跳过那些可能不匹配的位置，在多浪费一点空间的情况下，能够快速的构建双数组Trie树。下面是双数组Trie树使用java实现的一个版本：importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;importjava.util.TreeMap;importjava.util.Map.Entry;importlotusroots.algorithms.common.array.SimpleIntArrayList;importlotusroots.algorithms.common.array.SimpleObjectArrayList;/***Trie结构支持下的Mapbr*主要好处：br*1，内存占用很少；br*2，查询速度几乎是最快，好于其他任何Map结构；br*3，删除很快，比TreeMap好；br*4，加入速度可以，比TreeMap差；br*5，修改飞快，比TreeMap好；br*br*限制：br*只能使用String作为Keybr**@authorGoodzzp2007-5-10*@lastEditGoodzzp2007-5-10*/publicclassTrieMapT{/***状态列表*/SimpleIntArrayListm_states;/***状态检测列表*/SimpleIntArrayListm_checks;/***对应的对象*/SimpleObjectArrayListm_refObjs;/***构造函数*@paramds字符串列表*@paramos对应的对象列表*/publicTrieMap(ListStringds,ListTos){initial(ds,os);}/***构造函数*/publicTrieMap()搜索应用技术冲出宇宙2008.15{ListStringstrs=newArrayListString();ListTobjs=newArrayListT();strs.add(goodzzpproviderit!);objs.add(null);initial(strs,objs);}/***初始化*@paramds字符串列表*@paramos对象列表*/privatevoidinitial(ListStringds,ListTos){ListStringstrs=newArrayListString();ListObjectobjs=newArrayListObject();//1,排序TreeMapString,ObjectsortTree=newTreeMapString,Object();for(inti=0;ids.size();i++)sortTree.put(ds.get(i),os.get(i));IteratorEntryString,Objectiter=sortTree.entrySet().iterator();while(iter.hasNext()){EntryString,Objecte=iter.next();strs.add(e.getKey());objs.add(e.getValue());}//2,构建trie数组SimpleIntArrayListstates=newSimpleIntArrayList();SimpleIntArrayListchecks=newSimpleIntArrayList();SimpleObjectArrayListrefObjs=newSimpleObjectArrayList();s