基于双字Hash机制的交通信息分词算法研究

2014-08-25,,

浙江工业大学学报 2014年6期

(浙江工业大学计算机科学与技术学院，浙江杭州 310023)

目前，实时交通信息的采集与发布技术为交通管理部门和公众提供了很大便利.浮动车、感应线圈等传感器方式已经成为我国各大城市实时交通信息采集与发布的主要技术手段.然而，采用浮动车、感应线圈和视频监控方式采集得到的交通信息，覆盖范围较小，对突发性点状交通信息也难以获取[1-2].同时，来源于社交网络等互联网文本形式的交通信息日益增多，但受制于自然语言理解[3-4]技术的限制，难以被现有计算机系统直接利用，不能满足日益普及的高动态导航与位置服务需求.因此，开展互联网文本蕴含交通信息的实时分词技术[5-7]研究迫在眉睫，为文本蕴含交通信息语义理解提供技术支持，进而为高动态导航与位置服务提供重要的数据支撑，服务于公众出行需求.

交通信息文本分词主要采用正向逐字增加[8]的字符串匹配方式，但仍然是逐字匹配方法，所以其处理的效率不高.文献[1]充分考虑了词库记录长度的特点，提出了一种自然语言表达交通信息的跨阶分词算法，该算法通过对中文分词阶数进行设置，根据词库性质变化将中文分词的字符串指针设置为多阶跨越，对可能成词的中文字符串进行成词处理.该算法在一定程度上提高了中文分词效率，但仍然存在以下几个方面问题：1)由于采用了一种多层模式的词典结构，且最大层数为词库中最大词的单字数，所以，其匹配查询效率并没有得到最大限度的提高；2)对于长句或组合句表达的交通信息没有进行有效的处理.针对以上问题，笔者重新设计了专业词库，建立了一种双字Hash与List相结合的三层词典数据结构，基于该字典结构，对最大匹配算法进行改进，提出了一种基于双字Hash与List相结合的分词算法.

1 基于双字Hash和List的三层组合词典结构

词典是中文分词的基础，分词词典机制设计的优劣直接影响到中文分词的速度和效率[9-10].如前所述，对交通信息的分词有较特殊需求，因此其分词词典机制也具有一定的特殊性.

1.1 词库的设计

针对交通信息的特点，构建详细的交通信息专用词库，包括事件库，地址库，方向库，附属定位词库.地址库包含某一特定区域中所有地理实体的名称.如道路名、桥梁名及POI点名等；方向库包含交通信息中各种表达的方向信息，如南北双向、北向东、由南向北和以东等；事件库包含交通信息中状态信息的各种描述，如车多、交通管制和拥堵等；附属定位词库包含不能独立进行定位、与地址库中的词汇结合使用以及指向最终定位地址的词汇，如东口、南侧路等.每个词库记录长度都具有一定的分布规律，以上海市为例，其中交通信息相关的地址库记录长度分布如表1所示.

表1 自然语言描述交通信息词库地址库记录长度分布

1.2 词典数据结构设计

丰富的专业词库保证了交通信息分词的正确性，而合理的词库数据结构保证了交通信息分词的速度与效率.基于双字哈希分词词典机制[11-12]结合基于整词二分词典机制[13]与基于逐字二分的词典机制[14]两者的优点，在匹配的时间效率和空间效率上，达到了较好的效果.从表1可以看出：自然语言描述的实时交通信息所发生的地址具有一定的分布规律.因此，笔者从词典数据结构设计出发，在双字Hash分词词典机制的基础之上，充分考虑交通信息词库记录长度的分布规律，设计了一种基于双字Hash和List相结合的三层词典数据结构.该结构先对首字使用Hash定位，再对次字使用Hash定位，经过两次Hash定位后剩余字分配到List列表.各个词库中的内容在程序运行时加载到内存，以提高运行速度.其词典的数据结构设计如下：采用三层结构，外层Hash表的键为词条记录中首字，其值不能重复，而对应的值为一个内层的Hash表，内层Hash表键为词条记录中第二个字，其值为一个List列表，该列表保存了词条记录剩下字串的值，并依次排列，若为空，则表示前两个字是一个完整的词.基于表1统计的词库分布规律，采用这种结构，减少了与List列表的匹配次数，从而提高分词的效率.词典的部分记录的数据结构如表2所示.

表2 词典的数据结构

2 改进的最大匹配算法

