CN1630984A - 增量和连续的数据压缩 - Google Patents

Abstract

一种数据压缩系统及方法，它能在实际上无限大小的窗口中删除(202)和消除(206)可变长度的重复短语。

Description

增量和连续的数据压缩

有关申请

本申请要求在2000年7月25日提交的美国临时申请号为60/221,262的专利申请的优先权，该专利整体加入这里作为参考。

发明背景

1.发明领域

本发明涉及数据压缩领域，尤其涉及增量及连续的数据压缩的领域。

2.背景技术描述

传统通信系统的重要目标是改善数据的带宽的吞吐量。传统的系统不是发送每一位数据，而是使用压缩算法来减少从源到目标需要发送的数据量。两类压缩算法，无损压缩算法和有损压缩算法。无损压缩算法将数据转换成一种形式，其中包含在该数据中的信息不受损失。相反，有损压缩算法产生一种表示方式，其中，该数据的某些细节可能被排除。

压缩算法也能粗略地分成两个类别：专用的及通用的。专用压缩及解压缩应用于那样的数据，对那些数据它们的数据特征的先验知识是可以得到的。例如，视频数据已知由各个帧组成，每帧与其以前帧及后续帧的区别很少。在那样的情况，专用压缩方案能得益于此先验知识而设计更专门的因而可能更有效的压缩及解压缩算法。通用压缩算法(也称为万能压缩算法)不假设数据特征或产生数据的源的任何先验知识。因此，通用压缩常常比较低效，它更经常地导致比对于特殊数据类型的专用压缩算法更少程度的压缩。然而，通用压缩算法更灵活，因为如上所述，它们能有效地用于许多不同类型的数据，并在事先不知道有关数据的信息的情况下应用。

一类通用压缩算法是根据对数据中的重复的识别及消除。这些方法称为基于词典的压缩技术，因为它们试图发现重复项及短语的词典。学到的词典项随后被用于消除在目标数据组中的这些项的重复性。

两个其他类型的压缩算法是增量压缩算法和连续压缩算法。此两类算法不是互相排斥的，即一个压缩算法能既是增量的又是连续的，增量压缩算法是不需要处理整个输入流或输入流中的整个数据块来产生其输出的算法。相反，增量压缩算法在逐个符号的基础上(即增量地)处理输入，并在其仍然处理输入的过程中产生其输出，而不是在其处理整个输入之后。例如，计算在一段文字中的元音数的算法基本上是非增量算法，因为它必须处理整个文字输入来计算元音的总数。另外，将小写文字转换成大写文字的算法是增量的，因为它能独立地处理每个输入字符，并能在其处理每个输入字符时产生其输出。

连续算法是能在无限的输入数据流上无限地运行而不会用完如存储器及盘空间等那样的系统资源的算法。连续算法也常常称为流算法。注意，仅仅在处理所有输入后产生输出的非增量算法根据定义是非连续的(因为在连续算法中输入是无限长)。

数据的存储和传输的代价直接与数据对象的大小相关。因此，从数据中消除冗余是改善数据存储和传输的效率的高度有效的方法。最通用的无损数据压缩算法试图根据两个主要方法从数据中消除冗余：(1)识别和消除重复的项及短语；和(2)以更有效的方式编码数据。

能通过各种技术实现重复项或短语的识别。涉及的通常原则能借助例子说明。考虑到等式(1)中的字符序列。

S＝aabcaabdaabeaabf        等式(1)

基于词典的压缩算法能识别，短语“aab”在此序列中重复了4次。若算法用新的符号，如A替代“aab”的所有出现，该序列则被更有效地存储或传输。被压缩的序列然后看来如等式(2)中的序列。

S＝AcAdAeAf                等式(2)

除了上述压缩序列以外，该算法也必须存储或发送附加指令，指出在解压缩期间A的所有出现应由“aab”替代。因此，指令A＝aab是压缩所根据的词典项。为了能解压缩，该词典和压缩的字符串必须被存储或发送。虽然在此情况词典是易于确定的，对给定的输入序列已经示出，寻找产生高度压缩的词典的问题是NP-完成，它在计算机协会杂志29(4)(1982)925-951页J.A.Storer所著“Datacompression via textual Substitution”中描述，该文整个加入于此作为参考。

数据编码包括在每个字符的基础上修改数据的表示，使得经常发生的字符能更有效地表示(如用更少的位数)。考虑在等式(3)中14个字符的序列。

S＝abacadaeafagah                等式(3)

在此情况字符“a”发生7次而字符“b-h”的每一个只发生一次。若整个字符表只有8个字符“a-h”组成，它们能对每个字符使用3个位的二进制形式表示，如表1所示。

                           a  000

                           b  001

                           c  010

                           d  011

                           e  100

                           f  101

                           g  110

                           h  111

                            表1

这使得序列(S)需要总共14×3＝42位。另外，因为我们看到在数据中字符“a”出现得更频繁，可以更有效地用更少的位表示“a”，其代价是对字符表中的其余字符增加位数。例如，8个字符能改成如表2中那样地表示。

                           a  0

                           b  1000

                           c  1001

                           d  1010

                           e  1011

                           f  1100

                           g  1101

                           h  1110

                            表2

在此情况，字符串S需要1位表示7个“a”字符中每一个，4位表示余下字符的每一个。因而对S所需的总空间是7*1+7*4＝35位。这表示节省了超过有百分之16。

有这样统计编码技术的各种例子，如Huffman编码和算术编码。那样的方法的更详细描述在：D.A.Huffman的“A Method for the construction ofminimum-redudancy codes”，Proceeding IRE，40：1098-1101(1952)和Witten，Neal和Cleary的“Arithmetic coding for data compression”Communications of theAssociation for Computing Machinary，30(6)：520-540(1987)，它们整个被加入于此作为参考。

应用于许多那样的统计编码技术的一般原则由Shannon于1948年在下文中提出：“A Mathematical Theory of Communication”，Bell System TechnicalJonrnal，27：389-403(1948)，它作为整体加入于此作为参考。Shannon表示，需要编码以概率P出现的字符或字符串的位数是-log₂P。因此，若8个字符a-h每个以等概率出现，P＝1/8，每个字符能以-log₂(1/8)＝3位编码。但在我们上述例子中，我们知道“a”以概率7/14出现，而其余字符以概率1/14出现。因此，a能以-log2(7/14)＝1位编码，而每个余下的字符能以-log2(1/14)＝3.8位编码。

另外的编码方法是游程长度编码。在此情况，同样字符的序列用单个字符跟着指出字符重复次数的数来替代。在等式(4)中给出一个例子。

S＝aaaaabbbbb              等式(4)

此字符串能使用游程长度编码法编码，如等式(5)所示。

S＝a5b5                    等式(5)

许多传统的基于词典的，通用的，无损的压缩算法是根据上述两种方法的组合，例如，首先是基于词典的压缩重复的短语，随后最终压缩流作统计编码。现描述这些传统的压缩技术的某一些。

一种传统的压缩技术在下文中描述：Ziv和Lempel的“A Universal Algorithmfor Sequential Data Compression”，IEEE Transaction of Information Theory，IT-23(3)：337-343(1977)，它作为整体加入于此作为参考。此广泛使用的基于词典的通用压缩技术称之为LZ77，并形成若干其他压缩算法的基础。例如，广泛地与基于Unix的操作系统一起发行的“gzip”压缩程序使用LZ77方法的一个变例。LZ77是根据在固定大小的窗口中将指针用于短语以前的出现。通过穿过输入序列滑动窗口并搜索在该窗口中的任何重复字符串来寻找数据中重复的短语。例如，考虑在等式(6)中的输入序列。

S＝abcdefbcdgh                    等式(6)

