[發明專利]基于LZW算法的GPS軌跡數據的壓縮方法

有效

• 申請號: 201810920643.6
• 申請日: 2018-08-14
• 公開（公告）號: CN109286399B
• 公開（公告）日: 2022-04-15
• 發明（設計）人: 趙欽佩;饒衛雄;史揚;李江峰
• 申請（專利權）人: 同濟大學
• 主分類號: H03M7/30
• 分類號: H03M7/30;G06F16/29
• 代理公司: 上海科律專利代理事務所(特殊普通合伙) 31290
• 代理人: 葉鳳

1.一種基于LZW算法的GPS軌跡數據的壓縮方法，其特征在于：將傳統的軌跡數據結合路網信息，通過地圖匹配的辦法將原始軌跡數據轉化為使用路段序列表示的軌跡數據，之后為了便于處理，自定義一種編碼規則將路段軌跡數據轉化成文本類型的數據，最后利用LZW壓縮算法對轉化后的文本類型的軌跡數據進行壓縮和解壓縮；

包括如下步驟：

步驟1獲取GPS軌跡數據

原始的GPS軌跡數據包括了時間戳(time)、位置坐標的經緯度(longitude和latitude)以及軌跡的ID(tid)；

步驟2地圖匹配

使用地圖匹配的相關方法將步驟1獲取的GPS軌跡數據映射到地圖上得到了用路段序列表示的軌跡數據；

步驟3建立倒排表

通過步驟2地圖匹配后，將軌跡表示成一個路段的序列p₁→p₂→…→p_n,p_n∈S，S是路網路段集合；以所有的路段的標號作為字符集，對路段的索引進行格式轉換；為了處理的便利，需用建立倒查表，從路段倒查經過這個路段的所有軌跡的標號；

步驟4軌跡路段號的轉換

由于步驟3中路段號定義為一個整數，為了便于壓縮處理，我們自定義一種方法將其轉化為字符串，因為一個字符為8位，不夠存儲所有的字段號，需要將路段號轉化成更高位數的“字符”即多位字符串；

步驟5利用LZW算法進行壓縮

將經過步驟4轉化后的軌跡數據集合通過LZW算法進行壓縮，從而實現了對軌跡數據的壓縮功能；

壓縮算法具體步驟如下:

步驟1.開始時字典是只包含所有標準字符集的初始字典；定義現碼序列current_seq，后置碼變量next_char，輸出字符串變量output

步驟2.將需要壓縮的字符串s中下一個帶壓縮字符賦值給后置碼變量next_char

步驟3.當進入判斷：current_seq+next_char是否在字典里

(1)如果“是”，則將current_seq+next_char賦值給current_seq

(2)如果“否”，則對current_seq進行編譯后添加到輸出變量output中，并把current_seq+next_char添加到字典里作為一個新的編碼序列；最后把next_char賦值給current_seq

步驟4.當進入判斷：字符串s是否全部被取出

(1)如果“是”，則對current_seq進行編譯后添加到輸出變量output中，輸出output，壓縮過程結束；

(2)如果“否”，返回步驟2

所述的解壓縮算法具體步驟如下：

步驟1.開始時字典是只包含所有標準字符集的初始字典；定義前置碼previous_code，現碼current_code，輸出變量output

步驟2.將需要解壓的編碼序列s中下一個帶壓縮字符賦值給前置碼previous_code，通過字典解壓后添加到output；

步驟3.當進入判斷：編碼序列s是否全部被解壓

(1)如果“是”，獲得解壓結果output，解壓過程結束

(2)如果“否”，則將s中下一個需要解壓的編碼賦值給current_code，并通過字典把current_code解壓后添加到output；對previous_code進行解碼后連同current_code解碼后的第一個字符作為一個新的編碼序列添加到字典中；把previous_code和current_code進行合并后儲值給previous_code；返回步驟3。