[發(fā)明專利]基于LZW算法的GPS軌跡數(shù)據(jù)的壓縮方法

有效

• 申請?zhí)枺?/td>: 201810920643.6
• 申請日: 2018-08-14
• 公開（公告）號(hào): CN109286399B
• 公開（公告）日: 2022-04-15
• 發(fā)明（設(shè)計(jì)）人: 趙欽佩;饒衛(wèi)雄;史揚(yáng);李江峰
• 申請（專利權(quán)）人: 同濟(jì)大學(xué)
• 主分類號(hào): H03M7/30
• 分類號(hào): H03M7/30;G06F16/29
• 代理公司: 上海科律專利代理事務(wù)所(特殊普通合伙) 31290
• 代理人: 葉鳳

本發(fā)明涉及一種壓縮算法，具體為一種基于LZW算法的GPS軌跡數(shù)據(jù)的壓縮方法，本方法將傳統(tǒng)的軌跡數(shù)據(jù)結(jié)合路網(wǎng)信息，通過地圖匹配的辦法將原始軌跡數(shù)據(jù)轉(zhuǎn)化為使用路段序列表示的軌跡數(shù)據(jù)，之后為了便于處理，自定義一種編碼規(guī)則將路段軌跡數(shù)據(jù)轉(zhuǎn)化成文本類型的數(shù)據(jù)，最后利用LZW壓縮算法對轉(zhuǎn)化后的文本類型的軌跡數(shù)據(jù)進(jìn)行壓縮和解壓縮。本發(fā)明通過運(yùn)用地圖匹配、映射軌跡、路段號(hào)轉(zhuǎn)換等處理方法，將軌跡數(shù)據(jù)轉(zhuǎn)化成文本數(shù)據(jù)的形式，從而可以使用LZW算法對其進(jìn)行壓縮。與其它算法相比，本方法在保證運(yùn)行效率的同時(shí)，保證了壓縮率。

技術(shù)領(lǐng)域

本發(fā)明涉及一種壓縮算法。

背景技術(shù)

基于位置信息(location-acquisition)的技術(shù)的發(fā)展，我們可以獲得大量的軌跡信息，代表了行人，車輛，野生動(dòng)物，颶風(fēng)等移動(dòng)信息。軌跡數(shù)據(jù)屬于時(shí)空數(shù)據(jù)(spatiotemporal data)[1]的一種，一條軌跡記錄了移動(dòng)物體在一連串采樣時(shí)間下的位置信息。比如一個(gè)物體的移動(dòng)軌跡為：p₁p₂…p_n，每個(gè)點(diǎn)包含了移動(dòng)物體的地理位置坐標(biāo)和時(shí)間戳信息，如p＝(x,y,t)。軌跡信息可以幫助我們更好地了解移動(dòng)物體的行為特點(diǎn)，促進(jìn)了基于位置的應(yīng)用，智能傳輸網(wǎng)絡(luò)，智慧城市的發(fā)展。這些應(yīng)用的流行，反過來刺激了軌跡數(shù)據(jù)挖掘的研究，軌跡數(shù)據(jù)挖掘已經(jīng)逐漸成為跨學(xué)科的重要的研究領(lǐng)域，吸引了大量領(lǐng)域(如計(jì)算機(jī)科學(xué)，社會(huì)學(xué)，地理學(xué))的關(guān)注。

設(shè)備(如手機(jī)，平板等)的廣泛使用，使得我們可以得到大量的刻畫物體運(yùn)動(dòng)的時(shí)空數(shù)據(jù)。據(jù)統(tǒng)計(jì)，如果我們每隔15秒采集一次GPS數(shù)據(jù)，每天產(chǎn)生8億條數(shù)據(jù)，一個(gè)月3T的數(shù)據(jù)量。隨著采集設(shè)備和應(yīng)用的增加，以及時(shí)間的推移，數(shù)據(jù)量的增長難以想象，大量的數(shù)據(jù)使得存儲(chǔ)，查詢，分析和通信造成困難。由于軌跡數(shù)據(jù)一般數(shù)量巨大，并且很多點(diǎn)是冗余(重復(fù))和噪聲點(diǎn)，為了儲(chǔ)存并傳輸軌跡數(shù)據(jù)，應(yīng)用必須擁有較大的儲(chǔ)存空間和傳輸速率，而這對于一些耗電量和成本敏感的傳感器網(wǎng)絡(luò)來說較難做到。因此，對軌跡數(shù)據(jù)的壓縮成為軌跡數(shù)據(jù)挖掘的一個(gè)研究熱點(diǎn)。

根據(jù)輸入的軌跡數(shù)據(jù)的不同，目前常見的軌跡壓縮算法一般分為三類：離線壓縮，在線壓縮，基于語義的壓縮。顧名思義，離線壓縮是在軌跡數(shù)據(jù)完全獲得以后進(jìn)行的壓縮，在線壓縮是隨著物體的移動(dòng)，實(shí)時(shí)地進(jìn)行壓縮，而基于語義的壓縮利用了軌跡的一些具有語義含義的特殊點(diǎn)進(jìn)行壓縮。

離線壓縮：給定一條包含一系列完整帶有時(shí)間戳的點(diǎn)的軌跡，離線壓縮算法目標(biāo)是在誤差范圍內(nèi)，舍棄一些點(diǎn)，生成一條近似軌跡。算法的思路類比線簡化問題(linesimplification problem)，而線簡化問題在計(jì)算機(jī)圖形學(xué)和制圖學(xué)方面已經(jīng)有了成熟的研究。一個(gè)經(jīng)典的算法是Douglas-Peucker[2]，廣泛用于曲線化直問題。原始的Douglas-Peucker時(shí)間復(fù)雜度為O(N²)，N為軌跡點(diǎn)的個(gè)數(shù)，它的優(yōu)化版本的時(shí)間復(fù)雜度為O(NlogN)，為了保證生成的近似估計(jì)是最優(yōu)的，Bellman提出了一種動(dòng)態(tài)規(guī)劃的算法，時(shí)間復(fù)雜度為O(N³)。[3，4]中對軌跡點(diǎn)的角度進(jìn)行范圍限制，在一定的最大誤差范圍內(nèi)對軌跡點(diǎn)進(jìn)行壓縮。

在線壓縮：許多應(yīng)用要求軌跡傳輸是實(shí)時(shí)的，許多在線壓縮算法處理新獲取的數(shù)據(jù)來決定是否將其保留在壓縮軌跡中。主要有兩類在線壓縮算法，一種是基于窗口(window)的算法，比如滑動(dòng)窗口(Sliding Window)算法[5]和開窗口(Open Window)算法[6]，另一種主要基于移動(dòng)物體的速度和方向。

基于語義的壓縮：在對軌跡進(jìn)行壓縮時(shí)，盡量保留其語義信息。比如，對于一條行人的游玩軌跡，行人的停留點(diǎn)，拍照點(diǎn)，方向劇烈轉(zhuǎn)換的點(diǎn)比起其他的點(diǎn)，顯然有更重要的語義含義。