简化分词的地址匹配技术

摘　要：本文旨在探讨以一种较为简单的方式实现“地址匹配”技术。全文阐述了分级地址库的设计以及地址匹配算法两个方面的内容。笔者首先详细说明了现今地址库设计的主流方式并提出了自己的设计以及说明该设计的优势，紧接着基于该地址库提出了简化分词和基于加权的地址匹配算法思路

关键词：地址匹配；分级；简化分词；加权

0.引言

　　随着互联网的普及，人们的生活和互联网之间的联系越来越紧密，各种互联网技术也随之迅速发展。在众多互联网技术中，GIS技术在近年来由于国家政策的大力支持以及广大网民的普遍需求而得以迅速发展，其中的地址匹配技术也得到了越来越多的使用。

　　所谓的“地址匹配”技术，即使用者通过输入地名地址的关键字来获得对应地址的信息。该功能主要由两个部分组成：地名地址库和作用于地址库上的匹配算法。只有拥有良好的数据结构设计和算法设计，才能够实现一个速度流畅，用户体验优秀的地址匹配功能。

1.设计简介

　　本文提出了一套“地址匹配”技术的实现流程。它通过建立地名的分级地址库，使用基于该分级地址库的中文分词技术，并采用加权算法等多种数据筛选方式，实现了地址匹配功能。

　　相对于其它的地名地址技术，这种方法拥有以下特点：使用地址库进行分词，减少了维护分词字典这个步骤，简化了程序的实现流程以及维护开销；使用加权算法等多种方式来对地址进行匹配，不仅在匹配结果中体现出不同级别数据重要性的差异，而且能够动态挑选命中概率最高的结果，进一步提高了匹配结果的精确度，使用户获得更好的操作体验。

2.详细说明

2.1地址库：

　　地址匹配需要一个详细的分级地址库。现在国家对行政区划的分级一般为省、市、区县、镇（街道），另为了满足一般民众使用要求需要增加道路、名称（门牌号）两级，所以最终地址库设计共分为6级。

　　现今的分级地址库主要有两种实现方式：

　　一、 纵向设计。

　　每条记录只保存一个级别的一条信息，在该记录里存在描述信息和一个父对象id，通过保存父对象id的parentID字段可以一路往上获取更高级别的信息，直到地址分级的最高级别，最终整合这些信息可以获得完整记录。如图1所示(本文使用数据非真实数据，且为了展示简明，隐藏了记录坐标、地理编码等次要属性)：

                                  图1

　　详细设计方式可以参照论文《基于分词的地址匹配技术》——孙亚夫、陈文斌。

　　优点：减少数据冗余，原则上每个行政区划只需存储一次，该行政区划的下属行政区划通过它的id与它相关联；修改方便，每个行政区划的信息只保留在该行政区划的记录里，通过修改该条记录，就能够同时更新所有它下属的行政区划。

　　缺点：数据保存不直观，不能通过查看一条记录获得该地址的完整信息；数据结构的特殊性导致必须提供数据转换工具来对一般的地址信息进行转换；复杂的数据结构导致程序设计时必须考虑更多相关的风险，提高了系统的复杂度，从而增加了开发花销。

　　二、 横向设计。

　　每条记录代表一个兴趣点，该记录里面包含完整的分级的地址信息，所以每条记录存在与总级数相等的字段，里面放置各级信息。如图2所示：

                                          图2

　　优点：数据保存简明直观，可以直接通过查看数据表获得每条记录的详细信息；数据结构与数据采集方式大体一致，可以较为简单地进行数据录入；简单的数据结构更方便实现复杂的匹配算法。

　　缺点：每条记录都包含完整信息，记录条数越多数据冗余越严重；修改不便，修改一个行政区划的名字时必须对该行政区划的所有下属行政区划的记录进行修改。

　　本文参考了以上两种方法的优缺点，提出了另外一种实现方式：

