考虑重合字符位次差异的地名相似性度量方法

江西地名研究

关注我们，获取更多地名资讯

摘要：当前中文地名匹配常见的相似性度量或是只考虑重合字符的数量未考虑位次性，或是体现位次性但未考虑重合字符。通过考虑两个中文地名字符串的重合字符对应关系及其位次差距，构建了一种新的距离度量和相似性度量，能够结合重合字符和位次性两个因素计算两个地名的偏距和偏距相似度。针对重合字符复现的情形确定偏距最小原则，设计全体顺次匹配方案；针对字符片段偏移的情形调整距离度量，从而更符合两个地名相似性的直观认知。该距离度量满足正定性和对称性，但不满足三角不等式。与Jaccard系数和编辑距离相似度的测试对比结果表明，所提偏距算法对相似度刻画更为细致，能够检测到重合字符位次差异但更重视未重合字符的差异；在地名匹配实验中匹配正确率和运行时间分别为63.64%和2 940.56s，两项指标均优于Jaccard系数和编辑距离相似度。

关键词：相似性度量；近似字符串匹配；自然语言处理；地名匹配；中文地名

在中国测绘地理信息技术得到不断发展和广泛应用的背景下，标准地名数据库和多种尺度下的地图要素数据库的数据量大幅上升，显现出巨大的潜在应用价值。但是，由于“一地多名”的现象或数据生产时的疏忽，会出现同一地理实体在不同尺度地图要素数据库中的名称互不相同，出现错别字，或与标准地名不符等问题，给地图的多尺度展示和地理信息数据实体化带来诸多不便。因而有必要研究地名相似性度量方法以实现地名匹配，辅助同一地理实体在不同尺度下名称的统一和地理实体库的构建，促进地理信息的精细化管理和应用。

当前有关中文地名相似匹配研究中，采用的文本相似性度量［多为Jaccard相似系数（又称Jaccard系数）、编辑距离和词频-逆文档频率（term frequency-inverse document frequency，TF-IDF）等基于词频向量算法，但是以上相似度算法在实践中均存在各自的缺陷。如果将两地名都包含的字符称为重合字符，那么Jaccard系数定义为重合字符数和总字符数之比。Jaccard系数能够在一定程度上表达地名相似度，但是由于该指标仅考虑了重合字符数而没有考虑位次特征，因此它对相似性的描述是较为粗略的。编辑距离一般指莱文斯坦距离，定义为一个地名字符串变换为另一个地名字符串要经过的最少“操作”次数，其中“操作”包括插入、删除或替换单个字符。综合考量两个地名字符串编辑距离的实际数值和理论最大值可以进一步得到编辑距离相似度。编辑距离算法能够捕捉到两个地名字符串在字符位次排列特征上的相似性，在实际生产中应用也较为广泛。然而该指标容易忽视重合字符特征，在字符片段顺序颠倒等情况中可能对相似性作出不合理的描述。另外，也有学者使用TF-IDF等基于词频向量算法计算两地名相似度。但是究其原理，TF-IDF算法评估的是某个词语对于语料库中一份文档的“重要程度”，这与“文本相似度”的概念并不能等同。在用于地名地址匹配时，TF-IDF算法会将地名视为诸多关键词的简单集合从而忽略语序，且词频越高，评分越高的逻辑也并不适用于评估地名相似性。

综上，现有的地名相似性度量或是强调重合字符数量，或是强调字符位次特征，却不能将两者很好地结合起来。通过观察可发现，两个地名在字符层面的相似程度关键在于重合字符的匹配情况。因此，本文意在构建能够同时体现重合字符数量及位次特征的新相似性度量指标。由于Jaccard系数和编辑距离相似度同为考虑字符层面的文本相似性度量，在识别字符重合数量和字符位次特征上具有各自的优势且实际中运用广泛，故本文将重点与它们进行对比。

1

构建地名相似性度量

1.1重合字符偏距

考虑两个地名字符串A和B，找到两者所有的重合字符，按在地名A中从左到右的顺序依次记为1、2、3、···、n。对于任一重合字符，假定它在A和B中均刚好只出现一次。记在A中的位次是（即i是地名字符串A从左往右数第个字符）；在B中的位次是bi，如图1所示，显然每对重合字符恰好构成匹配（一一对应），并且两者的位次越接近（即和差值越小），意味着两个地名字符串A和B差异程度越小、相似度越高。

