鬼佬大哥大
  • / 23
  • 下載費用:30 金幣  

含冗余的數據壓縮與解壓縮的系統和方法.pdf

摘要
申請專利號:

CN201410743063.6

申請日:

2014.12.05

公開號:

CN105045783A

公開日:

2015.11.11

當前法律狀態:

實審

有效性:

審中

法律詳情: 實質審查的生效IPC(主分類):G06F 17/30申請日:20141205|||公開
IPC分類號: G06F17/30; G06F11/14 主分類號: G06F17/30
申請人: 莊顥; 王永東
發明人: 莊顥; 王永東
地址: 100094北京市海淀區北清路68號院24號樓C座601
優先權: 61/913,295 2013.12.07 US
專利代理機構: 北京紐盟知識產權代理事務所(特殊普通合伙)11456 代理人: 許玉順
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201410743063.6

授權公告號:

|||

法律狀態公告日:

2017.01.04|||2015.11.11

法律狀態類型:

實質審查的生效|||公開

摘要

本發明公開了含冗余的數據壓縮與解壓縮的系統和方法,用于處理數據的裝置及計算機實現的方法。該裝置包括存儲第一歷史數據的存儲器,以及至少一個處理器。該至少一個處理器設置成接收輸入數據,判定第一歷史數據與輸入數據的一個或多個部分之間的關系,生成反映上述關系的一個或多個引用令牌,以及傳輸一個或多個引用令牌至接收設備。

權利要求書

1.一種裝置,包括:
存儲第一歷史數據的存儲器;以及至少一個處理器,
該至少一個處理器設置成:
接收輸入數據;
判定所述第一歷史數據與所述輸入數據的一個或多個部分之間的
關系;
生成反映所述關系的一個或多個引用令牌;以及
傳輸所述一個或多個引用令牌至接收設備。
2.根據權利要求1所述的裝置,其中,所述一個或多個引用令牌允
許所述輸入數據的所述一個或多個部分在所述接收設備中重建。
3.根據權利要求1所述的裝置,其中,對所述第一歷史數據與所述
輸入數據的所述一個或多個部分之間的所述關系的所述判定包含判定
所述輸入數據的一個部分是否與所述第一歷史數據的任一部分相匹
配,所述至少一個處理器進一步設置成:響應于所述輸入數據的所述
一個部分與所述第一歷史數據的任一部分不相匹配的判定,傳輸所述
輸入數據的所述一個部分至所述接收設備。
4.根據權利要求1所述的裝置,其中,所述第一歷史數據包括一個
或多個第一數據塊,每一第一數據塊關聯一個或多個第一簽名,所述
一個或多個第一數據塊包含工作數據塊,對所述第一歷史數據與所述
輸入數據的所述一個或多個部分之間的所述關系的所述判定進一步包
含:
將一個或多個第二簽名與所述輸入數據關聯起來;以及
判定至少一個與所述工作數據塊關聯的第一簽名是否與至少一個
所述第二簽名相匹配。
5.根據權利要求4所述的裝置,其中,響應于所述工作數據塊的至
少一個第一簽名與至少一個所述第二簽名相匹配的判定,將與所述第
二簽名相匹配的所述第一簽名同所述工作數據塊的一部分相關聯起
來,將所述第二簽名同所述輸入數據的一部分相關聯起來,對所述第
一歷史數據與所述輸入數據的所述一個或多個部分之間的所述關系的
所述判定進一步包含:
判定所述工作數據塊的所述關聯部分與所述輸入數據的所述關聯
部分一致;以及
對與所述輸入數據的所述關聯部分一致的所述工作數據塊的所述
關聯部分,判定關于該所述工作數據塊的所述關聯部分的位置及大小
的信息,
生成第一引用令牌,所述第一引用令牌包含關于所述工作數據塊
的所述關聯部分的位置及大小的信息。
6.根據權利要求4所述的裝置,其中,所述裝置進一步包括存儲一
個或多個第二數據塊的數據存儲設備,每一第二數據塊與一個或多個
第三簽名關聯,對所述第一歷史數據與所述輸入數據的所述一個或多
個部分之間的所述關系的所述判定進一步包含:
響應于無所述第一簽名與任一所述第二簽名相匹配的判定,判定
是否至少一個所述第三簽名與至少一個所述第二簽名相匹配。
7.根據權利要求6所述的裝置,其中,對所述第一歷史數據與所述
輸入數據的所述一個或多個部分之間的所述關系的所述判定進一步包
含:
響應于所述至少一個所述第三簽名與至少一個所述第二簽名相匹
配的判定,從所述數據存儲設備中獲取與所述第三簽名關聯的所述第
二數據塊,該第三簽名與所述第二簽名相匹配,使獲取的所述第二數
據塊成為工作歷史數據塊。
8.根據權利要求5所述的裝置,其中,所述工作數據塊進一步包含
一個或多個數據區塊,至少一個所述第一簽名與至少一個所述數據區
塊關聯,并具有第一偏移,該第一偏移反映所述工作數據塊中的至少
一個數據區塊的位置,對關于所述工作數據塊的所述關聯部分的位置
及大小的信息的所述判定包含:
在所述工作數據塊中,相對于所述第一偏移所反映的位置正向和/
或反向查找與所述輸入數據的一個或多個部分相匹配的數據。
9.根據權利要求8所述的裝置,其中,至少一個所述第一簽名從諸
多子簽名中生成,每一子簽名從至少一個所述數據區塊的一部分中生
成。
10.根據權利要求4所述的裝置,其中,每一所述第一數據塊與一
個時間戳關聯,所述工作數據塊基于與所述工作數據塊關聯的所述時
間戳指定。
11.一種用于處理數據的計算機實現的方法,該方法包括:
接收輸入數據;
接收第一歷史數據;
判定所述第一歷史數據與所述輸入數據的一個或多個部分之間的
關系;
生成反映所述關系的一個或多個引用令牌;以及
傳輸所述一個或多個引用令牌至接收設備。
12.根據權利要求11所述的方法,其中,所述一個或多個引用令牌
允許所述輸入數據的所述一個或多個部分在所述接收設備中重建。
13.根據權利要求11所述的方法,其中,對所述第一歷史數據與所
述輸入數據的所述一個或多個部分之間的所述關系的所述判定包含判
定所述輸入數據的第一部分是否與所述第一歷史數據的任一部分相匹
配,所述方法進一步包括:
響應于所述輸入數據的所述第一部分與所述第一歷史數據的任一
部分不相匹配的判定,傳輸所述輸入數據的所述第一部分至所述接收
設備。
14.根據權利要求11所述的方法,其中,所述第一歷史數據包括一
個或多個第一數據塊,其中每一第一數據塊關聯一個或多個第一簽名,
所述一個或多個第一數據塊包含工作數據塊,對所述第一歷史數據與
所述輸入數據的所述一個或多個部分之間的所述關系的所述判定進一
步包含:
將一個或多個第二簽名與所述輸入數據關聯起來;以及
判定是否至少一個所述第一簽名與至少一個所述第二簽名相匹
配。
15.根據權利要求14所述的方法,其中,響應于所述工作數據塊的
至少一個第一簽名與至少一個所述第二簽名相匹配的判定,將與所述
第二簽名相匹配的所述第一簽名同所述工作數據塊的一部分相關聯起
來,將所述第二簽名同所述輸入數據的一部分相關聯起來,對所述第
一歷史數據與所述輸入數據的所述一個或多個部分之間的所述關系的
所述判定進一步包含:
判定所述工作數據塊的所述關聯部分與所述輸入數據的所述關聯
部分一致;以及
判定關于所述工作數據塊的所述關聯部分的位置及大小的信息,
生成第一引用令牌,所述第一引用令牌包含關于所述工作數據塊
的所述關聯部分的位置及大小的信息。
16.根據權利要求14所述方法,進一步包括從一個數據存儲設備接
收第二歷史數據,其中,每一第二數據塊與一個或多個第三簽名關聯,
對所述第一歷史數據與所述輸入數據的所述一個或多個部分之間的所
述關系的所述判定進一步包含:
響應于無所述第一簽名與任一所述第二簽名相匹配的判定,判定
是否至少一個所述第三簽名與至少一個所述第二簽名相匹配。
17.根據權利要求16所述的方法,其中,對所述第一歷史數據與所
述輸入數據的所述一個或多個部分之間的所述關系的所述判定進一步
包含:
響應于所述至少一個所述第三簽名與至少一個所述第二簽名相匹
配的判定,從所述數據存儲設備中獲取與所述第三簽名關聯的所述第
二數據塊,該第三簽名與所述第二簽名相匹配,使獲取的所述第二數
據塊成為工作歷史數據塊。
18.根據權利要求14所述的方法,其中,所述工作數據塊進一步包
含一個或多個數據區塊,至少一個所述第一簽名與至少一個所述數據
區塊關聯,并具有第一偏移,該第一偏移指示所述工作數據塊中的至
少一個數據區塊的位置,對關于所述工作數據塊的所述關聯部分的位
置及大小的信息的所述判定包含:
在所述工作數據塊中,相對于所述第一偏移所反映的位置正向和/
或反向查找與所述輸入數據的一個或多個部分相匹配的數據。
19.一種裝置,包括:
存儲歷史數據的存儲器;以及
至少一個處理器,該至少一個處理器設置成:
接收輸入數據;
生成一個或多個引用令牌,該引用令牌包含關于與所述輸入數據
相關聯的所述歷史數據的至少一部分的信息;以及
傳輸所述一個或多個引用令牌以及不在所述歷史數據中的所述輸
入數據的至少一部分至接收設備。
20.根據權利要求19所述的裝置,其中,所述關于所述歷史數據的
一部分的信息包含所述歷史數據的一部分的位置以及所述歷史數據的
一部分的大小。

