利用频率特征的Trie树索引快速构造算法

A Fast Trie Tree Index Construction Algorithm Using Frequency Characteristic

随着物联网技术的日益成熟和云计算标准的确立以及各种智能终端的大规模出现,互联网数据呈指数增加,为数据建立索引至关重要,为此提出一种基于词频的Trie树索引快速构造算法,首先对索引字符串进行排序,然后对排序文件进行预处理,预处理生成一个三元组,分别由相同字符横向偏移、纵向偏移及字符组成.快速算法依次扫描预处理数据的每一列,根据三元组的偏移跳过相同的字符前缀.实验结果显示,本算法的时间明显少于传统构造算法,优于Aoe的双数组Trie构造算法.

With maturity of ＂the Internet of things＂ and establishment of cloud computing national stand- ards, kinds of terminals appear quickly, and huge amounts of data＇s generation exponentially increase, so it＇s crucial to construct index for the data. A fast Trie-tree index construction algorithm is proposed. All the strings are sorted and then the sorted strings are preprocessed, and after that a matrix with the element of triple is generated, consisting of the character, the horizontal and vertical offset of the character. The fast algorithm scans each column in turn and skips the repeated rows and columns with the same prefix according to offset value in triple array. The experimental results show that the fast algorithm significantly reduces the construction time compared with traditional algorithm and the performance is better than Aoe＇s double-array Trie construction algorithm.