因此，定义偏距=─用于表征构成匹配的重合字符的位次差异程度。设所有重合字符的偏距构成偏距向量O，那么该向量记录了地名字符串A和B重合字符集的位次差异信息；记的绝对值之和为匹配总偏距D（O），该值代表了重合字符集的总体位次差异程度。

1.2未重合字符偏距

考虑未重合字符时，可以将偏距视为两个地名文本相似性的距离描述。重合字符的偏距绝对值越大，代表两个地名的文本相似性越小。未重合字符相当于无关字符，对两个地名文本相似性的影响应当比重合字符更大，即未重合字符的偏距绝对值应当更大。设想如下情形：任意找到一对重合字符（，），其中地名A的变为一个A和B中都不曾出现的全新字符j，那么此时i和j两个字符都转变成未重合字符。定义每个未重合字符带来的偏距为。根据直观认知，转变后的两个未重合字符（j，）带来的偏距2理应大于初始两个重合字符（，）偏距的绝对值。即希望找到一个合适的值，能够保证对所有的i满足：

假设A和B之间共有W个未重合字符，那么所有未重合字符带来的偏距之和记为未匹配总偏距，表达式为：

需要指出的是，值的定义是灵活的，并非一成不变。在实际应用场景下可以调整的值，使得未重合字符对相似性的影响变大或者变小。

1.3总偏距与偏距相似度

定义总偏距D（A，B）为匹配总偏距D（O）与未匹配总偏距之和。那么总偏距D（A，B）便是两个地名字符串A和B差异程度的距离度量。当A和B没有重合字符时，W=l（A）+l（B），此时给两地名字符串的差异程度最大，总偏距也正好取得最大值：

由定义可知，当且仅当A和B完全相同时，D（A，B）=0，S（A，B）=1；当且仅当A和B不存在重合字符时，D（A，B）=，S（A，B）=0。

2

地名相似性识别的复杂情形

2.1重合字符复现

通常情况下，重合字符在A和B中均刚好只出现一次；然而对于某些相对复杂的地名，重合字符是有可能在A和B中多次出现的。此时重合字符匹配不再是两个字符的简单对应，而是在多个字符中确定合适的匹配关系。任取一个重合字符，假设它在A中出现x次，在B中出现y次，将A、B间的重合字符尽可能地进行一一匹配，剩余|x-y|个无法匹配上的i则视为未重合字符处理。

直观来看，A（或B）中的每一个重合字符i只需要就近和B（或A）中的匹配起来即可，不然匹配关系与直观认知不符（见图2），也会带来一些多余且无谓的偏距。例如A和B为同一个地名“尖尖山”时，如果刻意地不就近匹配重合字符“尖”而是选择交叉匹配，那么D（A，B）=1+1= 2，与直观认知中A和B偏距应当为0是不符的。因此，将重合字符的匹配原则确定为“就近”，严格来讲即偏距最小原则。

根据偏距最小原则，容易得到以下结论：如果A中位次为m、n（m

证明过程如下：记顺次匹配的偏距为=|m-r|+|n-s|，逆次匹配的偏距为=|m-s|+|n-r|。按表1分类讨论计算-即可。并且-有可能取到0，意味着有时顺次匹配和逆次匹配的偏距相等。

当x=y（重合字符在A和B中出现次数相等）时，根据顺次匹配小于或等于逆次匹配的结论，对A、B间的所有重合字符进行全体顺次匹配（如图4所示，A的第1个匹配B的第1个，A的第2个匹配B的第2个，依次下去，重合字符的匹配连线不存在任何交叉），就能满足偏距最小原则。

当然，偏距取得最小值的匹配方案可能不止一种，本文只是选用了形式上最简洁的。例如，图5“杉杉”和“北京杉市杉”的两种匹配方案中，匹配总偏距分别为2+3=5、1+4=5，均满足偏距最小原则，而默认选用左侧全体顺次匹配的形式。

当x≠y（重合字符在A和B中出现次数不等）时，如果x>y，先从A的x个重合字符中取出y个，一共有种方法，再将取出的y个与B进行全体顺次匹配，便得到了个偏距，最后选择其中偏距最小的一种匹配方案。如果x

2.2字符片段偏移

