基于字典树的基数排序算法

来源:用户上传      作者:

　　摘要： 排序和查找是数据处理中最常用的运算之一，比较排序算法中时间复杂度最小的是快速排序，接近O（nlog2n）。基数排序是非比较排序算法中的一种，设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O（d（n+radix））。字典树是常用于字符串排序的算法，时间复杂度为O（n），排序速度快而且便于查找。结合两种算法的优点，提出一种更高效且合理的算法。
　　关键词： 基数排序；字典树；查找；时间复杂度
　　中图分类号：TP311.11文献标识码：A文章编号：1671－7597（2011）0720192－02
　　
　　0 引言
　　首先来看一个问题：图书馆为每本书都设置了唯一整数编号，经过一段时间后，需要了解哪些书被借出，并且当有人需要借某本书的时候，迅速查出这本书是否还在馆内。
　　该问题可以抽象为：有一个整数集合，乱序，且中间缺少一些数，使其不完整，现要查找其中差哪些数，并且查询某数当前是否在集合中。该问题需要对整数集合进行排序查找。对于整数排序，基数排序是相对来说效率较高的。
　　基数排序主要是通过关键字间的比较和移动记录这两种操作，而实现基数排序不需要进行记录关键字间的比较，它是一种利用多关键字排序的思想，即借助“分配”和“收集”两种操作对单逻辑关键字进行排序的方法[1]。
　　基数排序的实现方法有两种[2]，分别是：最高位优先（MostSignifi
　　CantDigitfirst）法，简称MSD法和最低位优先（LeastSignificantDigit
　　first）法，简称LSD法。MSD先按k[1]排序分组，同一组中记录，关键码k[1]相等，再对各组按k[2]排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码k[d]对各子组排序后。再将各组连接起来，便得到一个有序序列。LSD先从k[d]开始排序，再对k[d-1]进行排序，依次重复，直到对k[1]排序后便得到一个有序序列。
　　例如某个记录含有三个关键字，例如某个学生的年级、班级、班内序号，其中年级是最主位关键字，班级次之，班内序号最次位。
　　
　　基数排序的时间复杂度为O（d（n+radix），其中：分配为O（n），收集为O（radix）（radix为“基”），d为“分配-收集”的趟数，基数排序是稳定的排序方法。稳定排序的意思是指，待排序相同元素之间的相对前后关系，在各次排序中不会改变，比如表1中具有第二位数字1的两个数据（2001，2，15）和（2003，2，30），在第二位排序之前（2001，2，15）在（2003，2，30）之前，第二位排序之后，（2001，2，15）依然在（2003，2，30）之前。稳定排序能保证上一次的排序被保留，下一次排序过程能基于上一次排序成果。它是线性复杂度，即对n个数字处理了n次，但是每一次代价都比较高，而且对于排好的序列查找复杂度也较高，为O（n），查找时间依赖于数据个数，当n很大时查找时间将非常长。在图书馆管理中，虽然基数排序也能很好的完成排序功能，但是其查找某本书和搜索缺失书的复杂度相对来说很高，无法在短时间完成要求。
　　字典树（Trie）又称单词树，是一种树形结构，其核心思想就是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计[3]。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率相当高。
　　Trie树的构造过程会按照已有的字典规则插入，因为当查询如字符串“abc”是否为某个字符串的前缀时，显然以b，c，d……等不以a开头的字符串就不用查找了，所以建立Trie的复杂度为O（n*m），其中n为数据个数，m为字符串长度。而建立和查询过程在Trie中是可以同时执行的，建立的过程也就可以成为查询的过程，所以实际查询的复杂度只是O（m）[4]。对于上面提出的问题，字典树在查找是否存在某书和搜索缺失书的时候将会比基数排序的速度高出很多。
　　1 基数排序与字典树的结合
　　1.1 数据预处理
　　整数和字符串不一样，字符串是首位对齐比较，而整数是末位对齐比较，例如字符串“abcd”和“abefg”，首先比较第一位，都为“a”，再比较第二位，都为“b”，第三位“e”大于“c”，故“abefg”大于“abcd”，同理，“bcd”大于“abcd”。而在整数中，234小于1234，因为1234是四位数，比234三位数要高一位。因此如果想进行整数的排序需要首先对待排序的整数转换成字符串进行高位补0对齐，之后将其作为等长的字符串插入字典树中。
　　1）对于输入数据构成的数组Ai，i∈（1，n），n为数据个数。
　　2）最大数据长度t=[log10（maxAi）]+1。
　　3）定义字符串数组Bi，i∈（1，n），用来存储转换后的字符串。
　　4）对于每一个Ai，Bi[t-1-k]=（Ai/10k）%10，k∈（0，t-1）。
　　经过处理后得到的字符串长度均等于最大数的长度。
　　
　　每个节点都有一个长度为10的指针数组，每一个指针分别指向下一位0-9这十个数字中的一个。当next[i]==NULL，i∈（0，9）时，表示下一个路径不存在，停止此条路径的搜索。当next[i]!=NULL，i∈（0，9）时，说明下一路径存在，可以继续往下查找。
　　isnum是bool型的校验位，当该节点为true时则此节点包含了一个数据，否则此节点只是一个中间路径。
　　当我们找到一个节点isnum值为true时，该节点所代表的数值既是从Root到此节点（包括该节点）的路径连接成的字符串。
　　1.3 计算原理
　　因为数据经过处理转换为等长的字符串，所以字典树的枝干不存在数据，只有叶子才会保存数据。
　　十进制整数的一位数字是0-9，而且有序，故字典树插入的时候，我们就已经按照有序的方式插入每一位，最终得到的字典本身就是有序的，既插入的过程就是排序的过程，插入结束后的字典树也是有序的。
　　
　　该代码首先传入数值和最大长度，然后定义一个临时字符串，将数值按照最大长度转换为字符串，再将字符串按位一步一步插入Root节点中，在该字符全部插入完成后最后一个节点处将isnum设为true，标明该处为数值。
　　假设有5个数字，分别为：500、10、13、78、591、91。构造字典树的方法为：找到所有数字最高位数3，然后将数字转换为三位字符串500、010、013、078、591、091。根节点为空，从字符串左边第一位开始，将首字母作为子节点插入到树中，即下一个字符为上一个字符的子节点。当单词插入完毕时将最后的叶子节点标注为true。该字典树排序只需要根据层和数字的顺序遍历整个树标注过的节点即可得到排好序的列表。
　　字典树对某书是否在馆内的查找本身就提供了良好的效率，但是如何查找哪些书不在馆内呢？这需要对每个节点做额外设计。对于每一个节点，我们增加一个字段：childNumber，用来记录该节点所包含的数据个数。这样对于每个节点node，有：
　　
　　
　　同时对于包含了数值的叶子节点，其childNumber总是为1。这样，一个满字典树的任意一个节点的childNumber值都应该为10的幂，所以我们搜索缺失的书的时候，只需要查找字典树中哪一个节点不为10的幂，并且一层一层往下找，就可以找到所有缺失的数值。
　　2 算法评估
　　2.1 分析评估
　　当数据最大位数为m，数据个数为n的时候，该方法的时间复杂度为O（mn），其中n个数据分别插入一次，一个数据的插入过程有m位操作。查找过程复杂度为O（m）。
　　用IntelCoreDueT6600处理器，4G内存，Windows7x64操作系统，VC2010编译器，经过实际运算时间见表2。
　　
　　可以看出，相比于直接基数排序，本文基于字典树的方法耗时更短，而且在查找过程耗时几乎可以忽略不计，而基数排序的查找时间是线性增长的。
　　2.2 算法优化
　　由于字典树使用空间换时间，所以对空间的浪费较大。可以采取合理的优化方式将空间使用减小。双数组字典树就是一个比较好的方案[5]。双数组字典树定义两个数组，一个是base[]，另一个是check[]。设数组下标为i，如果base[i]，check[i]均为0，表示该位置为空。如果base[i]为负值，表示该状态为终止态（即词语）。check[i]表示该状态的前一状态。
　　对于输入字符c，从状态s转移到状态t，双数组字典树满足如下条件：
　　check[base[s]+c]=s
　　base[s]+c=t
　　Trie里有n个节点，字符集大小为m，一般字典树的空间大小是nm，里面有很大内存浪费，而双数组字典树的空间大小是n+cm，c是依赖于Trie稀疏程度的一个系数。由此可以看出双数组字典树能够很大程度上改善字典树对空间的浪费。对于本方法，双数组字典树也并没有增加时间复杂度，所以是可行的。
　　3 结论
　　对于引言提出的图书馆管理问题，基于字典树的方法相比于基数排序算法，虽然需要更多空间，但效率更高，在对大量数值排序且要求高性能
　　
　　
　　查找时字典树能够满足我们的需要，而且经过优化也能减少空间浪费。若其最大位数为m，则其查找时间复杂度只有O（m），是一种高效而且实用的方法。
　　
　　参考文献：
　　[1]黄竞伟，最高位优先基数排序的一种实现方法，系统工程理论与实践，1999（7）.
　　[2]高全清，基数排序的非链式分配算法，山东工程学院学报，1996（4）：43-45页.
　　[3]穆炯、蒲海波，对按位分段排序算法的研究，四川农业大学学报，2004（1）：79-82页.
　　[4]赵欢、朱红权，基于双数组Trie树中文分词研究，湖南大学学报（自然科学版），2009（5）：77-80页.
　　[5]王思力、张华平、王斌，双数组Trie树算法优化及其应用研究，中文信息学报，2006（5）：24-30页.

转载注明来源:https://www.xzbu.com/8/view-8873717.htm