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

江西地名研究

關(guān)注我們，獲取更多地名資訊

摘要：當(dāng)前中文地名匹配常見的相似性度量或是只考慮重合字符的數(shù)量未考慮位次性，或是體現(xiàn)位次性但未考慮重合字符。通過考慮兩個(gè)中文地名字符串的重合字符對(duì)應(yīng)關(guān)系及其位次差距，構(gòu)建了一種新的距離度量和相似性度量，能夠結(jié)合重合字符和位次性兩個(gè)因素計(jì)算兩個(gè)地名的偏距和偏距相似度。針對(duì)重合字符復(fù)現(xiàn)的情形確定偏距最小原則，設(shè)計(jì)全體順次匹配方案；針對(duì)字符片段偏移的情形調(diào)整距離度量，從而更符合兩個(gè)地名相似性的直觀認(rèn)知。該距離度量滿足正定性和對(duì)稱性，但不滿足三角不等式。與Jaccard系數(shù)和編輯距離相似度的測(cè)試對(duì)比結(jié)果表明，所提偏距算法對(duì)相似度刻畫更為細(xì)致，能夠檢測(cè)到重合字符位次差異但更重視未重合字符的差異；在地名匹配實(shí)驗(yàn)中匹配正確率和運(yùn)行時(shí)間分別為63.64%和2 940.56s，兩項(xiàng)指標(biāo)均優(yōu)于Jaccard系數(shù)和編輯距離相似度。

關(guān)鍵詞：相似性度量；近似字符串匹配；自然語(yǔ)言處理；地名匹配；中文地名

在中國(guó)測(cè)繪地理信息技術(shù)得到不斷發(fā)展和廣泛應(yīng)用的背景下，標(biāo)準(zhǔn)地名數(shù)據(jù)庫(kù)和多種尺度下的地圖要素?cái)?shù)據(jù)庫(kù)的數(shù)據(jù)量大幅上升，顯現(xiàn)出巨大的潛在應(yīng)用價(jià)值。但是，由于“一地多名”的現(xiàn)象或數(shù)據(jù)生產(chǎn)時(shí)的疏忽，會(huì)出現(xiàn)同一地理實(shí)體在不同尺度地圖要素?cái)?shù)據(jù)庫(kù)中的名稱互不相同，出現(xiàn)錯(cuò)別字，或與標(biāo)準(zhǔn)地名不符等問題，給地圖的多尺度展示和地理信息數(shù)據(jù)實(shí)體化帶來(lái)諸多不便。因而有必要研究地名相似性度量方法以實(shí)現(xiàn)地名匹配，輔助同一地理實(shí)體在不同尺度下名稱的統(tǒng)一和地理實(shí)體庫(kù)的構(gòu)建，促進(jìn)地理信息的精細(xì)化管理和應(yīng)用。

當(dāng)前有關(guān)中文地名相似匹配研究中，采用的文本相似性度量［多為Jaccard相似系數(shù)（又稱Jaccard系數(shù)）、編輯距離和詞頻-逆文檔頻率（term frequency-inverse document frequency，TF-IDF）等基于詞頻向量算法，但是以上相似度算法在實(shí)踐中均存在各自的缺陷。如果將兩地名都包含的字符稱為重合字符，那么Jaccard系數(shù)定義為重合字符數(shù)和總字符數(shù)之比。Jaccard系數(shù)能夠在一定程度上表達(dá)地名相似度，但是由于該指標(biāo)僅考慮了重合字符數(shù)而沒有考慮位次特征，因此它對(duì)相似性的描述是較為粗略的。編輯距離一般指萊文斯坦距離，定義為一個(gè)地名字符串變換為另一個(gè)地名字符串要經(jīng)過的最少“操作”次數(shù)，其中“操作”包括插入、刪除或替換單個(gè)字符。綜合考量?jī)蓚€(gè)地名字符串編輯距離的實(shí)際數(shù)值和理論最大值可以進(jìn)一步得到編輯距離相似度。編輯距離算法能夠捕捉到兩個(gè)地名字符串在字符位次排列特征上的相似性，在實(shí)際生產(chǎn)中應(yīng)用也較為廣泛。然而該指標(biāo)容易忽視重合字符特征，在字符片段順序顛倒等情況中可能對(duì)相似性作出不合理的描述。另外，也有學(xué)者使用TF-IDF等基于詞頻向量算法計(jì)算兩地名相似度。但是究其原理，TF-IDF算法評(píng)估的是某個(gè)詞語(yǔ)對(duì)于語(yǔ)料庫(kù)中一份文檔的“重要程度”，這與“文本相似度”的概念并不能等同。在用于地名地址匹配時(shí)，TF-IDF算法會(huì)將地名視為諸多關(guān)鍵詞的簡(jiǎn)單集合從而忽略語(yǔ)序，且詞頻越高，評(píng)分越高的邏輯也并不適用于評(píng)估地名相似性。