　　把地名库分为xzqh和address两个表，其中xzqh表保存省、市、区县、镇（街道）、道路前五级数据，采取横向设计。如图3所示：

                                图3

　　address表保存名称（门牌号）数据，其中parentID字段是xzqh表的外键，记录通过该字段可以获取前五级信息。如图4所示：

　　

                           图4

　　此种设计主要考虑如下：

　　一、 参考了横向设计的优点，数据结构较为简单，在数据库中使用简单的sql语句可以达到较好的显示效果，方便管理员直接管理查看数据库。

　　二、 该设计可以解决数据大量冗余的问题，因为前五级数据相对较少且较为稳定，采取横向设计影响很小，数量最多的第六级参考了纵向设计的理念，以parentID字段关联上几级信息，从而避免大部分冗余。

　　三、 该设计继承横向设计的一些缺点可以通过数据库的特性来避免。比如sql语句可以较好解决修改不便的问题。

　　四、 基于该数据结构的算法模型实现起来较纵向设计简单，并可以在查询过程中实现分步查询，先根据xzqh表获取地址对应范围，缩小address表中需匹配的记录条数，从而降低时间开销。

2.2地址匹配算法：

　　算法概要设计：首先根据关键词在xzqh表中进行匹配，获取地址所在范围，缩小address表中需查询的记录条数；接着针对address表中处于该范围之内的记录进行再次匹配，获取最终结果。

第一阶段算法及示例如下：

　　xzqh表由于使用了横向的数据库设计，每条记录都包含完整的地址信息。所以此阶段算法可以简化为对每条记录进行单独判断、计算，并把计算结果进行筛选。

　　此阶段基于地名地址库进行分词，而不另外建立一个字典。由于地址库记录分级存储的数据结构，可以把记录的每一级看成一个“词语”，从而使地址库拥有字典的基本功能。

用户输入：珠海翠香街道香宁四街124号

xzqh表记录：（省略部分属性，另为使例子易于理解，其中部分地名为虚构）

   id province  city county   town    street

   1 广东省 珠海市 香洲区 梅华街道 梅华西路

   2 广东省 珠海市 香洲区 梅华街道 香宁四街

   3 广东省 珠海市 香洲区 翠香街道 人民西路

   4 广东省 珠海市 香洲区 翠香街道 紫荆路

   5 广东省 珠海市 香洲区 翠香街道 香宁三街

　　一、 对地址库每个级别的地址分别赋予不同的权重，以区分不同级别的重要程度。比如：市级为1，县区级为2，镇街级为3，道路级为4。根据用户输入对每条记录进行加权计算，匹配记录的每级字段，如果用户输入拥有该级别的“词语”则该记录权重值上升该级别的权重，匹配完一条记录后获得该条记录的最终权重值。匹配完所有记录后获得地址库中存在的最高权重值。此过程应允许用户输入地名简写，比如“珠海”应可以匹配“珠海市”。

中间结果：

   id province  city co unty   town    street  权重值

   1 广东省 珠海市 香洲区 梅华街道 梅华西路  1

2 广东省 珠海市 香洲区 梅华街道 香宁四街  5

3 广东省 珠海市 香洲区 翠香街道 人民西路  4

4 广东省 珠海市 香洲区 翠香街道 紫荆路  4

   5 广东省 珠海市 香洲区 翠香街道 香宁三街  4

　　二、 抛弃与最高权重值差距过大的记录，对剩余记录按权重值进行分组，对每个分组进行差异值检查，以进一步提高精确度。如果用户输入字符全部存在于记录的地址中，则两者差别为0，如果有一个字符不存在于记录地址中，则差别为1，以此类推。匹配剩余所有记录后获得所有记录与用户输入的差异值以及用户输入在每个分组中的最小差异值。（连续的阿拉伯数字当成一个字符）

中间结果：珠海翠香街道香宁四街124号

   id province  city county   town    street  权重值 差异值