以上偏距计算都是基于字符而非词或词组。这样做的优点在于不会因为分词问题而捕捉不到全称与简称之间的相似性；缺点在于存在词或词组偏移时会产生不合理的偏距值。例如，A=“北京南湖路”，B=“南湖路北京”，C=“湖北南京路”，其中B相较于A虽然“北京”和“南湖路”两词的顺序颠倒，但所指代的地理实体没有发生改变，C相较于A字符顺序完全改变，导致所指代的地理实体也发生改变，因此D（A，C）应当大于D（A，B）。但是计算结果为D（A，C）=1+2+0+ 3+0=6 D（A，B）。因此，需要进一步识别出词或词组的偏移，即连续字符片段的整体偏移后，再去计算偏距。识别过程如图6所示，此时偏距的概念也得到推广——从仅限于字符之间的偏距，变为字符片段（包含单个字符）之间的偏距。

2.3相关定义更新

由于§2.1和§2.2对复杂情形的处理，前文关于O、D（O）、等定义的描述不再完全适用。相关定义更新如下：

经过重合字符匹配和字符片段识别后，所有匹配成功的重合字符片段（包含单个重合字符）的首字符偏距构成偏距向量O。所有的绝对值之和构成匹配总偏距D（O）。每个未匹配的字符（包括匹配失败的重合字符和未重合字符）带来的偏距均为，它们的和构成未匹配总偏距。此时总偏距D（A，B）的定义保持不变，仍为D（O）与两者之和。相似度S（A，B）的定义保持不变。

其中，总偏距D（A，B）作为新提出的距离度量有以下特点：

1）满足正定性。显然D（A，B）≥0恒成立，满足正定性。

2）满足对称性。只要D（A，B）和D（B，A）的重合字符匹配都遵循偏距最小原则，那么计算结果必然是同一个最小值，即满足对称性D（A，B）=D（B，A）。

3）不满足三角不等式。例如A=“北京大学”，B=“南湖”，C=“南湖西园”，D（A，B）==（4+2）×（4+2）/2=18，D（B，C）==2×（4+2）/2=6，D（A，C）==（4+4）×（4+4）/2=32，此时D（A，C）>D（A，B）+D（B，C）不满足三角不等式。

事实上，总偏距更像是两个地名间相似性推导过程中的一个分值，且满分值本身也会随地名而变化，所以不宜直接用它表达地名相似性而应当使用偏距相似度。当考虑3个及以上地名间的相似性关系时，可计算它们两两之间的偏距相似度。

3

相似度对比实验

为观察本文偏距算法的相似度表达能力与特性，先设计8对不同差异程度的地名和9对相似地名计算偏距相似度，并与经典的Jaccard系数和编辑距离相似度进行对比。如表2和表3所示。其中打钩(√)表示两地名指代的为同一个地理实体。

在辨别不同差异程度的地名时，本文的偏距算法对相似度的刻画更为细致合理，符合设计的初衷。遇到两个地名完全相同、仅位次不同、部分字符相同和完全不同等情况时，偏距相似度从1到0逐渐下降，且下降过程较为连续、平滑。与之相较，Jaccard系数整体呈下降趋势但在仅位次不同时恒为1，编辑距离相似度呈曲折变化，两者均不如偏距相似度数值变化均匀。

在辨别相似地名时，可进一步观察到偏距算法的特性：对字符差异重视程度较大，重合字符的比例减小时相似度显著降低；对单纯的位次差异重视程度较小，但也能体现在相似度数值的细微差距中。与之相较，Jaccard系数无法识别到位次差异；编辑距离相似度对位次差异和字符差异的重视程度没有显著区别。偏距算法的该特性决定了其会更适用于地名匹配等应用场景。例如位次差异的4个地名中，仅有偏距算法能通过最大相似度分辨出“北京南湖路”与“南湖路北京”构成匹配；字符差异的5个地名中，偏距算法也能通过寻找相似度最大的两项判别出“北京南湖路”与“南湖路”“北京市南湖路”构成匹配。

为测试本文偏距算法在地名匹配应用场景下的实际效果，通过数据预处理和随机筛选，获得了5万条中国北京市范围内的高德地图兴趣点（point of interest，POI）数据（见图7，图7的底图来源是天地图，行政界线未修改），其中每条数据均满足：（1）恰含一个地名和一个别名；（2）地名和别名均已去除特殊符号；（3）若地名或别名有英文字母则统一为小写；（4）别名和地名不等同。

