基于标志词的正向自适应长度匹配的地址分词算法与缺失地址要素补充方法

李净，朱贵鲜，周亮，郑西川

上海健康医学院附属第六人民医院东院 计算机中心，上海 201306

引言

随着纸质病历的逐渐退出，结构化电子病历成为各医院基本选择[1-2]。但门诊患者类型复杂、时效性较强、结构化病历转换复杂等因素，妨碍了门诊电子病历的深入应用[3-6]。其中患者住址为病人基本信息中的一条重要数据，但由于起初地址录入模型设计的不规范，导致患者地址信息地填写也不规范。这些非结构化的数据，对信息的提取工作造成了一定程度的困难。因此，将这些非结构化的地址数据转化为结构化的地址数据，显得尤为重要。

结构化的地址数据指地址按照统一的结构存储，比如按照省、市、区、街道等的结构存储。而目前医院电子病历中的地址数据结构混乱，往往存在地址信息不全面，大量的别名、简称，特殊符号（如#、-、/等）等问题。解决这些问题，实现非结构化地址数据向结构化地址数据转换，就需要将特殊符号转化成常规的文本信息，比如#表示号楼，然后将地址数据进行分词并记录每个分词的地址能级，并根据分词结果补充缺失的地址要素，并根据自定义的地址匹配规则库将别名、简称等标准化。

在以上所提要做的工作中，关键在于地址分词和缺失地址要素的补充。中文分词是目前很多学者的研究方向，主流的分词方法主要分为两类：机械分词法[7-14]和统计分词法[15-21]。由于地址数据里的地址要素常常会包含一些标志词，如省、市、区等，刘韬[9]提出了设立切分标志法对地址数据进行分词。但在实际的地址录入过程中，很多时候或省略标志词，如上海普陀曹杨街道，就会造成分词结果的不准确。马照亭等[10]在中文自动分词词库的基础上，添加了《中国地名用词库》中的通用地名词条和一个城市中的专用地名或地址词条，并为地址要素挂接“标准名称”和“地址级别”两个属性字段，提高了分词的准确率，但同时增长了分词的时间。赵阳阳等[4]提出了地址要素识别机制的地名地址分词算法，该算法依托整词二分词典并通过设置当下词属性的方式，得到了比较好的分词精度，但同样以牺牲运行时间为代价。冯永等[16]提出了基于自适应中文分词和近似SVM的文本分类算法，能很好的适应不同的预料规划问题，取得了不错的成绩。但基于二元统计模型的分词算法计算复杂，与上述三种基于机械分词方法的算法相比，计算量大，比较耗时。而中文地址分词与整个中文分词领域相比，语料之简单并不能相提并论，故本文方法选用了比较简单的机械分词法。比较常见的机械分词法有正向最大匹配法（Forward Maximum Matching Method，FMM）和逆向最大匹配法。因为地址文本不存在主干成分后置的问题[7]，故在比较简单的FMM算法原理的基础上进行改进。为了进一步提高地址分词的精度和速度，本文先根据标志词把地址数据进行粗分，在在粗分结果的基础上，以每个分词的长度自适应与标准数据库进行匹配。

1 基于地址要素标志的正向自适应长度匹配分词模型设计

一条地址数据中往往包含几种不同级别的地址要素，把这些不同级别的地址要素记作：A级代表省，B级代表市，C级代表区，D级代表街道，E级代表门牌，F级代表县，G级代表乡镇，H级代表村，I级代表建筑或单位名称，J表示其他，如表1所示。结构化的地址模型的组合方式主要包括两类三组：第一类，省下各区域ABCDE，ABFGHJ；第二类，直辖市或特别行政区BCDE。

表1 地址要素级别

由于地址数据里的地址要素往往包含不同级别的地址标志词，如省、市、路、街、弄、号、村、镇、乡等，本文提出了基于地址要素标志的正向自适应匹配中文地址分词算法。自适应在于将常规的FMM中的机器词典中的最长词条的长度替换为通过按照地址要素标志切分后所得的字符数组各项的长度，以减少匹配次数，提高匹配速度。本文提出的算法是建立在构建的存储标准地址数据集的标准地址库的基础上。该数据库存放了全国各地的地址要素，主要信息包括地址要素的名称（如上海市、黄浦区等）和级别（如省A，市B）等相关信息，用于本文分词算法的标准匹配库。本文的分词算法先通过设置地址要素的常规地址标志，如省，以及一些特殊字符作标志，如#代表几号楼等，对地址数据进行粗分；然后对粗分后的字符数组进行正向自适应长度的匹配操作。具体流程如下。

（1）输入一条中文地址字符串S。

（2）split (S) — str[n]，规则：按照制定的标志词，如果标志词在句首，不做切分；如果两个标志词间距为零，只在后面的标志词进行切分；若两标志词距离大于0，每个标志词都进行切分。