2 广东省 珠海市 香洲区 梅华街道 香宁四街  5    4（最小）

3 广东省 珠海市 香洲区 翠香街道 人民西路  4    6

4 广东省 珠海市 香洲区 翠香街道 紫荆路  4    6

   5 广东省 珠海市 香洲区 翠香街道 香宁三街  4    3（最小）

　　三、 在每个分组中对记录进行筛选，抛弃与该分组最小差异值过大的记录，获得第一阶段结果。

中间结果：

   id province  city county   town    street  权重值 差异值

2 广东省 珠海市 香洲区 梅华街道 香宁四街  5    4

   5 广东省 珠海市 香洲区 翠香街道 香宁三街  4    3

第二阶段算法及示例如下：

   在xzqh获取地址范围之后，就可以从address表中提取出相应范围的记录，进行二次匹配。以下为筛选出来的记录：

 id  parentID address

 1   2  124号

 2   2  南方大厦 

 3   5  1242号

 4   5  55号

　　一、 按分组进行匹对。把用户输入字符去除第一阶段完全对应的属性后得出新的匹配字段。比如parentID为2的第一分组匹配字段为“翠香街道124号”，parentID为5的第二分组匹配字段为“香宁四街124号”，这是为了剔除用户输入信息的已使用部分，以精确匹配结果。计算每条记录address字段与匹配字段的匹配值（address字段与匹配字段相同的字符个数）和相似度（计算公式为：匹配值/address字段长度）。

   id  parentID address  匹配值  相似度

 1   2  124号   2  100%

 2   2 南方大厦124号 2  33% 

 3   5  1242号   1  50%

 4   5  55号   1  50%

　　二、 结合匹配值和相似度，剔除命中可能性太低的结果。比如第一分组，在匹配值相同时选取相似度更高的记录；第二分组中由于匹配值太低，相似度没有参考意义，两条记录都应舍去。故第二阶段结果为

   id  parentID address  匹配值  相似度

 1   2  124号   2  100%

最终结果：

　　第一阶段找到了可能性最高的两条记录，其中第一条记录在address表中找到了更详细的地址，以该地址代替原先记录。故最终应返回用户以下结果：

   id province  city county   town    road   address

2 广东省 珠海市 香洲区 梅华街道 香宁四街  124号

   5 广东省 珠海市 香洲区 翠香街道 香宁三街  

　　此算法能够动态挑选命中可能性较高的几条记录，相对于一般的匹配算法，拥有更高的容错性和精确度。

3.结语

　　本文希望能够通过较为简单的方式实现速度流畅，用户体验优秀的地址匹配功能。笔者在此功能的实现过程中主要考虑了以下几个问题：

　　（1）采用新的数据库设计，以增加少量数据冗余为代价，增加了单条数据的独立性与可读性，而独立性的增加也对匹配算法的简化提供了数据支持。（2）弃用了传统的通过词典来进行分词的方法，采用基于地址库的分词方式，简化了分词步骤。（3）在挑选结果过程中使用加权算法，并从中选择命中用户需求可能性最大的几条记录，而非把满足某种绝对性条件的所有记录都返回给用户，增加了此功能的容错性和精确度。

参考文献：

[1]  孙亚夫;陈文斌;基于分词的地址匹配技术[A];中国地理信息系统协会第四次会员代表大会暨第十一届年会论文集[C];2007年

[2]  程昌秀;于滨;一种基于规则的模糊中文地址分词匹配方法[J];《地理与地理信息科学》;2011年03期

[3]????李军;李琦;毛东军;郭玲玲;北京市地理编码数据库的研究[J];计算机工程与应用;2004年02期

[4]????郭会;宋关福;马柳青;王少华;地理编码系统设计与实现[J];计算机工程;2009年01期

[5]?????洪莹;城市地名地址匹配方法研究与实验[D];辽宁工程技术大学;2008年