LZ77方法判定，短语“bcd”重复两次，并使用此信息压缩该序列。“bcd”的第一次出现不加修改。第二次出现被从S的起点到“bcd”第一次出现的距离和重复的长度组成的指针所替代。因此，序列S由LZ77被表示成如等式(7)那样。

S＝abcdef(1，3)gh

指针(1，3)表示，在从窗口起点距离为1并向右延伸3个字符的短语在当前的指针位置被重复。此方案的一个变例使用从当前位置反向的距离作为指针的第一元素(而不是从窗口起点向前的距离)。在此情况S表示成如等式(8)那样。

S＝abcdef(5，3)gh                  等式(8)

此处，指针(5，3)指出，从当前位置反向距离5处开始并向右延伸3个字符的短语被重复。

传统的基于LZ77的压缩程序根据将可变长重复转换成固定长指针的方法使用上述指针。然后通过应用统计编码技术压缩得到的符号和指针序列。这些程序能使用不同的方法发现重复的短语并编码最终的数据流。

LZ77方法的一个问题是它只能在固定大小的窗口中检测重复。有限的窗口大小不能检测离开距离大于窗口大小的重复数据。例如，在上述例子中，若窗口大小减少到5个字符，“bcd”的重复将不被检测，因为从“bcd”的第一次出现的开始到第二次出现的结束总的距离大于5。在LZ77方法中限制窗口的大小是为了限制搜索重复性所需要的时间。使用LZ77方法的搜索算法的复杂性和执行时间通常是所搜索的输入字符串的大小的函数。因而，通常传统的LZ77压缩技术将窗口大小限制到几千字符。例如，“gzip”程序使用32K字节的窗口。窗口大小的增加导致LZ77算法执行时间的很大增加。

LZ77压缩方法的另外的问题是它需要第二阶段的统计编码以提供足够的压缩率。由LZ77方法使用的统计编码技术是非增量的，因而是非连续的(如gzip使用Huffman编码，它是非增量的)。非增量编码技术在对一个数据块输出编码树以前必须完全地处理这块数据。由非增量技术使用的块的大小也需足够大以保证编码方案产生有效的编码树。因而LZ77技术不适合于实时或在线的压缩，其中有必须被增量地处理的连续流。

LZ77的另一个问题是可能的指针数目很大，因为它们能指向窗口内任何位置。

Ziv和Lempell针对LZ77技术中的某些问题在1978年提出新的压缩方案，称之为LZ78。这在下文中描述：Ziv和Lempell的“Compression of IndividualSequences Via Variable Rate Coding”，IEEE Transaction on InformationTheory，IT-24(5)：530-536(1978)，它作为整体被加入于此作为参考。不是使用指向窗口中位置的指针，LZ78方法使用在输入流中遇到的所有短语的词典的直接表示。词典通过建立在以前词典项之上增量式地构造。每当见到新的短语，在认为它可能以后被使用的前提下，将其加到词典中。考虑在等式(9)中的输入序列。

S＝cbaabacaccacccacccc                 等式(9)

LZ78产生短语(0，c)，其中0是空字符串而c是第一字符，下面两个字符也导致两个新的短语(0，b)和(0，a)。最终的短语序列示于表3。

             输入      短语号     输出短语

             c           1        (0，c)

             b           2        (0，b)

             a           3        (0，a)

             ab          4        (3，b)

             ac          5        (3，c)

             acc         6        (5，c)

             accc        7        (6，c)

             acccc       8        (7，c)

                        表3

因而序列S的最终编码将是表3中示出的输出短语列。如在此例能看出，词典项1，2，4在此编码中永不使用，因而是词典中的无用项。例如，虽然对“ac”的词典项被再使用以增量地产生“acc”，“accc”，和“acccc”，对“ab”的词典项不再使用，因而是无用的。

LZ78技术的一个问题是它使用积极的和推测的词典结构方案，这常导致不能有效地使用的项的结构。因此，词典能变成很大，并导致不能有效使用系统资源并降低压缩效率。此外，LZ78方案的收敛速率是慢的，因为词典以慢的速率增长。基于LZ78的压缩程序也常使用非增量的统计编码技术来改善压缩效率和程序速度，因而不能用于在线或连续的数据。而且没有措施来忘记(删除)不再使用的短语或词典项。对连续的，潜在无限的数据流，必要的是不仅动态地产生新的词典项，还在于忘记不常使用的项以重新使用系统资源，这用LZ78算法不能实现。因此，LZ78算法不是连续压缩算法。

第三种压缩算法是Sequitur算法，它在下文中描述：Nevill-Manning和Witten的“Compression and Explanation Using Hierarchical Grammars”，Computer Journal，40(2)：103-116(1997)，它作为整体加入于此作为参考。Sequitur算法从离散的符号序列推导出与上下文自由的语法。该语法分层地表示该序列的结构，并能用于产生该序列的结构的有用可视说明并推导在该序列中的词法单元。因为该语法完全地表示了整个输入序列，Sequitur也能用于数据压缩。

Sequitur通过在输入序列中施加两个约束而工作。第一约束是没有相邻符号对能出现多于一次。第二约束是由算法产生的每个规则应使用多于一次。Sequitur通过增量地检查该输入序列并保证在该序列的每一点满足此两个约束而应用这些约束。例如，在等式(10)中示出的输入序列中，

S＝abcdbcabcd             等式(10)

Sequitur将产生在等式(11)中的语法

S＝BAB

A＝bc                     等式(11)

B＝aAd

其中A和B是语法中的规则，它们类似于词典项。上述语法满足第一约束，因为没有符号对出现多于一次。第二约束也满足，因为在该语法中A和B均使用至少二次。

因为整个输入序列由语法表示，Sequitur使用此算法于通过应用算术编码压缩以编码整个语法。语法的规则(即词典项)被指针发送到重复以前的出现处，这类似于上述对于LZ77的技术。当在语法中第一次遇到规则时，其内容被发送。该规则的第二次出现作为指向用于构造该规则的序列的区域(如该规划第一次出现的内容)的指针被发送。在解码器及编码器能保留互相的规则号的轨迹的假设下，所有此规则的后续出现作为规则号被发送。

Sequitur压缩技术的一个问题是它不是隐含地增量的。为保证语法用最少的符号数发送，Sequitur需要语法在被发送前被完全构成。通过将序列S的发送点选在发送额外符号的概率低的地方，能使Sequitur看上去象增量的。用于检测在被压缩的序列中的某一点是否为发送该序列的安全点的算法需要检查就在此点以前该符号的所有以前的出现。因为Sequitur需要在输入序列的整个压缩中动态地选择这些点，为了连续地搜索这些发送点，该算法引起大量额外处理。此附加的处理(为使Sequitur成为增量的这是必需的)使得整个压缩算法是非线性，并因而大大减少了有效性。

Sequitur算法的另外问题是它是不连续的。该算法不提供任何手段来增量地发送被压缩的输出而同时删除不常访问的规则和符号(为了再使用系统资源)。因此，Sequitur不能应用于无限或很大的输入数据流，在线性时间内产生被压缩输出的连续流。

Sequitur算法还在其使用系统资源方面不太有效，因为它需要复杂的数据结构使能够作可变长度的规则的频繁建立及删除。此外，该算法在删除长的重复时计算上不太有效，因为在重复的短语中的每对符号需要规则的建立和删除。因此，重复的每个附加的出现会招致多次规则的建立和删除的计算上的过度开销。为了将规则的第二次出现作为指针发送，Sequitur的技术也需要额外的处理与存储开销。

第四个压缩算法是递归配对(Re-Pair)算法，它在下文中描述，Larsson和Moffat的“Offline Dictionary-Based Compression”，Proceeding DataCompression Conference，196-305(1999)，它被整体加入于此作为参考。Re-pair算法试图通过递归地检查整个输入序列以识别最频繁出现的符号对来计算用于压缩的最优词典。在该算法的每个阶段，最频繁出现的符号对用表示该词典中的新增加的新的符号来替代。然后再次检查整个经修改的序列以找到当前最频繁出现的对。此过程迭代，直到没有出现大于一次的对。然后编码最终的压缩的序列和词典，以产生最终的压缩输出。

