[發明專利]基于滑動窗口最大匹配算法的地址匹配方法

有效

• 申請號: 201510092653.1
• 申請日: 2015-03-02
• 公開（公告）號: CN104615782B
• 公開（公告）日: 2017-10-10
• 發明（設計）人: 李曉林;魏運運;張彥鐸;盧濤;段艷會;張玉敏;黃爽;萬永靜;楊威
• 申請（專利權）人: 武漢工程大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 湖北武漢永嘉專利代理有限公司42102
• 代理人: 王丹

技術領域

本發明涉及計算地址字符串中所有可能的行政區劃，具體涉及基于滑動窗口最大匹配算法的地址匹配方法。

背景技術

數字城市是以空間信息為核心的城市信息系統體系，而在數字城市的信息資源的集成和融合中，地名地址匹配是一項非常關鍵的技術。地名地址匹配，又稱為地理編碼，它是基于空間定位技術的一種編碼方法。

國外的地理賦值技術已基本成熟，但是對于中文地址的地理賦值方法還有待研究。一是因為中英文之間的差異，比如中文地址的詞與詞之間沒有空格隔開等問題的存在。二是因為我國的現有地名，地址體系異常復雜，地址系統混亂、無需、缺乏規律性和統一的標準。因此，國外已有的地理賦值技術并不適合中國國情，直接套用國外的地理賦值技術是不可行的。

目前，國內各部門與學者已經陸續開展了中國地質標準化的研究，為標準地址庫的建立奠定了良好的數據基礎。但是普通百姓在輸入其需要定位的地址時，往往輸入的地址是一些模糊的中文地址。以地址“湖北武漢洪山江蘇省鼓樓區辦事處”為例，可能有幾種不同的行政區劃，如何通過算法計算出所有的行政區劃，然后找出可信度最大的行政區劃來進行準確的定位，是我國進入實用階段的一個重要問題。

發明內容

針對上述現有技術中的不足，本發明的目的在于提供一種基于滑動窗口最大匹配算法的地址匹配方法，能夠有效減少數據庫的查詢訪問次數，加快匹配速度。

為了實現上述發明的目的，本發明提供了以下技術方案：一種基于滑動窗口最大匹配算法的地址匹配方法，其特征在于：它包括以下步驟：

S1、建立行政區劃表：

行政區劃表中包含行政區劃信息，每個行政區劃信息包含以下字段：序號、行政區劃名稱、行政區劃級別，三者一一對應；

S2、對行政區劃表建立匹配查詢關系：

根據行政區劃級別之間的隸屬關系對行政區劃信息建立關聯性；

匹配查詢：在給定一個查詢字符串時，根據上述關聯性輸出對應的行政區劃結果集，行政區劃結果集包含與該行政區劃匹配父行政區劃，直到最高行政區劃級別；

S3、設置滑動窗口，進行匹配查詢：

3.1、讀入待匹配地址字符串，設置滑動窗口的起始位置為待匹配地址字符串的第一位，截止位置為待匹配地址字符串的最后一位，取滑動窗口中的字符組成查詢字符串，進行匹配查詢；若匹配成功，則輸出對應的行政區劃結果集；若匹配不成功，則進行下一步；

3.2、滑動窗口的起始位置不變，將滑動窗口的截止位置向前移一位，取滑動窗口中的字符組成查詢字符串，進行匹配查詢；若匹配成功，則輸出對應的行政區劃結果集，將滑動窗口的起始位置設置為剩余字符串的開始，截止位置設置為剩余字符串的最后一位，繼續進行匹配查詢，直至截止位置減去起始位置的值小于2，進行下一步；若匹配不成功，則返回本步驟開始，繼續進行匹配查詢；

3.3、將滑動窗口的起始位置向后移一位，截止位置為待匹配地址字符串的最后一位，取滑動窗口中的字符組成查詢字符串，進行匹配查詢；若匹配成功，則輸出對應的行政區劃結果集；若匹配不成功，則返回本步驟開始，繼續進行匹配查詢，直至截止位置減去起始位置的值小于2，結束匹配查詢。

按上述方案，所述的匹配查詢包括完全匹配查詢和部分匹配查詢，若查詢字符串包含行政區劃特征詞則進行完全匹配查詢，否則進行部分匹配查詢；

完全匹配查詢：在給定一個包含行政區劃特征詞的查詢字符串時，根據上述關聯性輸出對應的行政區劃結果集，行政區劃結果集包含與該行政區劃匹配父行政區劃，直到最高行政區劃級別；

部分匹配查詢：在給定一個不含行政區劃特征詞的查詢字符串時，根據上述關聯性輸出對應的行政區劃結果集，行政區劃結果集包含與該行政區劃匹配的父行政區劃，直到最高行政區劃級別；

其中行政區劃隸屬于與該行政區劃匹配的父行政區劃；行政區劃結果集包含所有可能的行政區劃的集合。

本發明的有益效果為：

1、將地理賦值的兩個環節“地址分詞”與“地址匹配”整合到了一起，即在分詞的同時進行數據庫匹配，實現了在分詞完成的同時也查找到了所匹配的記錄；通過這種方法可以有效的減少數據庫的查詢訪問次數，從而加快匹配速度。

2、該算法通過移動窗口最大匹配算法，截取字符串中的字符對行政區劃表進行完全匹配查詢或部分查詢匹配，返回對應的行政區劃結果集，包含與該行政區劃匹配父行政區劃，直到省級。

具體實施方式

下面結合具體實例對本發明作進一步說明。