创新计划: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
No edit summary
imported>Y0ukn0w
 
(43 intermediate revisions by 5 users not shown)
Line 3: Line 3:
*'''''Attitude decides everthing'''''
*'''''Attitude decides everthing'''''


=Perfect Hashing Function Principles and Practice=
= Progress Log =


==1.前言==
*[[Yonghang]]
在很多应用中,都要用到一种动态集合结构,它仅支持INSERT,SEARCH和DELETE字典操作。例如,计算机程序设计语言的编译程序需要维护一个符号表,其中元素的关键字值为任意字符串,与语言中的标示符对应。实现字典的一种有效数据结构为散列表(hash table)。
在最坏情况下,在散列表中,查找一个元素的时间与在链表中查找一个元素的时间相同,在最坏情况下都是Θ(n),但在实践中,散列技术的效率是很高的。在一些合理的假设下,在散列表中查找一个元素的期望时间为O(1)。散列表是对普通数组概念的推广。[CLRS]
由于其具有其他很多数据结构都不具有的优点,散列的应用甚为广泛,从信息安全(例如文件校验,数字签名,签权协议)到搜索引擎(eMule)再到现在人们广泛应用的各种高速下载软件,都能看到其身影。可以说,如果没有它,Google都是不可能实现的。
毫无疑问,这种算法的探究具有重要意义。尽管前述各种方式看来在实现上似乎已经毫无问题,但是,我们要指出,完美散列仍然有一些问题没有解决,而这些问题也是在这种算法中最为重要的冲突。


==2.正文==
*[[Kaiyuan]]
===2.1  经典方法===
当关键字的全域U比较小时,直接寻址是一种简单而有效的技术。
然而,直接寻址技术存在一个明显的问题,如果域很大,受内存的限制,这就有点不实际了。而且分配给表T的大部分空间都要浪费掉。1953年,H.P.Luhn[Luh53]首先提出了散列表这一技术,以及用于解决碰撞的链接(chaining)方法。
我们利用hash function h,根据关键字k计算出槽的位置:
h:U→{0,1,…,m-1}
从而降低了空间开销。
这样做又有一个小问题:两个关键字可能映射到同一个槽上,我们称这种情形为发生了碰撞(collision)。我们需要采取有效的方法来避免碰撞。
====2.1.1====
链接法(chaining)是一种最简单的碰撞解决技术。在chaining中,把散列到同一槽中的所有元素都放在一个链表中,如图所示。槽j中有一个指针,它指向所有到j的元素构成的链表的头;如果不存在这样的元素,则j中为NIL。
====2.1.2====
在差不多同一时间,G.M.Amdahl首先提出了开放寻址法的思想。
在开放寻址法(open addressing)中,所有的元素都存放在散列表里。亦即,每个表项或包含动态集合的一个元素,或包含NIL。当查找一个元素时,要检查所有的表项,直到找到所需的元素,或者最终发现该元素不在表中。不像chaining,没有链表,没有元素存放在散列表外。Open addressing 的好处在于它根本不用指针,而是计算出要存取的各个槽。
有三种技术常用来计算open addressing中的探查序列:线性探查(linear probing),二次探查(quadratic probing),以及双重散列(double hashing)。
线性探查:给定一个普通的散列函数h’:U→{0,1,…,m-1},linear probing采用的散列函数为:h ( k , i )=( h’(k)+ i )mod m, i=0,1,…m-1。线性探查方法比较容易实现,但它存在一个问题,称为一次群集(primary clustering)。随着时间的推移,连续被占用的槽不断增加,平均查找时间也随着不断增加
二次探查:quadratic probing采用如下形式的的散列函数:
h( k , i ) = ( h’(k)+c1i+c2i2)mod m
初始的探查位置为T[h’(k)],后续的探查位置要在此基础上加上一个偏移量,该偏移量以二次的方式依赖于探查号i。这种探查方法的效果要比线性探查好很多。
双重散列:double hashing是用于开放寻址法的最好方法之一,因为它所产生的排列具有随机选择的排列的许多特性。它采用如下的散列函数:
h( k , i )=( h1(k)+ih2(k))mod m
与线性探查或二次探查不同的是,这里的探查序列以两种方式依赖于关键字k,因为初始探查位置、偏移量都可能发生变化。如图所示,给出了一个用双重散列法进行插入的例子。此处,散列表的大小为13,h1(k) = k mod 13,h2(k) = 1+(k mod 11)。因为14≡1(mod 13),且14≡3(mod 11),故在探查了槽1和槽5,并发现它们已被占用后,关键字14被插入到空槽9中。
====2.1.3 ====
任何一个特定的散列函数都可能出现某种最坏情况形态:所有的关键字全部散列到同一个槽中。唯一有效的改进方法是随机地选择散列函数,使之独立于要存储的关键字。这种方法称作全域散列(universal hashing)。
全域散列的基本思想是在执行开始时,就从一族仔细设计的函数中,随机地选择一个作为散列函数。就像在quick sort中,随机化保证了没有哪一种输入会始终导致最坏情况形态。同时,随机化使得即使是对于同一个输入,算法在每一次执行时的形态也都不一样。这样就可以确保对于任何输入,算法都具有较好的平均情况性态。
====2.1.4====
算法导论中介绍的版本,假设了一个理想的散列函数(hash function),是一个完全随机的函数.这个假设叫Simple Uniform Hash Assumption (SUHA或者UHA),认为经其散列后完全没有碰撞。
对这些经典方法的分析都建立在对hash function理想的假设前提下。SUHA为分析提供了方便,经典的结果例如TAOCP,算法导论等,都是基于这个假设。
这是一个过于理想的假设,实际中可以实现的散列函数是k-wise independent的,而k往往是一个常数。例如常用的linear congruential function (ax+b)mod n,它只是pair- wise independent,即2-wise。这已经成为了现实研究的一个瓶颈。
===2.2 现代方法===
====2.2.1====
如果某一种散列技术在进行查找时,其最坏情况内存访问次数为O(1)的话,则称其为完美散列(perfect hashing)。设计完全散列的基本想法是比较简单的。我们利用一种两级的散列方案,每一级采用全域散列,可以实现静态的部分功能。
perfect hashing是一个数据结构,它解决的问题是查找一个集合中元素的存在性.这也是计算机科学最经典的问题之一,Knuth的《计算机程序设计的艺术》第三卷《sorting and searching》的searching就是关于这个问题。这个问题的经典解法,二分查找和查找树等[Knu71],时间复杂度都是O(log n)。
而 perfect hashing在线性的O(n)空间复杂度上达到了常数级的时间复杂度。这是历史上第一次达到这样的解.在此之前人们甚至不太相信我们可以同时在时间和空间上达到最优。无论对于多么庞大的数据集,要查找一个数据对象,只需要读三次即可,这是非常惊人的。可以说如果没有发现这个解,Google都是不可能实现的。
基于SUHA,数学上可以证明,O(1)时间复杂度下至少需要O(n2)的空间复杂度,这显然不能令人满意。


