自适应检索树与对GPERF的改进算法

作     者：王管冲 

作者单位：福州大学 

学位级别：硕士

导师姓名：傅清祥

授予年度：2004年

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：自适应 检索树 散列算法 trie gperf hash 

摘      要：“查找在计算机的任何算法中几乎无处不在。据报道，计算机70％以上的时间在进行查找工作。因此节省查找的时间和空间成为了一个重要的研究课题。检索树（trie树）是支持较快查找算法的结构。传统的trie树是一种按字节进行检索的多叉树，具有比hash表更快的查找速度，主要应用于变长字符串的索引。其主要缺点是分支结点大，空间利用率低，因为传统的trie树的分支结点上的一个link指针仅可指向一个叶结点，通常情况下许多link指针为空。我们的实验表明其非空率只有1／40。对传统的hash算法，最坏情况下查找、插入、删除的时间复杂性都是O（n）。可扩充散列的查找在最坏情况下的时间复杂性为O（maxkeysize）(maxkeysize为关键字的最大长度，实际中多为常数)。但插入、删除的最坏时间复杂性都是O（n），并且空间复杂性随记录数的增加呈超线性增长，即空间利用率在记录数较大时是很低的。所谓“完美的自适应hash算法，虽然查找的时间复杂性一般较小，但插入后解决冲突的最坏时间复杂性均在O（n）以上。本文主要做两方面的工作。第一，改进自适应hash算法gperf，使解决冲突的速度提高数百倍，并进一步降低查找的时间。第二，在进一步分析检索树，散列，和可扩充散列等几种算法的设计思想和优缺点的基础上，进行综合，提出了自适应检索树的算法。该算法所支持的插入、查找、删除在最坏情况下时间复杂性均为O（maxkeysize），空间复杂性为O（n）。 本文的创新之处主要在于： 1．在研究了传统的检索树的基础上，提出自适应检索树的数据结构，并给出其支持ADT字典的算法，在不增加算法的时间复杂性的前提下，大大改善传统检索树的空间复杂性，使空间复杂性系数由原来的40左右，降低到3以下。其中的自适应性一方面体现在分支结点的规模按需的可伸缩，另一方面体现在分支结点的每一个指针（link）可指向一个字典元素的链表，而且链表的长度等于该分支结点所在的层次加1。这两方面的自适应性大大降低了全树空link的比例，从根本上降低了检索树的空间复杂度，使之作为字典的存储结构更具优势。 2．针对***的GPERF（完美的Hash函数生成器）中存在的效率问题，采取包括充分挖掘、利用字典元素关键字的信息，减少冲突，避免无效计算，限制单桶最大冲突数，将解决冲突的工作分摊给查找操作，分级散列等措施，提出对GPERF的改进算法，并被实验证明改进的效果显著，使解决冲突的速度提高数百倍，并进一步降低查找的时间。