說明書

含冗余的數據壓縮與解壓縮的系統和方法

本申請要求2013年12月7日提交的美國臨時專利申請號
No.61/913,295的優先權,以上申請的內容以引用方式全文并入于此。

技術領域

本發明涉及數據壓縮與解壓縮技術領域,特別涉及含冗余
的數據壓縮與解壓縮。

背景技術

通常通過計算機網絡或在存儲設備之間通過I/O(輸入/輸出)
界面轉存海量數據。例如,用戶可將整個主目錄從硬盤驅動器轉存至
非易失性存儲器(如閃存驅動器)以對硬盤驅動器進行定期備份,或者可
通過因特網轉存大文檔文件。轉存數據可包括冗余數據,即接收者已
經處理的數據,例如,用戶在閃存驅動器上生成硬盤驅動器定期備份
的情況下,將要傳輸至閃存驅動器的備份數據通常包括閃存驅動器中
已經存在的數據。同樣地,用戶通過因特網轉存文檔文件的情況下,
用戶可從網絡源(如一個服務器)下載文件、修正該文件并將該文件上傳
回該網絡源,如果該文檔文件未完全修正,上傳文件版本和下載文件
版本之間亦可存在公用數據。傳輸同時存儲于源和目標地的冗余數據
會導致I/O界面及因特網帶寬的低效利用。現有壓縮與解壓縮方法未能
利用這種數據冗余的優勢,因為在千兆字節到兆兆字節數據存儲上定
位冗余數據通常被認為費時且低效益。

因此,需要一種高效、冗余高定位概率的含巨量數據的冗
余數據查找技術,該技術可最小化冗余數據的傳輸并可提高I/O界面以
及因特網有限帶寬的利用。

發明內容

本發明實施方式的附加方面及優點在以下說明書中給出并
清楚描述,或從本發明實施方式的實施中得到。

根據一些實施方式,一種裝置包括存儲第一歷史數據的存
儲器;以及至少一個處理器,該處理器設置成接收輸入數據,判定所
述第一歷史數據和所述輸入數據的一個或多個部分之間的關系,生成
反映所述關系的一個或多個引用令牌,并傳輸所述一個或多個引用令
牌至接收設備。在一些實施方式中,所述引用令牌允許所述輸入數據
的所述一個或多個部分在所述接收設備中重建。在一些實施方式中,
響應于所述輸入數據的第一部分與所述第一歷史數據的任一部分不相
匹配的判定,所述至少一個處理器設置成傳輸所述輸入數據的第一部
分至所述接收設備。

根據一些實施方式,所述第一歷史數據包括一個或多個第
一數據塊,其中每一第一數據塊關聯一個或多個第一簽名,所述一個
或多個第一數據塊包含工作數據塊。在一些實施方式中,對所述第一
歷史數據與所述輸入數據的所述一個或多個部分之間的所述關系的所
述判定進一步包含:將一個或多個第二簽名關聯所述輸入數據;以及
判定至少一個與所述工作數據塊關聯的第一簽名是否與至少一個所述
第二簽名相匹配。在某些實施方式中,響應于所述工作數據塊的至少
一個第一簽名與至少一個所述第二簽名相匹配的判定,將與所述第二
簽名相匹配的所述第一簽名同所述工作數據塊的一部分相關聯起來,
將所述第二簽名同所述輸入數據的一部分相關聯起來,所述至少一個
處理器進一步設置成:判定所述工作數據塊的所述關聯部分與所述輸
入數據的所述關聯部分一致;以及判定關于所述工作數據塊的所述關
聯部分的位置及大小的信息,其中,生成第一引用令牌,所述第一引
用令牌包含關于所述工作數據塊的所述關聯部分的位置及大小的信
息。在一些實施方式中,所述第一引用令牌還包括與所述工作數據塊
關聯的識別碼。