这些算法的主要缺点是在于它们基本上是非增量及非连续的。在任何输出能够产生之前，整个输入序列必须通过递归配对处理。这些作者本身将算法描述为“离线”技术。

需要一种数据压缩的系统及方法，它们(1)是通用压缩算法；(2)是无损压缩算法；(3)对数据的线性增加不需要执行时间的非线性增加；(4)不需要有限的数据窗口大小；(5)是增量压缩算法；(6)是连续压缩算法。

发明概述

本发明是有效的压缩算法，它能在实际上无限大小的窗口中删除和消除重复的可变长度短语。窗口的大小只受可用的系统存储的数量的限制且不影响算法的速度。本发明是在线性执行时间内运行的通用无损压缩算法，能使用无限的窗口大小，隐含地是增量的，且能在连续的输入流上连续地运行。

附图简述

图1是本发明的一个实施例可以在其中运行的计算机系统的图示。

图2是按本发明的一个实施例编码和封装(EE)单元和解码和解封装(DD)单元的部件的图示。

图3是本发明的检测器部件的实施例的图示。

图4是按本发明的一个实施例的检测技术的例子的图示。

图5是示出按本发明的一个实施例的发送过程的流程图。

图6是示出本发明的一个实施例的解压缩算法的流程图。

图7是按本发明的一个实施例的发送技术的例子的图示。

图8a和8b是按本发明的一个实施例删除技术的LRU和父指针的例子的图示。

图9是按本发明的一个实施例的删除技术的流程图示。

较佳实施例详述

现参考附图描述本发明的较佳实施例，其中类似的参照号指示等同的或功能上类似的单元。而且在图中，每个参照号的最左边数字对应于该参照号首次使用的图。

图1是本发明的一个实施例可以在其中运行的计算机系统的图示。计算机系统100包括第一系统102A和第二系统102B。每个系统是独立的计算机或软件过程。每个系统包括传统的处理器110，存储设备112，输入/输出设备114和操作系统116。每个系统还包括编码和封装(EE)单元106和解码及解封装(DD)单元108。EE和DD能作为在处理器上运行的软件或作为专门设计的硬件(在此情况处理器不是必须的)嵌入。两个系统102A和102B能通过任何物理的或逻辑的网络链路连接。可以想象，本发明能完全在两个系统中运行且在图1中的实施例是示例性的，它不试图限制本发明的范围。下面将更详细地描述EE单元106和DD单元108的操作。例如，在另外的实施例中，EE单元106及DD单元108可以是专用集成电路(ASIC)的一部分。

EE单元106实现本发明的压缩技术。例如，EE单元106能作为计算机软件程序、硬件、固件或它们的组合来实现。在一个实施例中，本发明的压缩技术能以存储在传统的EE单元106中的存储模块并由处理器110执行软件来实现。本发明的压缩技术是时间线性的，完全增量的，和连续的数据压缩算法。为便于参照，该算法在此文件中称为“IZ”。本发明的解压缩工作在DD单元中完成，并能作为如计算机软件程序，硬件，固件，或它们的组合而实现。

本发明包括同时操作的三个组件。图2是按本发明的一个实施例的编码和封装(EE)单元106和解码和解封装(DD)单元组件的图示。第一组件是检测器组件202，它检测在线性时间输入流中任何处的重复短语/项。为本专利的目的。术语“项”和“符号”可交替使用。“短语”或“数据短语”包括固定数目的顺序数据项。数据项可以是数据符号和/或数据短语标识符。检测器组件202通过使用实际上无限的窗口大小识别并消除重复的短语，增量地压缩输入流。此过程能使用作为检测器组件的部分的识别单元，压缩单元，和库建立单元(散列建立单元)完成。这些单元的操作在下面参考图3和4描述。第二组件是发送组件204，它以隐含的增量方式发送经压缩的序列和有关的短语的词典。发送组件204还保证压缩和解压缩算法总是完全同步。第三组件是删除组件206，它使IZ算法能删除并有效地“忘记”不常使用的短语和符号以释放系统资源。因而该删除组件使IZ能在无限的输入数据流上连续地运行。DD单元108包括解压缩单元，这在下面详述。

检测器组件202，发送组件204和删除组件206能以各种方式实现。检测器组件的一个实现方法示于图3。

短语检测算法使用下列步骤，以增量地将输入序列S转换成被压缩的序列S’。

重复的符号对的检测能使用散列表(如库)完成以记录所有已被检测组件202观察到的所有唯一的符号对。每个散列表的项包括指向唯一符号对的位置的指针。若该符号对只出现一次，则对此符号对的散列表项将指向S’中第一符号的位置。若该符号对已发生多于一次，且因而由词典短语表示，则对该符号对的散列表项将指向对应的词典短语。为保证检测所有重复的符号对，该算法必须保证每当一个符号被加入或从S’中删除，该散列表被适本地更新。例如，在图3中示出的算法中的步骤314导致增加新的项到表中。类似地，步骤314，318和332将导致从散列表中删除一个或多个项。

现参考图4中示出的例子描述图3的流程图。

在图4中示出的例中的输入序列是“abcdcdabcd”。在步骤302“Y”被设成等于下一个输入符号“a”，并在304附在S’之后(它以前等于空)。X然后被设成序列中“a”之前的符号(空)。在308，XY的组合以前未发生，所以XY在309被加到散列表，过程在步骤302重复。图4的第1行示出在此点处该例子的状态。

然后在302 Y被设成等于下一个符号b，在304附在S’之后，并在304 X被设成Y前的符号(“a”)。在308 XY的组合(ab)以前未出现，所以XY在309被加到散列表，过程在步骤302处重复。图4的第2行示出在此点处该例子的状态。

然后在302 Y被设成下一个符号“c”，在304附在S’之后，在306 X被设成Y之前的符号(“b”)。在308 XY的组合(bc)以前未出现，所以在309 XY被加到散列表，过程在步骤302处重复。图4的第3行示出在此点处该例子的状态。

然后在302 Y被设成下一个符号“d”，在304附在S’之后，在306 X被设成Y之前的符号(“c”)，在308 XY的组合(cd)以前未出现，所以在309 XY被加散列表，过程在步骤302处重复。图4的第4行示出在此点处该例子的状态。

然后在302 Y被设成下一个符号“c”，在304附在S’之后，在306 X被设成Y之前的符号(“d”)。在308 XY的组合(dc)以前未出现，所以在309 XY被加到散列表，过程在步骤302处重复。图4的第5行示出在此点处该例子的状态。

然后在302 Y被设成下一个符号“d”，在304附在S’之后，在306 X被设成Y之前的符号(“c”)。XY的组合(cd)以前已经出现，所以过程继续。因为XY的以前出现是在序列S’，且在310不是作为词典短语的右端项，这意味着XY是应该新建并加到词典中去的新短语。因此，在312通过建立新的词典短语P₁且将其设成等于XY，过程继续。在此例中P₁设成等于“cd”。然后XY的以前出现在314中在S’由P₁替代。注意，此替代步骤314导致从散列表去除两个项并将两个新的项加到散列表。这些散列表更新包括X以前的符号(称为X_p)和Y之后的符号(称为Y_n)。因为XY从S’中去除，符号对X_pX和YY_n必须也从散列表中去除。因为XY被P_i替代，符号对X_pP_i和P_iY_n必须加到散列表。在此例子中，“bc”和“dc”从散列表被去除，“bP₁”和“P₁c”被加到散列表。然后，在316 Y从S’的末端去除，在318 X从S’的末端去除。而且，在318 X从S’的末端去除将导致符号对(对应于X前的符号及X)从散列表去除。在此例子中，“P₁c”将从散列表去除。然后Y被设成等于P1，且在步骤304过程继续。在此点该例的状态是S’＝abP₁且Y等于P₁。

