太阳城集团

  • / 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://zh228.com/p-6401450.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');