应用于大数据的Trie树排序算法  

Trie tree sorting algorithm applied to big data

作　　者：赵林洁 肖英 张宇[3] ZHAO Lin-jie;XIAO Ying;ZHANG Yu(College of Information Engineering,China Jiliang University,Hangzhou 310018,China;Key Laboratory of Electromagnetic Wave Information Technology and Metrology of Zhejiang Province,China Jiliang University,Hangzhou 310018,China;Research and Development Center,Hangzhou Coding Intelligent Technology Limited Company,Hangzhou 310018,China)

机构地区：[1]中国计量大学信息工程学院,浙江杭州310018 [2]中国计量大学浙江省电磁波信息技术与计量检测重点实验室,浙江杭州310018 [3]杭州代码哥智能科技有限公司研发中心,浙江杭州310018

出　　处：《计算机工程与设计》2022年第2期427-433,共7页Computer Engineering and Design

基　　金：浙江省自然科学基金项目(Y20F010069)。

摘　　要：针对在数据量动态增加的场景下现有的排序算法管理数据导致算法性能大大降低的问题,提出一种16-bit Trie树排序算法。借助邻居节点上存储的链节点指针完成排序,它不仅可以边构建边排序,且引入动态数组可以提高该算法的空间效率。仿真结果表明,传统Trie树支持数据动态更新,但通过遍历Trie树的方式完成排序耗时较多,快速排序算法在数据动态增加时效率低,16-bit Trie树排序算法支持数据动态更新,排序时间明显少于传统Trie树,优于快速排序,这表明16-bit Trie树排序算法在处理海量动态数据时具有突出优势。Aiming at the problem that the data management of the proposed algorithm results in reducing performance greatly with the increase of data volume dynamically,16-bit Trie tree sorting algorithm,which finished sorting with the help of the chain node pointer stored on a neighbor node,was presented.The algorithm not only built structure while sorting,but also improved the space efficiency by introducing a dynamic array.Simulation results show that traditional Trie tree supports dynamic data update,but it takes more time to complete sorting by traversing the Trie tree.The Quicksort algorithm becomes inefficient when the data dynamically increases.The 16-bit Trie tree sorting algorithm supports dynamic data update,and its sorting time is shorter than the traditional Trie tree and the Quicksort,which shows that the 16-bit Trie tree sorting algorithm has a prominent advantage in processing massive data.

关 键 词：字典树 排序算法 压缩 字符串排序 字典树结构 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]