綜上，現(xiàn)有的地名相似性度量或是強(qiáng)調(diào)重合字符數(shù)量，或是強(qiáng)調(diào)字符位次特征，卻不能將兩者很好地結(jié)合起來(lái)。通過觀察可發(fā)現(xiàn)，兩個(gè)地名在字符層面的相似程度關(guān)鍵在于重合字符的匹配情況。因此，本文意在構(gòu)建能夠同時(shí)體現(xiàn)重合字符數(shù)量及位次特征的新相似性度量指標(biāo)。由于Jaccard系數(shù)和編輯距離相似度同為考慮字符層面的文本相似性度量，在識(shí)別字符重合數(shù)量和字符位次特征上具有各自的優(yōu)勢(shì)且實(shí)際中運(yùn)用廣泛，故本文將重點(diǎn)與它們進(jìn)行對(duì)比。

1

構(gòu)建地名相似性度量

1.1重合字符偏距

考慮兩個(gè)地名字符串A和B，找到兩者所有的重合字符，按在地名A中從左到右的順序依次記為1、2、3、···、n。對(duì)于任一重合字符，假定它在A和B中均剛好只出現(xiàn)一次。記在A中的位次是（即i是地名字符串A從左往右數(shù)第個(gè)字符）；在B中的位次是bi，如圖1所示，顯然每對(duì)重合字符恰好構(gòu)成匹配（一一對(duì)應(yīng)），并且兩者的位次越接近（即和差值越小），意味著兩個(gè)地名字符串A和B差異程度越小、相似度越高。

因此，定義偏距=─用于表征構(gòu)成匹配的重合字符的位次差異程度。設(shè)所有重合字符的偏距構(gòu)成偏距向量O，那么該向量記錄了地名字符串A和B重合字符集的位次差異信息；記的絕對(duì)值之和為匹配總偏距D（O），該值代表了重合字符集的總體位次差異程度。

1.2未重合字符偏距

考慮未重合字符時(shí)，可以將偏距視為兩個(gè)地名文本相似性的距離描述。重合字符的偏距絕對(duì)值越大，代表兩個(gè)地名的文本相似性越小。未重合字符相當(dāng)于無(wú)關(guān)字符，對(duì)兩個(gè)地名文本相似性的影響應(yīng)當(dāng)比重合字符更大，即未重合字符的偏距絕對(duì)值應(yīng)當(dāng)更大。設(shè)想如下情形：任意找到一對(duì)重合字符（，），其中地名A的變?yōu)橐粋€(gè)A和B中都不曾出現(xiàn)的全新字符j，那么此時(shí)i和j兩個(gè)字符都轉(zhuǎn)變成未重合字符。定義每個(gè)未重合字符帶來(lái)的偏距為。根據(jù)直觀認(rèn)知，轉(zhuǎn)變后的兩個(gè)未重合字符（j，）帶來(lái)的偏距2理應(yīng)大于初始兩個(gè)重合字符（，）偏距的絕對(duì)值。即希望找到一個(gè)合適的值，能夠保證對(duì)所有的i滿足：

假設(shè)A和B之間共有W個(gè)未重合字符，那么所有未重合字符帶來(lái)的偏距之和記為未匹配總偏距，表達(dá)式為：

