[發明專利]壓縮流數據的方法及設備

有效

• 申請號: 201410653071.1
• 申請日: 2014-11-17
• 公開（公告）號: CN105680868B
• 公開（公告）日: 2019-04-12
• 發明（設計）人: 李震國;羅戈;易珂;范偉;何誠
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 北京龍雙利達知識產權代理有限公司 11329
• 代理人: 王君;肖鸝

1.一種壓縮流數據的方法，其特征在于，包括：

獲取流數據，其中，所述流數據包括多個數據點，所述多個數據點中的每個數據點包括采集所述每個數據點的采集時間以及在所述采集時間所采集的數據值；

獲取預定義的最大誤差，根據所述多個數據點和所述最大誤差，構造多個線段，所述多個線段互不相交，所述多個線段中的每個線段表示以時間為自變量的線性函數，并且當所述自變量的值為所述采集時間時，所述函數的函數值與所述采集時間所采集的數據值之差的絕對值小于或等于所述最大誤差；

根據所述多個線段，確定目標分段線性函數，其中，所述目標分段線性函數包括多個線性函數，所述多個線性函數中的每兩個線性函數的自變量的取值范圍的交集最多包括一個值；

根據所述目標分段線性函數，輸出參考數據點，所述參考數據點用于表示壓縮后的流數據，其中，所述參考數據點包括所述目標分段線性函數的連續點和間斷點，所述連續點為所述目標分段線性函數的拐點，所述間斷點為所述目標分段線性函數的非連續點。

2.根據權利要求1所述的方法，其特征在于，所述根據所述多個數據點和所述最大誤差，構造多個線段，包括：

根據所述多個數據點和所述最大誤差，構建擴展多邊形，其中，所述擴展多邊形用于表示所述多個線段所在的區域；

在所述擴展多邊形的基礎上計算鏈表，其中，所述鏈表包括信息域C[k]以及指針域pred[k]，所述信息域C[k]用于表示所述多個線段，所述指針域pred[k]用于表示所述信息域C[k]指向信息域C[pred[k]]，k為不等于1的非負整數，每一個k的取值所對應的C[k]用于表示所述多個線段中的一個線段。

3.根據權利要求2所述的方法，其特征在于，所述C[k]通過如下的表達式得到：

條件1為：k＝0；

條件2為：k＝3或者k≥5且cw(C[k-2])位于cw(nw(C[k-3]))的左側；

對k＝0，pred[0]為空；

對k≠0，若C[k]＝cw(nw(C[k-3]))，則pred[k]＝k-3；

若C[k]＝cw(C[k-2])，則pred[k]＝k-2；

其中，w₀為起始窗口，cw(·)表示關閉窗口，nw(·)表示下一個窗口，所述窗口表示所述多個數據點構成的擴展多邊形中上鏈的一點與下鏈的一點之間的連線段，所述起始窗口為所述擴展多邊形構成的窗口中在時序上最早的一個窗口，所述關閉窗口為所述擴展多邊形的任意一個窗口的可見區域的最右側的窗口，所述可見區域為所述任意一個窗口的右側的數據點中與所述任意一個窗口的連線位于所述擴展多邊形內部的數據點構成的區域，所述右側為沿著時間增加的方向，所述下一個窗口為所述關閉窗口右側的第一個數據點所在的窗口。

4.根據權利要求2或3所述的方法，其特征在于，所述根據所述多個線段，確定目標分段線性函數，包括：

根據所述多個線段之間的指向關系，確定所述目標分段線性函數。

5.根據權利要求2或3所述的方法，其特征在于，所述根據所述多個線段，確定目標分段線性函數，包括：

對所述鏈表進行剪枝，以使得不同的k，pred[k]互不相等；

根據所述剪枝以后的鏈表，確定所述目標分段線性函數。

6.根據權利要求5所述的方法，其特征在于，所述鏈表還包括計數域ref[k]，用于表示所述信息域C[k]被指向的個數，

若pred[k+2]＝k且pred[k+3]＝k，則ref[k]＝2；

若pred[k+2]＝k且pred[k+3]≠k，則ref[k]＝1；

若pred[k+2]≠k且pred[k+3]＝k，則ref[k]＝1；

若pred[k+2]≠k且pred[k+3]≠k，則ref[k]＝0。

7.根據權利要求6所述的方法，其特征在于，所述對所述鏈表進行剪枝，包括：

將與ref[j]＝0對應的C[j],pred[j],ref[j]從所述鏈表中刪除，并更新ref[pred[j]]，所述j表示使得所述ref[j]等于0的指標。