一種改進的Lucene算法及在空間數據融合中的應用

陳利燕，林　鴻，張新長

(1. 中山大學地理科學與規劃學院，廣東 廣州 510275； 2． 廣州市城市規劃勘測設計研究院，廣東 廣州 510060)

?

一種改進的Lucene算法及在空間數據融合中的應用

陳利燕1，2，林鴻2，張新長1

(1. 中山大學地理科學與規劃學院，廣東 廣州 510275； 2． 廣州市城市規劃勘測設計研究院，廣東 廣州 510060)

在“互聯網+”時代，眾源地理空間數據已成為重要的數據來源，但由于眾源數據存在冗余和精度不高等問題，如何有效利用眾源數據已成為地理信息技術研究的熱點。眾源POI數據一般通過與標準數據進行同名點匹配解決上述等問題。而同名點匹配常用的方法有編輯距離算法、最長公共子串算法、貪心字符串匹配算法，這些方法存在匹配效率低、缺少語義判斷等問題。為此本文基于Lucene提出了一種基于語義相似度的快速匹配算法，試驗結果表明，與傳統的字符匹配方法相比，本文提出的方法在運算效率上有顯著的提升，同時還能通過判斷語義相似度提高匹配率。

同名點匹配；字符串匹配；Lucene索引；語義相似度

隨著“互聯網+”時代的來臨，眾源地理空間數據已成為當前空間信息應用的重要數據來源。與傳統地理信息采集和更新方式相比，來自非專業大眾的眾源空間數據具有數據量大、現勢性好、信息豐富、成本低等特點和優勢[1]，成為近年來國際地理信息科學領域的研究熱點。在移動及Web環境下，眾源POI數據與地理框架背景數據的混搭式地圖應用，越來越多地出現在主流地理信息平臺及LBS服務中。但由于眾源POI數據存在信息冗余、缺乏質量信息或質量信息不精確等問題[1]，在應用前必須利用匹配技術進行信息空間位置糾正和篩選去重操作。POI點匹配原理主要是利用對象之間的名稱或位置描述字符串相似度來判斷是否為同一對象。常用字符串相似度計算方法有編輯距離算法、最長公共子串算法、貪心字符串匹配算法等，但這些匹配算法對于眾源POI海量數據而言，逐條循環匹配效率低，且缺少語義相似度的判斷。Lucene算法作為當前流行的信息檢索技術，雖然也被廣泛應用于地理信息應用領域，但都是基于傳統詞頻分析技術，對其存在的檢索精確度和召回率存在的不足很少有人討論，同時也忽視了語義的判斷。為此本文提出一種改進的Lucene算法，以改進傳統基于詞頻的方法對語義忽視所造成的檢索不夠精確的問題，同時給出一個初步判定語義相似性的算法。試驗結果表明,通過這些改進，與傳統的字符串匹配，本文提出的方法能較好地提高運行效率和查詢準確率。

一、相關研究

文獻[2]中對編輯距離(LD)[3]、最長公共子串(LCS)[4]、貪心字符串匹配(GST)[5]和改進的貪心字符串匹配[6-7]等算法原理進行了詳細描述。這些算法雖然能較好地反映字符串之間的相似程度，但存在檢索效率低、忽略對象之間語義關系等問題。Lucene作為一個通用的搜索引擎開發工具包被廣泛地應用于檢索領域中[8-9]，通過索引技術提高了檢索的效率。也有學者將其應用于地理信息系統應用中，如文獻[10]將其應用于地圖信息搜索，文獻[11—12]將其應用于地址匹配等。盡管Lucene已在地理信息領域被廣泛應用，相關的研究也層出不窮，然而大多數研究都是基于Lucene內部默認實現的詞頻分析檢索函數來考察對象之間的相似性來進行檢索，很少有考慮對詞項語義的Lucene檢索研究。雖然文獻[13]提出基于信息理論的詞項語義相似度量方法計算詞項之間的語義相似性，但該算法對于POI同名點在名稱或空間位置字符串信息匹配上也同樣存在精度不高的問題。

二、改進后Lucene基本工作流程

本算法在傳統的Lucene工作流程上進行了改進(如圖1所示)，基本工作流程主要分3個階段。

圖1　算法基本工作流程

第1階段，根據區域內地名特征，對詞庫進行完善，包括：1-1對研究區范圍的專有地名、街路巷等詞匯進行提取；1-2將專業詞匯及相關的近義詞添加至詞庫。

第2階段，將參考基準數據庫建立索引文件，包括：2-1將基準數據庫的名稱和位置信息提取；2-2利用詞庫通過分詞器將提取的字符串信息進行分割；2-3將分詞后的信息按照規則保存至索引文件。

第3階段，眾源數據與參考基準數據的匹配，包括：3-1從眾源數據中提取出包含名稱和位置等可用于匹配的信息；3-2對可用于匹配的信息利用分詞器進行詞法分析和語義處理得到系列檢索詞樹；3-3依據搜索詞樹通過讀取索引搜索結果集；3-4對搜索結果集采用基于語義相似度評分機制進行排序，并返回最終結果。

