第34卷第8期2009年8月
武汉大学学报·信息科学版GeomaticsandInformationScienceofWuhanUniversity
Vol.34No.8Aug.2009
文章编号:167128860(2009)0820943205
文献标志码:
A 一种中文自然语言表达交通信息的跨阶分词算法 陆 锋
1 刘焕焕1,
2 陈传彬1,
3 (1 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京市朝阳区大屯路甲11号,100101)(
2 中国矿业大学(北京)资源与安全工程学院,北京市海淀区学院路丁11号,100083)(
3 福州大学福建省空间信息工程研究中心,福州市工业路523号,350002) 摘 要:在分析中文分词算法和交通信息自然语言表达特点基础上,提出了一种自然语言表达交通信息的跨阶匹配分词算法,以适应动态出行信息服务对数字形式结构化实时交通信息的迫切需求。
该算法充分考虑了交通信息自然语言描述词库记录长度特点,通过设置对应的中文分词阶数,将传统中文分词的字符串指针1阶跨越方法改进为依词库性质变化的多阶跨越方法,对可能成词的中文字符串进行整体处理,极大地提高了自然语言表达交通信息的实时分词与理解效率。
通过与改进MM(maximummatching)算法的实验比较,本方法在理解成功率和容错性相同的情况下,效率比MM分词算法提高了10倍以上。
关键词:交通信息;中文自然语言处理;分词;跨阶法中图法分类号:P208 目前,实时交通信息采集和发布技术在各大城市日趋成熟,对提高城市交通管理和公众出行效率起到了很大的作用。
然而,来源于浮动车和感应线圈采集的交通流信息,难以覆盖整个路网,也难以获取突发性点状交通信息;来源于短信息、电话、监控摄像头的交通信息目前只能通过人工处理方式加以利用,或直接通过语音广播形式发送,并且发送量十分有限,无法服务于日益普及的动态导航过程。
因此,迫切需要开展自然语言表达交通信息的实时分词技术研究,进而与路网空间信息进行实时融合,通过各种通讯协议发布,服务于广大的交通出行者。
目前的中文分词算法主要有以下三种[125]:①机械分词法。
又称词典式切分法,包括最大匹配法(MM算法)、部件词典法、词频统计法、设立标志法、并行分词法、词库划分和联想匹配法等。
②语义分词法。
切分时引入语义分析,如邻接约束法、综合匹配法、后缀分词法、特征词库法、约束矩阵法、语法分析法等。
③人工智能法。
模拟人脑思维功能进行分词,如神经网络分词法和专家系统分词法。
目前,各种流行的分词算法有着不 同的技术特点和适应性。
机械分词法较为简洁,易于实现,尤其是最大匹配法及其改进算法,在工程上得到了广泛的应用[628]。
但机械分词法难以处理未登录词,无法有效克服歧义切分。
语义分词法切分精度较高,但在引入了语义分析的同时也增大了时空开销。
人工智能法研究还处于初步阶段,效率不高,不易实现。
由于目前还不能达到真正意义上的自然语言理解,对于特定的应用领域,可以根据自然语言描述的规则,建立受限语法规则,获取输入自然语言中的关键字词信息[9,10]。
因此,对于中文自然语言表达交通信息的自动化理解,应当根据交通信息自然语言表达的特点,开展分词方法研究。
从应用特点上看,交通信息具有很强的实时性,只关心能否快速、正确地处理地点、方向、数值偏移量、事件等类型的关键词汇,忽略无关词汇。
自然语言理解过程对分词算法的时间效率要求较高。
从信息特征上看,交通信息描述较为简短,采用规范的陈述句句型,关键词汇具有长词优先的特点,存在较少的理解歧义。
此外,由于理解目的在于和空间信息匹配,所有涉及的地址、方位和事件词汇已经在 收稿日期:2009205220。
项目来源:国家863计划资助项目(2006AA12Z209,2007AA12Z241);国家自然科学基金资助项目(40871184);中国科学院知识创 新工程重点方向性资助项目(KZCX22YW2308)。
944 武汉大学学报·信息科学版 2009年8月 词汇库中存在,不需要考虑未登录词的处理。
因此,比较适合采用机械分词法中的匹配方法。
然而,传统的MM算法在匹配分词过程中通常采用逐渐减一字方式处理,处理效率低下。
而词库中的最大词长通常大于所切分出的词长,即使采用正向逐一递增循环方式处理,虽然在一定程度上提高了传统MM方法中文分词的效率,但是依然采取逐字匹配方法,没有考虑词库记录长度的特点,对可能成词的中文字符串进行特别处理。
也有文献基于长词优先原则,提出了首字扩词分词法,根据查询自然语言字符串首字符对词汇库的记录进行筛选,并在缩小匹配范围时根据筛选后的子词库记录长度决定匹配长度[11]。
该算法避免了MM算法在匹配过程中固定不变的字符加减方式,更适合字符串长度完全随机的匹配分词过程。
而交通信息词库记录字符串长度具有很强的规律性,应当利用这一特征尽早判断可能成词的中文字符串,尽可能避免无谓匹配过程。
因此,本文提出一种采用跨阶匹配的中文自然语言表达交通信息分词算法。
1 跨阶分词算法原理 以中文自然语言表述的实时交通信息通常表示形式为“<地址>+{方向}+{偏移量}+<事件>”。
交通信息描述词库包括地址词库、方向词库和事件词库。
地址词库存储交通信息发生地址;方向词库存储描述交通信息时采用的方向信息,如“由东向西”、“从南到北”等;而事件词库则存储交通信息所对应的具体事件,如“车行缓慢”“、追尾”、“两车刮蹭”等。
各词库中记录长度分布具有一定的规律。
以笔者开发的北京市交通信息处理与融合系统为例,其中交通信息涉及的地址库记录长度分布如表1所示。
从表1可以看出,自然语言描述的交通信息发生地址长度具有一定的统计规律,地址库中 表
1 交通信息描述词库地址库记录长度分布 Tab.1 LengthDistributionofAddressRecordsin Real2timeTrafficInformation 记录长度 记录数 比例/%
2 29 0.71
3 797 19.48
4 1480 36.18
5 1218 29.77 6≥7合计 4271404091 10.443.42100 99.3%的记录长度大于
2,尤以记录长度为4或5居多。
方向信息和事件信息也具有类似的统计规律。
因此,采用经典或改进的MM算法进行分词时,指针在整个句子中逐字移动,并进行累加词库匹配,没有利用交通信息词库记录长度分布的统计规律,对可能成词的中文字符串进行整体处理,无疑是一种比较低效的方法。
因此,本文基于交通信息自然语言描述词库记录长度特点,设置对应的中文分词阶数,提出跨阶匹配分词思想,将传统中文分词的字符串指针一阶跨越方法改进为依词库性质变化的多阶跨越,以提高分词效率。
对中文自然语言描述的实时交通信息进行分词处理时,首先将整个句子从左侧开始,与地址库进行匹配,然后将分词后的字符串再分别与地址库(接受可能出现的二重地址描述)、方向库及事件库进行匹配。
与地址库进行匹配时,根据地址库记录长度分布特点,设置初始阶数为
3,根据匹配结果设置指针的前移或后移;与方向库进行匹配时,按照方向库中记录的最大长度设置阶数为
4,成词则成功切分,若不成词,指针前移,再次与方向库进行匹配;与事件库进行匹配时,根据事件库记录长度分布特点,设置初始阶数为
2,根据匹配结果设置指针的前移。
2 数据结构与算法流程 2.1 数据结构本文采用了一种多层模式的数据结构。
其具 体描述如下:最大的层数为词库中最大词的单字数。
其中,字母表示一个字,数字表示成词标志,0代表当前字串不能单独成词,只是某一词汇的一部分,1则代表可以成词。
第一层存储单字,第二层存储以第一层的字串为前缀的双字或者双字词,第三层存储以第二层的字串为前缀的三字或者三字词,依此类推。
采用多层树型结构,能不断 图
1 词库存储数据结构Fig.1 DataStructureofwordLibrary 第34卷第8期 陆 锋等:一种中文自然语言表达交通信息的跨阶分词算法 945 限定匹配范围,提高分词算法的效率。
2.2 算法流程 本文提出的跨阶中文匹配分词算法思想如下。
目标:对一个以中文自然语言描述的交通信息语句C1C2…Cn进行分词处理。
其定义符号如下:A地址库;O方向库;E事件库;currentWord为当前与词库比较的词汇;F为地址词汇切分标记,初始为false。
1)读入Ck,判断F值,若是true,则判断Ck是哪个词库的前缀字符,若是A的前缀则转入步骤2),若是O的前缀转入步骤3),若是E的前缀转入步骤4),若是A与O或E的前缀,转入步骤5)。
若Ck不是3个词库的前缀,将Ck从整个句子中切分出去,读入下一个可能成词的字符;若F为false,只判断Ck是否是A的前缀,如是则转入步骤2),否则将Ck从整个句子中切分出去。
2)如Ck是A的前缀字符,读入Ck+1Ck+
2,判断CkCk+1Ck+2是否也是A的前缀,如是则判断是否可成词,不成词继续循环读入下一个字符,再进行判断,如可成词则将CkCk+1Ck+2切分出来作为 候选地址,然后判断CkCk+1Ck+2是否同时也是A中另外某词的前缀,若是,再循环往下读字符并进行判断,否则将CkCk+1Ck+2作为成功切分地址,F设为true。
如CkCk+1Ck+2不是A的前缀,指针后退2位,以Ck+1作为起始字符转入步骤1)。
3)如Ck是O的前缀字符,读入Ck+1Ck+2Ck+
3,判断CkCk+1Ck+2Ck+3是否可成词,如是则成功切分;不成词则指针前移,判断CkCk+1Ck+2是否成词。
依此类推,若成词则进行成功切分,如始终不成词,则以Ck+1为开始字符转入步骤1)。
4)如Ck是E的前缀字符,则读入Ck+
1,判断CkCk+1是否是成词前缀,如是则判断是否成词,成词则成功切分,否则循环继续读入下一个字符,再进行判断。
如CkCk+1不是成词前缀,以Ck+1作为起始字符转入步骤1)。
5)读入Ck+
1,判断CkCk+1是否是O或E的成词前缀,若是则转入步骤3)或步骤4),若不是则判断CkCk+1是否是A的成词前缀,如是则转入步骤2),否则以Ck+1作为起始字符转入步骤1)。
其算法流程如图2所示。
图
2 自然语言交通信息跨阶分词算法流程Fig.2 FlowChartofCross2stepWordSegmentationAlgorithmforTrafficInformationinNaturalChinese 946 武汉大学学报·信息科学版 2009年8月 以实时交通信息“健翔桥由南向北行驶缓慢”为例,来介绍跨阶中文分词方法的运行过程:首先读入“健”字,写入currentWord,直接与地址库进行比较,判断currentWord是地址库中词的前缀。
继续读入“翔桥”,currentWord修改为“健翔桥”,能够单独成词,此外地址词库中也不存在其他以“健翔桥”为前缀的词,则成功切分出地址为“健翔桥”。
然后将currentWord置空,将地址切分标志F设为true;读入“由”字,写入currentWord,判断其为方向库的前缀,则读入“南向北”,修改cur2rentWord为“由南向北”,判断成词,则成功切分出方向信息。
再将currentWord置空,读入“行”字,写入currentWord,判断其为事件库中词的前缀,继续读入“驶”字,currentWord修改为“行驶”“,行驶”也是成词前缀,不能单独成词,继续读入“缓”和“慢”字符,currentWord置为“行驶缓慢”,可以单独成词,则成功切分出对应交通事件。
值得注意的是,交通信息中还可能存在数字型偏移量,偏移量数值难以预先在词库中逐一枚 举。
针对这一问题,本文采用数值型偏移量与字符串匹配分开处理策略,先以跨阶法处理输入的自然语言表达的交通信息,再对无法匹配的剩余字符串进一步处理,从而一次性提取出数字信息,以此达到偏移量切分目的。
3 效率实验 在上述算法研发的基础上,笔者采用Java技术实现了实时交通信息的跨阶中文分词算法。
实时交通信息来源于北京交通广播电台,空间信息采用基于路幅段模型构建的路网数据集,符合地理导航数据库国际标准GDF4.0中1层定义[12]。
采用Oracle10g数据库管理系统完成所有数据的管理工作。
选择北京市五环内城市路网作为示范区域,并随机收集了2007211209∶08∶00～18∶00这一时段内北京交通广播电台发布的实时交通信息,共计400条,如图3所示。
图
3 自然语言描述的实时交通信息Fig.3 Real2timeTrafficInformationRepresentedinNaturalChinese 实时交通信息是对交通状况的即时反映,而且具有很强的时效性。
针对实时出行和智能导航,实时交通信息的处理效率至关重要。
对400条交通信息分别用跨阶分词算法和改进的MM分词算法进行中文分词,跨阶分词算法和改进的MM分词算法理解成功率均为98%,容错性也完全相同,但改进的MM分词算法耗时为2951ms,而跨阶分词算法耗时仅为229ms,跨阶分词算法比改进MM中文分词的效率提高了10倍以上,体现出很好的效率优势。
本文所提出的自然语言表达交通信息的跨阶匹配分词算法,充分考虑了交通信息自然语言描述词库记录长度特点,通过设置对应的中文分词阶数,将传统中文分词的字符串指针一阶跨越方法改进为依词库性质变化的多阶跨越,对可能成 词的中文字符串进行成词处理。
在理解成功率和容错性相同的情况下,该算法极大地提高了自然语言表达交通信息的实时分词与理解效率,效率比经典的MM分词算法提高10倍以上。
后续研究中将进一步提高算法的容错性,使其可处理以长句或组合多句表达的交通信息,以尽可能提高自然语言表达的实时交通信息的自动化、智能化处理水平。
参 考 文 献 [1] 文庭孝,邱均平,侯经川.汉语自动分词研究展望[J].现代图书情报技术,2004
(7):629 [2] 张春霞,郝天永.汉语自动分词的研究现状与困难[J].系统仿真学报,2005,17
(1):1382143 [3] 邱均平,文庭孝,周黎明.汉语自动分词与内容分析 第34卷第8期 陆 锋等:一种中文自然语言表达交通信息的跨阶分词算法 947 法研究[J].情报学报,2005,24
(3):3092317[4] 黄昌宁,赵海.中文分词十年回顾[J].中文信息学 报,2007
(9):8219[5] FuG,KitC,WebsterJJ.ChineseWordSegmenta2 tionasMorpheme2basedLexicalChunking[J].In2formationSciences,2008,178:228222296[6] 乐小虬,杨崇俊,于文洋.基于空间语义角色的自然语言空间概念提取[J].武汉大学学报·信息科学版,2005,30(12):110021103[7] 胡斌,汤伟,刘晓明.基于自然语言理解的文本标图系统设计与实现[J].解放军理工大学学报(自然科学版),2005,6
(2):1322136[8] 马林兵,龚健雅.空间信息自然语言查询接口的研究与应用[J].武汉大学学报·信息科学版,2003, 28
(3):3012305[9] 龙毅,张翎,胡雷地,等.移动GIS中语音与自然语 言的应用模式探讨[J].测绘科学技术学报,2008,25
(1):8212[10]徐爱萍,边馥苓.GIS中文查询系统的词典设计与分词研究[J].武汉大学学报·信息科学版,2006,31
(4):3482351[11]吴静,蔡砥,王铮.地理信息系统中自然语言查询的分词处理与应用[J].地球信息科学[J],2005,7
(3):67271[12]蒋捷,韩刚,陈军.地理导航数据库[M].北京:科学出版社,2003 第一作者简介:陆锋,博士,研究员,博士生导师,研究方向包括空间数据库管理技术、交通GIS理论与技术、LBS与导航数据库技术、城市发展与城市GIS技术等。
E2mail:luf@lreis. ACross2stepWordSegmentationAlgorithmforUnderstandingTrafficInformationRepresentedinNaturalChineseLanguage LUFeng1 LIUHuanhuan1,
2 CHENChuanbin1,
3 (1 LREIS,InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,A11DatunRoad,Beijing100101,China)(
2 CollegeofResourcesandSafetyEngineering,ChinaUniversityofMiningandTechnology,D11XueyuanRoad,Beijing100083,China) (
3 SpatialInformationResearchCenter,FuzhouUniversity,523GongyeRoad,Fuzhou350002,China) Abstract:Anovelcross2stepwordsegmentationalgorithmisproposedtoprocessreal2timetrafficinformationrepresentedinnaturalChineseinthispaper,tomeettheurgentneedofreal2timetravelinginformationservice,fordynamictrafficinformation.Consideringthere2cordlengthdistributionofthewordlibrariesdepictingreal2timetrafficinformation,thisal2gorithmsetscorrespondingstepsofwordsegmentationforaddress,directionandeventli2braries,andimprovestheonesteprunningofthestringpointerinclassicalChinesewordsegmentationtoflexiblemultiplestepsrunning,soastoaggregatepossibleChinesewordsefficiently.Acasestudyshowsthattheproposedalgorithmruns10timesfasterthananim2provedMMalgorithm,whilstkeepingsimilaruracyandrobustness.Theauthorsarguedthatthepresentedalgorithmisgreatlyhelpfultotheautomaticandintelligentprocessingofthereal2timetrafficinformation,andfacilitatethedevelopmentoftravelinformationserv2ices.Keywords:trafficinformation;naturalChineseprocessing;wordsegmentation;cross2stepalgorithm Aboutthefirstauthor:LUFeng,researcher,Ph.D,Ph.Dsupervisor,Researchinterestsincludespatialdatabasetechnologies,GISfortransportationandLBSapplications,urbandevelopment,etc.E2mail:luf@lreis.
A 一种中文自然语言表达交通信息的跨阶分词算法 陆 锋
1 刘焕焕1,
2 陈传彬1,
3 (1 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京市朝阳区大屯路甲11号,100101)(
2 中国矿业大学(北京)资源与安全工程学院,北京市海淀区学院路丁11号,100083)(
3 福州大学福建省空间信息工程研究中心,福州市工业路523号,350002) 摘 要:在分析中文分词算法和交通信息自然语言表达特点基础上,提出了一种自然语言表达交通信息的跨阶匹配分词算法,以适应动态出行信息服务对数字形式结构化实时交通信息的迫切需求。
该算法充分考虑了交通信息自然语言描述词库记录长度特点,通过设置对应的中文分词阶数,将传统中文分词的字符串指针1阶跨越方法改进为依词库性质变化的多阶跨越方法,对可能成词的中文字符串进行整体处理,极大地提高了自然语言表达交通信息的实时分词与理解效率。
通过与改进MM(maximummatching)算法的实验比较,本方法在理解成功率和容错性相同的情况下,效率比MM分词算法提高了10倍以上。
关键词:交通信息;中文自然语言处理;分词;跨阶法中图法分类号:P208 目前,实时交通信息采集和发布技术在各大城市日趋成熟,对提高城市交通管理和公众出行效率起到了很大的作用。
然而,来源于浮动车和感应线圈采集的交通流信息,难以覆盖整个路网,也难以获取突发性点状交通信息;来源于短信息、电话、监控摄像头的交通信息目前只能通过人工处理方式加以利用,或直接通过语音广播形式发送,并且发送量十分有限,无法服务于日益普及的动态导航过程。
因此,迫切需要开展自然语言表达交通信息的实时分词技术研究,进而与路网空间信息进行实时融合,通过各种通讯协议发布,服务于广大的交通出行者。
目前的中文分词算法主要有以下三种[125]:①机械分词法。
又称词典式切分法,包括最大匹配法(MM算法)、部件词典法、词频统计法、设立标志法、并行分词法、词库划分和联想匹配法等。
②语义分词法。
切分时引入语义分析,如邻接约束法、综合匹配法、后缀分词法、特征词库法、约束矩阵法、语法分析法等。
③人工智能法。
模拟人脑思维功能进行分词,如神经网络分词法和专家系统分词法。
目前,各种流行的分词算法有着不 同的技术特点和适应性。
机械分词法较为简洁,易于实现,尤其是最大匹配法及其改进算法,在工程上得到了广泛的应用[628]。
但机械分词法难以处理未登录词,无法有效克服歧义切分。
语义分词法切分精度较高,但在引入了语义分析的同时也增大了时空开销。
人工智能法研究还处于初步阶段,效率不高,不易实现。
由于目前还不能达到真正意义上的自然语言理解,对于特定的应用领域,可以根据自然语言描述的规则,建立受限语法规则,获取输入自然语言中的关键字词信息[9,10]。
因此,对于中文自然语言表达交通信息的自动化理解,应当根据交通信息自然语言表达的特点,开展分词方法研究。
从应用特点上看,交通信息具有很强的实时性,只关心能否快速、正确地处理地点、方向、数值偏移量、事件等类型的关键词汇,忽略无关词汇。
自然语言理解过程对分词算法的时间效率要求较高。
从信息特征上看,交通信息描述较为简短,采用规范的陈述句句型,关键词汇具有长词优先的特点,存在较少的理解歧义。
此外,由于理解目的在于和空间信息匹配,所有涉及的地址、方位和事件词汇已经在 收稿日期:2009205220。
项目来源:国家863计划资助项目(2006AA12Z209,2007AA12Z241);国家自然科学基金资助项目(40871184);中国科学院知识创 新工程重点方向性资助项目(KZCX22YW2308)。
944 武汉大学学报·信息科学版 2009年8月 词汇库中存在,不需要考虑未登录词的处理。
因此,比较适合采用机械分词法中的匹配方法。
然而,传统的MM算法在匹配分词过程中通常采用逐渐减一字方式处理,处理效率低下。
而词库中的最大词长通常大于所切分出的词长,即使采用正向逐一递增循环方式处理,虽然在一定程度上提高了传统MM方法中文分词的效率,但是依然采取逐字匹配方法,没有考虑词库记录长度的特点,对可能成词的中文字符串进行特别处理。
也有文献基于长词优先原则,提出了首字扩词分词法,根据查询自然语言字符串首字符对词汇库的记录进行筛选,并在缩小匹配范围时根据筛选后的子词库记录长度决定匹配长度[11]。
该算法避免了MM算法在匹配过程中固定不变的字符加减方式,更适合字符串长度完全随机的匹配分词过程。
而交通信息词库记录字符串长度具有很强的规律性,应当利用这一特征尽早判断可能成词的中文字符串,尽可能避免无谓匹配过程。
因此,本文提出一种采用跨阶匹配的中文自然语言表达交通信息分词算法。
1 跨阶分词算法原理 以中文自然语言表述的实时交通信息通常表示形式为“<地址>+{方向}+{偏移量}+<事件>”。
交通信息描述词库包括地址词库、方向词库和事件词库。
地址词库存储交通信息发生地址;方向词库存储描述交通信息时采用的方向信息,如“由东向西”、“从南到北”等;而事件词库则存储交通信息所对应的具体事件,如“车行缓慢”“、追尾”、“两车刮蹭”等。
各词库中记录长度分布具有一定的规律。
以笔者开发的北京市交通信息处理与融合系统为例,其中交通信息涉及的地址库记录长度分布如表1所示。
从表1可以看出,自然语言描述的交通信息发生地址长度具有一定的统计规律,地址库中 表
1 交通信息描述词库地址库记录长度分布 Tab.1 LengthDistributionofAddressRecordsin Real2timeTrafficInformation 记录长度 记录数 比例/%
2 29 0.71
3 797 19.48
4 1480 36.18
5 1218 29.77 6≥7合计 4271404091 10.443.42100 99.3%的记录长度大于
2,尤以记录长度为4或5居多。
方向信息和事件信息也具有类似的统计规律。
因此,采用经典或改进的MM算法进行分词时,指针在整个句子中逐字移动,并进行累加词库匹配,没有利用交通信息词库记录长度分布的统计规律,对可能成词的中文字符串进行整体处理,无疑是一种比较低效的方法。
因此,本文基于交通信息自然语言描述词库记录长度特点,设置对应的中文分词阶数,提出跨阶匹配分词思想,将传统中文分词的字符串指针一阶跨越方法改进为依词库性质变化的多阶跨越,以提高分词效率。
对中文自然语言描述的实时交通信息进行分词处理时,首先将整个句子从左侧开始,与地址库进行匹配,然后将分词后的字符串再分别与地址库(接受可能出现的二重地址描述)、方向库及事件库进行匹配。
与地址库进行匹配时,根据地址库记录长度分布特点,设置初始阶数为
3,根据匹配结果设置指针的前移或后移;与方向库进行匹配时,按照方向库中记录的最大长度设置阶数为
4,成词则成功切分,若不成词,指针前移,再次与方向库进行匹配;与事件库进行匹配时,根据事件库记录长度分布特点,设置初始阶数为
2,根据匹配结果设置指针的前移。
2 数据结构与算法流程 2.1 数据结构本文采用了一种多层模式的数据结构。
其具 体描述如下:最大的层数为词库中最大词的单字数。
其中,字母表示一个字,数字表示成词标志,0代表当前字串不能单独成词,只是某一词汇的一部分,1则代表可以成词。
第一层存储单字,第二层存储以第一层的字串为前缀的双字或者双字词,第三层存储以第二层的字串为前缀的三字或者三字词,依此类推。
采用多层树型结构,能不断 图
1 词库存储数据结构Fig.1 DataStructureofwordLibrary 第34卷第8期 陆 锋等:一种中文自然语言表达交通信息的跨阶分词算法 945 限定匹配范围,提高分词算法的效率。
2.2 算法流程 本文提出的跨阶中文匹配分词算法思想如下。
目标:对一个以中文自然语言描述的交通信息语句C1C2…Cn进行分词处理。
其定义符号如下:A地址库;O方向库;E事件库;currentWord为当前与词库比较的词汇;F为地址词汇切分标记,初始为false。
1)读入Ck,判断F值,若是true,则判断Ck是哪个词库的前缀字符,若是A的前缀则转入步骤2),若是O的前缀转入步骤3),若是E的前缀转入步骤4),若是A与O或E的前缀,转入步骤5)。
若Ck不是3个词库的前缀,将Ck从整个句子中切分出去,读入下一个可能成词的字符;若F为false,只判断Ck是否是A的前缀,如是则转入步骤2),否则将Ck从整个句子中切分出去。
2)如Ck是A的前缀字符,读入Ck+1Ck+
2,判断CkCk+1Ck+2是否也是A的前缀,如是则判断是否可成词,不成词继续循环读入下一个字符,再进行判断,如可成词则将CkCk+1Ck+2切分出来作为 候选地址,然后判断CkCk+1Ck+2是否同时也是A中另外某词的前缀,若是,再循环往下读字符并进行判断,否则将CkCk+1Ck+2作为成功切分地址,F设为true。
如CkCk+1Ck+2不是A的前缀,指针后退2位,以Ck+1作为起始字符转入步骤1)。
3)如Ck是O的前缀字符,读入Ck+1Ck+2Ck+
3,判断CkCk+1Ck+2Ck+3是否可成词,如是则成功切分;不成词则指针前移,判断CkCk+1Ck+2是否成词。
依此类推,若成词则进行成功切分,如始终不成词,则以Ck+1为开始字符转入步骤1)。
4)如Ck是E的前缀字符,则读入Ck+
1,判断CkCk+1是否是成词前缀,如是则判断是否成词,成词则成功切分,否则循环继续读入下一个字符,再进行判断。
如CkCk+1不是成词前缀,以Ck+1作为起始字符转入步骤1)。
5)读入Ck+
1,判断CkCk+1是否是O或E的成词前缀,若是则转入步骤3)或步骤4),若不是则判断CkCk+1是否是A的成词前缀,如是则转入步骤2),否则以Ck+1作为起始字符转入步骤1)。
其算法流程如图2所示。
图
2 自然语言交通信息跨阶分词算法流程Fig.2 FlowChartofCross2stepWordSegmentationAlgorithmforTrafficInformationinNaturalChinese 946 武汉大学学报·信息科学版 2009年8月 以实时交通信息“健翔桥由南向北行驶缓慢”为例,来介绍跨阶中文分词方法的运行过程:首先读入“健”字,写入currentWord,直接与地址库进行比较,判断currentWord是地址库中词的前缀。
继续读入“翔桥”,currentWord修改为“健翔桥”,能够单独成词,此外地址词库中也不存在其他以“健翔桥”为前缀的词,则成功切分出地址为“健翔桥”。
然后将currentWord置空,将地址切分标志F设为true;读入“由”字,写入currentWord,判断其为方向库的前缀,则读入“南向北”,修改cur2rentWord为“由南向北”,判断成词,则成功切分出方向信息。
再将currentWord置空,读入“行”字,写入currentWord,判断其为事件库中词的前缀,继续读入“驶”字,currentWord修改为“行驶”“,行驶”也是成词前缀,不能单独成词,继续读入“缓”和“慢”字符,currentWord置为“行驶缓慢”,可以单独成词,则成功切分出对应交通事件。
值得注意的是,交通信息中还可能存在数字型偏移量,偏移量数值难以预先在词库中逐一枚 举。
针对这一问题,本文采用数值型偏移量与字符串匹配分开处理策略,先以跨阶法处理输入的自然语言表达的交通信息,再对无法匹配的剩余字符串进一步处理,从而一次性提取出数字信息,以此达到偏移量切分目的。
3 效率实验 在上述算法研发的基础上,笔者采用Java技术实现了实时交通信息的跨阶中文分词算法。
实时交通信息来源于北京交通广播电台,空间信息采用基于路幅段模型构建的路网数据集,符合地理导航数据库国际标准GDF4.0中1层定义[12]。
采用Oracle10g数据库管理系统完成所有数据的管理工作。
选择北京市五环内城市路网作为示范区域,并随机收集了2007211209∶08∶00～18∶00这一时段内北京交通广播电台发布的实时交通信息,共计400条,如图3所示。
图
3 自然语言描述的实时交通信息Fig.3 Real2timeTrafficInformationRepresentedinNaturalChinese 实时交通信息是对交通状况的即时反映,而且具有很强的时效性。
针对实时出行和智能导航,实时交通信息的处理效率至关重要。
对400条交通信息分别用跨阶分词算法和改进的MM分词算法进行中文分词,跨阶分词算法和改进的MM分词算法理解成功率均为98%,容错性也完全相同,但改进的MM分词算法耗时为2951ms,而跨阶分词算法耗时仅为229ms,跨阶分词算法比改进MM中文分词的效率提高了10倍以上,体现出很好的效率优势。
本文所提出的自然语言表达交通信息的跨阶匹配分词算法,充分考虑了交通信息自然语言描述词库记录长度特点,通过设置对应的中文分词阶数,将传统中文分词的字符串指针一阶跨越方法改进为依词库性质变化的多阶跨越,对可能成 词的中文字符串进行成词处理。
在理解成功率和容错性相同的情况下,该算法极大地提高了自然语言表达交通信息的实时分词与理解效率,效率比经典的MM分词算法提高10倍以上。
后续研究中将进一步提高算法的容错性,使其可处理以长句或组合多句表达的交通信息,以尽可能提高自然语言表达的实时交通信息的自动化、智能化处理水平。
参 考 文 献 [1] 文庭孝,邱均平,侯经川.汉语自动分词研究展望[J].现代图书情报技术,2004
(7):629 [2] 张春霞,郝天永.汉语自动分词的研究现状与困难[J].系统仿真学报,2005,17
(1):1382143 [3] 邱均平,文庭孝,周黎明.汉语自动分词与内容分析 第34卷第8期 陆 锋等:一种中文自然语言表达交通信息的跨阶分词算法 947 法研究[J].情报学报,2005,24
(3):3092317[4] 黄昌宁,赵海.中文分词十年回顾[J].中文信息学 报,2007
(9):8219[5] FuG,KitC,WebsterJJ.ChineseWordSegmenta2 tionasMorpheme2basedLexicalChunking[J].In2formationSciences,2008,178:228222296[6] 乐小虬,杨崇俊,于文洋.基于空间语义角色的自然语言空间概念提取[J].武汉大学学报·信息科学版,2005,30(12):110021103[7] 胡斌,汤伟,刘晓明.基于自然语言理解的文本标图系统设计与实现[J].解放军理工大学学报(自然科学版),2005,6
(2):1322136[8] 马林兵,龚健雅.空间信息自然语言查询接口的研究与应用[J].武汉大学学报·信息科学版,2003, 28
(3):3012305[9] 龙毅,张翎,胡雷地,等.移动GIS中语音与自然语 言的应用模式探讨[J].测绘科学技术学报,2008,25
(1):8212[10]徐爱萍,边馥苓.GIS中文查询系统的词典设计与分词研究[J].武汉大学学报·信息科学版,2006,31
(4):3482351[11]吴静,蔡砥,王铮.地理信息系统中自然语言查询的分词处理与应用[J].地球信息科学[J],2005,7
(3):67271[12]蒋捷,韩刚,陈军.地理导航数据库[M].北京:科学出版社,2003 第一作者简介:陆锋,博士,研究员,博士生导师,研究方向包括空间数据库管理技术、交通GIS理论与技术、LBS与导航数据库技术、城市发展与城市GIS技术等。
E2mail:luf@lreis. ACross2stepWordSegmentationAlgorithmforUnderstandingTrafficInformationRepresentedinNaturalChineseLanguage LUFeng1 LIUHuanhuan1,
2 CHENChuanbin1,
3 (1 LREIS,InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,A11DatunRoad,Beijing100101,China)(
2 CollegeofResourcesandSafetyEngineering,ChinaUniversityofMiningandTechnology,D11XueyuanRoad,Beijing100083,China) (
3 SpatialInformationResearchCenter,FuzhouUniversity,523GongyeRoad,Fuzhou350002,China) Abstract:Anovelcross2stepwordsegmentationalgorithmisproposedtoprocessreal2timetrafficinformationrepresentedinnaturalChineseinthispaper,tomeettheurgentneedofreal2timetravelinginformationservice,fordynamictrafficinformation.Consideringthere2cordlengthdistributionofthewordlibrariesdepictingreal2timetrafficinformation,thisal2gorithmsetscorrespondingstepsofwordsegmentationforaddress,directionandeventli2braries,andimprovestheonesteprunningofthestringpointerinclassicalChinesewordsegmentationtoflexiblemultiplestepsrunning,soastoaggregatepossibleChinesewordsefficiently.Acasestudyshowsthattheproposedalgorithmruns10timesfasterthananim2provedMMalgorithm,whilstkeepingsimilaruracyandrobustness.Theauthorsarguedthatthepresentedalgorithmisgreatlyhelpfultotheautomaticandintelligentprocessingofthereal2timetrafficinformation,andfacilitatethedevelopmentoftravelinformationserv2ices.Keywords:trafficinformation;naturalChineseprocessing;wordsegmentation;cross2stepalgorithm Aboutthefirstauthor:LUFeng,researcher,Ph.D,Ph.Dsupervisor,Researchinterestsincludespatialdatabasetechnologies,GISfortransportationandLBSapplications,urbandevelopment,etc.E2mail:luf@lreis.
声明：
该资讯来自于互联网网友发布，如有侵犯您的权益请联系我们。