根据面向交通信息的自然语言理解过程中的分词算法的改进需求，对最大匹配算法进行了改进.结合上述所提出的基于双字Hash与List相结合的词典数据结构，笔者改进了最大匹配算法，由传统的逐字减一的方式改变为正向逐字加一的方式进行匹配；对长句或组合句采用分治的方法，将长句或组合句划分为多个短句，先对短句进行分词，最后归并其结果，从而实现长句或组合句的有效处理；同时，在切分过程中增加了对关键词汇的词库归属性判断，保存了根据各个词库切分出来的关键词汇的个数与顺序，使其能够满足基于模板规则自然语言语义理解的需求.

2.1 算法描述

改进的最大匹配算法的流程如图1所示.具体算法描述如下.

目标：对一个句子C1C2C3…Cn，进行分词处理.

1) 预处理阶段.依次判断C1C2C3…Cn是否为非中文汉字，如果是非中文汉字，按这些非中文字符把语句切分成多个短句，分别对这些短句进行分词处理，转到步骤2)；如果全是中文汉字，取句子的第一个字C1作为当前字串，转到步骤3).

2) 取第一个短句进行分词处，取句子的第一个字C1作为当前字串.

3) 分别在地址库，方向库，事件库等的首字Hash表中查找是否存在；若都不存在，转到步骤4)；若C1在地址库、方向库、事件库等某一个库中的首字Hash表中存在，则转到步骤5).

4) 则切分C1，标记C1为非词汇，从C2开始下一次分词.

5) 判断次字Hash表是否为空.若为空，转到步骤6)；若不为空，转到步骤7).

6) 则C1成词，保存C1，记录C1所隶属词库及顺序标志，取下一个字作为当前字串，转到步骤3).

7) 取下一个字C2，在次字Hash表中查找是否存在.若不存在，转到步骤4)；若存在，转到步骤8).

8) 取C1C2为词首的剩下汉字的列表.若列表为空，C1C2成词，切分C1C2，记录C1C2所隶属词库及顺序标志，一次分词结束，取下一个字作为当前字串，转到步骤3).若列表不为空，则二分查找C3…Ci(i≥3)是否存在列表中.若存在列表中，记录最后成词i值，在i处切分，一次分词结束，保存C1…Ci，切分C1…Ci，记录C1…Ci所隶属词库及顺序标志，一次分词结束，取下一个字作为当前字串，转到步骤3)；若不存在列表中，则直接切分C1…Ci，一次分词结束，取下一个字作为当前字串，转到步骤3).

9) 不断循环取下一个短句，按步骤2)进行分词，直到句子结束的最后一个字Cn.

然而，交通信息中可能会存在一些数字型偏移量.偏移量是动态估算的，其数值是不断变化的，在词库中无法逐一列举出来，这也给基于字符串匹配的分词带来了新的问题.针对这一问题，笔者算法采用数字型偏移量与字符串表示的中文进行分开处理.先按照图1的步骤对输入的交通信息进行分词，然后再对输入的交通信息中无法匹配的剩余字符串进一步的处理，从中一次性提取中数字型信息，作为数字偏移量，以此来解决数字型偏移量问题.

按照上述步骤，切分出来的关键词汇包含了该词汇的隶属词库，然后以关键词汇、个数和顺序为条件，进行基于模板规则的自然语言理解，成功匹配的词汇认为已达到自然语言理解目的，否则予以排除，尽而完成面向自然语言描述的交通信息的自然语言理解.

2.2 示例描述

目标：对“浙江中路以东300 m，发生一起交通事故”进行分词为例.

1) 逐次判断是否包含非中文字符和数字，以包含的非中文字符为界将字串分为两个短字串，“浙江中路以东300 m南京路”和“发生一起交通事故”，分别对这两部分短句进行分词.

2) 取字串“浙”，作为关键字在地址库，方向库，事件库等的首字Hash表进行匹配，在地址库的首字Hash表中匹配成功得到以“浙”为键的Hash表.

3) 取字串“江”，作为关键字在2)中得到的Hash表中进行匹配，匹配成功，得到以“浙江”为前缀，由剩下字串组成的列表.

4) 取字串“中”，作为关键字在3)中得到的列表中进行二分查找，匹配失败.

5) 取字串“中路”，作为关键字在3)中得到的列表中进行二分查找，匹配成功，记录“浙江中路”.

6) 取字串“中路以”，作为关键字在3)中得到的列表中进行二分查找，直到短句结束，匹配失败.