然后在304 Y附于S’之后(现在S’＝abP₁P₁)且在306 X被设成等于在S’中Y前的符号(“P₁”)。在308，序列中XY(P₁P₁)未出现，所以XY在309被加到散列表，过程在步骤302处重复。在图4的第6行用S’＝abP₁P₁示出在此点该例子的状态。

然后在302 Y被设成下一个符号“a”，在304附在S’之后，在306 X被设成Y之前的符号(“P1”)。在308 XY的组合(P₁a)以前未出现，所以在309 XY被加到散列表，过程在步骤302处重复。图4的第7行示出在此点处该例子的状态。

然后在302 Y被设成下一个符号“b”，在304附在S’之后，在306 XY被设成Y之前的符号(“a”)。XY的组合(ab)以前已在序列中出现，所以过程继续。因为XY的以前出现是在序列S’中，且不是作为词典短语310的右端项，这意味着XY是应该新建并加到词典中去的新短语。因此，在312通过建立新的词典短语P₂且将其设成等于XY，过程继续。在此例中，P₂设成等于“ab”。然后在314中XY  的以前出现在S’由P₂替代。如之前，该步骤导致从散列表去除两个符号并加上两个符号。然后，在316 Y从S’的末端去除，在318 X从S’的末端去除(这也导致从散列表去除一个符号对)。然后Y被设成等于P₂，且在步骤304过程继续。在此点该例的状态是S’＝P₂P₁P₁，且Y等于P。

然后在304 Y附于S’之后(现在S’＝P₂P₁P₁P₂)且在306 X被设成等于在S’中Y前的符号(在此情况它实际上是数据短语标识符“P₁”)。在308，序列XY(P₁P₂)未出现，所以在309 XY被加到散列表，过程在步骤302处重复。在图4的第8行用S’＝P₂P₁P₁P₂示出在此点该例子的状态。

然后在302 Y被设成下一个符号“c”，在304附在S’之后，在306 X被设成Y之前的符号(“P₂”)。在308 XY的组合(P₂c)以前未出现，所以在309 XY被加到散列表，过程在步骤302重复。图4的第9行示出在此点处该例子的状态。

然后在302 Y等于下一个符号“d”，在304附在S’之后，在306 X被设成Y之前的符号(“c”)。XY的组合(cd)前面已经在序列中出现，所以过程继续。因为XY等于词典短语310的右端项，通过在330从S’的末端去除Y，在332从S’的末端去除X，过程继续。在332从S’的末端去除X导致从散列表去除符号对(对应于X前的符号及X)。然后在334中Y被设为等于XY的词典短语。在此例中Y被设成等于P₁。过程在步骤304继续。在这点此例的状态是S’＝P₂P₁P₁P₂且Y等于P₁。

然后在304 Y附于S’之后(现在S’＝P₂P₁P₁P₂P₁)，且在306 X设成等于在S’中Y之前的符号(“P₂”)。XY的组合(P₂P₁)在序列中以前已出现且因为XY不等于词典短语310的右端项，通过在312建立新的词典短语P₃并将其设成等于XY，过程继续。在此例中，P₃被设成等于“P₂P₁”。然后在314 XY在序列S’以前的出现由P₃所替代。然后在316 Y从S’的末端除去，在318 X从S’的末端除去。随后Y被设成等于P₃，过程在步骤304继续，在此点上本例的状态是S’＝P₃P₁而Y等于P₃。

随后在304 Y附在S’之后(现在S’＝P₃P₁P₃)且X在306被设成等于S’中Y之前的符号(“P₁”)。在308 XY(P₁P₃)在序列中以前未出现，所以在309 XY被加到散列表且过程在步骤302重复。图4中的第10行用S’＝P₃P₁P₃示出在此点本例的状态。过程能对任何数目的输入继续。

本发明能检测在输入流中任何处的重复。本发明不需要直接的搜索窗口，且因而能够检测重复性而不论重复发生得多远。也应用某些加窗口技术使得该算法如下述那样继续，但是此窗口是基于系统存储器的大小且不影响该算法的速度。上述算法已示出在时间和空间上是线性的。线性度的证明是根据计算处理长度n的序列所需的总操作数。此数示作为0(n)(即应是正比于n的数)。因而，本发明能经过实际只在线性时间中无限的窗口检测可变大小的重复。重复的短语的检测也比如上述Sequitur技术那样的其他技术更有效，因为IZ对在短语中的每个符号对不需要任何不是必须的规则的建立和删除。

发送组件204保证被压缩的序列(S’)和短语(P_i)的词典均被发送，以确保精确的解压缩。因而，发送组件必须保证压缩单元永不发送参照到词典短语，它在解压缩单元中不存在，从而不能由解压缩单元进行解参照。为保证该算法是完全增量的，IZ使用下面的图5中描述的过程发送S’和短语词典。

图5是示出按本发明的一个实施例的发送过程的流程图。在502使用指针(T)指向已被发送的压缩序列(S’)中的最后符号。从T到S’的末端的所有符号在将新的短语加入到词典(如图3中的步骤312)以前被发送。然后重复短语的两次出现在506用新建的短语替代，包括如在步骤312-320中在S’的末端的出现。然后，在508指针(T)被设成指向附在S’末端之后的新的短语。

图5中示出的实施例的效果是头两次发生重复短语时，它被不加修改地发送(可以想象在本发明的另外实施例中出现其他变化，下面将描述其中一些)。因为每次重复由嵌入的符号对组成，重复短语的第二次出现通常借助直接送出其内容(它只包括两个符号)而更有效地发送，而不是使用指针，后者需要额外的处理开销。因而解压缩算法以与压缩算法完全相同的形式接收重复短语的头两次出现。这就允许解压缩算法产生与压缩算法所产生的对重复的完全相同的词典短语。解压缩算法利用与压缩算法相同的短语编号技术，从而允许压缩算法将所有短语的未来出现只作为一个短语号发送。

DD108包括解压缩单元208，它在解压缩组件210中包括以如计算机程序，固件，或硬件形式的解压缩算法。图6是示出本发明的一个实施例的解压缩算法的流程图。该解压缩算法产生原始的输入流，同时保证完全与压缩算法同步。

每个压缩的符号在602被接收，而解压缩单元208在604判定，该符号是否为对如P_i那样的词典短语号的参照，若符号是那样的参照，解压缩单元208在606提取该短语号的内容并产生原始的输入序列。然后解压缩单元在608借助将短语的内容通过除最后发送步骤的所有压缩步骤而同步压缩和解压缩算法。

若符号不是对词典短语号的参照，则解压缩单元208在610将该符号通过所有压缩步骤(除最后的发送)以保证解压缩与压缩算法同步。此处理过程对所有接收的符号在612重复。

因为本发明的一个实施例恰恰在产生短语之前发送产生该短语所需的内容，它保证解压缩算法永不会在解压缩算法产生特定的短语之前接收对短语的参照。因此，压缩及解压缩之前接收对短语的参照。因此，压缩及解压缩算法能隐含地保证，它们保持同样的短语编号方案，并它们对应的词典包含同样的信息。注意，此隐含的词典同步技术需要被压缩算法发送的经压缩的数据以与发送完全相同的次序被解压缩单元接收。若某些被压缩的数据被解压缩单元次序紊乱地接收，或若某些被压缩的数据丢失，解压缩算法可以构成与压缩算法不同的词典，这可能转而导致不正确的解压缩。因此，在网络情况中，在压缩和解压缩单元之间发送的被压缩数据必须在可靠的传输信道发送。

