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

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

作　　者：徐聪[1,2] 张丰[1,2] 杜震洪[1,2] 张逸然[1,2] 陈明[1,2] 刘仁义[2] 

机构地区：[1]浙江大学浙江省资源与环境信息系统重点实验室,浙江杭州310028 [2]浙江大学地理信息科学研究所,浙江杭州310027

出　　处：《浙江大学学报（理学版）》2014年第2期217-222,共6页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(41001227);国家863计划项目(2007AA12Z182;2009AA12Z222);浙江省科技攻关计划项目(2009C33011);教育部博士点专项基金资助项目(200803350017);浙江省自然科学基金资助项目(Y5090130)

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

关 键 词：哈希函数 双数组trie树 地址分类 地址规则 地址匹配 

分 类 号：P208[天文地球—地图制图学与地理信息工程]