7) 保存最后匹配成功的字串“浙江中路”，切分，记录所隶属词库及顺序，一次分词结束.

8) 取成词的下一字“以”，按步骤2)操作在地址库，方向库，事件库等的首字Hash表进行匹配进行Hash匹配，依次顺序进行，直到短句结束.

9) 取下一个短句，同理切分出词“事故”，直到整个句子结束.

10) 分词处理完成后，在无法匹配的字串中一次性提取出数字信息，将此作为数字型偏移量.

11) 最后切分出的结果：“浙江中路”是第一个地址词，“以东”是方向词，“交通事故”是事件词，“300米”是数字型偏移量.

3 实验结果

基于上述算法设计，使用Java平台来实现交通信息分词测试.实验数据来源于上海出行网发布的实时交通信息，共计400条，如图2所示.测试环境操作系统：win7系统，处理器：IntelI5，内存：4 G.采用Oracle 10 g数据库管理系统完成所有数据的管理工作.

图2 自然语言描述的实时交通信息

实时交通信息是对交通状况的即时反映，具有很强的时效性，因此，实时交通信息的分词对指导公众实时出行和智能导航具有重要意义.分别采用跨阶分词算法和笔者算法对400条实时交通信息实验数据进行中文分词，排除无关的通用词条记录，笔者分词算法将专业交通信息词库加载到内存，以提高运行效率.由表3可以看出：笔者算法和跨阶分词算法理解成功率均为98%，容错性也完全相同.笔者算法在分词匹配时，由于采用的两层的Hash结构，每次都将查询固定在一定的范围内，所以其分词的效率较高.同时，跨阶分词算法对长句或组合句没有进行有效处理.实验结果表明：笔者的算法对于长句或组合句的分词成功率为96%.实际应用表明：笔者算法执行简单，不需要词法、句法及语义等知识的支持，数据结构也较为简单，较符合实时交通信息分词应用需求.

表3 分词性能分析

4 结论

自然语言表达的交通信息的中文分词，具有一定的特殊性.通过对基于词典的中文分词算法进行研究，并充分考虑专用词库中词条记录的长度分布特点，提出了一种基于双字Hash与List结合的词典机制的改进的最大匹配算法，在切分过程中增加了对关键词汇的词库归属性判断，保存了根据各个词库切分出来的关键词汇的个数与顺序，使其能够有效地为面向交通信息的自然语义理解提供技术支持，提高了自然语言表达的交通信息分词效率.并且，对于长句或组合多句表达的交通信息，也能够很好地进行处理，经测试取得了较好的效果.由于未登录词的识别难度较大，容易造成错分、误分的情况，因此，如何进一步提高未登录词的辨识度也是后续自然语言描述的交通信息分词研究的关键.另外，对算法的容错性需要进一步提高，使其能在更加复杂的组合句描述的交通信息处理上取得更好的效果.

参考文献：

[1] 陆锋，刘焕焕，陈传彬．一种中文自然语言表达交通信息的跨阶分词算法[J]．武汉大学学报：信息科学版，2009，34(8)：943-947．

[2] 陈传彬，陆锋，励惠国，等．自然语言表达实时路况信息的路网匹配融合技术[J]．中国图象图形学报，2009，14(8)：1669-1676．

[3] 王秋．浅析自然语言理解及其应用[D]．西安：陕西师范大学，2008．

[4] 陈周娟，续海峰，钮王杰．基于静态知识库的领域内自然语言理解的语义处理研究[J]．机床与液压，2007，35(7)：37-39．

[5] 张黎，徐蔚然．中文分词研究[J]．软件，2012，33(12)：103-108．

[6] 黄昌宁，赵海．中文分词十年回顾[J]．中文信息学报，2007，21(3)：8-19．

[7] 龙树全，赵正文，唐华．中文分词算法概述[J]．电脑知识与技术，2009，5(10)：2605-2607．

[8] 邵星星．基于Lucene的中文分词技术研究[D]．西安：西安电子科技大学，2012．

[9] 张林曼，吴升．地理编码系统中地名地址分词算法研究[J]．测绘科学，2010，35(2)：46-48．

[10] 郭瞳康．基于词典的中文分词技术研究[D]．哈尔滨：哈尔滨理工大学，2010．

[11] 杨安生．二次Hash+二分最大匹配快速分词算法[J]．情报探索，2009(8)：90-92．