需要指出的是，值的定義是靈活的，并非一成不變。在實(shí)際應(yīng)用場(chǎng)景下可以調(diào)整的值，使得未重合字符對(duì)相似性的影響變大或者變小。

1.3總偏距與偏距相似度

定義總偏距D（A，B）為匹配總偏距D（O）與未匹配總偏距之和。那么總偏距D（A，B）便是兩個(gè)地名字符串A和B差異程度的距離度量。當(dāng)A和B沒有重合字符時(shí)，W=l（A）+l（B），此時(shí)給兩地名字符串的差異程度最大，總偏距也正好取得最大值：

由定義可知，當(dāng)且僅當(dāng)A和B完全相同時(shí)，D（A，B）=0，S（A，B）=1；當(dāng)且僅當(dāng)A和B不存在重合字符時(shí)，D（A，B）=，S（A，B）=0。

2

地名相似性識(shí)別的復(fù)雜情形

2.1重合字符復(fù)現(xiàn)

通常情況下，重合字符在A和B中均剛好只出現(xiàn)一次；然而對(duì)于某些相對(duì)復(fù)雜的地名，重合字符是有可能在A和B中多次出現(xiàn)的。此時(shí)重合字符匹配不再是兩個(gè)字符的簡(jiǎn)單對(duì)應(yīng)，而是在多個(gè)字符中確定合適的匹配關(guān)系。任取一個(gè)重合字符，假設(shè)它在A中出現(xiàn)x次，在B中出現(xiàn)y次，將A、B間的重合字符盡可能地進(jìn)行一一匹配，剩余|x-y|個(gè)無(wú)法匹配上的i則視為未重合字符處理。

直觀來(lái)看，A（或B）中的每一個(gè)重合字符i只需要就近和B（或A）中的匹配起來(lái)即可，不然匹配關(guān)系與直觀認(rèn)知不符（見圖2），也會(huì)帶來(lái)一些多余且無(wú)謂的偏距。例如A和B為同一個(gè)地名“尖尖山”時(shí)，如果刻意地不就近匹配重合字符“尖”而是選擇交叉匹配，那么D（A，B）=1+1= 2，與直觀認(rèn)知中A和B偏距應(yīng)當(dāng)為0是不符的。因此，將重合字符的匹配原則確定為“就近”，嚴(yán)格來(lái)講即偏距最小原則。

根據(jù)偏距最小原則，容易得到以下結(jié)論：如果A中位次為m、n（m

證明過程如下：記順次匹配的偏距為=|m-r|+|n-s|，逆次匹配的偏距為=|m-s|+|n-r|。按表1分類討論計(jì)算-即可。并且-有可能取到0，意味著有時(shí)順次匹配和逆次匹配的偏距相等。

當(dāng)x=y（重合字符在A和B中出現(xiàn)次數(shù)相等）時(shí)，根據(jù)順次匹配小于或等于逆次匹配的結(jié)論，對(duì)A、B間的所有重合字符進(jìn)行全體順次匹配（如圖4所示，A的第1個(gè)匹配B的第1個(gè)，A的第2個(gè)匹配B的第2個(gè)，依次下去，重合字符的匹配連線不存在任何交叉），就能滿足偏距最小原則。

當(dāng)然，偏距取得最小值的匹配方案可能不止一種，本文只是選用了形式上最簡(jiǎn)潔的。例如，圖5“杉杉”和“北京杉市杉”的兩種匹配方案中，匹配總偏距分別為2+3=5、1+4=5，均滿足偏距最小原則，而默認(rèn)選用左側(cè)全體順次匹配的形式。

當(dāng)x≠y（重合字符在A和B中出現(xiàn)次數(shù)不等）時(shí)，如果x>y，先從A的x個(gè)重合字符中取出y個(gè)，一共有種方法，再將取出的y個(gè)與B進(jìn)行全體順次匹配，便得到了個(gè)偏距，最后選擇其中偏距最小的一種匹配方案。如果x

2.2字符片段偏移

