(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(10)申请公布号 CN 103914544 A
(43)申请公布日 2014.07.09
(21)申请号 CN201410134887.3
(22)申请日 2014.04.03
(71)申请人 浙江大学
    地址 310027 浙江省杭州市浙大路38号
(72)发明人 杜震洪 张丰 刘仁义 徐聪 张逸然 郑晔
(74)专利代理机构 杭州求是专利事务所有限公司
    代理人 张法高
(51)Int.CI
      G06F17/30
                                                                  权利要求说明书 说明书 幅图
(54)发明名称
      一种基于地址特征词的多层次快速中文地址匹配方法
(57)摘要
      本发明公开了一种基于地址特征词的多层次快速中文地址匹配方法，属于地理信息科学的数据空间化研究领域。本发明所述方法具体包括标准中文地址匹配词典构建和地址匹配两个环节，以地址特征词为分词依据对标准中文地址进行中文分词，并采用双数组trie树和哈希运算完成标准中文地址匹配词典的构建，采用双向扫描及哈希运算代替数据库检索的方式，获取待匹配中文地址的地理空间坐标，完成地址匹配。本发明的优点在于能够在计算机内存中完成整个地址匹配过程，并采用双向扫描和边分词边匹配的方式，提高了地址匹配的匹配速率。同时，根据中文地址的分类、分层及组合规则，解决了部分中文地址由于地址要素缺失无法完成地址匹配的问题，提高了地址匹配的准确度。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.一种基于地址特征词的多层次快速中文地址匹配方法,其特征在于包括如下步骤:
       
1)从标准中文地址数据库中读入所有标准中文地址的记录,包括每一个标准中文地址的地理空间坐标x值、y值;
       
2)根据中文地址的分类规则,以地址特征词为分词依据对标准中文地址进行正向扫描中文分词,将中文分词所获得的5类地址要素插入到对应的5类双数组trie树中;
       
3)从5类双数组trie树中获取标准中文地址所对应的地址编码元素集合,按照最小代价原则,以中文地址的分层和组合规则为依据对地址编码元素进行组合和排列,获取唯一表示该标准中文地址的4个地址编码,对这4个地址编码进行哈希运算,将该标准中文地址的地理空间坐标存储在哈希表中其哈希函数值对应的位置上,对所有标准中文地址依次进行步骤2)~步骤3)的操作,完成标准中文地址匹配词典构建;
       
4)读取待匹配中文地址字符串,分别赋值S1和S2,同时进行正向扫描匹配和逆向扫描匹配;
       
5)判断正向扫描匹配和逆向扫描匹配是否成功,若正向扫描匹配或逆向扫描匹配失败,返回步骤4);若正向扫描匹配和逆向扫描匹配成功,获取对应匹配结果的地址编码组合T1和T2;
       
6)设地址编码T = T1 + T2,对T进行哈希运算,通过哈希函数值在哈希表中查对应的地理空间坐标,若存在,获
取对应地理空间坐标,地址匹配成功,若不存在,地址匹配失败,重复步骤4)~步骤6),完成所有待匹配中文地址的地址匹配。
       
2.根据权利要求1所述的一种基于地址特征词的多层次快速中文地址匹配方法,其特征在于所述的步骤2)为:
       
(1)中文地址的分类规则是指一个指意明确的标准中文地址由行政区划名、街巷名、小区名、门楼址名和兴趣点名这5类地址要素组成,其中地址要素是指地址字符串中一个相对独立的部分,具有明确的地址意义;
       
(2)正向扫描中文分词方法是一种从字符串序列起首位置开始,从左往右依次对字符串进行切分的方法;
       
(3)双数组trie树由base数组和check数组组成,其中base数组每一个元素表示trie树的一个节点状态,数组值为
状态转移的基值,check数组表示一个状态的前驱状态,数组值为校验值,当base数组和check数组的值均为0时,该状态空闲,5类双数组trie树分别存储每一个标准地址所包含的5类地址要素,5类双数组trie树具体为行政区划双数组trie树、街巷名双数组trie树、住宅小区双数组trie树、门楼址双数组trie树和POI双数组trie树;
       
(4)双数组trie树的一次插入操作为在构建双数组trie树时进行一次状态的转移,当状态m转移到状态n时,必须满足以下2个条件:
       
base[m] + c = n,
       
check[n] = m,
       
其中,m是当前状态的下标,n是转移状态的下标,c是输入字符的数值。
       
3.根据权利要求1所述的一种基于地址特征词的多层次快速中文地址匹配方法,其特征在于所述的步骤3)包括:
       
(1)从5类双数组trie树中获取一个标准中文地址所对应的5类地址编码元素,并按照最小代价原则,以中文地址的分层和组合规则对地址编码元素进行组合和排列,获取唯一表示标准中文地址的4个地址编码,其中地址编码元素是指每一个地址要素中最后一个字符在双数组trie树中的数组下标值,地址编码是由地址编码元素组合和排列而成;
       
(2)中文地址的分层规则是指按照中文地址5个地址要素的从属关系,可以将其分为三个层次,第一层次为行政区划名,包括省级、市级、县级、乡级、村级;第二层次为街巷名和小区名;第三层次为门楼址名和POI名;
       
(3)中文地址的组合规则是指按照中文地址的分层规则,一个标准的中文地址可以有16种指意明确的待匹配中
文地址与其相匹配,其中按照最小代价原则,包含3类地址要素的4种地址表达形式为:
       
行政区划名/街巷名/门楼址
       
××省××市××区××街道××路××号;
       
行政区划名/街巷名/兴趣点名
       
××省××市××区××街道××路××小学;
       
行政区划名/小区名/门楼址
       
××省××市××区××街道××小区××号;
       
行政区划名/小区名/兴趣点名
       
××省××市××区××街道××小区××广场。
       
4.根据权利要求1所述的一种基于地址特征词的多层次快速中文地址匹配方法,其特征在于所述的步骤4)包括:
       
正则匹配哈希值
(1)正向扫描匹配首先以行政区划特征词为切分依据对S1进行正向扫描中文分词,若分词失败,正向扫描匹配失败,若分词成功,获取对应的行政区划地址编码元素,在行政区划双数组trie树中查询该地址编码元素的匹配分
支,若查询成功,获取该匹配分支最后一个状态所对应的数组下标值T1,若查询失败,正向扫描匹配失败;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。