基于最大匹配算法的地址树编码研究

基于最大匹配算法的地址树编码研究 田 奎 Tian Kui (东华理工大学信息工程学院, 江西 抚州 344000) (Schoolof Information Engineering, East ChinaIn stitute of TechnologyJ, iangxi Fuzhou 344000) 摘 要: 本文在当前邮政编码方法的基础上，提出一种新的地址树编码算—法—最大匹配算法。该算法结合了地址树 的特点，考虑了地址树的唯一性，提出了最佳匹配理论，同时考虑到地址树的匹配速度，引入了地址树结点的可关联层数，提高 了匹配的效率。由于地址树具有变动性，为了及时更新地址树词库信息，通过智能化手段自动增加未知结。点 关键词: 编码;地址树;结点;匹配 中图分类号:TP301.6 文献标识码:A 文章编号:1671-4792(-2008)10-0014-03 Abstract: Basedon the analysis of currentz ip code, thisa rticle put forward a new encoding alg orithm of the address tree- the largest matchinga lgorithm. This algorithm combines the crhaacteristics of the address tree, ciondersing the uniquenesofs the address tree,r aises a best matching theory, and takintiong the matching speedof t he address tree,bri ngs in the associate floors of the nodeof the address treeto mprove the ecency of the match. Becauofs ethe changofe the address tree, the addtrreees s ’s thesaurusin order iffii to timely updateit s information, increase unknown node byin telligent meansa utomatically. , , , Keywords: CodeAddress TreeNodeMatching 、可阅读的、 可 投 递 的地 址 应 该包 括 以 下三一个严格的0 引言 个要素,准确的地址名,明确的隶属关系,精确的地址点。 地 地址树编码研究在我国已经 有二 、 三 十 年的 历 史 , 其应 用最广泛的方式就是邮政编码。 邮政编码由六位阿拉伯数字 址树模型是完整描述具体地址的数字模型,这个数字模型同 组 成 , 它 的 结 构 是 四 级 六 位 制 , 分 别 代 省 , 自 治 区 、 直 辖 样必须包含三个要素 ,地址名描述、地址 隶 属 关系 和 投 递地 市,、邮区、市,县,局及投递局四级。 址点。 很明显,这种编码方式只是简单地按地址中夹带的行政 1.2 地址树基本分析算法 区域划分的信息简单地组合成一种编码形式,而且其最细只 建立地址树模型的目的是为了阅读和地址,地址分 划分到投递局。 单靠编码仍不知投递到何处,还需要人工地 析算法就是用来阅读和规范地址的工具,它是一个基于地址 查看地址的具体信息。 因此,如何通过编码去标识地址树是 树模型的递归算法。 算法变量说明,MAXL 代表允许最大匹 配 数 ,IADD 代 表 初 始 待 分 析 地 址 ,P 代 表 父 结 点 编 号 , 首要问题,?建立合理的地址树模型 ,?构造 以 地 址树 为 知 RADD 代表匹配返回的地址,L[i]代表每个匹配成功的节点, 识基础的地址分析器,?建立不断壮大和调整地址树模型的 M[L[i]]代 表第 i 个 结 点 信 息 描 述 ,RLEN[i] 代 表 匹 配 字 符 串 机制。 的长度,RLEV[i]代表根结点到当前匹配的结点层数。 算法流 1 地址树模型 程如图一所示, 1.1 地址树模型的原理 点描述, ?进入分析算法的地址一定要做简 因为书写地址有很多不同的方式,计算机分析 们输入的地址,是从地址词库中取地址信息。 些地址做简单的规范处理,最大化地符合标准 描述;?同名问题。 分析地址时经常会遇到一 有多个同名。 同名有多种表现形式,像缺少区 名,例如北京市的同名为北京。 还有真正意义 中国的每个省份都有一个简称,?最佳匹配。 有可能找到多个合理的匹配, 因而存在一个 算法 中 , 定 义最 佳 匹 配的 条 件 为 ,? 匹 配 子 / 少,?匹配长度最大。 2 地址树的建立、维护 2.1 地址树的建立与维护 地址树的建立和维护有以下两种方式,? 特点设计地址模型调查表 ,将调查表发给 投 集投递部门的调查表并录入到系统中, 从而 图一匹配图并完善地址词库信息 ,?根据当地市政府 对 流程说明, 、行政区域变动情况的批文来新增地址 , 扩区 ?当分析地址时, 如 果可 匹 配 的数 量 大 于某 一 定 的数 中新的地址信息。 ,原地址一定有某些问题,例如,某市某区一 街, 可 能 在 词量2.2 智能化自动增加结点 库中符合条件的地址有几十个, ,能有条件如果碰到地址模型没有地址时 ?输出,L [1]、L [2]、… 、L [N], 增加,以便更加完善地址树词库信息,如图二 如 果 子 结 点 则?计 算 本 结点 与 子 / 孙 结 点 层 数 差 距 , Level=1,子结点的子结点 Level=2,以此类推, ? (RLEV [K],RLEN [K])= (Min (RLEV [i]),Max (RLEN [i])), i=1…N,提取最佳匹配; ?歧义地址。 原地址在地址模型中找到两个或两个以上 的地址匹配,则此地址产生歧义,无法分析。 1.3 地址树模型的构造 经过上述分析 ,地址树模型定 义为 , 以 多 叉树 状 的 数学 模型来描述地址的隶属关系。 地址树模型有以下两个要素组 成,?地址结点,地址结点描述一个具体的地 址 区 域或 者 地 ,权重值大的作为地址分析的优选路径。 同理,访问重的参考度。 如图三所示,可以为公园 1 结点加上关联层数 3。 量大的子树也将会有较大的权重。 4 结束语 本文对地址树编码的原理进行了详细的分析,并根据出 现不同种类的地址类型提出了相应的分析处理方式,同时采 用缓存技术加快了搜索速度。 地址树编码的研究既考虑到服 务器的响应速度,同时也考虑了地址匹配的精确度。 地址树 编码的研究为中国实现数字化和网 络 化城 市 有 一定 的 参 考 意义。 参考文献 [1]揭春雨 , 刘 源, 梁 南 元. 论汉 语 自 动分 词 方 法[J].中 文 信息学报,1989,(1):36-40. 图三 结点可关联层数示意图[2] 黄 俊 杰 . 书 面 汉 语 自 动 分 词 的 研 究 [J]. 计 算 机 杂 志 , 3.2 建立地址基树表 1991,(1):17-20. 在实际的地址模型中, 叶结点或接近叶结点的分支,会 [3]程伟,刘玉军,卢泽新.最佳比较字符串匹配算法研究 占整个地址模型数据量的很大一部分 ,地址 树主 干 、 区 路街 和应用[J].计算机工程与设计,2004,25(9):1430-1432. 等地址区域,只占总量的很少一部份。 因此,将地址主干抽出 [4]陈 桂 林. 一 种 改 进 的 快 速 分 词 算 法[J]. 计 算 机 研 究 与 来成为一个表,基树表,,如图四中的虚线方框地址主干可以 发展,2004,,04,. 构建一个地址基树表,从而加快地址分析的速度。 [5] 郭 辉 . 一 种 改 进 的 MM 分 词 算 法 [J]. 微 型 电 脑 应 用 , 2002,18(1):13-15. 作者简介 田奎(1981—),男,硕士研究生,主要研究方向,数据挖掘。