论文部分内容阅读
摘要：排序是软件领域的基本问题，常用排序算法中，快速排序算法最快，时间复杂度为O(n*lnn)。基数排序算法的时间复杂度可以达到O（g（n+mg））。并且只适合于像整数、字符串这类有明显结构特征的数据。我们在本文中提出一种新型的排序算法——哈希插入排序。它将哈希算法用于排序中。通过概率统计分析，证明它的时间复杂度为O(n)，大大优于基数排序。
关键词：排序；哈希；字符串数据结构；文本数据库
中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)01-0105-02
排序理论中存在一个基本原则：将一个大的数据集划分成许多小数据集将大大提高排序的效率。采用这一原则的算法被称为划分—归并排序算法，快速排序和归并排序是其中两种。然而，这两种算法需要许多步递归过程将一个大数据集划分成许多只包含一个数据的小数据集。在划分完成之后，归并排序还需要进行递归的归并，这都降低了排序的效率。
直接基数排序算法是另外一种划分-归并排序算法。直接基数排序算法使用2g个桶来划分有序队列。首先使用最高g位（ib-1ib-2 … ib-g）关键字，根据这g位关键字将数据放到各个桶中，这g位关键字具有相同值的数据被放到一个桶中。同样的，第二趟中，每个桶中的数据根据接下来的g位(ib-(g + 1)ib-(g+2)…ib-2g)关键字进行划分，每个桶中的数据被分到m个新的子桶中，后面的几趟也是这样进行。这样，数据一直没有离开它被分配到的桶。一个显著的问题是桶（子桶）的数量将会迅速爆炸，很多桶中只有很少的数据[4] 。直接基数排序算法的时间复杂度是O（g（n+mg））。
三路基数快速排序是另外一种基于这一原则的排序算法。同快速排序算法一样，它将数据分为三部分：大于，小于和等于给定值。同基数排序相似，当前输入等于初始的字符，移到下一位字符。 [6]
这些算法都需要许多步来完成把一个大数据集分成许多小数据集的工作。那么是否可以找到一种算法，使得这一过程可以一步完成？哈希函数可以做到这一点。
在计算机领域中，排序和哈希是两种完全不同的概念。原因在于，一个数据在有序表中的位置不仅仅由它的关键字的值决定，也受这个数据集的上下文环境影响。哈希函数只考虑使用关键字的值来组织哈希表，所以寻找一个哈希值，使数据在有序表中位置的哈希函数是几乎不可能的。即使存在，它也很复杂，效率很低。然而，我们发现哈希是一种很好的划分方法。冲突是哈希中的一种重要概念，降低冲突是设计哈希函数所需要重点考虑的因素。但从另一方面，两个数据的哈希值冲突，说明这两个数据被分到一个组中，这样划分就只需要一步来完成。
在本文中，我们将给出一种新的排序算法，它使用哈希的方式，将大数据集分为许多小数据集。使用插入排序对每个小数据集进行排序。在第1节中给出一些作为该算法基础的定义，在第2节中给出算法描述，在第3节中给出算法的性能分析，在第4节中给出针对冗余编码的关键字的改进。
1 定义
定义1(完美哈希函数)：一个哈希函数是完美哈希函数，当且仅当这个哈希函数能够给每一个数据一个唯一的哈希值。[1]
定义2(超级哈希函数)：一个哈希函数是一个超级哈希函数，当且仅当它的结果是一个全序关系，并且是一个完美哈希函数。[1]
William F. Gilreath提出文献[1]一种超级哈希函数，但这类哈希函数比较复杂，而且不容易找到。这是由于数据在有序线性表中的位置不仅仅由它的关键字的值决定，还取决于其他数据的关键字的值，即它所处的上下文环境。但这里可以找到一种弱化要求的哈希函数，这就是下面定义的划分哈希函数。
定义3 (划分哈希函数)
划分哈希函数的结果是一个偏序关系，即，将具有相同哈希值的数据视为一个集合，那么一个集合中的数据将都大于或者等于（小于或者等于）另一个集合中的数据。
最简单的划分哈希函数就是使用前k位关键字的值作为哈希值，将所有数据分到2k个子线性表中。进行这次划分操作只需要对每个数据进行一次操作，这大大优于快速排序算法。
2 数据结构和算法
下面考虑哈希插入排序算法，首先考虑非冗余关键字。该算法首先是使用使划分哈希函数将整个线性表分为许多小的线性表。这里我们采用最简单的划分哈希函数，即使用关键字的前k位的值作为哈希值，将数据分到2k个子线性表中。这些子线性表的顺序由划分哈希函数确定。即，子线性表A在子线性表B之前，当且仅当子线性表A中的所有数据的关键字的值都大于子线性表B中所有数据的关键字的值。在将一个数据放到一个子线性表中时，按照插入排序的插入操作的方式进行。由于同一个字线性表中所有数据的开头k个字符的值都相同，所以当一个数据的关键字长度小于或者等于k时，直接将其放在队列的开头。最后根据这些子线性表的顺序将它们连成有序的线性表。
顺序存储结构不适合哈希插入排序。因为将数据分到许多子线性表中，并最终合并成一个有序线性表，这一过程中有大量移动操作，所以链式结构更适合实现哈希插入排序。
下面是哈希插入排序的过程：
1) 设A是要被排序的线性表。
2) 构建一个线性表的数组Φ，他的大小L（L=2k），k是哈希函数使用的关键字位数。
3) 计算每个数据的关键字的哈希值。根据哈希值，将每个数据使用插入排序的插入方式插入数组Φ中对应的线性表。如果这个数据的关键字的长度小于或者等于k，那么直接放到对应线性表的开头。
4) 按照数组Φ中的线性表的顺序，将数组Φ中的线性表合并成为有序线性表。
下面我们证明哈希插入排序算法的正确性。任取两个数据：数据A和数据B。如果它们有相同的哈希值，将被放到在同一个线性表中，因为在将一个数据放到一个线性表中时，按照插入排序的方式执行了插入操作，所以他们之间必然是有序的。如果它们的哈希值不同，那么它们将被放到不同的线性表中，由于线性表之间是有序的，所以这两个数据之间也是有序的。所以这个算法运行结束后，整个线性表将是有序的。
3 性能分析
现在分析哈希插入排序的效率。同时需要最合适和k值，使得排序的时间最短。从算法描述可以看出，哈希插入排序算法所花费的时间包括三部分：哈希函数计算时间，插入子线性表的时间和连接子线性表的时间。哈希计算对于每个数据而言，都进行一次操作。然后将这个数据按照插入排序的方式，执行插入操作。一般情况下，每个子线性表的长度遵守二项式分布，。其中n是数据的数量，L是子线性表的数量。对于每个子线性表，比较操作的数量是，其中t是这个子线性表的长度。所以所有插入操作所执行的比较操作的数量之和为。这里用S表示。下面是当数据量（n）为10000，1000000和100000000 时的比较操作的数量图。图中横坐标L为子线性表的数量，纵坐标为比较次数。
下面我们需要一个合适的L值，来平衡内存和时间的要求。我们发现，L =n,即2k = n时，进行插入操作所需要的总的比较次数是n。这是一个可以接受的值。选择一个L，使得dN/dL=-1时，这个L是一个更好的结果。经过计算，这个L大概是0.7n。所需要的移动操作和比较操作的数据基本相等。所以我没可以选择k=log2n或者k=log20.7n。
将子线性表连接在一起的时间是固定的，为2k次移动操作。当k=log2n时，需要n次移动操作、所以对于哈希插入排序，取k=log2n时，共需要n次比较操作（包括计算哈希值），n 次移动操作。这是一个线性时间。
4 冗余编码关键字的扩展
我们在前面考虑的都是非冗余码。然而很多关键字采用的是冗余编码，如字符串关键字。需要对定义的划分哈希函数进行修改。下面是一种针对冗余编码的划分哈希函数。
我们假设关键字是一串取自字符表α的符号串。符号表α中有k种不同符号。每个符号有相同的划分能力。每个符号有m位编码。这样我们就需要使用「logk1?骎×m位关键字将数据分到k「logk1?骎个小数据集中。l是我们需要的小数据集的数量。每m位关键字可以把数据分到k个不同的小数据集中。可以使用映射方式来完成这一划分函数。
5 结束语
对于大数据集，哈希插入排序是一种很好的排序方法，特别是数据的关键字长度较大时。它只需要线性时间来完成排序。对于划分-归并排序而言，哈希插入排序只需要一步来完成划分过程。其他这类排序往往需要对一个数据进行多次操作来完成划分步骤，如基数排序，快速排序和归并排序。
哈希插入排序依然有一些问题。特别是我们假设字母表中的每个符号都有相同的划分能力。但这种假设在有些情况下不成立。如英文字母，不同字母出现的频率会有不同，划分能力就不相同。字母的出现频率越高，划分能力越差。在今后的研究中将在这方面寻找改进方式。
参考文献：
[1] William F. Gilreath. Hash sort: A linear time complexity multiple-dimensional sort algorithm[J]. Proceedings of First Southern Symposium on Computing,2004.
[2] Steffen HEIN, Justin ZOBEL, Hugh E. WILLIAMS. Burst Tries: A Fast, Effcient Data Structure for String Keys[J]. ACM Transactions on Information Systems,2002,20(2):92-223.
[3] Ranjan SINHA, Justin ZOBELl. Efficient Trie-based Sorting of large set of String[J]. Australian Computer Society,Inc,2003.
[4] Shin-Jae LEE, Minsoo Jeon, Andrew SOHN, and Dongseung KIM[C].Partitioned Parallel Radix Sort, ISHPC. 2000, LNCS 1940:160-171.
[5] BENTLEY J, SEDGEWICK R. Fast algorithms for sorting and searching strings, In Proc. Annual ACM-SIAM Symp[C].on Discrete Algorithms.New Orleans,Louisiana,1997:360-369.
[6] BENTLEY J, SEDGEICK R. Sorting Strings with Three-Way Radix Quicksort[J]. Dr. Dobbs Journal,1998.
关键词：排序；哈希；字符串数据结构；文本数据库
中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)01-0105-02
排序理论中存在一个基本原则：将一个大的数据集划分成许多小数据集将大大提高排序的效率。采用这一原则的算法被称为划分—归并排序算法，快速排序和归并排序是其中两种。然而，这两种算法需要许多步递归过程将一个大数据集划分成许多只包含一个数据的小数据集。在划分完成之后，归并排序还需要进行递归的归并，这都降低了排序的效率。
直接基数排序算法是另外一种划分-归并排序算法。直接基数排序算法使用2g个桶来划分有序队列。首先使用最高g位（ib-1ib-2 … ib-g）关键字，根据这g位关键字将数据放到各个桶中，这g位关键字具有相同值的数据被放到一个桶中。同样的，第二趟中，每个桶中的数据根据接下来的g位(ib-(g + 1)ib-(g+2)…ib-2g)关键字进行划分，每个桶中的数据被分到m个新的子桶中，后面的几趟也是这样进行。这样，数据一直没有离开它被分配到的桶。一个显著的问题是桶（子桶）的数量将会迅速爆炸，很多桶中只有很少的数据[4] 。直接基数排序算法的时间复杂度是O（g（n+mg））。
三路基数快速排序是另外一种基于这一原则的排序算法。同快速排序算法一样，它将数据分为三部分：大于，小于和等于给定值。同基数排序相似，当前输入等于初始的字符，移到下一位字符。 [6]
这些算法都需要许多步来完成把一个大数据集分成许多小数据集的工作。那么是否可以找到一种算法，使得这一过程可以一步完成？哈希函数可以做到这一点。
在计算机领域中，排序和哈希是两种完全不同的概念。原因在于，一个数据在有序表中的位置不仅仅由它的关键字的值决定，也受这个数据集的上下文环境影响。哈希函数只考虑使用关键字的值来组织哈希表，所以寻找一个哈希值，使数据在有序表中位置的哈希函数是几乎不可能的。即使存在，它也很复杂，效率很低。然而，我们发现哈希是一种很好的划分方法。冲突是哈希中的一种重要概念，降低冲突是设计哈希函数所需要重点考虑的因素。但从另一方面，两个数据的哈希值冲突，说明这两个数据被分到一个组中，这样划分就只需要一步来完成。
在本文中，我们将给出一种新的排序算法，它使用哈希的方式，将大数据集分为许多小数据集。使用插入排序对每个小数据集进行排序。在第1节中给出一些作为该算法基础的定义，在第2节中给出算法描述，在第3节中给出算法的性能分析，在第4节中给出针对冗余编码的关键字的改进。
1 定义
定义1(完美哈希函数)：一个哈希函数是完美哈希函数，当且仅当这个哈希函数能够给每一个数据一个唯一的哈希值。[1]
定义2(超级哈希函数)：一个哈希函数是一个超级哈希函数，当且仅当它的结果是一个全序关系，并且是一个完美哈希函数。[1]
William F. Gilreath提出文献[1]一种超级哈希函数，但这类哈希函数比较复杂，而且不容易找到。这是由于数据在有序线性表中的位置不仅仅由它的关键字的值决定，还取决于其他数据的关键字的值，即它所处的上下文环境。但这里可以找到一种弱化要求的哈希函数，这就是下面定义的划分哈希函数。
定义3 (划分哈希函数)
划分哈希函数的结果是一个偏序关系，即，将具有相同哈希值的数据视为一个集合，那么一个集合中的数据将都大于或者等于（小于或者等于）另一个集合中的数据。
最简单的划分哈希函数就是使用前k位关键字的值作为哈希值，将所有数据分到2k个子线性表中。进行这次划分操作只需要对每个数据进行一次操作，这大大优于快速排序算法。
2 数据结构和算法
下面考虑哈希插入排序算法，首先考虑非冗余关键字。该算法首先是使用使划分哈希函数将整个线性表分为许多小的线性表。这里我们采用最简单的划分哈希函数，即使用关键字的前k位的值作为哈希值，将数据分到2k个子线性表中。这些子线性表的顺序由划分哈希函数确定。即，子线性表A在子线性表B之前，当且仅当子线性表A中的所有数据的关键字的值都大于子线性表B中所有数据的关键字的值。在将一个数据放到一个子线性表中时，按照插入排序的插入操作的方式进行。由于同一个字线性表中所有数据的开头k个字符的值都相同，所以当一个数据的关键字长度小于或者等于k时，直接将其放在队列的开头。最后根据这些子线性表的顺序将它们连成有序的线性表。
顺序存储结构不适合哈希插入排序。因为将数据分到许多子线性表中，并最终合并成一个有序线性表，这一过程中有大量移动操作，所以链式结构更适合实现哈希插入排序。
下面是哈希插入排序的过程：
1) 设A是要被排序的线性表。
2) 构建一个线性表的数组Φ，他的大小L（L=2k），k是哈希函数使用的关键字位数。
3) 计算每个数据的关键字的哈希值。根据哈希值，将每个数据使用插入排序的插入方式插入数组Φ中对应的线性表。如果这个数据的关键字的长度小于或者等于k，那么直接放到对应线性表的开头。
4) 按照数组Φ中的线性表的顺序，将数组Φ中的线性表合并成为有序线性表。
下面我们证明哈希插入排序算法的正确性。任取两个数据：数据A和数据B。如果它们有相同的哈希值，将被放到在同一个线性表中，因为在将一个数据放到一个线性表中时，按照插入排序的方式执行了插入操作，所以他们之间必然是有序的。如果它们的哈希值不同，那么它们将被放到不同的线性表中，由于线性表之间是有序的，所以这两个数据之间也是有序的。所以这个算法运行结束后，整个线性表将是有序的。
3 性能分析
现在分析哈希插入排序的效率。同时需要最合适和k值，使得排序的时间最短。从算法描述可以看出，哈希插入排序算法所花费的时间包括三部分：哈希函数计算时间，插入子线性表的时间和连接子线性表的时间。哈希计算对于每个数据而言，都进行一次操作。然后将这个数据按照插入排序的方式，执行插入操作。一般情况下，每个子线性表的长度遵守二项式分布，。其中n是数据的数量，L是子线性表的数量。对于每个子线性表，比较操作的数量是，其中t是这个子线性表的长度。所以所有插入操作所执行的比较操作的数量之和为。这里用S表示。下面是当数据量（n）为10000，1000000和100000000 时的比较操作的数量图。图中横坐标L为子线性表的数量，纵坐标为比较次数。
下面我们需要一个合适的L值，来平衡内存和时间的要求。我们发现，L =n,即2k = n时，进行插入操作所需要的总的比较次数是n。这是一个可以接受的值。选择一个L，使得dN/dL=-1时，这个L是一个更好的结果。经过计算，这个L大概是0.7n。所需要的移动操作和比较操作的数据基本相等。所以我没可以选择k=log2n或者k=log20.7n。
将子线性表连接在一起的时间是固定的，为2k次移动操作。当k=log2n时，需要n次移动操作、所以对于哈希插入排序，取k=log2n时，共需要n次比较操作（包括计算哈希值），n 次移动操作。这是一个线性时间。
4 冗余编码关键字的扩展
我们在前面考虑的都是非冗余码。然而很多关键字采用的是冗余编码，如字符串关键字。需要对定义的划分哈希函数进行修改。下面是一种针对冗余编码的划分哈希函数。
我们假设关键字是一串取自字符表α的符号串。符号表α中有k种不同符号。每个符号有相同的划分能力。每个符号有m位编码。这样我们就需要使用「logk1?骎×m位关键字将数据分到k「logk1?骎个小数据集中。l是我们需要的小数据集的数量。每m位关键字可以把数据分到k个不同的小数据集中。可以使用映射方式来完成这一划分函数。
5 结束语
对于大数据集，哈希插入排序是一种很好的排序方法，特别是数据的关键字长度较大时。它只需要线性时间来完成排序。对于划分-归并排序而言，哈希插入排序只需要一步来完成划分过程。其他这类排序往往需要对一个数据进行多次操作来完成划分步骤，如基数排序，快速排序和归并排序。
哈希插入排序依然有一些问题。特别是我们假设字母表中的每个符号都有相同的划分能力。但这种假设在有些情况下不成立。如英文字母，不同字母出现的频率会有不同，划分能力就不相同。字母的出现频率越高，划分能力越差。在今后的研究中将在这方面寻找改进方式。
参考文献：
[1] William F. Gilreath. Hash sort: A linear time complexity multiple-dimensional sort algorithm[J]. Proceedings of First Southern Symposium on Computing,2004.
[2] Steffen HEIN, Justin ZOBEL, Hugh E. WILLIAMS. Burst Tries: A Fast, Effcient Data Structure for String Keys[J]. ACM Transactions on Information Systems,2002,20(2):92-223.
[3] Ranjan SINHA, Justin ZOBELl. Efficient Trie-based Sorting of large set of String[J]. Australian Computer Society,Inc,2003.
[4] Shin-Jae LEE, Minsoo Jeon, Andrew SOHN, and Dongseung KIM[C].Partitioned Parallel Radix Sort, ISHPC. 2000, LNCS 1940:160-171.
[5] BENTLEY J, SEDGEWICK R. Fast algorithms for sorting and searching strings, In Proc. Annual ACM-SIAM Symp[C].on Discrete Algorithms.New Orleans,Louisiana,1997:360-369.
[6] BENTLEY J, SEDGEICK R. Sorting Strings with Three-Way Radix Quicksort[J]. Dr. Dobbs Journal,1998.