算法的改進主要體現在圖1所示的“詞庫”的完善和“基于的語義相似度評分機制”。“詞庫”主要包括專有名詞和同義詞(近義詞)庫的補充和完善。詞庫完成后利用分詞器可實現字符串按語義進行分詞，如“中山大學”將被分割成“中山”“大學”和“中大”。“基于語義相似度評分機制”主要是利用分詞后的詞項之間的語義相似度評分來判斷是否為同名點對象。

三、基于語義的詞庫的完善

“詞”是字符串中最小的可以獨立運用的單位，如“廣州大學”可以分詞為“廣州”和“大學”。由于中文本身的復雜性及地址信息描述規則的不確定性，使中文分詞成為分詞技術中的難點。如“廣州大學”和“廣大”都表示的是同一個對象，如何讓計算機能夠基于語義判斷地理對象之間的相似度是提高匹配準確率的關鍵技術。為此本文借助“充分大的”盤古詞庫，按照一定的策略將待分析的位置信息與詞庫的詞條進行匹配后切分成一系列有意義的詞。本文主要有兩個方面的改進：①根據試驗區內的專有地名、街路巷等信息完善擴充和完善“詞庫”，位置信息中含有許多專有詞匯，因此“詞庫”不完整會導致分詞不準確而降低檢索的查準率。如“廣州市越秀區白米巷”因詞庫中缺少“越秀區”和“白米巷”會被分割成“廣州/廣州市/越秀/區/白米/巷/”；②組建了地名、地址和POI點的近義詞庫。利用文獻[14]的規則，將試驗區內的位置、地名和機構等簡稱進行特征分析，利用人工交互的方法，建立近義詞庫，從而使得語義相同或相近的“詞”可以進行有效匹配。地理位置信息的同名點判斷通過“詞”與“詞”之間的語義相似度的相關函數確定。

四、Lucene相似度函數的改進

設參考基準空間數據庫為D，對任意參考基準記錄dk位置信息文檔，經語義分詞后將每個詞表示為如下m維向量形式

V(dk)=[wk,1wk,2…wk,m]

對于待匹配的任一記錄空間位置信息q個經分詞后形成由搜索詞項tm的權重組成查詢向量

V(q)=[s1s2…sn]

傳統Lucene搜索模型是基于VSM，即向量空間模型[8]，將參考基準向量及查詢向量放到一個N維空間中，每個詞t(term)是一維。兩個向量之間的夾角越小，相關性越大。計算夾角的余弦值作為相關性的度量，夾角越小，余弦值越大，分值越高，相關性越大(如圖2所示)。相似度最終可表示為[15]

(1)

圖2　字符相似度空間多維向量

(2)

逆文檔頻率權重的加入，使得完全相同的兩個位置信息描述字符串比較最終的相似度也不是100%，因此為了便于相似程度的比較，將相似度計算函數作如下的簡化和改進

(3)

式中，sim(wk,si)表示查詢項搜索詞Si與參考基準文檔d的wk的語義相似度；max{sim(wk,si)}表示與wk語義相似度的最大值。

與式(2)相比，本文簡化了相似度計算的公式，使得相似度計算值更容易理解并比較，同時檢索結果不僅包含了與被檢索詞項相同的文檔，而且還包含了與被檢索詞項相似的文檔，從而更為準確地體現了檢索的含義。

五、試驗與分析

1) 試驗數據：廣州電信公司提供的越秀區的網點數據共1509條(XLS格式)，從2014年廣州市基礎測繪成果中提取越秀區門牌數據共40 490條(shapefile格式)。

2) 試驗環境與試驗平臺：試驗在Window7操作環境下進行，本文采用VisualStudio2010結合ArcGISEngine10開發了基于字符串相似度匹配算法的點要素空間數據融合原型系統。

3) 試驗結果評估：在眾源數據融合使用中，主要是根據匹配融合的效率、匹配的精度(匹配總量和誤匹配量)來評估算法的優劣性。

1. 試驗1

為了比較不同數據量匹配融合的時間消耗，從數據源中提取部分街路巷的數據，匹配對比分為3組，各組的數據量(電信網點數據×基礎地理門牌數據)分別為500×5092條(組1)；1000×9881條(組2)、1509×40 490條(組3)，各種算法在不同匹配數據量上的時間消耗見表1，時間增長率如圖3所示。

表1　各組匹配數據時間消耗　s

從圖3可以很明顯地看出，在數量量不大的情況下，本文所提算法的優勢并不明顯；但隨著數據量的增大，傳統字符匹配算法時間消耗增長率呈線性增長，而本文提出的算法繼承了傳統Lucene算法在檢索時間上的優勢，在時間消耗上增長并不明顯，由此也可以看出本算法在大數據融合使用中具有更好的應用前景。

圖3　算法時間消耗對比

2. 試驗2