测试方案为：对于任意一个别名，计算它和每一个地名的相似度，寻找该别名的最大相似度地名；若最大相似度地名仅有一个且和别名恰好对应同一条POI数据，则为匹配正确；统计5万个别名中匹配正确的数量，并记录算法运行时间。分别采用Jaccard系数、编辑距离相似度和偏距相似度进行上述测试，匹配结果如表4所示。部分别名的最大相似度地名如表5所示，如果该别名的最大相似度地名存在多个，则取其中一个作为示例，打钩(√)表示该别名匹配正确。

偏距相似度的匹配正确率为63.64%，相较于Jaccard系数提升2.34%，相较于编辑距离相似度提升13.48%。参考表5实例可发现，偏距相似度无论遇到错别字（例如“万恒万泽中心”-“方恒万泽中心”）、字符片段颠倒（例如“北环西路大发路路口”-“大发路北环西路路口”）还是各类全称或简称（例如“央央生物”-“北京央央生物技术有限公司”），都能凭借对重合字符片段的敏感性而更容易匹配正确，而Jaccard系数没有考虑字符顺次结构，导致“龙跃苑4区12号楼”错误匹配到“龙跃苑三区14号楼”，编辑距离相似度对片段颠倒和简称辨识能力较差，因此“北环西路大发路路口”和“建壮咨询”等别名均没有匹配正确。

虽然偏距相似度的构建初衷是提升地名相似度评价的合理性，但在实验过程中它的运行时间指标同样展现出明显优势。其耗时2 940.56s，仅为Jaccard系数的73.41%，编辑距离相似度的42.39%。时间效率优势的原因主要在于偏距相似度算法的第一步便是定位所有重合字符，作为后续处理的基础。一般只有当别名遇到对应地名或少数相似地名时才会存在较多重合字符，大多数无重合字符或重合字符很少的地名都将被快速处理，所以运行时间更短。此外，Jaccard系数算法虽然也是基于寻找重合字符，但它运用了集合去重复和取交集等复杂操作，所以运行时间相对较长。

综上，偏距相似度是地名匹配测试中总体表现最佳的，在匹配正确率和运行时间两项指标上都更为优秀。但是也需承认在5万条数据量的情形下，偏距相似度算法的匹配正确率相比于其他两种算法提升幅度有限。这一方面是因为数据量较大时，同类型的相似地名的频繁出现容易导致匹配错误。例如，统计的5万个别名中有2 402个包含“停车场”，5万个地名中亦有2 449个包含“停车场”；随着同类型的相似地名的频繁出现，它们在匹配过程中产生混淆的概率也会增加。另一方面则是因为偏距相似度本质仍为文本相似性度量，只能关注字符层面的相似性而难以顾及复杂的语义。当附加过多通名字符或地址信息字符时，偏距相似度会显著降低从而难以正确匹配，例如“达懿集团”未能正确匹配到“山西达懿电子集团有限公司”；当出现“1”和“一”等语义一致的字符时，偏距相似度同样不能理解从而导致失败，例如“大溪地1区16号楼”没有正确匹配到“大溪地一区16号楼”。

4

结语

本文通过计算重合字符偏距定义未重合字符偏距，以及处理重合字符复现和字符片段偏移等复杂情形，最终构建出新的中文地名相似性度量。本文提出的偏距相似度具有数值刻画细致的优点和重视字符差异且能识别位次差异的特性，在匹配正确率和运行时间上的表现均优于Jaccard系数和编辑距离相似度。未来可在处理复杂情形的算法设计、对其他语种适用性和考虑地名语义结构上进一步优化。需要指出的是，考虑地名语义结构通常需要引入较为全面的通名词典或借助各类复杂的自然语言模型，此类方法在提升匹配正确率的同时也会牺牲时间效率。

作者：姜宇荣，高苏，蔡忠亮，王巧

来源：《武汉大学学报（信息科学版）》

2025年第7期

选稿：耿 瞳

编辑：江 桐

校对：汪鸿琴

审订：杨 琪

责编：耿 瞳

（由于版面内容有限，文章注释内容请参照原文）

微信扫码加入

中国地名研究交流群

QQ扫码加入

江西地名研究交流群

欢迎来稿！欢迎交流！

转载请注明来源：“江西地名研究”微信公众号