在一些實施方式中,所述裝置進一步包括存儲一個或多個
第二數據塊的數據存儲設備,每一第二數據塊與一個或多個第三簽名
關聯。所述至少一個處理器進一步設置成:響應于無所述第一簽名與
任一所述第二簽名相匹配的判定,判定是否至少一個所述第三簽名與
至少一個所述第二簽名相匹配。如果至少一個所述第三簽名與至少一
個所述第二簽名相匹配,所述至少一個處理器進一步設置成:從所述
數據存儲設備中獲取與所述第三簽名關聯的所述第二數據塊,該第三
簽名與所述第一簽名相匹配,使獲取的所述第二數據塊成為工作歷史
數據塊。

根據一些實施方式,所述工作數據塊進一步包含一個或多
個數據區塊,其中至少一個所述第一簽名與至少一個所述數據區塊關
聯,并具有第一偏移,該第一偏移反映所述工作數據塊中的至少一個
數據區塊的位置。在一些實施方式中,對關于所述工作數據塊的所述
關聯部分的位置及大小的信息的所述判定包含:在所述工作數據塊中,
相對于所述第一偏移所反映的位置正向和/或反向查找與所述輸入數據
的一個或多個部分相匹配的數據。在一些實施方式中,至少一個所述
第一簽名從諸多子簽名中生成,每一子簽名從至少一個所述數據區塊
的一部分中生成。在一些實施方式中,每一所述第一數據塊與時間戳
關聯,所述工作數據塊基于與所述工作數據塊關聯的所述時間戳指定。

根據一些實施方式,一種用于處理數據的計算機實現的方
法包括:接收輸入數據;接收第一歷史數據;判定所述第一歷史數據
與所述輸入數據的一個或多個部分之間的關系;生成反映所述關系的
一個或多個引用令牌;以及傳輸所述一個或多個引用令牌至接收設備。
在一些實施方式中,響應于所述輸入數據的第一部分與所述第一歷史
數據的任一部分不相匹配的判定,該方法進一步包括傳輸所述輸入數
據的所述第一部分至所述接收設備。

根據一些實施方式,一種裝置包括:存儲歷史數據的存儲
器;以及至少一個處理器。該至少一個處理器設置成:接收輸入數據;
生成一個或多個引用令牌,該引用令牌包含關于與所述輸入數據相關
聯的所述歷史數據的至少一部分的信息;以及傳輸所述一個或多個引
用令牌以及不在所述歷史數據中的所述輸入數據的至少一部分至接收
設備。在一些實施方式中,所述關于所述歷史數據的一部分的信息包
含所述第一歷史數據的一部分的位置以及所述歷史數據的一部分的大
小。

附圖說明

體現本發明申請實施例的附圖的參考說明,其中:

圖1示出本發明的實施方式的示例網絡系統的框圖。

圖2示出本發明的實施方式的示例系統的框圖。

圖3A-3C示出根據本發明的實施方式的便于歷史數據查找
的示例數據結構的框圖。

圖4A示出根據本發明的實施方式的示例壓縮模塊的框圖。

圖4B示出根據本發明的實施方式的示例解壓縮模塊的框
圖。

圖5示出根據本發明的實施方式,與數據片段相關聯的塊
簽名生成示例方法的流程圖。

圖6示出根據本發明的實施方式,壓縮數據示例方法的流
程圖。

圖7示出根據本發明的實施方式,解壓縮數據示例方法的
流程圖。

具體實施方式

下面結合附圖對本發明的具體實施方式進行詳細描述,不
論何時,同樣的引用數字在整個附圖中用于表示相同或相近的特征。

實施方式的描述僅為示例性描述,并不起限定作用。為描
述目的,本發明和權利要求書中引用數字“第一”、“第二”以及“第
三”,本領域的普通技術人員應當理解,它們不表示或不是指“特定的
第一”、“特定的第二”或“特定的第三”。

