顾及字符特征的中文地名词典查询方法|字符串|汉字|索引|词典

摘要：地名词典查询是地名校正、地名匹配等地名服务应用的重要基础，但是地名数量的快速增长使得词典查询性能面临严峻挑战。针对大规模数据环境中传统词典查询方法准确率不高且效率较低等问题，提出了一种顾及字符特征的中文地名词典查询方法(CGQM)。首先，查询具有相同字符特征的地名形成候选地名集合，同时构建单字索引提升查询效率；其次，依据字符数量特征比较查询地名与候选地名的差异，进一步过滤候选地名集合；最后，基于字符位置特征优化查询结果排序策略，使得结果排序更为合理。实验以全国地名词典为例，构建5组测试集进行CGQM方法与Lucene检索方法的对比分析。研究结果表明，CGQM方法对于增强地名词典查询功能、提升查询效率具有实际意义。

关键词：中文地名；地名词典查询；地名词典单字索引；地名相似度；地名字符特征

引言

近年来，随着移动互联网的快速发展和基于位置的服务技术在各行业的广泛应用，社会公众对地名信息的应用需求日显增长。在国家“十二五”、“十三五”和相关行业发展规划的推动下，我国地名信息化建设在数据规模和地名服务等方面均取得了长足发展。地名词典查询是地名服务中的一个重要基础环节，为地名文本校正、地名语义消歧、位置信息匹配等提供地名词语知识的支持。由于地名数据积累规模的日益增大，实现地名词典的快速、准确查询成为地名服务面临的重要技术挑战。

早期的词典查词王要是基于传统Hash方法进行，将词典结构分为词典正文、词索引表、首字散列表等三级。通过首字散列表的Hash定位和词索引表获取查询词的位置范围，进而依据二分法在词典正文中定位。由于在查询过程中采用全词匹配，效率较为低下。基于Trie树的词典查询机制由首字散列表和Trie索引树结点两部分组成，词典查询时按照树链顺序逐字匹配，减少无谓的字符串比较。但是，Trie树结构对于内存消耗巨大，同时索引构造与维护也较为复杂。双字Hash机制词典查询方法的提出，开始将字符特征融合在查询过程中。对于2个字词以下的短词用Trie索引树机制实现，3字及以上的长词部分用线性表组织。能够避免部分的深度搜索，一定程度上提高了查询性能。由于词典文件可以作为一种全文数据，全文检索方法也被越来越多应用到词典查询中。全文检索具有灵活高效的特点，但是基于关键字/词的检索机制可能会返回大量无关结果。事实上，中文地名具有字符长度较短、数据量巨大、描述形式多样等特点。现有的地名词典查询大多直接采用或借鉴通用检索方法，忽略了地名本身的字符特征和描述规律。因此，如何在中文地名词典查询中有效利用其字符结构特性，成为实质性提升查询性能的突破口。

基本思路

同一地点的地名表述存在多种方式，而且查询地名输入错误的情况也比较普遍。因此，地名词典查询不仅要求对于输入的查询请求具有较好的容错性，而且能够高效返回完全准确或者最为接近的查询结果。本文利用地名中的相同字符、字符数量、字符位置等语言特征，按照“候选地名查询一字符数量过滤一相似程度排序”的技术路线(图1)，设计一种高效的中文地名词典查询方法(简称CGQM)。首先，从地名词典中查询拥有相同汉字的地名形成候选集合，同时构建地名单字索引以提升查询效率；其次，将候选地名集合中与查询地名字符数量差异过大的地名进行筛除，加强查询结果精确程度的同时保证后期排序过程效率；最后，对地名过滤结果依据字符位置相似度高低排序，将排序靠前的地名作为查询结果以进一步完善查询的准确性。

基于相同字符的候选地名查询

3.1单字索引构建

传统的词典索引结构多数以词组为对象提取索引词，由于受到词组描述粒度及数量的影响，对于查询条件的容错性存在一定局限。汉字作为汉语构成的最小单元，其对于词典中词项的关联性较词组更为丰富。当查询地名中存在部分信息失真时，基于单个汉字的索引形式能够依据剩余的部分准确字符与目标地名知识建立关联关系。在大规模数据环境下，索引词的增多极易产生数据冗余，也容易导致检索效率下降。中文地名中常用汉字规模较为固定，词典数据规模的扩大不会导致索引项的线性增长。在索引查找过程中，能够有效避免无关词项的深度搜索。因此，以地名中包含的单字作为索引词建立中文地名索引，对于地名查询具有更强的适应性。

