[發明專利]一種使用二進制字符串來比較行程路徑的方法

在審

• 申請號: 201710850727.2
• 申請日: 2017-09-20
• 公開（公告）號: CN107818131A
• 公開（公告）日: 2018-03-20
• 發明（設計）人: 繆涵澄;齊石;金偉
• 申請（專利權）人: 上海保橙網絡科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海天翔知識產權代理有限公司31224
• 代理人: 劉粉寶

技術領域

本發明涉及一種比較行程路徑的方法，特別涉及一種使用二進制字符串來比較行程路徑的方法。

背景技術

已有的比較行程路徑的方法基本都基于抓取路名來組成路名-方向-距離的辦法標識每一個行程，通過切分字符串來進行比較，使用起來很不方便，且存儲成本高。

發明內容

本發明要解決的技術問題是提供一種無需抓取路名，節約存儲成本的使用二進制字符串來比較行程路徑的方法。

為達到上述目的，本發明的技術方案如下：

一種使用二進制字符串來比較行程路徑的方法，所述方法包括如下步驟：

(1)開始，通過智能手機中的GPS定位模塊來得到用戶駕駛外部路徑數據，其中數據包括GPS定位信息；

(2)將上述數據進行遍歷，對第一個行程進行下述處理；

(3)將第一個行程路徑的所有GPS定位點，通過RDP算法將行程上的點進行迭代平滑化，將路徑上偏移點、誤差點剔除，將主路徑點保留，并記錄下來；

(4)判斷平滑后的點是否過少，判斷條件為：是否仍然構成原路徑相似路線，通過所有點距離累加進行判斷，如果所有點的累加距離與原來軌跡總距離相差超過30％，表示平滑后的點過少，則返回步驟(2)直至平滑后的點正常；如果所有點的累加距離與原來軌跡總距離相差不超過30％，表示平滑后的點正常，則繼續下一步驟；(5)將步驟3中保留下來的主路徑點通過DDA算法將平滑后的路徑點補齊成直線，得到由多個線段組成的路徑圖；

(6)通過將世界經緯度按400平方米來劃分，通過經度和緯度給出編號，具體是從0，0點開始，每0.00005經度和每0.00005緯度計算為一個矩形，將矩形按緯度順序排序后再按經度順序排序，給出每個矩形唯一對應的編號；

(7)如果路徑點所在的矩形編號為1則是起點，如果路徑點所在的矩形編號等于路徑點總數則為終點；

(8)將所有補全后的路徑點篩選出來，判斷補全后的路徑點是否在矩形的邊界上，如果在邊界上，則進入下一步驟；如果不在邊界上，則返回步驟(5)，直至補全后的路徑點在矩形的邊界上；該步驟是找出再矩形邊界上的點，用于確定路徑經過了哪些矩形；

(9)將所有步驟(8)保留下的點進行計算，查找出每個點經過的矩形，將矩形的編號按順序排列，拼接成一個字符串，并且將原始行程記錄到的第一個GPS點和原始行程記錄到的最后一個GPS點放入開始和結尾處；

(10)將拼接完成后的字符串進行處理，轉換為64位二進制字符串；

(11)將轉換為64位二進制字符串的所有行程路徑標識數據存入數據庫；

(12)對是否還有行程路徑未處理進行判斷，具體判斷方法為：通過數據庫中查詢是否有未處理行程，已處理會加上標記，未處理則沒有；如有未處理的，則將下一個行程作為第一個行程返回步驟3，直至沒有未處理的行程路徑；如沒有未處理的，則進入下一步驟；

(13)在所有行程路徑的標識數據處理完成后，對于所有行程進行兩兩之間的比較，比較次數為行程數的階乘次，比較方法為最小編輯距離法；

(14)最小編輯距離對否小于閾值進行判斷，若相似程度小于80％，則跳過；若相似程度大于80％，則存入相似行程數據庫，編輯距離算法返回相似比例；

(15)結束。

在本發明的一個實施例中，步驟(3)中的RDP算法即抽吸算法，其原理為：一段軌跡頭尾連接成一條線，如果其間所有的點距離這條線的距離都小于3KM，則去掉中間所有的點；如果以上條件不滿足，則取距離最大的點，把原始軌跡拆分成兩條軌跡，重復以上迭代，直至完成，其中效果為剔除偏移點、誤差點，也進行了迭代平滑。

在本發明的一個實施例中，步驟(8)中補全后的路徑點是否在矩形的邊界上的具體判斷方法為：將所有補全后的路徑點篩選出來，匹配是否第五位小數為0或5，第五位小數為0或5就是邊界上的點，否則就不是邊界上的點。

在本發明的一個實施例中，步驟(13)中的最小編輯距離算法是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數；許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符；一般來說，編輯距離越小，兩個串的相似度越大。

通過上述技術方案，本發明的有益效果是：

本發明只需將行程信息轉換成二進制字符串就可以進行比較，無需抓取路名，節約了存儲成本；且可以讓用戶在完成行程之后的30秒內，匹配出與自己有相同行程路徑的行程信息。

本發明無需外接接口，只需要本地就可以完成所有處理。