為了進一步比較各類算法的優劣性，對組1(500×5 092條)匹配結果進行了詳細分析，結果見表2。傳統的Lucene算法和編輯距離算法在誤匹配量上最大，本文算法的誤匹配數量最少，查準率最高。通過對誤匹配的數據記錄進行分析，發現造成誤匹配的原因主要有兩個方面：一是基準數據不完整，由于各類算法的匹配策略是將相似度判斷值最大的對象作為結果進行匹配，且基礎測繪成果中的門牌數據不完善，確有部分電信網點的地址信息不被包含，由此而造成了誤匹配；二是算法的不完善，因為各算法相似度計算方法不完善造成的錯誤匹配。

由于傳統的Lucene算法在相似度函數中加入了逆文檔頻率權重的判斷，使得在匹配過程中字符信息完全相同的對象之間的得分不一定是最高，而造成了誤匹配。針對上述問題，本文對相似度函數進行了改進，同時加入了語義相似度的判斷，減少了因算法不完善而引起的誤匹配量，提高了匹配的準確率。

表2　各類算法匹配結果

六、結　論

同名對象匹配作為矢量空間數據融合的重要過程，其匹配的效率和準確率決定了數據融合使用的質量。基于傳統的字符串相似度匹配技術存在著效率低和缺少語義判斷等問題，在匹配效果上不盡如人意。本文基于語義相似度判斷對Lucene算法進行改進，有效提高了匹配的效果和精度。通過試驗，得出的結論如下：

1) 隨著同名匹配數據量的增加，本文的方法在效率上優勢明顯，且保持了較高準確率，在眾源海量空間數據融合上具有良好應用前景。

2) 本文通過對近義詞(同義詞)庫的補充和完善，實現了基于語義相似度的比較，有效解決了因數據來源不一致導致的同點不同名的現象，極大地提高了匹配的準確度。

本文的不足之處在于同名字符信息的語義分詞依賴詞庫的完整性，由于詞庫的局限性，對特有名詞或新詞的匹配上有些不盡如人意的地方，需要對詞庫進行不斷的更新和完善。

[1]王明,李清泉,胡慶武,等. 面向眾源開放街道地圖空間數據的質量評價方法[J]. 武漢大學學報(信息科學版), 2013, 38(12): 1490-1494.

[2]牛永潔,張成. 多種字符串相似度算法的比較研究[J]. 計算機與數字工程, 2012, 40(3): 14-17.

[3]刁興春,譚明超,曹建軍. 一種融合多種編輯距離的字符串相似度計算方法[J]. 計算機應用研究, 2010, 27(12): 4523-4525.

[4]張毅超,車玫,馬駿. 求最長公共子串問題的算法分析[J]. 計算機仿真, 2007(12): 97-100, 116.

[5]于海英. 字符串相似度度量中LCS和GST算法比較[J]. 電子科技, 2011, 24(3): 101-103, 124.

[6]WISE M J. Running Karp-Rabin Matching and Greedy String Tiling[C]∥The Third International Conference on Intelligent Systems for Molecular Biology.Cambridge，England:[s.n.], 1993: 393-401.

[7]牛永潔. RKR-GST算法在.NET中的分析與實現[J]. 信息技術, 2012(3): 171-174.

[8]張校乾,金玉玲,侯麗波. 一種基于Lucene檢索引擎的全文數據庫的研究與實現[J]. 現代圖書情報技術, 2005 (2): 40-43, 48.

[9]張俊,李魯群,周熔. 基于Lucene的搜索引擎的研究與應用[J]. 計算機技術與發展, 2013, 23(6): 230-232.[10]梁明,羅榮,胡最. 基于Lucene和PostGIS的地圖搜索研究[J]. 測繪通報, 2014(11): 42-45.

[11]柴潔. 基于IKAnalyzer和Lucene的地理編碼中文搜索引擎的研究與實現[J]. 城市勘測, 2014(6): 45-50.

[12]陳德權. GIS地名搜索系統的關鍵技術設計與實現[J]. 測繪與空間地理信息, 2013, 36(8): 58-60.

[13]黃承慧,印鑒,陸寄遠. 一種改進的Lucene語義相似度檢索算法[J]. 中山大學學報(自然科學版), 2011, 50(2): 11-15.

[14]郝娟,楊靜. 采用上下文特征匹配的中文機構名簡稱識別[J]. 小型微型計算機系統, 2015, 36(7): 1432-1437.

[15]任樹懷. LUCENE搜索算法剖析及優化研究[J]. 圖書館雜志, 2014, 133(12): 17-23.

[16]陳換新,孫群,肖強,等. 空間數據融合技術在空間數據生產及更新中的應用[J]. 武漢大學學報(信息科學版), 2014, 31(1): 117-122.

An Improved Lucene Algorithm and Its Application to Spatial Data Fusion

CHEN Liyan，LIN Hong，ZHANG Xinchang

陳利燕，林鴻，張新長.一種改進的Lucene算法及在空間數據融合中的應用[J].測繪通報，2016(10)：106-109.DOI:10.13474/j.cnki.11-2246.2016.0341.

2015-12-18

國家自然科學基金重點項目(41431178)

陳利燕(1981—)，女，博士，高級工程師，研究方向為空間數據更新與融合。E-mail：jimigao@163.com

P208

B

0494-0911(2016)10-0106-04