人类的愿望有两点:
*[[current target]]
1.  O(1)时间O(n)空间(时、空复杂度同时最优)
2. 将理想的hash function假设转变为现实的假设。
====2.2.2====
第一点,人们一直以为不可能实现,人们以为二分查找的O(log n)复杂度对于线性空间已经最优了。直到Yao1981[Yao81]和Tarjan&Yao1979[TY79]提出了O(1)时间和O(n)空间的可能,但它们二者都对hash function的定义域提出了不符合现实的假设,前者需要假设hash function的定义域极大,后者却假设太小。这两个方法都不是现实中可以使用的方法,但却为实现perfect hashing的梦想开启了一扇门,使人们意识到这是可能的。
1984年,基于Yao的工作,由三位数学家Fredman ,Komlos和Szemeredi提出的FKS perfect hashing[FKS84],可以使每次查询只需要常数级的时间,而且数据结构的空间复杂度仍然只有线性的O(n)。
FKS算法的思路是把hash table分散到两级:
In the first level, n items are hashed to n buckets by a 2-universal hash function h.
Let Bi be the set of items hashed to the it h bucket.
In the second level, construct a | Bi | 2-size perfect hashing for each bucket Bi.
The data structure can be stored in a table. The first few entries are reserved to store the primary hash function h. To help the searching algorithm locate a bucket, we use the next n entries of the table as the "pointers" to the bucket: each entry stores the address of the first entry of the space to store a bucket. In the rest of table, the n buckets are stored in order, each using a | Bi | 2 space as required by perfect hashing.
26年过去了,这个漂亮的理论结果对计算机理论研究产生了深远的影响。在实际应用中,Linux下的CMPH library实现了基于FKS思想的一系列数据结构。然而CMPH library只针对静态的情况,即数据集不会改变。FSK算法只是静态的,而实际应用中往往需要更新(update)。
1994年,数据集中的元素被动态的添加(insert)和删除(delete)在理论上已经得到常数级的解[DKM+94]。然而这个结果在现实中仍然缺乏很好的实现,目前还没有任何标准库实现了这一功能。其原因是它所利用的散列函数 (hash function)的计算需要很多的乘法运算,这在理论模型中是被忽略的,但在苛刻的现实条件中,cpu做乘法被认为是及其低效的。
这个结果还有个缺陷,不是最坏时间复杂度O(1)而是amortized time complexity,平摊时间复杂度是O(1)。原因在于FKS的hash function的分配并不平均。
====2.2.3====
第二点,由理想的simple uniform hash assumption转为Carter-Wegman[CW79]的universal classes of hash functions。universal classes of hash functions可以被视为一条链接理论和现实的辅助线。从理论的角度而言,它是更弱的随机性假设。从现实的角度,它是可以有效实现的随机性保证。因此,从universal hashing的假设出发,可以严格的证明(而不是基于理想的假设)hash table的效率。Carter-Wegman原始的universal hash function的构造是基于多项式,效率不够好(因为需要乘法和模运算)。[DHKP97]提出了新的universal hash function的构造,非常高效,因此在实践中大量使用。这个函数甚至可以被表示成为仅仅一行的c代码:
h(x) = a * x >> ( 32 – k );
它的不足在于随机性能不够好(只保证pair-wise independence),因此在FKS中使用仍然无法做到平均分配。因此动态更新的时间复杂度无法从amortized O(1) time改进为worst-case O(1) time。对此,[DMadH90]中的hash function可以做到FKS的worst-case O(1) time所需的足够的随机性。然而,[DMadH90]中的hash function无论空间的使用(O(sqrt(n)))还是计算的效率都远远落后与[DHKP97]提出的那个已在在现实中大量应用hash function。因此现实中人们宁愿忍受糟糕的worst-case time complexity,也仍旧使用随机性不够好却可以高效计算的[DHKP97]的hash function。
我们需要解决这一对矛盾。寻找既有良好随机性,足够另FKS拥有worst-case O(1) time,又可以高效率计算的hash function。
====2.2.4====
最新发展情况。出现了cuckoo hashing,其基本思想是使用两个hash function而不是只用一个,这样对于每个关键词有两个可能的位置。当插入一个新关键词的时候,采用贪心法,如果该位置已经被占,则像杜鹃一样把它踢出巢,被踢出的元素寻找下一个可选位置,这个定义是递归的。对于cuckoo hashing,Pagh 2001[Pag01]提出了静态版本。Pagh, Rodler 2004[PR04]提出了动态版本。两个目前都基于uniform hash assumption的理想假设。理论上,使用uniform hashing function是open problem, 实践中,目前根本没有实现cuckoo hashing的标准库。
因此我们可以实验cuckoo hashing在实际hash function上的性能,以及实现一个可以用的cuckoo hashing 库。
==3.小结==
===3.1===
关于现有的perfect hashing库如CMPH、gperf、Sux4J。
上面已经提过了,在实际应用中,Linux下的CMPH library实现了基于FKS思想的一系列数据结构。然而CMPH library只针对静态的情况,即数据集不会改变。同样的,gperf和Sux4j也类似。
===3.2===
我们要做的就是在有限的独立性假设下,支持完美散列。这是非常有现实意义的一件事。[DKM+94]这个结果没有很好的实现,主要原因是对于散列函数的假设过于理想,这是一个比较基本的难点。
1.同时,我们需要解决随机性和运算效率之间的矛盾,得到一个令人较为满意的散列函数。
2.此外,测试cuckoo hashing的性能,并实现一个可以用的cuckoo hashing库。
3.实现一个动态perfect hashing的Linux open source library。
4.尝试对成果数学性质的证明。
===3.3===
可能的实践方案如下: 
  第一步:在前人的假设基础上以及理论支持下(包括使用已有的解决碰撞的问题和已有的散列函数)实现静态版本的完美散列,从中体会散列表这种数据结构优点及其存在的不足。
  第二步:在第一步的基础上,实现动态版本的完美散列。主要实现数据的更新,包括对关键字的增加和更改等。
  第三步:自己独立设计散列函数,记录构造过程。然后在用自己的散列函数去实现静态和动态的完美散列。
  第四步:从理论上论证函数的可行性。推导构造同类函数的具体过程。
  第五步:将解决碰撞的函数和实现动态更新功能的完美散列联系起来,得到综合性解决方案,针对前述的问题加以修正完善。
  第六步:做出令人满意的库函数。至少可以做出比目前的标准库更好的。
  第七步:尝试对数学性质的证明。