中文地名单字索引由词典文件和索引文件两部分组成。词典文件用于存储地名词典中全部的地名数据，按照无换行无间隔的方式依次排列，形成一条连续的字符串；索引文件是存储索引记录的物理文件，用于存储索引记录和词典文件中地名词项之间的对应关系。一条索引记录中包含3部分信息：地名个数，字符编码以及词典位置。假设词典文件中共有n个不重复汉字，表示汉字的编码，为词典文件中包含汉字的地名个数，每个地名的起始位置与结束位置分别表示为，那么地名在词典文件中的存储位置序列表示为。以地名“中岗子”为例，将“中岗子”存储到词典文件中，记录下（“中”在字符串中位置1001)与（“子”在字符串中位置1003)。之后在索引文件中生成“中”、“岗”、“子”3条索引记录，其中“中”字索引为[11079][OxE4B8AD][1001，1003，1015，1017，…，83475，83478]，记录字符编码(OxE4B8AD)、词典文件中所有包含“中”字地名的个数(11079)及其存储位置，既有“中岗子”所在位置(1001，1003)，还有“中夹滩”、“姜尾林中”等其它含“中”地名所在位置，如(1015，1017)(83475，83478)等(图2)。

对地名单字索引解析算法的时间复杂度进行分析，设索引文件中共有n个索引项，查询地名中共有m个不同的单字，则与之相关的m个索引项中共有r个位置映射记录。在依据索引进行地名查询时，对以上n个索引项进行一次扫描即可获得全部的查询结果。其时间复杂度，即T=O(max(f(n)，g(r)))。f(n)与g(r)都为单循环遍历查找，时间复杂度都为O(N)。因此单字索引解析计算的时间复杂度为O(N)。

3.2候选地名查询

候选地名查询的目的是从地名词典中查询到与查询地名包含相同汉字的地名。首先对输入查询地名进行中文分词，采用一元分词形式将所有中文字符按照单字形式输出，如查询“中岗子”拆分为“中/岗/子”。其次，以分词结果分别作为查询关键字，在索引文件中查询其对应的索引记录。之后对索引记录中的信息进行逆向解析，根据索引中位置信息查询词典文件中对应的地名数据，并将全部查询结果返回形成候选结果集合(图3)。

基于字符数量的地名过滤

候选结果集合规模的降低有利于减小后期相以度计算的运行时间，进而提升查询方法的整体效率。需要选取特征对候选结果进行筛选，尽可能多的过滤掉与查询目标不相符的候选项。常见的地名不准确描述方式包括替换字符、缺失字符、增加字符及交换字符等形式(表1)。虽然错误方式形式各异，但是查询地名与目标地名在字符长度上具有较高相似性。因此，可以根据查询地名的字符数量，对候选结果集合中的地名项进行过滤。首先，记录查询地名P的字符数量为n，候选结果集合W中地名的字符数量为m，设定阈值范围为k，则当满足时，将保存到过滤结果集合C中。

基于字符位置的地名相似度排序

字符匹配法是较为典型的中文词汇(或字符串)相似度判别方法之一。假设有A和B两个字符串，N表示A与B之间的相同字符数(匹配度)，表示N与A的总字符数之比，表示N与B的总字符数之比。N、C1、C2共同构成A与B的匹配度，以此判断A和B之间的文本相似度。字符匹配法只考虑词汇之间的字符相同程度，却忽视了匹配字符位于字符串中的位置信息。中文里绝大多数汉字都是表意单元，词语搭配比较灵活多样。然而，地名作为一种专有名词，其中各字符间顺序通常不可调换。因此，对于中文地名间相似度的判定，需要在相似度评价时增加对字符串间词序位置关系(匹配序)的计算。基于此，本文提出一种基于字符位置的地名相似度计算方法(式(1))。