以上偏距計(jì)算都是基于字符而非詞或詞組。這樣做的優(yōu)點(diǎn)在于不會(huì)因?yàn)榉衷~問題而捕捉不到全稱與簡(jiǎn)稱之間的相似性；缺點(diǎn)在于存在詞或詞組偏移時(shí)會(huì)產(chǎn)生不合理的偏距值。例如，A=“北京南湖路”，B=“南湖路北京”，C=“湖北南京路”，其中B相較于A雖然“北京”和“南湖路”兩詞的順序顛倒，但所指代的地理實(shí)體沒有發(fā)生改變，C相較于A字符順序完全改變，導(dǎo)致所指代的地理實(shí)體也發(fā)生改變，因此D（A，C）應(yīng)當(dāng)大于D（A，B）。但是計(jì)算結(jié)果為D（A，C）=1+2+0+ 3+0=6 D（A，B）。因此，需要進(jìn)一步識(shí)別出詞或詞組的偏移，即連續(xù)字符片段的整體偏移后，再去計(jì)算偏距。識(shí)別過程如圖6所示，此時(shí)偏距的概念也得到推廣——從僅限于字符之間的偏距，變?yōu)樽址危ò瑔蝹€(gè)字符）之間的偏距。

2.3相關(guān)定義更新

由于§2.1和§2.2對(duì)復(fù)雜情形的處理，前文關(guān)于O、D（O）、等定義的描述不再完全適用。相關(guān)定義更新如下：

經(jīng)過重合字符匹配和字符片段識(shí)別后，所有匹配成功的重合字符片段（包含單個(gè)重合字符）的首字符偏距構(gòu)成偏距向量O。所有的絕對(duì)值之和構(gòu)成匹配總偏距D（O）。每個(gè)未匹配的字符（包括匹配失敗的重合字符和未重合字符）帶來(lái)的偏距均為，它們的和構(gòu)成未匹配總偏距。此時(shí)總偏距D（A，B）的定義保持不變，仍為D（O）與兩者之和。相似度S（A，B）的定義保持不變。

其中，總偏距D（A，B）作為新提出的距離度量有以下特點(diǎn)：

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

2）滿足對(duì)稱性。只要D（A，B）和D（B，A）的重合字符匹配都遵循偏距最小原則，那么計(jì)算結(jié)果必然是同一個(gè)最小值，即滿足對(duì)稱性D（A，B）=D（B，A）。

3）不滿足三角不等式。例如A=“北京大學(xué)”，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，此時(shí)D（A，C）>D（A，B）+D（B，C）不滿足三角不等式。

事實(shí)上，總偏距更像是兩個(gè)地名間相似性推導(dǎo)過程中的一個(gè)分值，且滿分值本身也會(huì)隨地名而變化，所以不宜直接用它表達(dá)地名相似性而應(yīng)當(dāng)使用偏距相似度。當(dāng)考慮3個(gè)及以上地名間的相似性關(guān)系時(shí)，可計(jì)算它們兩兩之間的偏距相似度。

3

相似度對(duì)比實(shí)驗(yàn)

為觀察本文偏距算法的相似度表達(dá)能力與特性，先設(shè)計(jì)8對(duì)不同差異程度的地名和9對(duì)相似地名計(jì)算偏距相似度，并與經(jīng)典的Jaccard系數(shù)和編輯距離相似度進(jìn)行對(duì)比。如表2和表3所示。其中打鉤(√)表示兩地名指代的為同一個(gè)地理實(shí)體。

在辨別不同差異程度的地名時(shí)，本文的偏距算法對(duì)相似度的刻畫更為細(xì)致合理，符合設(shè)計(jì)的初衷。遇到兩個(gè)地名完全相同、僅位次不同、部分字符相同和完全不同等情況時(shí)，偏距相似度從1到0逐漸下降，且下降過程較為連續(xù)、平滑。與之相較，Jaccard系數(shù)整體呈下降趨勢(shì)但在僅位次不同時(shí)恒為1，編輯距離相似度呈曲折變化，兩者均不如偏距相似度數(shù)值變化均勻。