==4.References==
=Document=
*[http://en.wikipedia.org/wiki/Introduction_to_Algorithms <nowiki>[CLRS]</nowiki> T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms.]
 
*[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-4B55K9J-D&_user=6422187&_coverDate=04/30/1979&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1512554346&_rerunOrigin=scholar.google&_acct=C000056877&_version=1&_urlVersion=0&_userid=6422187&md5=7cbcb9763f8abaffa112614676cef7d6&searchtype=a<nowiki>[CW79]</nowiki> J.L. Carter and M.N. Wegman. Universal classes of hash functions. Journal of computer and system sciences, 18(2):143{154,1979.]
*[[Literature Review]]
*[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-45NJK2G-2&_user=6422187&_coverDate=10/31/1997&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1512562639&_rerunOrigin=scholar.google&_acct=C000056877&_version=1&_urlVersion=0&_userid=6422187&md5=8f79b5111fe7a572f057cce708aa0ff0&searchtype=a <nowiki>[DHKP97]</nowiki> M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen. A Reliable Randomized Algorithm for the Closest-Pair Problem. Journal of Algorithms, 25(1):19{51, 1997.]
*[[FSK Hashing]]
*[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=21968&tag=1<nowiki>[DKM+94]</nowiki> M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F.M. Heide,H. Rohnert, and R.E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM Journal on Computing, 23(4):738{761, 1994.]
*[[Dynamic Perfect Hashing]]
*[http://www.springerlink.com/content/5467537110456057/<nowiki>[DMadH90]</nowiki> M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP'90), volume 443, pages6{19. Springer, 1990.]
*[[Cuckoo Hashing]]
*[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4568389<nowiki>[FKS84]</nowiki> M.L. Fredman, J. Koml_os, and E. Szemer_edi. Storing a SparseTable with O(1) Worst Case Access Time. Journal of the ACM (JACM), 31(3):538{544, 1984. ]
*[http://www.dcc.uchile.cl/~rbaeza/handbook/hbook.html<nowiki>[GBY91]</nowiki> G.H. Gonnet and R.Baeza-Yates. Handbook of algorithms and data structures: in Pascal and C. Addison-Wesley, 1991.]
*[http://www.springerlink.com/content/uj8j384065436q61/<nowiki>[Knu71]</nowiki> D.E. Knuth. Optimum binary search trees. Acta Informatica, 1(1):14{25, 1971.]
*[http://neerc.ifmo.ru/school/io/archive/20090516/problems-advanced-07.pdf<nowiki>[Knu73]</nowiki> D.E. Knuth. The art of computer programming. Vol. 3, Sortingand Searching. Addison-Wesley, 1973.]
*[http://onlinelibrary.wiley.com/doi/10.1002/asi.5090040104/abstract<nowiki>[Luh53]</nowiki> H.P. Luhn. A New Method of Recording and Searching Information. American Documentation, page 14, 1953.]
*[http://portal.acm.org/citation.cfm?id=380836 <nowiki>[Pag01]</nowiki> R. Pagh. On the cell probe complexity of membership and perfect hashing. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 425{432. ACM NewYork, NY, USA, 2001.]
*[http://www.springerlink.com/index/5EHE9T6TQDRBH9WX.pdf<nowiki>[PR04]</nowiki> R. Pagh and F.F. Rodler. Cuckoo hashing. Journal of algorithms, 51(2):122{144, 2004.]
*[http://portal.acm.org/citation.cfm?id=359175<nowiki>[TY79]</nowiki> R.E. Tarjan and A.C.C. Yao. Storing a sparse table. Communications of the ACM, 22(11):606{611, 1979.]
*[http://portal.acm.org/citation.cfm?id=322274&dl=GUIDE,%E5%AF%86<nowiki>[Yao81]</nowiki> A.C.C. Yao. Should Tables Be Sorted? Journal of the ACM(JACM), 28(3):615{628, 1981.]


=Member=
=Member=
=== ===
name:徐勇航
----
E-mail:xuyonghang@gmail.com
=== ===
name:温开源
----
E-mail:weikaiyuan123@gmail.com


=Progress=
*;Member 1
:true name:徐勇航
:nickname:y0ukn0w,xyhchess
:E-mail:xuyonghang@gmail.com


=Document=
*;Member 2
:name:温开源
:nickname:NULL
:E-mail:weikaiyuan123@gmail.com


=Links=
=Links=
*[http://en.wikipedia.org wikipedia]
*[http://www.google.com google]
*[http://bbs.nju.edu.cn lilybbs]
*[http://songshuhui.net songshuhui:)]
*[http://innov.nju.edu.cn innovation project]
*[http://www.mtime.com mtime]

Latest revision as of 12:54, 2 December 2010

What We'd Like to Say

  • Theory is modern art
  • Attitude decides everthing

Progress Log

Document

Member

  • Member 1
true name:徐勇航
nickname:y0ukn0w,xyhchess
E-mail:xuyonghang@gmail.com
  • Member 2
name:温开源
nickname:NULL
E-mail:weikaiyuan123@gmail.com

Links