| 应用于大数据的Trie树排序算法 |
| |
| 引用本文： | 赵林洁,肖英,张宇.应用于大数据的Trie树排序算法[J].计算机工程与设计,2022,43(2):427-433. |
| |
| 作者姓名： | 赵林洁 肖英 张宇 |
| |
| 作者单位： | 中国计量大学 信息工程学院,浙江 杭州 310018;中国计量大学 浙江省电磁波信息技术与计量检测重点实验室,浙江 杭州 310018;杭州代码哥智能科技有限公司 研发中心,浙江 杭州 310018 |
| |
| 基金项目： | 浙江省自然科学基金项目(Y20F010069)。 |
| |
| 摘 要： | 针对在数据量动态增加的场景下现有的排序算法管理数据导致算法性能大大降低的问题,提出一种16-bit Trie树排序算法.借助邻居节点上存储的链节点指针完成排序,它不仅可以边构建边排序,且引入动态数组可以提高该算法的空间效率.仿真结果表明,传统Trie树支持数据动态更新,但通过遍历Trie树的方式完成排序耗时较多,快速排...
|
| 关 键 词： | 字典树 排序算法 压缩 字符串排序 字典树结构 |
Trie tree sorting algorithm applied to big data |
| |
| ZHAO Lin-jie,XIAO Ying,ZHANG Yu.Trie tree sorting algorithm applied to big data[J].Computer Engineering and Design,2022,43(2):427-433. |
| |
| Authors: | ZHAO Lin-jie XIAO Ying ZHANG Yu |
| |
| Affiliation: | (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) |
| |
| Abstract: | 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. |
| |
| Keywords: | dictionary sorting algorithm compaction string sort Trie tree structure |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