IZ算法隐含地是增量的，因为发送点自动地由压缩算法确定，并不需要特定算法的选择。因此，也没有附加的计算开销来选择发送点或计算对发送的指针(如在LZ77或Sequitur的情况)。

图7是按本发明的一个实施例的发送技术的例子的图示。

在图7中，数据序列是“abababcabc”。注意，这不同于在图4中示出的例子。开始，指针T在502被设成第一个接收数据位置的前一个位置。在此例中使用上述参考图3的压缩技术。使用此压缩技术第一个新的词典短语被加到第4行。然而，在增加新的词典短语之前，发送组件204将S’中的发送从T到S’的末端所有符号。在此例子中，发送包括如图7中的第4行示出的符号“abab”。然后，在506使用图3所述的技术替代重复短语的所有出现。然后，指针(T)被设成等于刚加入的新的短语。在此例中，T被设成等于P₁在第4行中的第二次出现。

符号继续被接收及累积而不发送，直到接收到图7中第10行的序列。此时，第二个短语被加到词典(P₂＝P₁c)。在加入第二短语之前，发送组件204在504将发送从指针(T)到S’的末端所有S’中的符号。在此例中，发送符号“P₁cP₁c”。新短语在S’中的出现在506中按图3中描述的技术替代，且指针(T)在508被设成新加入短语的末端。在此例中，T被设成等于在图7的第10行中示出的S’中的第二个P₂。此过程对任何数量的数据继续。

上面发送过程隐含地同步了压缩和解压缩词典并保证解压缩单元总能解参照它接收的每个词典短语。本发明的另一个实施例使用直接的词典发送过程以保证所有短语的可解压缩性。此另外的发送过程是基于将短语在独立而并行的通信信道中发送到解压缩算法。每当压缩算法发现新的词典短语，它被加上标记“installed＝0”，指出该短语尚未被安装在解压缩词典中。此新的短语号和它的内容经可靠的传输信道被发送到解压缩单元。解压缩算法对每个它收到的规则送回确认。当压缩算法对短语收到确认，它在该短语上设置标记“installed＝1”，指出该短语已被接收并安装在解压缩词典中。在由压缩算法发送任何短语之前，该算法校验“installed”标记。若installed等于0，即FALSE(假)，则发送该短语的内容。注意，当短语的内容被发送时，该算法也必须递归地对在这些内容中的任何嵌入短语校验installed标记。若installed等于1，即TRUE(真)，发送短语本身。通过使用此另外的直接词典发送过程，压缩算法能同步两个词典并保证解压缩算法永不会接收不能解参照的短语。此方法还显著地改变了解压缩算法的结构。因为在此方法中词典短语直接发送到解压缩算法，它不需要从数据流中发现这些短语。因此，解压缩算法只需要解参照(即解压缩)它接收的数据并不需要处理通过压缩算法的短语检测器和删除组件的数据(在以前描述的隐含词典同步实施例中是必须的)。还注意到，在此直接词典发送模型中，词典同步不需要被压缩的数据在可靠的传输信道(即保证按顺序递交所有数据包的信道)中发送。因为被压缩的数据不用于隐含地同步词典，在压缩单元和解压缩单元之间的数据的丢失或数据提交次序紊乱将不导致不一致的词典，从而不导致不精确的解压缩。

在上述直接词典中，同步技术能以各种方法进一步优化。例如，只有遇到大于“N”次的短语能选择由压缩算法发送。设N＝1，将导致所有短语被发送，并因此提供最大的压缩和最快的收敛。但同时，为同步两个词典所需的附加带外词典发送通信量也将最大。当N增加时，压缩和收敛将降低，但额外的带外词典同步通信量也将降低。因而N能根据所遇到的通信量的类型动态地选择以便使总的输出通信量最小。而且，若有任何与发送单独词典短语更新有关的开销，可以缓存多个短语并作为单个数据包一起发送。

上述直接词典发送模型也能通过从解压缩算法对每个由压缩算法发送的词典更新消除确认的需要而优化。在上面实施例中，压缩单元必须从解压缩单元接收“短语收到”的确认，以便将对该短语的“installed”标记从0(即假)改到1(即真)，并从而允许压缩算法能在未来的压缩中使用该短语。此过程保证由压缩单元在被压缩的数据中发送的所有短语参照能由解压缩单元解参照以产生该短语的原始内容。在直接词典发送模型的另一个实施例中，在预定但动态调节的时间间隔之后，压缩算法自动地将对新发送的短语的installed标记从0改变到1。当短语从压缩单元(经独立可靠的词典传输信道)发送时，它被本地标记一时间标签(t₀)指出发送的时间。同时对被发送的短语的“installed”标记被初始化成0。在预定的时间间隔(T)以后，该短语的“installed”标记从0改变成1，从而允许压缩算法使用该短语于未来的压缩。此词典发送模式推测，若短语的更新在时间t₀从压缩单元发送到解压缩单元，则任何使用此短语并从压缩单元在时间t₀+T之后发送的被压缩数据在短语更新之后到达解压缩单元。时间间隔T能考虑到在压缩和解压缩单之间数据发送的速率和等待时间的可变性加以调节。此推测的词典发送模型改进了压缩的程度，因为它允许压缩单元在短语的更新被发送之后开始使用短语T秒，而不必等待从解压缩单元来的对该短语的确认。从而短语更快地成为可用，它产生更高的压缩。

因为上述推测的词典发送模型是基于在压缩和解压缩单元之间发送时间变化的估计，有可能在特定的短语的内容经由独立的词典同步信道被接收之前，解压缩单元接收在被压缩数据中的该短语的参照。当发生此情况时，解压缩单元发送信号给压缩单元，指出它(解压缩单元)在经由词典更新信道接收短语内容之前经数据信道接收到该短语。压缩单元使用从解压缩单元来的这些误差信号适本地调节在发送新短语和将该短语的installed标记改成1之间的时间间隔(T)。

上面推测词典发送模型的另一个组件是当解压缩算法接收到它不能精确地解参照的短语时它应能检测。这能用许多方法达到。推测的词典发送模型的一个实施例对在压缩单元和解压缩单元中发送和安装的短语的总数保持一个计数器。因为所有短语有序地发送和接收(由于它们经由可靠的传输信道发送)，这些计数器能用于检测在短语的内容经由词典同步信道接收之前是否解压缩信道经数据信道收到该短语的参照。在压缩单元的每个短语根据被安装的计数器的当前值用“本地安装的计数器”本地标记。每个从压缩单元发送的压缩的数据包，对在压缩数据包中参照的所有短语用“本地安装的计数器”的最大值标记。

此“最大安装计数器”指出在压缩的数据包中使用的最近“安装”的短语。当解压缩单元接收被压缩的数据包时，通过校验“最大安装计数器”是否大于其自己当前的安装计数器来检测该数据包是否包含非可解参照的短语。若是这样情况，则在压缩的数据包内至少存在一个解压缩单元尚未收到其更新的内容的短语。此事件随后被用于启动上述反馈机制以发送误差信号给压缩单元。用于计数发送和安装短语数的计数器最终能达到其最大值并返回到零。借助保证超过当前安装计数器的任何“本地安装的计数器”被复位到某个初始值(可能为0)来处理此情况。系统还保证，当发送计数器达到其最大值时，在对应于最大的计数器值的短语被压缩单元确认，压缩单元才发送任何新的短语更新。因而发送的解压缩单元除了对应于最大接收的计数器的短语更新以外不需要确认任何被接收的短语更新。

