测绘科学ScienceofSurveyingandMapping第35卷第2期2010年3月Vol135No12Mar1地理编码系统中地名地址分词算法研究张林曼,吴升(福州大学福建省空间信息工程研究中心,空间数据挖掘与信息共享教育部重点实验室,福州350002)【摘要】对中文分词有关技术进行分析和研究,结合地理编码的特点,设计了基于双字哈希和数组的三层组合分词词典数据结构,以及逐次增字的最大正向分词算法。并通过构建和遍历地名通名词典,识别地名地址中未登录词。测试表明,本文算法速度和效果较好,解决了地理信息系统中中文分词的相关问题。【关键词】GIS;地理编码;中文分词;地名【中图分类号】TP391【文献标识码】A【文章编号】100922307(2010)02200462031引言在实际生活中,人们通过地址来识别和寻找定位城市中的目标地物。在地理信息系统中,这种现实世界的定位方式是通过一段文字来表达目标位置的。例如“福州市井田路523号”。为了让计算机通过诸如以上文字叙述而直接寻找到目标的位置,必须建立非空间信息与空间信息之间的关联,地理编码[1,2]正是解决这一问题的方法。地理编码包括编码技术与地址匹配技术;前者利用地址模型和编码规则形成编码,后者解析地址并与标准地址模型进行匹配。地址匹配技术属于信息检索技术的范畴。作为信息检索基础的中文分词技术[3,4]直接决定了检索的准确度。在地理编码系统中,需要分词解析处理的是一些地名地址,这些地名地址中包含大量的专有名词,即未登录词。因此,设计出适合于地理编码的分词算法,并解决未登录词识别问题,是地理编码系统的关键。2基于中文分词的地址匹配原理地理编码的目标是为任何输入的地址信息数据返回最准确的匹配结果。地址匹配是指将记录的地址属性与地理编码库中地理实体的地址属性进行匹配,从海量的地理编码库中检索出符合需求的记录,然后将地理实体的坐标赋给匹配成功的记录。一般的做法,首先对地理编码库建立字或词的倒排索引,用来存储关键字和记录之间的映射关系,建立这样的索引避免了在所有记录中搜索关键字的麻烦,大大提高了检索效率。以“福州市井田路523号”为例,首先对地址进行解析和分词,得到“福州市/井田路/523/号”,然后对每一个切分出来的词建立其倒排索引,包括关键词出现的次数、频率、位置等等。如果不进行分词(按字检索),可能检索的结果与用户的期望大相径庭,例如检索“市井”就会把“福州市井田路523号”检索出来。因此,基于中文分词的地址匹配编码能大大提高准确率。3中文分词技术书面汉语是字的序列,词与词之间没有间隔标记,难以界定。目前,基于汉语的自动分词算法[5]主要包括:1)基于词典匹配的分词方法包括最大正向匹配法和最大逆向匹配法。最大正向匹配法MM(MaximumMatchingMethod)的基本思想为:设D为词典,MAX表示D中的最大词长,str为待切分的字串MM法每次从str中取长度为MAX的子串与D中的词进行匹配。若成功,则该子串为词,指针后移MAX个汉字后继续匹配,否则子串逐次减一进行匹配。最大逆向匹配法RMM(ReverseMaximumMatcingMethod)的基本原理与MM法相同,不同的是分词的扫描方向,它是从右至左取子串进行匹配。统计结果表明,单纯使用正向最大匹配的错误率为1/169,单纯使用逆向最大匹配的错误率为1/245,RMM法在切分的准确率上比MM法有很大提高。2)基于词频的统计分词方法统计方法一般不依赖于词典,而是将原文中任意前后紧邻的两个字作为一个词进行出现频率的统计,出现的次数越高,成为一个词的可能性也就越大。在频率超过某个预先设定得阈值时,就将其作为一个词进行索引。这种方法能够有效地提取出未登录词。3)基于知识理解的分词方法该方法主要基于句法、语法分析,并结合语义分析,通过对上下文内容所提供信息的分析对词进行定界。这类方法试图让机器具有人类的理解能力,需要使用大量的语言知识和信息。其中,基于词典匹配的分词方法在实际应用最为广泛。但这种方法的效率和准确性受到词库容量的约束;基于词频的统计分词方法所需的词频数据均由机器从语料中自动获得,无须人工介入,但对于地理编码数据库来说,很多地名地址数据都只出现一次,按照词频很难识别其为一个词,所以该方法不太适合未登录词比较多的地理编码;基于知识理解的分词方法涉及...