在辨別相似地名時(shí)，可進(jìn)一步觀察到偏距算法的特性：對(duì)字符差異重視程度較大，重合字符的比例減小時(shí)相似度顯著降低；對(duì)單純的位次差異重視程度較小，但也能體現(xiàn)在相似度數(shù)值的細(xì)微差距中。與之相較，Jaccard系數(shù)無(wú)法識(shí)別到位次差異；編輯距離相似度對(duì)位次差異和字符差異的重視程度沒有顯著區(qū)別。偏距算法的該特性決定了其會(huì)更適用于地名匹配等應(yīng)用場(chǎng)景。例如位次差異的4個(gè)地名中，僅有偏距算法能通過最大相似度分辨出“北京南湖路”與“南湖路北京”構(gòu)成匹配；字符差異的5個(gè)地名中，偏距算法也能通過尋找相似度最大的兩項(xiàng)判別出“北京南湖路”與“南湖路”“北京市南湖路”構(gòu)成匹配。

為測(cè)試本文偏距算法在地名匹配應(yīng)用場(chǎng)景下的實(shí)際效果，通過數(shù)據(jù)預(yù)處理和隨機(jī)篩選，獲得了5萬(wàn)條中國(guó)北京市范圍內(nèi)的高德地圖興趣點(diǎn)（point of interest，POI）數(shù)據(jù)（見圖7，圖7的底圖來(lái)源是天地圖，行政界線未修改），其中每條數(shù)據(jù)均滿足：（1）恰含一個(gè)地名和一個(gè)別名；（2）地名和別名均已去除特殊符號(hào)；（3）若地名或別名有英文字母則統(tǒng)一為小寫；（4）別名和地名不等同。

測(cè)試方案為：對(duì)于任意一個(gè)別名，計(jì)算它和每一個(gè)地名的相似度，尋找該別名的最大相似度地名；若最大相似度地名僅有一個(gè)且和別名恰好對(duì)應(yīng)同一條POI數(shù)據(jù)，則為匹配正確；統(tǒng)計(jì)5萬(wàn)個(gè)別名中匹配正確的數(shù)量，并記錄算法運(yùn)行時(shí)間。分別采用Jaccard系數(shù)、編輯距離相似度和偏距相似度進(jìn)行上述測(cè)試，匹配結(jié)果如表4所示。部分別名的最大相似度地名如表5所示，如果該別名的最大相似度地名存在多個(gè)，則取其中一個(gè)作為示例，打鉤(√)表示該別名匹配正確。

偏距相似度的匹配正確率為63.64%，相較于Jaccard系數(shù)提升2.34%，相較于編輯距離相似度提升13.48%。參考表5實(shí)例可發(fā)現(xiàn)，偏距相似度無(wú)論遇到錯(cuò)別字（例如“萬(wàn)恒萬(wàn)澤中心”-“方恒萬(wàn)澤中心”）、字符片段顛倒（例如“北環(huán)西路大發(fā)路路口”-“大發(fā)路北環(huán)西路路口”）還是各類全稱或簡(jiǎn)稱（例如“央央生物”-“北京央央生物技術(shù)有限公司”），都能憑借對(duì)重合字符片段的敏感性而更容易匹配正確，而Jaccard系數(shù)沒有考慮字符順次結(jié)構(gòu)，導(dǎo)致“龍躍苑4區(qū)12號(hào)樓”錯(cuò)誤匹配到“龍躍苑三區(qū)14號(hào)樓”，編輯距離相似度對(duì)片段顛倒和簡(jiǎn)稱辨識(shí)能力較差，因此“北環(huán)西路大發(fā)路路口”和“建壯咨詢”等別名均沒有匹配正確。

雖然偏距相似度的構(gòu)建初衷是提升地名相似度評(píng)價(jià)的合理性，但在實(shí)驗(yàn)過程中它的運(yùn)行時(shí)間指標(biāo)同樣展現(xiàn)出明顯優(yōu)勢(shì)。其耗時(shí)2 940.56s，僅為Jaccard系數(shù)的73.41%，編輯距離相似度的42.39%。時(shí)間效率優(yōu)勢(shì)的原因主要在于偏距相似度算法的第一步便是定位所有重合字符，作為后續(xù)處理的基礎(chǔ)。一般只有當(dāng)別名遇到對(duì)應(yīng)地名或少數(shù)相似地名時(shí)才會(huì)存在較多重合字符，大多數(shù)無(wú)重合字符或重合字符很少的地名都將被快速處理，所以運(yùn)行時(shí)間更短。此外，Jaccard系數(shù)算法雖然也是基于尋找重合字符，但它運(yùn)用了集合去重復(fù)和取交集等復(fù)雜操作，所以運(yùn)行時(shí)間相對(duì)較長(zhǎng)。

