基于哈希和双数组trie树的多层次地址匹配算法

针对目前地址匹配算法匹配速率低、空间开销大的不足,提出了一种基于哈希和双数组trie树的多层次地址匹配算法.利用中文地址的分类、分层及组合规则,改进了地址匹配词典的构建方式,减少了词典构建的时间和空间开销.通过哈希运算,将空间坐标存储在哈希表相应的位置上,加快了空间坐标的检索效率.同时,在地址匹配的过程中,采用双向扫描及哈希运算代替传统的数据库检索方式,提高了地址匹配速率.最后,通过实验对算法的有效性进行了验证.

A multi-level address-matching algorithm based on Hash function and double-array trie-tree

Based on Hash function and double-array trie-tree, a multi-layer address-matching algorithm is proposed in this paper against several shortcomings of conventional solutions, i.e. low efficiency and huge memory occupation. According to principles of classification, layering and combination for Chinese addresses, the construction method of the address-matching dictionary is optimized and hence its occupation on time and memory is reduced. With hash op- erations, space coordinates are stored in their corresponding hash table positions, in which the retrieval efficiency is improved. Meanwhile, a strategy combining the dual-scan matching and hash operations is used instead of the tradi- tional database retrieval method to augment the address-matching velocity. Experiments are conducted and success- fully verify the algorithm＇s effectiveness.