（3）将粗切分得到的字符数组的第i项先按str[i]的长度与标准库地址要素formData进行匹配；若匹配成功，则将formData作为一个地址要素，存到输出数组out中，以及formData所代表的级别存到级别数组level中，并将str[i]中与formData匹配成功的字符移除，退出本循环；若不成功，取str[i]的前str[i].length-1个与标准库匹配，以此类推，直到匹配成功将formData及级别分别存入out和level中，或匹配结束仍未成功，直接把str[i]存到输出数组out中。

（4）loop（ 3），直至粗切分数组str每一项都处理完毕。

其中，（3）与（4）过程算法伪代码如下：

2 缺失的地址要素补充与地址要素重组方法

对于不完整的地址数据，由于我国第二级行政区域的名称是唯一的，其对应的第一级行政区域也是唯一的，所以省略第一级行政区域并不影响书写地址的正确性，但如果省略第二级或第三极行政区域，则不一定正确理解地址信息[10]。对于一份残缺地址，可以根据当前地址要素的parentid找到父级地址要素。为实现补充缺失地址要素的功能以及统一同一个地点不同的表述，设计了自定义的地址匹配规则库。

自定义的地址匹配规则库用于补充缺失的地址要素，并把以建筑物或单位名称（I级）书写的地址要素转化成D级地址要素（街道名称）。因此该库包含的信息主要为地址要素名称，父级地址要素名称parentid等信息。相同位置的D级地址要素和I级地址要素具有相同的parentid，因此可以完成两种类型的地址要素间的转化。同时，根据parentid，也能找到缺失的地址要素。

缺失地址要素的补充是通过上一章分词所得到的数组，从后往前与自定义的地址匹配规则库匹配，找个parentid，进而找到父级地址要素，具体流程如下。

（1）从out数组从后往前查找，若parentid为null，向前移一个分词查找。

（2）若parentid不为null，若parentId仅有一个，则可唯一确定一个地址；若parentid为多个，则拿搜索到的父级地址要素与out数组的前一个地址要素匹配，若匹配成功，则可以唯一确定一个地址，若匹配失败（原因1地址要素漏项较多；原因2书写错误，对于原因2尚未处理），则查找搜索到的父级地址要素的父级地址要素，与out数组的前一个地址要素的前一个要素匹配，直至匹配成功，唯一确定一个地址，或out数组已经遍历完成，则地址无法唯一确定，对该地址不做处理。

3 结果

3.1 基于标志词的正向自适应长度匹配的地址分词算法

本文以本院病案首页中的地址数据为实验数据。为了验证本文所提的分词算法的效果，从病案首页的地址数据中随机选取1000条数据，分为10、100和1000条3组进行实验，并与FMM算法作对比，以观察批量处理地址数据时，随之输入数据的增多，算法在性能上的变化。实验结果如表2所示。

表2 本文算法与最大长度匹配算法性能比较

从表2可以看出，本文所提出的算法，随着输入的变化，不论是在地址分词的精度还是在消耗的时间上，与FMM算法相比，都有一定程度的提高。这两种方法差异的主要原因在于，首先从精度上讲，中文地址与普通中文文本相比，其语料非常简单，而且常常有明显的标志词，通过划分标志词的方法比按照中文复杂的语料直接匹配断句更为精确；从时间上讲，按照标志词作预划分，其结果本身比较接近真实情况，而且每轮匹配长度的初始值按照预划分分项的长度，不仅使匹配长度自适应，与FMM算法每次按最大长度匹配相比也减少了匹配次数，进而节省时间。

3.2 缺失地址要素补充方法

图1为本文缺失地址要素补充方法得到的几条实验结果。从结果可以看出，能够唯一确定一条地址记录的数据（如1、2、4、5），缺失的地址要素能够很好的补充完整；对于数据3，由于地址要素缺失严重，无法唯一确定一条地址，在该算法对此数据是不做处理的（宁愿地址具有模糊也不应该补进去一个可能错误的要素），但为了显示实验效果，说明不作处理的原因，数据3实验结果仍保留了多条匹配记录。对于数据4，补充的结果出现两个“号”，在今后的工作中对“号”与“弄”等诸如此类的差别需要做的更精细，也需要更多的数据支撑。

图1 缺失地址要素补充方法结果

4 结语

本文通过对电子病历中的文本数据分析，提取出相对正确的地址，大大减少临床数据的重复录入，极大提高了临床工作效率、方便了数据上报和统计分析。同时补充了不完整的地址，完成地址标准化的工作，极大提高了数据质量，给临床信息录入和科研工作打下坚实基础。不仅如此，该研究成果对于电子病历中其他数据的标化具有重要指导价值。