如上所述，为了使压缩技术在无穷尽的数据上连续地工作而不需要大的系统资源，压缩系统和技术应有效地可行地删除短语和符号以减少词典的大小。本发明达到了此目标。即因为短语词典和被压缩的序列S’使用系统资源(如系统存储器)保持它们的状态信息，为了保证本发明能在无限的数据流上连续地运行，必须提供有效的方法来从词典中删除老的短语并删除被压缩的序列S’的最老的部分。若这些“忘记”(删除)措施不具备，该算法最终将用完系统资源并必须终止。

因为短语是分层的(即短语能包含输入字(符号)或对其他短语(数据短语标识符)的参照)，不可能简单地删除短语而不管它是否被更高层短语参照。例如，若短语P_i被P_j参照(如P_j＝P_ia)，且P_i被删除，则P_j的任何未来使用将导致错误。因而，必须判定的不仅是哪个短语能删除，而且还要保证参照这些短语的所有短语也被删除。本发明通过在“最近最少使用(LRU)”的数据结构中表示所有短语来解决所有这些问题。在本发明的一个实施例中LRU作为链表实现，并每当在压缩期使用短语时使用LRU有效地将其移到表的前端。因而，若短语“P_i＝ab”在LRU的中间且符号ab出现在输入流中，则P_i从它在表的当前位置去除并附到该表当前前端(或头部)。建立的新短语也放在表的当前前端(或头部)。因而，在算法的任何点，在表的末端(或尾部)的短语是最近最少使用的短语。若必须删除短语以释放系统资源再度使用，则最近最少使用的短语将是首先要删除的。

虽然能使用LRU识别哪个短语要删除，但它没有指出哪个较高层短语参照此短语，因而也必须删除。本发明通过要求每个短语保持一个“父指针”来解决此问题，它总是保持该短语最近一次被参照的轨迹。例如，若P_i最近被P_j参照，而P_j最近被压缩的字符串S’参照，则P_i应包含到P_j的父指针，而P_j应包含指向S’中被使用的位置的父指针。图8a和8b是按本发明的一个实施例的删除技术的LRU和父指针的例子的图示。

在图8a中短语LRU和父指针直接图示在输入符号“ab”到达之后。

在图8b中短语LRU和父指针直接图示在输入符号“c”到达之后。

在图8中示出的数据结构允许算法能精确地判定实际哪个短语被另外的较高层短语参照。因此，能按照图9实现短语的删除。图9是示出按本发明的一个实施例的删除技术的流程图。

使用图9示出的技术，X在902设成在LRU尾部的短语。然后Y在904设成X的父指针。若在906如图8a，Y指向一个短语，则在LRU中从位置X到Y的所有短语在908被删除(包括X但不包括Y)，X在910设成Y，过程在步骤904处重复。若当906 Y指向符号，则删除单元208在919删除X并随后在920删除从S’的尾部到Y的所有符号。

此算法递归地保证，若任何短语被删除，在短语词典和在S’中对该短语的参照也被删除。此算法还导致从压缩的序列S’删除符号。因此，由不常访问的短语和S’中的老的符号占用的系统资源通过此技术能再度使用。若必须释放附加的资源，也能删除S’的尾部的符号而不应用上述短语删除算法。这能简单地从S’的尾部去除所需数目的符号(只要这些符号以前已被发送过)来完成。若被删除的符号是对一个短语的参照，则校验该特定的短语，判断其父指针是否指向S’中被删除的符号的位置。若是这样情况，则该父指针被设成空值，说明在S’中它所指向的符号已被删除。或者该短语及其后代(即指向它的其他短语)也能被删除。

也能使用上述短语和符号删除算法设定由本发明的系统和方法使用的系统存储器的数量的固定限制。两种删除算法招致最小的计算开销且不影响IZ算法的线性度。在处理无限输入流时，连续运行的IZ过程动态地选择要删除的短语和符号并重新使用释放的资源，以保证它不会超过预定的或浮动的限制。

在上述本发明的实施例中，对重复两次的每个符号对在词典中建立新的短语。它可以修改，使得仅当一个符号对至少重复K次时建立新的词典短语，其中K＝3，4，5等。此修改将减少在词典中短语的数目，并可增加或减少压缩的效率。

用本发明发送的数据能使用如算术编码那样的增量编码方案统计地编码。此步骤常常是不必要的，因为由统计编码得到的附加压缩与去除大的重复短语得到的压缩相比是微不足道的。例如，因为IZ能用单个短语号替代隔开很大距离的大的重复，通过删除和消除重复短语得到高度的压缩。在那样情况，由编码和压缩的序列得到的附加压缩将是微小的。因此，能避免与统计编码及其相关的计算开销而不会在压缩效率上有大的降低。这是与其他基于词典的技术相反，它们只能检测相当小的窗口内的重复并因此通过统计编码步骤得到它们主要的压缩。因此如果这些其他程序的输出不作统计编码，它们将大大地降低了压缩效率。

若由本发明产生的压缩数据在发送前包装成数据包，则该数据包能借助应用其他增量的或非增量的统计编码或压缩技术(如Huffman编码)作进一步处理。这可以是应用到输出的后处理步骤，因而不影响本发明的增量本质。

本发明在逻辑上对每个信道由两个通信模块组成，它们是压缩的。压缩模块在信道源处压缩数据，而解压缩模块在信道目标处解压缩数据。若单个源与多个目标通信，本发明能伸缩并重复，使得对每个目标存在单独的压缩模块。所有这些压缩模块能驻留在同一个压缩单元或设备。类似地，若多个源和单个目标通信，本发明能伸缩并重复，使得对每个源存在一个单独的解压缩模块。而且所有这些解压缩模块能驻留在同一个解压缩单元或设备。此外，多个压缩和解压缩模块能驻留在同一单元或设备上，它然后成为组合的压缩和解压缩单元。

本发明的本实施例对每压缩和解压缩模块使用独立的词典。本发明的另外的实施例使用在共存于同一源的多个压缩模块之间的共享词典。此另外的共享词典实施例能使用上述直接词典同步技术保证共享的压缩词典与每个解压缩词典同步。在压缩单元的共享词典能通过建立单个共享数据结构以存储所有由压缩算法学到的短语来实现。每个短语还保持共享的总体版本号，每当属于该短语的内容被删除或用新的短语替代时，此版本号增加。因此，在此共享的词典实施例中，所有压缩单元的检测器和删除组件能被共享。每个压缩单元具有它自己单独的发送单元，它保持独立的本地短语版本号和状态标志。当新的短语参照从检测器组件传送到发送组件以备发送到解压缩单元时，共享的总体版本号与对特定于给定的发送组件的本地版本号相比较。若两个号相同，则发送组件校验与短语相关的其本地状态标志，以判定该短语是否已被发送和安装。若两个号不同，则发送组件知道它是由共享的检测器组件建立的新短语。在此情况，发送组件复位状态标志以指出该短语尚未被发送，并根据上述直接词典发送协议处理该短语。此共享的词典发送实施例使能更有效的使用系统存储器资源，因为所有共存于同一设备的压缩单元共享单个短语层次和符号数据结构。所有短语的内容仅存入共享的数据结构中。加入到该设备的每个附加的压缩单元实际上只需要一个附加的短语索引表来存储每个短语的本地版本号及状态。

用于每个输入符号的字长是可变的。本发明用1，2，4个字节的字长实现，产生变化的结果。字长也能设成大于4个字节。因为算法的速度取决于它处理的符号的数目，较大的字长产生较大的数据通量。若每个符号对应于4个字节(即字长＝4字节)，该算法近似于在任何时间周期处理相当于每个符号对应于1个字节时的4倍的数据量。另一方面，使用4字节的字长使该算法不能检测在4个字节边界上发生的重复(即由一系列字节数分离的重复，而字节数不是4的倍数)。

在短语检测算法中使用的散列函数和表是灵活的。它们能优化成最适合于被压缩数据的类型。

用于短语LRU和压缩序列S’的链表能作为单链表或双链表实现。如阵列那样的其他数据结构也能使用并能提供更好的存储器使用。