根據一些實施方式,此中描述的運算、技術和/或要素可通
過電子設備實現,該電子設備可包含一個或多個特殊用途計算設備。
這些計算設備之間可以為硬連接以執行此中描述的運算、技術和/或要
素;或可包含數字電子設備,例如:一個或多個特定用途集成電路
((ASICs)或可現場編程門陣列(FPGAs),他們持續運行以執行此中描述
的運算、技術和/或要素;或可包含一個或多個硬件處理器,運行該硬
件處理器根據固件、存儲器、其他存儲件或他們的組合中的程序指令
執行本發明的這些特征。這些特殊用途計算設備亦可將定制硬連接邏
輯、特定用途集成電路或可現場編程門陣列與定制程序聯合來完成本
發明的技術和其他特征。特殊用途計算設備可以為臺式計算機系統、
手提計算機系統、手持設備、網絡設備或并入硬連接和/或程序邏輯以
實現本發明的技術或其他特征的任何其他設備。

一個或多個特殊用途計算設備通常可被運算系統軟件控制
或協調,例如因特網操作系統、安卓、黑莓、谷歌操作系統、Windows
XP、WindowsVista、Windows7、Windows8、Windows服務器、Windows
CE、Unix、Linux、SunOS、Solaris、VxWorks或其他兼容操作系統。
在其他實施方式中,計算設備可被專用操作系統控制。操作系統控制
安排計算機執行過程,執行存儲管理,提供文件系統、網絡化及I/O/
服務,并在其他項中為用戶提供界面功能,例如:圖形用戶界面(GUI)。

圖1示出實施方式描述中使用的示例系統100的框圖。如
圖1所示,系統100包含第一計算機系統110、網絡130以及第二計算
機系統140。第一計算機系統110包含一個或多個處理器112、存儲器
114、存儲設備116以及網絡界面118,所有這些部件可通過總線120
相互通信,第一計算機系統110可通過網絡130與第二計算機系統140
交換數據。第二計算機系統140也包含一個或多個處理器142、存儲器
144、存儲設備146以及網絡界面148,所有這些部件可通過總線150
相互通信。

存儲器114和144均可為用于存儲分別由處理器112和142
執行的信息和指令的隨機存取存儲器(RAM)或其他非易失性存儲設
備,存儲器114和144還可用來在處理器112和142執行指令時存儲
臨時參數或其他中間信息。在被存儲于可訪問處理器112和142的非
臨時性存儲媒介(例如存儲設備116和146)后,這些指令使計算機系統
110和140成為定制執行指令指定運算的特殊用途機器。這些指令可組
織成不同軟件模塊,舉例來說,不同軟件模塊可包含要素(例如軟件要
素、面向對象的軟件要素、分類要素以及任務要素)、過程、功能、域、
步驟、子程序、程序代碼片段、驅動器、固件、微代碼、電路、數據、
數據庫、數據結構、表、陣列以及變量。

通常,此處引用的“模塊”一詞是指硬件或固件中包含的
邏輯或指軟件指令的集合,可能具有入口和出口點,用編程語言如
Java、Lua、C或C++編寫。軟件模塊可匯編或鏈接至可執行程序,安
裝于動態鏈接庫或編寫在如BASIC、Perl或Python解譯程序語言中。
還應當注意到,軟件模塊可從其他模塊或其自身中隨時被調用,和/或
可響應于檢測到的項目或干擾被調用,用于在計算設備上執行的軟件
模塊可提供在計算機可讀媒介上,如壓縮盤、數字錄像盤、閃存驅動
器、磁盤、或任何其他有形媒介,或數字下載件(通常以壓縮件或安裝
格式存儲,在執行前需要安裝、解壓縮或解密);這些軟件代碼可部分
或全部存儲在執行計算設備的存儲器上,由計算設備執行;軟件指令
可嵌入固件中,如可擦可編程只讀存儲器(EPROM)。還應當注意,硬
件模塊可包括連接的邏輯單元,如選擇器開關和觸發器,和/或可包括
可編程單元,如可編程序門陣列或處理器。此中描述的模塊或計算設
備功能最優由軟件模塊實現,但是可由硬件或固件替換。一般來說,
雖然為實體組織或存儲,此中描述的模塊是指可與其他模塊結合或可
分割為子模塊的邏輯模塊。

計算機系統110和140可以采用定制硬連接邏輯、一個或
多個特定用途集成電路或現場可編程門陣列、結合計算機系統促使或
安排計算機系統110和140成為特殊用途機器的固件和/或程序邏輯實
現此中描述的技術。根據一些實施方式,此中描述的運算、功能、技
術或其他特征由計算機系統110和140并且響應于執行分別包含于存
儲器114和144中的一個或多個指令的一個或多個序列的處理器112
和142執行,這些指令可從其他存儲媒介如存儲設備116和146中讀
入存儲器114和144,包含于存儲器114和144中的指令序列的執行促
使處理器112和142執行此中描述的處理步驟。在替換實施方式中,
硬連接電路替換為或結合軟件指令。

此中使用的術語“非臨時性媒介”是指用于存儲促使機器
以特殊方式運行的數據或指令的任何非臨時性媒介,這些非臨時性媒
介可包括非易失性媒介和/或易失性媒介。舉例來說,非易失性媒介可
包含動態存儲器如存儲器114和144,非臨時性媒介的通常形式包含例
如軟盤、軟磁盤、硬盤、固態驅動器、磁帶或其他任何磁性數據存儲
媒介、CD-ROM、其他任何光學數據存儲媒介、其他任何具有空穴陣
列的實體媒介、隨機存取存儲器、可編程只讀存儲器、可擦可編程只
讀存儲器、快擦編程只讀存儲器、其他任何存儲芯片或盒式存儲器、
以及等同網絡版。

網絡界面118和148可提供聯結網絡130的雙向數據通信,
例如,網絡界面118和148可以為綜合服務數字網絡(ISDN)卡、光纜
調制解調器、衛星調制解調器或調制解調器以提供與相應類型電話線
的數據通信連接;另一個例子,網絡界面118和148可以為局域網(LAN)
卡,提供與兼容LAN的數據通信連接。在這樣任一實施中,網絡界面
118和148可發送和接收載有代表各種類型信息的數字數據流的電信
號、電磁信號或光信號,并將數據流提供給存儲設備116和146,處理
器112和142可將數據轉換為不同形式(例如通過執行軟件指令來壓縮
或解壓縮數據),然后將轉換后的數據存儲在存儲設備中(例如存儲設備
116和146),以及/或者將轉換后的數據通過網絡界面118和148在網
絡130上傳輸。

圖2示出本發明實施方式的示例系統200的框圖。在一些
實施方式中,系統200如同圖1中的系統110一樣實現,包含數據壓
縮模塊230、數據解壓縮模塊250、歷史數據管理器270以及探索握手
模塊290,在通過處理器(例如圖1中的處理器112)執行時,數據壓縮
模塊230、數據解壓縮模塊250、歷史數據管理器270以及探索握手模
塊290中的至少部分可檢索和/或更新存儲于存儲設備160中的歷史數
據294以及一個或多個表296。雖然圖2顯示系統200既包含數據壓縮
模塊230又包含數據解壓縮模塊250,應當理解為,系統200可以只包
含數據壓縮模塊230來壓縮數據,而接收系統(例如圖1所示的系統140)
可以只包含數據解壓縮模塊250來接收來自系統200的壓縮數據,然
后將數據解壓縮。此外,雖然圖2顯示歷史數據294和表296為兩個
獨立的整體,應當理解為兩者均可以為數據結構的一部分。

歷史數據294包含最近壓縮的數據和/或因解壓縮其他數據
而最近生成的數據,表296包含便于在歷史數據294中查找數據片段
的信息。在一些實施方式中,歷史數據294包含系統200認為對于特
定傳輸來說是冗余的數據,例如,當系統200接收指示傳輸數據至接
收系統(例如圖1所示的系統140)的指令,系統200可能認為待傳輸數
據的至少一部分已經是存儲于系統140中的相應歷史數據的一部分,
因此使數據的這部分成為冗余而不需要傳輸冗余數據。使用表296中
的信息時,系統200在歷史數據294中可查找并定位冗余數據,定位
冗余數據后,且知道系統140已經存儲相同冗余數據,系統200向系
統140傳輸表示冗余數據和歷史數據294(和/或存儲于系統140的相應
歷史數據)之間關系的信息,這種關系可以為例如存儲于系統140的相
應歷史數據中的冗余數據的位置或大小,這種關系通常可以用比冗余
數據本身更少的數據來表示,因此,關系信息的傳輸,而不是冗余數
據,可節省傳輸在其上進行的媒介(如圖1所示的網絡130)的帶寬。系
統200還可壓縮上述信息來進一步減少傳輸數據的大小,歷史數據294
和表296的進一步詳細信息將在下面討論。

數據壓縮模塊230可接收原始數據(例如來自圖1中的處理
器112執行的另一運用)和指令來壓縮原始數據,數據壓縮模塊230然
后可利用表296中的信息來從歷史數據294中尋找原始數據,歷史數
據294的一部分可以存儲在存儲器(例如圖1中存儲114)和/或存儲設備
(例如圖1中的存儲設備116)中。如果數據壓縮模塊230從歷史數據294
中找到了原始數據,數據壓縮模塊230可以產生引用令牌,該引用令
牌包含協助接收系統從相應歷史數據中找到原始數據的相同片段的信
息,包含在引用令牌中的該信息可指示在歷史數據294中的位置以及
與原始數據相匹配的數據的長度,然后引用令牌被傳輸至接收系統。
另一方面,如果數據壓縮模塊230不能從歷史數據294中找到原始數
據,原始數據將作為原始令牌的一部分被傳輸至接收系統。在一些實
施方式中,輸入數據也可添加至歷史數據294中,將在更新的歷史數
據294中定位所添加輸入數據的信息在表296中更新。在一些實施方
式中,令牌流可利用一個或多個無損數據流壓縮算法在傳輸前被壓縮。
在一些實施方式中,令牌流(已壓縮或未壓縮)可通過如圖1所示的網絡
界面118包格式化,包格式化的令牌流可在網絡(如圖1所示的網絡130)
上傳輸。數據壓縮模塊還可以添加原始數據到歷史數據294中,將在
更新的歷史數據294中定位所添加數據的信息在表296中更新。

數據解壓縮模塊250可從數據壓縮模塊230所傳輸的令牌
流中重建數據流,接收及多路分解包格式化后的數據以檢索含有引用
和/或原始令牌的數據包(如果為壓縮數據,并解壓縮多路分解的數據)
得到令牌流,在此之后,數據解壓縮模塊250可從令牌流中識別引用
令牌和/或原始令牌,數據解壓縮模塊250可基于引用令牌的位置和長
度信息從歷史數據294中檢索與引用令牌相關聯的數據,添加檢索到
的數據至輸出數據流即例如處理器112上執行的另一應用,對于原始
令牌,數據解壓縮模塊250可添加包含有原始令牌的原始數據至輸出
數據流。數據解壓縮模塊250還可更新歷史數據294來包含輸出數據
流,將在更新的歷史數據294中定位所添加數據的信息在表296中更
新。

歷史數據管理器270在數據壓縮模塊230和數據解壓縮模
塊250執行更新時管理歷史數據294的創建與刪除,例如,歷史數據
管理器270可以刪除歷史數據294中占有新歷史數據的空間的舊數據,
歷史數據管理器270亦可與接收系統同步,或與系統200從其處接收
關于歷史數據變化的數據的其他系統同步,這樣,參與令牌流傳輸的
兩邊具有相同的歷史數據。壓縮歷史數據同步和管理的方法和系統的
具體實施方式在2014年1月10日提交的發明名稱為壓縮歷史數據同
步的方法和裝置的美國臨時專利申請No.61/926,145中已經描述,上述
專利申請的全部內容在此以引用方式并入作為參考。

探索握手模塊290判定通信節點是否支持與本發明的實施
方式一致的壓縮和/或解壓縮方法,例如,判定可包含節點是否包含數
據壓縮模塊230和/或數據解壓縮模塊250以及是否可以根據本發明的
實施方式處理(和/或傳輸)引用令牌和原始令牌。壓縮設備握手和挖掘
的方法和系統的具體實施方式在2014年1月19日提交的發明名稱為
壓縮設備握手和挖掘的方法和系統的美國臨時專利申請No.61/926,158
中已經描述,上述專利申請的全部內容在此以引用方式并入作為參考。

圖3A示出根據本發明的實施方式的便于歷史數據查找的
示例數據塊結構300的框圖。在一些實施方式中,歷史數據(例如圖2
中的歷史數據294)可組織為一個或多個數據塊,每個數據塊以數據塊
結構300表示,數據塊結構300存儲于存儲器(例如圖1中的存儲器114)
和/或存儲設備(例如圖1中的存儲設備116)中。正如后續討論,數據塊
結構可從存儲器中交換出存入存儲設備中,或者反向進行。每一數據
塊結構300包含塊數據310,塊數據310可包含一個或多個數據區塊
312和314,區塊是指數據大小單位,該數據大小單位被與本發明的實
施方式一致的壓縮和/或解壓縮方法支持的所有設備所采用。

數據塊結構300亦與塊表316相關聯,雖然圖3A顯示塊
表316為數據塊結構300的一部分且緊鄰數據區塊312和314,應當理
解為,塊表316不需要存儲于與數據區塊相同的位置。在一些實施方
式中,塊表316可以為圖2中的表296的一部分,包含用于在數據塊
結構300中定位數據片段的信息,這些信息可包含用于識別數據片段
以及數據塊結構300中數據定位的識別碼。如圖3A所示,塊表316包
含存儲區塊簽名的域318,區塊簽名用于代表數據特定區塊的內容,例
如,“1234”的區塊簽名關聯數據區塊312,另外,“5678”的區塊簽名
關聯數據區塊314。關于區塊簽名生成的進一步描述將在下面討論。

塊表316還包含以字節存儲有數據偏移的域320,數據偏
移關聯數據塊結構300中數據特定區塊的位置。因為數據區塊312為
數據塊結構300中第一數據區塊,與數據區塊312相關聯的數據偏移
為0,數據區塊314在數據塊結構中緊鄰存儲。在這一特殊實施例中,
數據區塊312的大小為64字節,所以與數據區塊314相關聯的數據偏
移為64字節。數據塊結構300進一步包含域322,域322可用來關聯
一個特定數據塊結構300與塊識別碼(ID),塊識別碼在為歷史數據存儲
相同數據塊的系統之間是一致的,唯一識別數據塊。基于已知的區塊
簽名,通過尋找與已知簽名匹配的一個或多個區塊簽名,數據片段可
在該特定數據塊結構中高效地被定位(或判定為無數據片段),雖然圖
3A未示出,每一數據塊結構300還可關聯一個時間戳,查找可從最近
更新的指定為工作歷史數據塊的數據塊結構上開始。

圖3B示出根據本發明的實施方式的便于歷史數據查找的
示例存儲器塊表350的框圖。存儲器塊表350可方便從最近存儲在易
失性存儲器(例如圖1中的存儲器114)的每一歷史數據塊(例如根據圖
3A中的數據塊結構300存儲)中查找數據片段。如圖3B所示,存儲器
塊表350包含存儲塊ID的域352,每一塊ID識別存儲器中的數據塊結
構。對于域352識別的每一數據塊結構,存儲器塊表350進一步包含
分別關聯代表數據塊結構內特定數據區塊和數據區塊位置的域354和
356,基于已知簽名,通過尋找與已知簽名匹配的一個或多個區塊簽名,
輸入數據的片段可在存儲于存儲器內的一組數據塊結構中高效地被定
位(或判定為無數據片段),如果輸入數據位于特定數據塊結構中,關聯
這一特定數據塊結構以及該數據塊結構中數據位置的塊ID可被檢索
到。在一些實施方式中,檢索到的塊ID以及位置信息可用來做二次甚
至多次精細檢索,相關內容將在下面詳述。是否需要二次檢索取決于
區塊簽名如何計算——如果區塊簽名不能獨一無二地識別數據(即不同
數據值可產生相同的區塊簽名),二次檢索可能是必要的,以確定位于
數據塊結構內的數據區塊與輸入數據完全一致,這樣,由此生成的引
用令牌準確代表輸入數據。

圖3C示出根據本發明的實施方式的便于歷史數據查找的
示例磁盤塊表370的框圖。磁盤塊表370可方便從最近存儲在非易失
性存儲器(例如圖1中的存儲器116)的每一歷史數據塊(例如根據圖3A
中的數據塊結構300存儲)中查找數據片段。如圖3C所示,磁盤塊表
370包含存儲塊ID的域372,每一塊ID識別代表存儲設備中數據塊的
數據塊結構,對于域372識別的每一數據塊結構,磁盤塊表370進一
步包含存儲磁盤簽名的域374,磁盤簽名用于代表存儲與存儲設備中的
多個數據區塊的內容。

在一些實施方式中,表316、350和370提供用于查找組
織為數據塊結構300的歷史數據的層級結構(以下簡稱歷史數據塊),為
了定位歷史數據中的數據片段,通過尋找與數據的簽名相匹配的一個
或多個具有區塊簽名的區塊,基于與工作歷史數據塊相關聯的表316,
從載入存儲器的最近歷史數據塊(指定為工作歷史數據塊)開始查找。如
果不能找到數據,基于表350上的信息,查找范圍可擴展至最近載入
存儲器的每個歷史數據塊。基于一些原因,首先限定在存儲器內查找
是可取的,第一,很有可能存儲于存儲器內的數據包含最近的更新(例
如,包含因壓縮或解壓縮而添加的數據),因此,找到數據片段的可能
性會更高;第二,從存儲器中訪問數據通常比從存儲設備中訪問數據
要塊,這就價款可查找,因此,可從最近存儲與存儲器上的歷史數據
塊中開始查找。

如果從存儲器中不能定位數據片段,可以從存儲于存儲設
備上具有表370上的信息的歷史數據塊中開始查找,如果基于磁盤簽
名找到匹配,含有關聯匹配磁盤簽名的塊ID的歷史數據塊可載入到存
儲器,那么通過關聯的表316上的信息,可在最新載入的歷史數據塊
中基于區塊簽名更精確地進行查找。

圖4A示出根據本發明的實施方式的示例壓縮模塊430的
框圖。在一些實施方式中,壓縮模塊430的功能類似于如圖2所示的
數據壓縮模塊230的功能。壓縮模塊430包含簽名生成器431、第一階
段壓縮模塊432以及第二階段壓縮模塊433。第一階段壓縮模塊432
進一步包含粗查找模塊434、細查找模塊435、原始令牌生成器模塊436
以及引用令牌生成器模塊437。

隨著壓縮模塊430接收輸入數據,該數據可被簽名生成器
431處理產生一個或多個區塊簽名,其中,每個區塊簽名與每一連續的
大小為例如64字節的數據區塊相關聯,關于區塊簽名生成將在下面進
一步詳述。

輸入數據的至少一個區塊簽名生成后,生成的區塊簽名以
及輸入數據可通過第一階段壓縮模塊432的粗檢索模塊434。基于生成
的區塊簽名,粗檢索模塊可在特定歷史數據塊(例如工作歷史數據塊)
中、基于例如與工作歷史數據塊相關聯的塊表316上的信息查找匹配
區塊簽名。在一些實施方式中,通過利用例如如圖3A-3C所示的表316、
350以及370上的信息,粗檢索模塊可對存儲與存儲器和存儲設備中的
歷史數據塊進行層次查找,如果找到匹配,這表明找到輸入數據(或其
部分)的準確副本的可能性很大,工作歷史數據塊中的輸入數據以及與
含有匹配區塊簽名的數據區塊相關聯的數據偏移可通過細檢索模塊。

在細檢索模塊435階段,可進行工作歷史數據塊中輸入數
據的更精確查找。在一些實施方式中,進行這類查找來確定位于該工
作歷史數據塊的數據區塊與輸入數據完全一致。基于數據偏移,細檢
索模塊435可讀取數據區塊并針對該數據區塊進行準確字節串比較來
確認輸入數據與數據區塊完全匹配。為了最大化與相同大小輸入數據
的一部分相匹配的數據區塊的數量,在數據偏移指示位置之前或之后,
通過從工作歷史數據塊中讀取數據區塊(或其部分),細檢索模塊435亦
可正向或反向擴大比較范圍。在工作歷史數據塊中定位最大量匹配數
據區塊后,輸入數據的相應部分可由引用令牌代表,該引用令牌指示
歷史數據塊中匹配數據區塊的位置及數量(或作為數據區塊一部分的匹
配數據的長度)。在一些實施方式中,引用令牌還包含與工作歷史數據
塊相關聯的塊ID。引用令牌由引用令牌生成器模塊437生成,并添加
至代表輸入數據的令牌流中。

另一方面,對于輸入數據的一部分,盡管事實是匹配的區
塊簽名存在,但是粗檢索模塊434沒有找到匹配的區塊簽名,細檢索
模塊435也沒有精確匹配輸入數據的一部分的數據片段,那么這樣一
個輸入數據的一部分用原始令牌代表。在一些實施方式中,原始令牌
包含輸入數據的一部分的副本,原始令牌由原始令牌生成器模塊436
生成,并添加至代表輸入數據的令牌流中。在一些實施方式中,壓縮
模塊430進一步包含歷史數據更新模塊438,歷史數據更新模塊438
將輸入數據添加至壓縮模塊430可訪問的歷史數據中,并在存儲器塊
表350和磁盤塊表370至少之一中更新,存儲器塊表350和磁盤塊表
370中含有區塊和/或為輸入數據生成的磁盤簽名。

第一階段壓縮模塊432生成令牌流的至少一個令牌后,生
成的令牌流可通過第二階段壓縮模塊433進一步壓縮令牌流。在一些
實施方式中,第二階段壓縮模塊433應用無損數據流壓縮算法進行壓
縮,然后壓縮的令牌流可用來代表壓縮狀態的輸入數據。

圖4B示出根據本發明的實施方式的示例解壓縮模塊450
的框圖。在一些實施方式中,解壓縮模塊450的功能類似于如圖2所
示的數據解壓縮模塊250的功能。解壓縮模塊450包含令牌流解壓縮
模塊451、令牌處理模塊452、簽名生成器模塊453以及歷史數據更新
模塊454。令牌流解壓縮模塊451可從例如壓縮模塊430中接收壓縮的
令牌流,根據進行壓縮模塊430的第二階段壓縮模塊433使用的壓縮
算法進行解壓縮來恢復令牌流,恢復的令牌流進而由令牌處理模塊452
處理,令牌處理模塊452可以從令牌流中識別一個或多個引用令牌和/
或原始令牌,通過引用令牌,令牌處理模塊452可從解壓縮模塊450
可訪問的歷史數據中定位工作歷史數據塊(例如最近更新的塊,或由作
為引用令牌的一部分傳輸的塊ID信息所識別的數據塊),并基于位置
信息以及引用令牌內包含的匹配數據大小信息,提取引用令牌所代表
的歷史數據的一部分。令牌處理模塊452還可檢索包含在原始令牌內
的輸入數據的一部分(提供給壓縮模塊430),基于令牌流,令牌處理模
塊452可重建與輸入數據一致的數據流,然后重建的數據流通過簽名
生成器模塊453,簽名生成器模塊453生成區塊和/或重建數據流的磁
盤簽名。歷史數據更新模塊454可將重建的數據流添加至解壓縮模塊
450可訪問的歷史數據中,這樣,重建的數據流與解壓縮模塊450可訪
問的歷史數據匹配并在存儲器塊表350和磁盤塊表370至少之一中更
新,存儲器塊表350和磁盤塊表370中含有區塊和/或為重建數據流生
成的磁盤簽名。

圖5示出示出根據本發明的實施方式,與數據片段相關聯
的塊簽名生成示例方法500的流程圖,該方法由電子設備執行。在這
一示例說明中,電子設備(例如圖1中的計算機系統110)接收包含一個
或多個數據區塊的輸入數據流,使用每一數據區塊內的滑動窗計算一
個或多個子簽名,并基于子簽名為每一數據區塊生成簽名。雖然流程
圖披露以下特定順序的步驟,應當注意的是,為與本發明的公開一致,
至少某些步驟可做適應性移動、修改或刪除。并且,以下步驟通過電
子設備實現,應當注意的是,這些步驟通過多個電子設備實現。

步驟502中,電子設備接收輸入數據流,輸入數據流可來
自任何源(例如由圖4A中的壓縮模塊430壓縮的或由圖4B中的解壓縮
模塊450重建的數據流),且包含一個或多個數據區塊,每一數據區塊
包含多個字節的數據。

步驟504中,電子設備設定計算子簽名的初始位置為0,
這就是說處理將從輸入數據的第一字節開始。電子設備還設定數據區
塊數量值為1,這表示輸入數據的第一數據區塊的區塊簽名生成。

步驟506中,電子設備基于數據區塊數量和數據區塊大小
設定數據區塊位置終端,連同數據區塊數量一起,數據區塊位置終端
界定輸入數據的主窗口(其等同于一個數據區塊內數據字節數),區塊簽
名在該主窗口內生成。

步驟508中,電子設備基于初始位置和子簽名計算窗口大
小設定用于計算子簽名的終端位置。在一些實施方式中,子簽名計算
窗口大小小于數據區塊大小,因此,一個數據區塊內可以生成多個子
簽名。在一些實施方式中,子簽名計算窗口可能進入相鄰數據區塊,
因此,生成的子簽名(通過其生成的簽名)可更好的代表數據,這可進一
步提高粗檢索模塊434執行的查找準確性。

步驟510中,電子設備判定計算子簽名的終端位置是否超
過一個位置閾值,該閾值可為塊內的任一位置且可為每一輪簽名生成
更新。如果情況不是這樣,電子設備將進行步驟512來基于子簽名計
算串口內的數據計算子簽名,計算子簽名的方法有多種,比如:子簽
名為窗口內的數據提供很好的代表,例如,傳統方法可用來從與簽名/
子簽名相關聯的數據中生成數字簽名/子簽名。

計算子簽名后,電子設備進行步驟514子簽名存儲,步驟
516中初始位置增量為1,再次回至步驟508更新用于計算子簽名的終
端位置。這樣一個安排,創建用于計算子簽名的滑動窗口,每次重復
窗口滑動一字節,直到子簽名計算窗口超過當前數據區塊邊界,同時
表明計算子簽名的終端位置超過數據區塊位置終端,當這些發生時,
電子設備進行步驟518。

步驟518中,電子設備基于存儲的步驟512重復中生成的
子簽名值生成區塊簽名,從子簽名生成簽名有多種方法,例如,哈希
算法可用來基于子簽名計算區塊簽名,特定子簽名亦可從生成的子簽
名中選取(例如通過選取具有最大值的一個)作為區塊簽名。

步驟520中,電子設備將區塊簽名與數據區塊關聯。不同
的方法可以執行關聯的方法,例如,針對輸入數據的初始,電子設備
可更新類似于圖3中的塊表316的表來繪制含有以字節或區塊大小測
定偏移的簽名。

步驟522中,電子設備將區塊簽名與數據區塊關聯后,電
子設備可將數據區塊數量增加1,指示處理下一數據區塊以生成下一區
塊簽名。可選地,在電子設備回至步驟506開始生成下一數據區塊的
新子簽名之前,電子設備可清除存儲的子簽名值。

圖6示出根據本發明的實施方式,壓縮數據示例方法600
的流程圖。在這一示例說明中,執行壓縮模塊(例如圖4A中的壓縮模
塊430)的電子設備(例如圖1中的計算機系統110)接收輸入數據流并生
成代表輸入數據的令牌流,雖然流程圖披露了以下特定順序的步驟,
應當注意的是,為與本發明的公開一致,至少某些步驟可做適應性移
動、修改或刪除。并且,以下步驟通過電子設備實現,應當注意的是,
這些步驟通過多個電子設備實現。

步驟602中,電子設備生成一個或多個與輸入數據相關聯
的區塊和/或磁盤簽名,該生成可由壓縮模塊430的簽名生成器431通
過類似于如圖5所示的方法500的方法實現。

步驟604中,電子設備從歷史數據中識別工作歷史數據塊,
工作歷史數據塊可包含于數據塊結構300類似的結構并與時間戳相關
聯,工作歷史數據塊基于該時間戳(例如最近更新的)被識別。歷史數據
塊亦可與塊表316相關聯,塊表316包含如圖3A所示的區塊簽名與數
據偏移之間的映射關系。

步驟606中,電子設備從塊表316中查找一個或多個區塊
簽名,塊表316將區塊簽名與輸入數據相匹配,如果找不到匹配簽名,
電子設備可進行步驟610,從當前存儲在儲存器中的所有歷史數據塊中
查找,利用例如圖3B中的存儲器塊表350中的信息,尋找含有與輸入
數據的區塊簽名相匹配的區塊簽名的歷史數據塊。如果沒有存儲數據
塊含有匹配的區塊簽名,電子設備進行步驟612,對當前存儲在存儲設
備的歷史數據塊進行查找,尋找含有與輸入數據磁盤簽名相匹配的磁
盤簽名的歷史數據塊。如果通過步驟612沒有找到匹配的磁盤簽名,
電子設備進行步驟614,生成包含未壓縮輸入數據的原始令牌,如果找
到了匹配的磁盤簽名,電子設備可嘗試將與匹配的磁盤簽名相關聯的
歷史數據塊從存儲設備載入到存儲器中。在步驟616中,如果電子設
備判定數據塊從存儲設備中的載入不能按時完成(例如在一定的時間閾
值內),電子設備將決定稍后載入數據塊(例如在處理下一輸入數據片段
之前,這樣,當重新開始步驟602處理下一輸入數據片段時,數據塊
已經載入存儲器),然后進行步驟614,生成原始令牌。否則,電子設
備將從存儲設備載入歷史數據塊到存儲器,然后進行步驟604來指定
該歷史數據塊為工作歷史數據塊,在該找到的工作歷史數據塊執行步
驟606和610以找到匹配的區塊簽名,步驟606至612以及步驟616
通過例如圖4A中的粗檢索模塊434實現,而步驟614則通過例如圖
4A中的原始令牌生成器模塊436實現。

另一方面,如果在歷史數據塊中找到了匹配區塊簽名(步驟
606),或者從存儲器塊表中找到了匹配區塊簽名(步驟610),這將表明
很有可能歷史數據塊包含與輸入數據部分或全部一致的數據,那么電
子設備進行步驟618,基于與匹配的區塊簽名相關聯的數據偏移,從工
作歷史數據塊中檢索塊數據部分,然后進行步驟620,在塊數據和輸入
數據之間進行字節串比較,作為步驟620的一部分,電子設備還可相
對于數據偏移在正向和反向擴大比較范圍。如果在塊數據的任一部分
和輸入數據之間找到了匹配,電子設備可進行步驟622,生成引用令牌,
引用令牌包含歷史數據塊中的與輸入數據相匹配的塊數據的位置及長
度,如果他們不能匹配,電子設備將進行步驟614,生成原始令牌。步
驟618和620可通過例如圖4A中的細檢索模塊435實現,而步驟622
則可通過例如圖4A中的引用令牌生成器模塊437實現。然后電子設備
可進行步驟624生成包含有原始令牌以及引用令牌的令牌流,進而通
過如圖4A中的第二階段壓縮模塊433進一步壓縮該令牌流。雖然圖6
中未示出,電子設備還可將輸入數據添加到歷史數據中,并在存儲器
塊表350和磁盤塊表370至少之一中更新,存儲器塊表350和磁盤塊
表370中含有為輸入數據生成的區塊和/或磁盤簽名。

圖7示出根據本發明的實施方式,解壓縮數據示例方法700
的流程圖。在這一示例說明中,執行解壓模塊(例如圖4B中的解壓縮
模塊450)電子設備(例如圖1中的計算機系統100)接收代表一定數據的
令牌流,然后重建與該令牌流所代表的數據相匹配的數據流。雖然流
程圖披露以下特定順序的步驟,應當注意的是,為與本發明的公開一
致,至少某些步驟可做適應性移動、修改或刪除。并且,以下步驟通
過電子設備實現,應當注意的是,這些步驟通過多個電子設備實現。

步驟702中,電子設備從令牌流中檢索令牌。在一些實施
方式中,令牌流可能已經被壓縮(例如被圖4A中的第二階段壓縮模塊
433),電子設備可解壓已經被壓縮的流。步驟702可通過圖4B中的令
牌流解壓縮模塊451實現。

電子設備可進行步驟704來判定檢索到的令牌是否為引用
令牌,該引用令牌包含與引用令牌所代表的數據相匹配的歷史數據塊
中的數據片段的位置和長度信息,和/或識別工作歷史數據塊的塊ID。

如果令牌為引用令牌,電子設備進行步驟706來識別歷史
數據塊。歷史數據塊可基于與其相關聯的時間戳被識別(例如最近更新
的數據塊),和/或從作為引用令牌的一部分存儲的塊ID中被識別,識
別工作歷史數據塊后,電子設備可進行步驟708,基于引用令牌的位置
和長度信息,從被識別的歷史數據塊中檢索數據。

如果令牌為原始令牌,電子設備可進行步驟710,檢索包
含在原始令牌內的原始數據。然后電子設備可進行步驟712,使用檢索
到的塊數據(來自步驟708)和/或原始令牌中的原始數據(來自步驟710),
重建輸出數據流。步驟706可通過例如圖4B中的令牌處理模塊452實
現。雖然圖7中未示出,電子設備還可將重建的數據流添加到歷史數
據中,并在存儲器塊表350和磁盤塊表370至少之一中更新數據生成
的區塊和/或磁盤簽名。

上述的說明書中,實施方式描述了根據不同實施而不同的
很多特定的細節,當然可作出對所描述的實施方式的某些適應性的改
變和修正,對于本領域的技術人員,參考本發明的所公開的說明書及
實施,其他實施方式是顯而易見的。說明書和實施例僅作為示例性說
明,本發明的真正保護范圍及精神由以下的權利要求書限定。附圖中
所示的步驟順序僅用于說明目的,并不是對任何步驟的特定順序的限
定,同樣地,本領域的技術人員可領會到在實施相同方法時這些步驟
可以以不同順序進行。

關 鍵 詞:
冗余 數據壓縮 解壓縮 系統 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:含冗余的數據壓縮與解壓縮的系統和方法.pdf
鏈接地址:http://www.wwszu.club/p-6401450.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大