簡化分詞的地址匹配技術(shù)

1、簡化分詞的地址匹配技術(shù)    摘要：本文旨在探討以一種較為簡單的方式實現(xiàn)“地址匹配”技術(shù)。全文闡述了分級地址庫的設(shè)計以及地址匹配算法兩個方面的內(nèi)容。筆者首先詳細說明了現(xiàn)今地址庫設(shè)計的主流方式并提出了自己的設(shè)計以及說明該設(shè)計的優(yōu)勢，緊接著基于該地址庫提出了簡化分詞和基于加權(quán)的地址匹配算法思路    關(guān)鍵詞：地址匹配；分級；簡化分詞；加權(quán)     0.引言隨著互聯(lián)網(wǎng)的普及，人們的生活和互聯(lián)網(wǎng)之間的聯(lián)系越來越緊密，各種互聯(lián)網(wǎng)技術(shù)也隨之迅速發(fā)展。在眾多互聯(lián)網(wǎng)技術(shù)中，GIS技術(shù)在近年來

2、由于國家政策的大力支持以及廣大網(wǎng)民的普遍需求而得以迅速發(fā)展，其中的地址匹配技術(shù)也得到了越來越多的使用。所謂的“地址匹配”技術(shù)，即使用者通過輸入地名地址的關(guān)鍵字來獲得對應(yīng)地址的信息。該功能主要由兩個部分組成：地名地址庫和作用于地址庫上的匹配算法。只有擁有良好的數(shù)據(jù)結(jié)構(gòu)設(shè)計和算法設(shè)計，才能夠?qū)崿F(xiàn)一個速度流暢，用戶體驗優(yōu)秀的地址匹配功能。1.設(shè)計簡介本文提出了一套“地址匹配”技術(shù)的實現(xiàn)流程。它通過建立地名的分級地址庫，使用基于該分級地址庫的中文分詞技術(shù)，并采用加權(quán)算法等多種數(shù)據(jù)篩選方式，實現(xiàn)了地址匹配功能。相對于其它的地名地址技術(shù)，這種方法擁有以下特點：使用地址庫進行分詞，減少了維護分詞字典這個步驟

3、，簡化了程序的實現(xiàn)流程以及維護開銷；使用加權(quán)算法等多種方式來對地址進行匹配，不僅在匹配結(jié)果中體現(xiàn)出不同級別數(shù)據(jù)重要性的差異，而且能夠動態(tài)挑選命中概率最高的結(jié)果，進一步提高了匹配結(jié)果的精確度，使用戶獲得更好的操作體驗。2.詳細說明2.1地址庫：地址匹配需要一個詳細的分級地址庫?，F(xiàn)在國家對行政區(qū)劃的分級一般為省、市、區(qū)縣、鎮(zhèn)（街道），另為了滿足一般民眾使用要求需要增加道路、名稱（門牌號）兩級，所以最終地址庫設(shè)計共分為6級?，F(xiàn)今的分級地址庫主要有兩種實現(xiàn)方式：一、 縱向設(shè)計。每條記錄只保存一個級別的一條信息，在該記錄里存在描述信息和一個父對象id，通過保存父對象id的parentID字段可以一路往上

4、獲取更高級別的信息，直到地址分級的最高級別，最終整合這些信息可以獲得完整記錄。如圖1所示(本文使用數(shù)據(jù)非真實數(shù)據(jù)，且為了展示簡明，隱藏了記錄坐標、地理編碼等次要屬性)：                                  圖1詳細設(shè)計方式可以參照論文基于分

5、詞的地址匹配技術(shù)孫亞夫、陳文斌。優(yōu)點：減少數(shù)據(jù)冗余，原則上每個行政區(qū)劃只需存儲一次，該行政區(qū)劃的下屬行政區(qū)劃通過它的id與它相關(guān)聯(lián)；修改方便，每個行政區(qū)劃的信息只保留在該行政區(qū)劃的記錄里，通過修改該條記錄，就能夠同時更新所有它下屬的行政區(qū)劃。缺點：數(shù)據(jù)保存不直觀，不能通過查看一條記錄獲得該地址的完整信息；數(shù)據(jù)結(jié)構(gòu)的特殊性導(dǎo)致必須提供數(shù)據(jù)轉(zhuǎn)換工具來對一般的地址信息進行轉(zhuǎn)換；復(fù)雜的數(shù)據(jù)結(jié)構(gòu)導(dǎo)致程序設(shè)計時必須考慮更多相關(guān)的風險，提高了系統(tǒng)的復(fù)雜度，從而增加了開發(fā)花銷。二、 橫向設(shè)計。每條記錄代表一個興趣點，該記錄里面包含完整的分級的地址信息，所以每條記錄存在與總級數(shù)相等的字段，里面放置各級信息。如圖