如上所述，本发明是有效的压缩算法，它能检测并消除在实际上无限大小窗口内可变长度的重复短语。窗口的大小只受可用的系统存储器的大小的限制，并不影响算法的速度。不是使用在LZ77压缩技术中常用的几千字节的窗口大小，本发明能使用从数十到数千兆字节的窗口大小(只受系统资源的限制)，而在程序速度方面没有大的变化。因为在本发明中窗口只由压缩数据组成，关于未压缩的数据的窗口的实际大小能变化并超过数千兆字节(取决于压缩程度)。在窗口大小方面惊人的增加是重要的优点，因为它使算法能检测分隔很大距离的重复。因此不仅能压缩单个文件或对象，本发明能用于压缩多个文件或对象一起的任意集合，并因而达到高得多的压缩程度。因而本发明能用于压缩累积的交互对话的网络信息量的连续流，其中在不同对象或数据包之间的重复可被大量数据隔离。因而本发明能够既作对象内部的(本地的)压缩又作对象之间的(全局的或交互会话的)压缩而不是只作对象内部的压缩。

本发明的另外优点是它是完全增量的和连续的。因此，本发明能应用于无限数据流而没有算法失败或终止的危险。本发明增量地处理到达的输入并在线性的时间内连续地产生输出。本发明能配置成总是保持在固定大小的系统存储器内并永远不超过此预置的限制。算法通过动态地删除短语和符号并重新使用它们的资源以学到新的词典短语而达到此连续和流式的功能。该算法也是自适应的并学到新的词典短语以适应输入数据的变化。IZ算法的此隐含的增量的，连续的和线性的特性(除了它实际上无限搜索窗口大小)是独一无二的特征，它不包括在任何其他的通用无损压缩技术中。

本发明的另外优点是它的有效性。本发明线性地执行。即当输入数据量增加时执行时间不是非线性地(如指数地)增加。本发明的线性度不受程序的增量发送和连续短语/符号删除组件的影响。线性度也不受从中能检测重复的窗口大小的影响。因此，任何输入流能在正比于输入大小的时间内通过本发明压缩。此外，因为本发明使用短语的分层表示，整个词典能比其他基于词典的技术(如LZ77)更有效地存储。本发明只有当短语出现多于一次时才将它们加入词典。因此，词典项比在LZ78中更好地被利用，后者使用更积极和推测性的词典结构技术。本发明还比其他基于分层规则的技术更有效，因为它不需要任何附加的处理来选择增量发送点(如Sequitur的为选择发送点的计算量大的算法)。

本发明的隐含的词典短语的发送比其他基于指针的技术(如LZ77和Sequitur)更有效，因为本发明不需要使用标记或其他方法来计算并发送对每个指针的起始位置。由本发明使用的表示短语和符号的数据结构也比由Sequitur使用的有更高的存储效率。此外，本发明的重复的检测方法在检测长的重复时比Sequitur更有效，因为当重复的短语被扩展时，本发明不需要连续地建立和删除短语。

本发明是结合上述四个优点的仅有的通用无损压缩算法，它们是线性速度，实际上无限的窗口大小，隐含的增量性，和完全连续的压缩。这四个优点使本发明能在以前压缩尚未被成功地应用的广泛的领域中使用。例如，本发明能通过检测和消除类似的或同样的对象或数据包用于压缩网络数据流。本发明能用于改善在网络中经过任何两个通信节点的带宽利用。发送类似或相同的对象的任何网络结构能从此发明大大得益。例如，从内容提供者发出的万维网信息量常包含发送到不同用户的相同的或相似的对象。在此情况，本发明有用于趋同和压缩发送到不同用户的数据，并因而大大地减少了经因特网传输该数据的带宽需求。解压缩算法能在靠近终端用户处选出压缩流，并在将该数据送到用户之前将其扩展成其原始大小。这将不仅导致在压缩方和解压缩方之间大大降低带宽的使用，而且导致大大加快了数据向用户的传递。有若干本发明提供很大应用价值的其他网络情况，如在压缩经过专线网或虚拟专线网发送的数据中。此外，本发明能用于有效地压缩整个数据库以便更有效地存储和发送。

在所有这些情况中，本发明将提供高于其他压缩技术的附加实用价值，因为它能在线性时间内达到对象之间和对象内部(交互会话的)压缩。本发明在线性时间内运行，使用实际上无限的窗口大小，隐含地是增量的，并能连续地在无限输入流上运行，由于这些事实所有这些应用和益处是可能的。

虽然本发明参照较佳实施例和若干另选的实施例已予以特别示出和描述，但在相关领域中的技术人员可以理解，在不背离本发明的精神和范围的前提下可以作出在形式和细节方面的各种变化。

Claims (50)

1.一种用于压缩数据流的方法，包括下列步骤：

接收具有多个数据符号的数据流；

识别第一数据短语作为第一重复短语，所述的第一数据短语是第一数据项和至少第二数据项的组合，若所述第一数据短语匹配第一库短语，则所述第一库短语是在短语库中多个库短语之一；

若所述第一数据短语被识别为所述第一重复短语，则将所述第一数据短语用与所述第一库短语相关的第一数据短语标识符替代以产生压缩数据流；

若第一数据短语不匹配所述多个库短语的任何一个，则所述第一数据短语作为第二库短语存储。

若所述第一数据短语没有识别为所述第一重复短语，则将所述第一数据短语用与所述第二库短语相关的第二数据短语标识符替代，以产生压缩数据流；和

发送所述压缩数据流，同时还接收在所述数据流中的附加数据符号；

其中每个所述的数据短语包括固定数目的数据项；

其中每个所述的数据项是数据符号和数据短语标识符中之一。

2.如权利要求1的方法，其特征在于在每个所述库短语中数据项的固定数目是2。

3.如权利要求1的方法，其特征在于所述数据流的值在接收之前未知，其中所述压缩的数据流不损失任何数据，且其中压缩方法对具有任何长度的数据流操作。

4.如权利要求1的方法，其特征在于仅当所述第一数据短语在数据流的第一部分中出现固定次数时，所述第一数据短语才作为第二库短语被存储；且

其中仅当所述第一数据短语在数据流的第一部分中出现固定次数时，所述第一数据短语才用所述第二数据短语标识符替代。

5.如权利要求4的方法，其特征在于还包括下述步骤：

发送库短语，包括下列步骤：

识别尚未被发送的第一组库短语；

与所述第一组中所述库短语中任何一个相关的数据短语标识符作为所述的压缩数据流被发送之前，发送所述第一组库短语。

6.如权利要求5的方法，其特征在于还包括下述步骤：

根据第一准则删除所述多个库短语的第三库短语。

7.如权利要求6的方法，其特征在于所述第一准则是第一时间周期终止的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

8.如权利要求7的方法，其特征在于还包括下述步骤：

当所述第四库短语包括所述第三库短语时，删除第四库短语。

9.如权利要求4的方法，其特征在于还包括下列步骤：

接收所述的压缩数据流；和

根据所述的压缩数据流确定所述库短语。

10.如权利要求1的方法，其特征在于还包括下述步骤：

发送库短语，包括下列步骤：

识别尚未被发送的第一组库短语；

与所述第一组的所述库短语的任一个相关的数据短语标识符作为所述的压缩数据流被发送之前，发送所述的第一组库短语。

11.如权利要求10的方法，其特征在于还包括下述步骤：

根据第一准则删除所述多个库短语的第三库短语。

12.如权利要求11的方法，其特征在于所述第一准则是第一时间周期终止的准则，在此期间所述第一库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

13.发权利要求12的方法，其特征在于还包括下述步骤：

当所述第四库短语包括所述第三库短语时，删除第四库短语。

14.如权利要求1的方法，其特征在于还包括下列步骤：