式中：P与W分别表示2个地名字符串；m与n分别表示P与W的字符总数；c表示P与W的字符匹配度；与分别表示匹配字符i在P与W中的匹配序；与分别表示匹配度与匹配序评价结果的权重，并且与的和为1。通常情况下与的取值依据黄金分割定律，分别取0.6与0.4。匹配序按照从左到右的顺序，从起始位置1开始以递增的方式计算。以P=“师范大学”，W=“南京师范大学”为例，P与W的匹配字符为“师”、“范”、“大”、“学”。其在P中的匹配序为1(师)、2(范)、3(大)、4(学)，在W中的匹配序位3(师)、4(范)、5(大)、6(学)。按照本文的相似度计算方法，P与W的相似度定义为：

实验评估分析

以480万条全国地名数据构建实验词典，从中抽取1700条地名作为查询地名。为模拟实际查询情况，对查询地名人为增加错误。错误类型涵盖了表1归纳的各类描述方式，并依据与原有标准地名对比的准确度将其划分为5个等级(表2)。准确度定义如式(3)所示。

式中：c表示查询地名p中与目标地名w相比准确的字符数量；n表示查询地名p字符数量。开源全文搜索引擎Lucene在文本分类、信息检索等方面有大量研究与应用。词典作为非结构化文本文件，能够应用Lucene索引机制。因此，本文选取Lucene检索方法与CGQM进行对比实验。查询性能评价指标包括运行效率、准确率(P)、召回率(R)，F值。其中，运行效率是指单条地名查询所耗费的时间。P，R与F度量值的具体计算公式如式(4)-(6)所示。式中，是指目标地名i和查询结果j之间相同的数量，是指目标地名i的数量，是指模型查询结果j的数量，F(i，j)是指i和j之间的F度量值。本次实验中设置的地名过滤阈值k，为查询地名与目标地名中较长地名字符数量的30%。同时以相似度数值大于60%的候选地名作为查询结果，结果依据相似度数值大小进行排序。实验测试机器配置为Intel Corei7-7700HQ主频2.8GHz处理器，内存16GB，Windows10操作系统，开发语言为Java。

实验结果表明，CGQM的性能明显优于Lucene方法。CGQM在大规模数据环境下可以保持较高的运行效率，同时能够在查询地名不准确的情况下较为准确的查询到目标地名(表3)。Lucene以词元为单位，通过对查询地名分词再与索引进行精确匹配。①Lucene在进行查询时，借助分词器与分词词典对查询地名进行拆分更为复杂；②也会因分词词典中缺少必要词项，使用分词时遇到歧义而产生了错误切分影响查询准确性。CGQM对查询地名分割不依赖任何语义知识，同时操作简单。特别是，当查询地名准确度在80%以上时，CGQM能够较为准确查询到目标地名。受到测试集准确度的影响，各测试集间准确率存在差异。随着查询地名准确度的降低查询准确率也不断降低，但更多是由于查询条件中准确信息缺失导致的语义改变。

对CGQM方法的各个中间环节进行具体分析，部分实验数据查询过程如表4所示。查询过程体现出，CGQM方法利用的地名中相同字符、字符数量、字符位置等语言特征，能够较为有效的逐级排除无关候选项。然而实验中仍有部分地名查询不准确，分析其原因主要在于汉语中具有相同词形结构的地名数量众多。以查询地名“山村”为例，查询结果排序前十位的结果都不是目标地名“雨山村”，但是都为统一的“X山村”词形结构。这不利于相似度评价结果的区分，进而影响了最终查询结果排序的准确性。

结论

本文以挖掘中文地名的字符特征为突破口，提出了一种较为有效的中文地名词典查询方法。该方法基于相同字符特征查找候选地名，对查询地名具有良好的容错性，并提出地名词典单字索引结构提升了查询效率。利用字符数量进行候选地名过滤，结合字符位置特征进行相似度排序，使得查询结果更加准确与人性化。在今后研究中地名查询还应综合考虑字形、语义等其他多种因素，同时借鉴检索系统中分布式、多线程等技术手段。以此促进地名查询准确率与效率的进一步提升，推动地名信息公共服务的拓展。

文章作者：叶鹏；张雪英；杜咪

文章来源：《地球信息科学学报》2018,(第7期)

选稿：耿曈

编辑：罗舒平

校对：吴雪菲

审定：李春燕

责任编辑：罗舒平

微信扫码加入

中国地名研究交流群

QQ扫码加入

江西地名研究交流群

欢迎来稿！欢迎交流！