綜上，偏距相似度是地名匹配測(cè)試中總體表現(xiàn)最佳的，在匹配正確率和運(yùn)行時(shí)間兩項(xiàng)指標(biāo)上都更為優(yōu)秀。但是也需承認(rèn)在5萬(wàn)條數(shù)據(jù)量的情形下，偏距相似度算法的匹配正確率相比于其他兩種算法提升幅度有限。這一方面是因?yàn)閿?shù)據(jù)量較大時(shí)，同類型的相似地名的頻繁出現(xiàn)容易導(dǎo)致匹配錯(cuò)誤。例如，統(tǒng)計(jì)的5萬(wàn)個(gè)別名中有2 402個(gè)包含“停車場(chǎng)”，5萬(wàn)個(gè)地名中亦有2 449個(gè)包含“停車場(chǎng)”；隨著同類型的相似地名的頻繁出現(xiàn)，它們?cè)谄ヅ溥^程中產(chǎn)生混淆的概率也會(huì)增加。另一方面則是因?yàn)槠嘞嗨贫缺举|(zhì)仍為文本相似性度量，只能關(guān)注字符層面的相似性而難以顧及復(fù)雜的語(yǔ)義。當(dāng)附加過多通名字符或地址信息字符時(shí)，偏距相似度會(huì)顯著降低從而難以正確匹配，例如“達(dá)懿集團(tuán)”未能正確匹配到“山西達(dá)懿電子集團(tuán)有限公司”；當(dāng)出現(xiàn)“1”和“一”等語(yǔ)義一致的字符時(shí)，偏距相似度同樣不能理解從而導(dǎo)致失敗，例如“大溪地1區(qū)16號(hào)樓”沒有正確匹配到“大溪地一區(qū)16號(hào)樓”。

4

結(jié)語(yǔ)

本文通過計(jì)算重合字符偏距定義未重合字符偏距，以及處理重合字符復(fù)現(xiàn)和字符片段偏移等復(fù)雜情形，最終構(gòu)建出新的中文地名相似性度量。本文提出的偏距相似度具有數(shù)值刻畫細(xì)致的優(yōu)點(diǎn)和重視字符差異且能識(shí)別位次差異的特性，在匹配正確率和運(yùn)行時(shí)間上的表現(xiàn)均優(yōu)于Jaccard系數(shù)和編輯距離相似度。未來(lái)可在處理復(fù)雜情形的算法設(shè)計(jì)、對(duì)其他語(yǔ)種適用性和考慮地名語(yǔ)義結(jié)構(gòu)上進(jìn)一步優(yōu)化。需要指出的是，考慮地名語(yǔ)義結(jié)構(gòu)通常需要引入較為全面的通名詞典或借助各類復(fù)雜的自然語(yǔ)言模型，此類方法在提升匹配正確率的同時(shí)也會(huì)犧牲時(shí)間效率。

作者：姜宇榮，高蘇，蔡忠亮，王巧

來(lái)源：《武漢大學(xué)學(xué)報(bào)（信息科學(xué)版）》

2025年第7期

選稿：耿 瞳

編輯：江 桐

校對(duì)：汪鴻琴

審訂：楊 琪

責(zé)編：耿 瞳

（由于版面內(nèi)容有限，文章注釋內(nèi)容請(qǐng)參照原文）

微信掃碼加入

中國(guó)地名研究交流群

QQ掃碼加入

江西地名研究交流群

歡迎來(lái)稿！歡迎交流！

轉(zhuǎn)載請(qǐng)注明來(lái)源：“江西地名研究”微信公眾號(hào)