6、2所示：                                          圖2優(yōu)點：數(shù)據(jù)保存簡明直觀，可以直接通過查看數(shù)據(jù)表獲得每條記錄的詳細信息；數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)采集方式大

7、體一致，可以較為簡單地進行數(shù)據(jù)錄入；簡單的數(shù)據(jù)結(jié)構(gòu)更方便實現(xiàn)復(fù)雜的匹配算法。缺點：每條記錄都包含完整信息，記錄條數(shù)越多數(shù)據(jù)冗余越嚴重；修改不便，修改一個行政區(qū)劃的名字時必須對該行政區(qū)劃的所有下屬行政區(qū)劃的記錄進行修改。本文參考了以上兩種方法的優(yōu)缺點，提出了另外一種實現(xiàn)方式：把地名庫分為xzqh和address兩個表，其中xzqh表保存省、市、區(qū)縣、鎮(zhèn)（街道）、道路前五級數(shù)據(jù)，采取橫向設(shè)計。如圖3所示：                &#

8、160;               圖3address表保存名稱（門牌號）數(shù)據(jù)，其中parentID字段是xzqh表的外鍵，記錄通過該字段可以獲取前五級信息。如圖4所示：                        

9、   圖4此種設(shè)計主要考慮如下：一、 參考了橫向設(shè)計的優(yōu)點，數(shù)據(jù)結(jié)構(gòu)較為簡單，在數(shù)據(jù)庫中使用簡單的sql語句可以達到較好的顯示效果，方便管理員直接管理查看數(shù)據(jù)庫。二、 該設(shè)計可以解決數(shù)據(jù)大量冗余的問題，因為前五級數(shù)據(jù)相對較少且較為穩(wěn)定，采取橫向設(shè)計影響很小，數(shù)量最多的第六級參考了縱向設(shè)計的理念，以parentID字段關(guān)聯(lián)上幾級信息，從而避免大部分冗余。三、 該設(shè)計繼承橫向設(shè)計的一些缺點可以通過數(shù)據(jù)庫的特性來避免。比如sql語句可以較好解決修改不便的問題。四、 基于該數(shù)據(jù)結(jié)構(gòu)的算法模型實現(xiàn)起來較縱向設(shè)計簡單，并可以在查詢過程中實現(xiàn)分步查詢，先根據(jù)xzqh表獲取地址對應(yīng)范圍，縮

10、小address表中需匹配的記錄條數(shù)，從而降低時間開銷。2.2地址匹配算法：算法概要設(shè)計：首先根據(jù)關(guān)鍵詞在xzqh表中進行匹配，獲取地址所在范圍，縮小address表中需查詢的記錄條數(shù)；接著針對address表中處于該范圍之內(nèi)的記錄進行再次匹配，獲取最終結(jié)果。第一階段算法及示例如下：xzqh表由于使用了橫向的數(shù)據(jù)庫設(shè)計，每條記錄都包含完整的地址信息。所以此階段算法可以簡化為對每條記錄進行單獨判斷、計算，并把計算結(jié)果進行篩選。此階段基于地名地址庫進行分詞，而不另外建立一個字典。由于地址庫記錄分級存儲的數(shù)據(jù)結(jié)構(gòu)，可以把記錄的每一級看成一個“詞語”，從而使地址庫擁有字典的基本功能。用戶輸入：珠海翠香

11、街道香寧四街124號xzqh表記錄：（省略部分屬性，另為使例子易于理解，其中部分地名為虛構(gòu)）   id province  city county   town    street   1 廣東省 珠海市 香洲區(qū) 梅華街道 梅華西路   2 廣東省 珠海市 香洲區(qū) 梅華街道 香寧四街   3 廣東省 珠海市 香洲區(qū) 翠香街道 人民西路   4 廣東