接收所述的压缩数据流；和

根据所述的压缩数据流确定所述库短语。

15.如权利要求1的方法，其特征在于还包括下述步骤：

根据第一准则删除所述多个库短语的第三库短语。

16.如权利要求15的方法，其特征在于所述第一准则是第一时间周期终止的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

17.一种用于压缩数据流的系统，包括：

接收装置，用于接收具有多个数据符号的数据流；

识别装置，用于识别第一数据短语作为第一重复生语，所述第一数据短语是第一数据项和至少第二数据项的组合，若所述第一数据短语匹配第一库短语，则所述第一库短语是在短语库中多个库短语之一；

第一替代装置，用于若所述第一数据短语被识别为所述第一重复短语，则将所述第一数据短语用与所述第一库短语相关的第一数据短语标识符替代以产生压缩数据流；

第一存储装置，用于若第一数据短语不匹配所述多个库短语的任何一个，则将所述第一数据短语作为第二库短语存储；

第二替代装置，用于若所述第一数据短语没有识别为所述第一重复短语，则将所述第一数据短语用与所述第二库短语相关的第二数据短语标识符替代，以产生压缩数据流；和

发送装置，用于发送所述压缩数据流，同时还接收在所述数据流中的附加数据符号；

其中每个所述的数据短语包括固定数目的数据项；

其中每个所述的数据项是数据符号和数据短语标识符中之一。

18.如权利要求17的系统，其特征在于在每个所述库短语中数据项的固定数目是2。

19.如权利要求17的系统，其特征在于所述数据流的值在接收之前未知，其中所述压缩数据流不损失任何数据，且其中压缩方法对具有任何长度的数据流操作。

20.如权利要求17的系统，其特征在于仅当所述第一数据短语在数据流的第一部分中出现固定次数时，所述第一数据短语才作为第二库短语被存储；且

其中仅当所述第一数据短语在数据流的第一部分中出现固定次数时，所述第一数据短语才用所述第二数据短语标识符替代。

21.如权利要求20的系统，其特征在于还包括：

短语识别装置，用于识别尚未被发送的第一组库短语；

短语发送装置，用于在与所述第一组中所述库短语中任何一个相关的数据短语标识符作为所述的压缩数据流被发送之前，发送所述第一组库短语。

22.如权利要求21的系统，其特征在于还包括：

短语删除装置，用于根据第一准则删除所述多个库短语的第三库短语。

23.如权利要求22的系统，其特征在于所述第一准则是第一时间周期终止的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

24.如权利要求23的系统，其特征在于所述的删除装置在所述第四库短语包括所述第三库短语时，删除第四库短语。

25.如权利要求20的系统，其特征在于还包括：

接收装置，用于接收所述的压缩数据流；和

库建立装置，用于根据所述的压缩数据流确定所述库短语。

26.如权利要求17的系统，其特征在于还包括：

短语识别装置，用于识别尚未被发送的第一组库短语；

短语发送装置，用于在与所述第一组的所述库短语的任一个相关的数据短语标识符作为所述的压缩数据流被发送之前，发送所述的第一组库短语。

27.如权利要求26的系统，其特征在于还包括：

短语删除装置，用于根据第一准则删除所述多个库短语的第三库短语。

28.如权利要求27的系统，其特征在于所述的第一准则是第一时间周期走完的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

29.如权利要求28的系统，其特征在于所述的短语删除装置在所述第四库短语包括所述第三库短语时，删除第四库短语。

30.如权利要求17的系统，其特征在于还包括：

接收装置，用于接收所述压缩数据流；和

库建立装置，用于根据所述的压缩数据流确定所述库短语。

31.发权利要求17的系统，其特征在于还包括：

短语删除装置，用于根据第一准则删除所述多个库短语的第三库短语。

32.如权利要求31的系统，其特征在于所述的第一准则是第一时间周期终止的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

33.如权利要求32的系统，其特征在于所述的短语删除装置在所述第四库短语包括所述第三库短语时，删除第四库短语。

34.一种用于压缩数据流的系统，包括：

数据接收器，用于接收具有多个数据符号的数据流；

具有多个库短语的短语库；

连接到所述数据接收器的删除单元，包括：

第一识别单元，用于识别第一数据短语作为第一重复短语，所述第一数据短语是第一数据项和至少第二数据项的组合，若所述第一数据短语匹配第一库短语，则所述第一库短语是在短语库中多个库短语之一；

库建立单元，用于若第一数据短语不匹配所述多个库短语的任何一个，则将所述第一数据短语作为第二库短语存储；

替代单元，用于若所述第一数据短语被识别为所述第一重复短语，则将所述第一数据短语用与所述第一库短语相关的第一数据短语标识符替代以产生压缩数据流，并用于若所述第一数据短语没有识别为所述第一重复短语时，则将所述第一数据短语用与所述第二库短语相关的第二数据短语标识符替代，以产生压缩的数据流；和

发送单元，用于发送所述压缩数据流，同时还接收在所述数据流中的附加数据符号；

其中每个所述的数据短语包括固定数目的数据项；

其中每个所述的数据项是数据符号和数据短语标识符中之一。

35.如权利要求34的系统，其特征在于每个所述库短语中数据项的固定数目是2。

36.如权利要求34的系统，其特征在于所述数据流的值在接收之前未知，其中所述压缩的数据流不损失任何数据，且其中压缩方法对具有任何长度的数据流操作。

37.如权利要求34的系统，其特征在于仅当所述第一数据短语在数据流的第一部分中出现固定次数时，所述第一数据短语才作为第二库短语被存储；且

其中仅当所述第一数据短语在数据流的第一部分中出现固定次数时，所述第一数据短语才用所述第二数据短语标识符替代。

38.如权利要求37的系统，其特征在于还包括：

库短语识别器，用于识别尚未被发送的第一组库短语；

库发送器，用于在与所述第一组中所述库短语中任何一个相关的数据短语标识符作为所述的压缩数据流被发送之前，发送所述第一组库短语。

39.如权利要求38的系统，其特征在于还包括：

删除单元，用于根据第一准则删除所述多个库短语的第三库短语。

40.如权利要求39的系统，其特征在于所述第一准则是第一时间周期终止的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中中所述第三数据短语未被参照。

41.如权利要求40的系统，其特征在于所述的删除单元在所述第四库短语包括所述第三库短语时，删除第四库短语。

42.如权利要求37的系统，其特征在于还包括：

接收单元，用于接收所述压缩数据流；和

库确定单元，用于根据所述的压缩数据流确定所述库短语。

43.如权利要求34的系统，其特征在于还包括：

库短语识别器，用于识别尚未被发送的第一组库单元。

库发送器，用于在与所述第一组中的所述库短语的任一个相关的数据短语标识符作为所述压缩数据流被发送之前，发送所述的第一组库短语。

44.如权利要求43的系统，其特征在于还包括：

删除单元，用于根据第一准则删除所述多个库短语的第三库短语。

45.如权利要求44的系统，其特征在于所述的第一准则是第一时间周期终止的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

46.如权利要求45的系统，其特征在于所述删除单元在所述第四库短语包括所述第三库短语时，删除第四库短语。

47.如权利要求34的系统，其特征在于还包括：

接收单元，用于接收所述压缩数据流；和

库确定单元，用于根据所述压缩数据流确定所述库短语。

48.如权利要求34的系统，其特征在于还包括：

删除单元，用于根据第一准则删除所述多个库短语的第三库短语。

49.如权利要求48的系统，其特征在于所述的第一准则是第一时间周期终止的准则，在此期间所述第三库短语未被参照，并接收第一数量的符号，其中所述第三数据短语未被参照。

50.如权利要求49的系统，其特征在于所述删除单元在所述第四库短语包括所述第三库短语时，删除第四库短语。

Images