[發明專利]一種運用于導航終端的快速模糊容錯搜索交叉路口的方法

在審

• 申請號: 201410530920.4
• 申請日: 2014-10-10
• 公開（公告）號: CN104268259A
• 公開（公告）日: 2015-01-07
• 發明（設計）人: 季剛;涂巖愷;黃家乾;時宜
• 申請（專利權）人: 廈門雅迅網絡股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G01C21/34
• 代理公司: 廈門市精誠新創知識產權代理有限公司 35218
• 代理人: 巫麗青

技術領域

本發明涉及電子導航技術領域，具體涉及一種運用于導航終端的快速模糊容錯搜索交叉路口的方法。

背景技術

隨著車載導航系統應用技術的發展，車載導航終端以及軟件也更加成熟，導航數據信息已逐步完善。車載導航終端對于沒有固定名稱的地址信息-交叉路口的檢索還處于較為初級的階段，交叉路口是指平面交叉路口，即兩條或者兩條以上道路在同一平面相交的部位。在主流的導航終端中，普遍提供交叉路口檢索功能，供駕駛人員檢索道路交叉路口點情況，方便行車駕駛。交叉路口檢索基本方式是，用戶輸入兩條道路名稱，導航終端根據用戶輸入信息，檢索出這兩條道路的交叉路口點。

目前交叉路口檢索存在的一個問題是，用戶需要清楚地知道要檢索的兩條道路名字全稱，當用戶進行交叉路口檢索，輸入的道路名稱不全或順序有誤時，則無法檢索到要查找的道路交叉路口。提高交叉路口檢索功能的使用便捷性，是車載導航應用中需要解決的問題。

發明內容

解決上述技術問題，本發明提供了一種運用于導航終端的快速模糊容錯搜索交叉路口的方法，使得用戶在輸入道路名稱不全甚至道路名稱順序有誤的情況下，仍然能夠快速地搜索到想要了解的道路交叉路口信息。

為了達到上述目的，本發明所采用的技術方案是，一種運用于導航終端的快速模糊容錯搜索交叉路口的方法，該方法包括：

根據原始道路數據中的道路索引號遍歷所有道路名稱，建立兩級索引機制，第一級索引機制以道路名稱中所含單字為索引項，每一單字索引項與其對應的道路索引號集合相關聯，第二級索引機制以根據道路索引號排序的道路名稱為道路索引項，每一道路索引項與其相交的道路條數相關聯，

利用上述兩級索引機制獲取交叉路口搜索結果，包括步驟：對用戶檢索輸入的道路名稱做拆分預處理，利用第一級索引機制獲取搜索結果道路的索引號集合，利用第二級索引機制獲取搜索結果道路的交叉路口點。

進一步的，第一級索引機制以道路名稱中所含單字為索引項，并根據單字的GB2312碼值大小對單字索引項進行排列，構成第一索引文件，該第一索引文件中，每一單字索引項包括“單字”、“在第二索引文件中的偏移地址”和“道路索引號個數”三個字段，所述第二索引文件的存儲結構為：每一單字索引項對應的道路索引號集合。

進一步的，第二級索引機制以根據道路索引號排序的道路名稱為道路索引項，并根據道路索引號大小對道路索引項進行排列，構成第三索引文件，該第三索引文件中，每一道路索引項包括“在第四索引文件中的偏移地址”、“道路名稱長度”和“與其相交的道路條數”三個字段，所述第四索引文件的存儲結構為：道路中文名稱+【交叉點經度+交叉點緯度+另外一條道路索引號】*與其相交的道路條數。

進一步的，利用上述兩級索引機制獲取交叉路口搜索結果步驟中，利用第二級索引機制獲取搜索結果道路的交叉路口點后還包括步驟：對檢索結果做相關性排序，所述排序方式為正序匹配和逆序匹配。

進一步的，利用第一級索引機制獲取搜索結果道路的索引號集合的步驟中，采用的是折半查找法。因在第一索引文件中已將各個單字按碼值從小到大排序存儲，利用折半查找法，能夠迅速查找到各個單字所對應的的道路索引號集合。然后對這幾組道路索引號集合進行交集運算。因為在建立索引時，已對各集合中的道路索引號做了排序處理，可以大大加快交集運算速度。

本發明通過采用上述技術方案，與現有技術相比，具有如下優點：

本發明提出一種在導航終端中快速模糊容錯搜索交叉路口的方法，通過合理地設計兩級索引文件結構，對檢索結果進行相關性排序，使得用戶在輸入道路名稱不全甚至道路名稱順序有誤的情況下，仍然能夠快速地搜索到想要了解的道路交叉路口信息。大大提高了交叉路口檢索功能的使用便捷性。

附圖說明

圖1是本發明的實施例的第一索引文件的內容格式。

圖2是本發明的實施例的第三索引文件的內容格式。

具體實施方式

現結合附圖和具體實施方式對本發明進一步說明。

本發明一種運用于導航終端的快速模糊容錯搜索交叉路口的方法，該方法包括：

該方法主要分為兩個步驟：

(1)根據原始道路數據中的道路索引號遍歷所有道路名稱，建立兩級索引機制，該步驟的目的是生成兩級索引文件，為后續交叉路口檢索做準備。其主要包括以下步驟：

①建立以道路名稱中所含單字為索引項的第一級索引機制。第一級索引機制以道路名稱中所含單字為索引項，每一單字索引項與其對應的道路索引號集合相關聯，