12、省 珠海市 香洲區(qū) 翠香街道 紫荊路   5 廣東省 珠海市 香洲區(qū) 翠香街道 香寧三街一、 對地址庫每個級別的地址分別賦予不同的權(quán)重，以區(qū)分不同級別的重要程度。比如：市級為1，縣區(qū)級為2，鎮(zhèn)街級為3，道路級為4。根據(jù)用戶輸入對每條記錄進行加權(quán)計算，匹配記錄的每級字段，如果用戶輸入擁有該級別的“詞語”則該記錄權(quán)重值上升該級別的權(quán)重，匹配完一條記錄后獲得該條記錄的最終權(quán)重值。匹配完所有記錄后獲得地址庫中存在的最高權(quán)重值。此過程應(yīng)允許用戶輸入地名簡寫，比如“珠?！睉?yīng)可以匹配“珠海市”。中間結(jié)果：   id provin

13、ce  city co     unty   town    street  權(quán)重值   1 廣東省 珠海市 香洲區(qū) 梅華街道 梅華西路  12 廣東省 珠海市 香洲區(qū) 梅華街道 香寧四街  53 廣東省 珠海市 香洲區(qū) 翠香街道 人民西路  44 廣東省 珠海市 香洲區(qū) 翠香街道 紫荊路  4&#

14、160;  5 廣東省 珠海市 香洲區(qū) 翠香街道 香寧三街  4二、 拋棄與最高權(quán)重值差距過大的記錄，對剩余記錄按權(quán)重值進行分組，對每個分組進行差異值檢查，以進一步提高精確度。如果用戶輸入字符全部存在于記錄的地址中，則兩者差別為0，如果有一個字符不存在于記錄地址中，則差別為1，以此類推。匹配剩余所有記錄后獲得所有記錄與用戶輸入的差異值以及用戶輸入在每個分組中的最小差異值。（連續(xù)的阿拉伯數(shù)字當成一個字符）中間結(jié)果：珠海翠香街道香寧四街124號   id province  city county&

15、#160;  town    street  權(quán)重值 差異值2 廣東省 珠海市 香洲區(qū) 梅華街道 香寧四街  5    4（最?。? 廣東省 珠海市 香洲區(qū) 翠香街道 人民西路  4    64 廣東省 珠海市 香洲區(qū) 翠香街道 紫荊路  4    6   5 廣東省 珠海市 香洲區(qū) 翠香

16、街道 香寧三街  4    3（最?。┤?、 在每個分組中對記錄進行篩選，拋棄與該分組最小差異值過大的記錄，獲得第一階段結(jié)果。中間結(jié)果：   id province  city county   town    street  權(quán)重值 差異值2 廣東省 珠海市 香洲區(qū) 梅華街道 香寧四街  5    4   5 廣東省 

17、珠海市 香洲區(qū) 翠香街道 香寧三街  4    3第二階段算法及示例如下：   在xzqh獲取地址范圍之后，就可以從address表中提取出相應(yīng)范圍的記錄，進行二次匹配。以下為篩選出來的記錄： id  parentID address  1   2  124號 2   2  南方大廈   3   5 

18、0;1242號 4   5  55號一、 按分組進行匹對。把用戶輸入字符去除第一階段完全對應(yīng)的屬性后得出新的匹配字段。比如parentID為2的第一分組匹配字段為“翠香街道124號”，parentID為5的第二分組匹配字段為“香寧四街124號”，這是為了剔除用戶輸入信息的已使用部分，以精確匹配結(jié)果。計算每條記錄address字段與匹配字段的匹配值（address字段與匹配字段相同的字符個數(shù)）和相似度（計算公式為：匹配值/address字段長度）。   id  parentID addr

19、ess  匹配值  相似度 1   2  124號   2  100% 2   2 南方大廈124號 2  33%  3   5  1242號   1  50% 4   5  55號

20、0;  1  50%二、 結(jié)合匹配值和相似度，剔除命中可能性太低的結(jié)果。比如第一分組，在匹配值相同時選取相似度更高的記錄；第二分組中由于匹配值太低，相似度沒有參考意義，兩條記錄都應(yīng)舍去。故第二階段結(jié)果為   id  parentID address  匹配值  相似度 1   2  124號   2  100%最終結(jié)果：第一階段找到了可能性最高的兩條記錄，其中第一條記錄在address表中找到了更詳細的地址，以該地址代替原先記錄。故最終應(yīng)返回用戶以下結(jié)果：   id province  city county   town    r