A Universal Algorithm for Sequential Data Compression
用于顺序数据压缩的通用算法

IN MANY situations arising in digital communications and data processing, the encountered strings of data display various structural regularities or are otherwise subject to certain constraints, thereby allowing for storage and time-saving techniques of data compression. Given a discrete data source, the problem of data compression is first to identify the limitations of the source, and second to devise a coding scheme which, subject to certain performance criteria, will best compress the given source.
在数字通信和数据处理中的许多情况下,遇到的数据串显示各种结构性规则或受到某些约束,从而允许使用数据压缩的存储和节时技术。给定一个离散数据源,数据压缩的问题首先是识别该源的局限性,其次是设计一个在某些性能标准下最佳压缩给定源的编码方案。

Once the relevant source parameters have been identified, the problem reduces to one of minimum-redundancy coding. This phase of the problem has received extensive treatment in the literature [1]-[7].
一旦确定了相关的源参数,问题就简化为最小冗余编码的问题。这个问题的这一阶段在文献[1]-[7]中已经得到了广泛的研究。

When no a priori knowledge of the source characteristics is available, and if statistical tests are either impossible or unreliable, the problem of data compression becomes considerably more complicated. In order to overcome these difficulties one must resort to universal coding schemes whereby the coding process is interlaced with a learning process for the varying source characteristics [8], [9]. Such coding schemes inevitably require a larger working memory space and generally employ performance criteria that are appropriate for a wide variety of sources.
当没有先验源特征知识可用,且统计检验要么不可能要么不可靠时,数据压缩问题将变得更加复杂。为克服这些困难,必须依赖通用编码方案,其中编码过程与对变化源特征的学习过程交织在一起。这种编码方案必然需要更大的工作内存空间,并通常采用适合多种源的性能准则。

In this paper, we describe a universal coding scheme which can be applied to any discrete source and whose performance is comparable to certain optimal fixed code book schemes designed for completely specified sources. For lack of adequate criteria, we do not attempt to rank the proposed scheme with respect to other possible universal coding schemes. Instead, for the broad class of sources defined in Section III, we derive upper bounds on the compression efficiency attainable with full a priori knowledge of the source by fixed code book schemes, and
在本文中，我们描述了一种通用编码方案，可应用于任何离散源，其性能可与为特定源设计的某些最优定长码本方案相媲美。由于缺乏适当的标准，我们没有尝试将所提出的方案与其他可能的通用编码方案进行排名比较。相反，对于第三节中定义的广泛源类，我们推导了利用定长码本方案在完全事先知道源的情况下可以达到的最大压缩效率的上界。

then show that the efficiency of our universal code with no a priori knowledge of the source approaches those bounds.
然后证明我们的无先验知识的通用编码的效率接近于这些界限。

The proposed compression algorithm is an adaptation of a simple copying procedure discussed recently [10] in a study on the complexity of finite sequences. Basically, we employ the concept of encoding future segments of the source-output via maximum-length copying from a buffer containing the recent past output. The transmitted codeword consists of the buffer address and the length of the copied segment. With a predetermined initial load of the buffer and the information contained in the codewords, the source data can readily be reconstructed at the decoding end of the process.
该提议的压缩算法是对最近[10]在关于有限序列复杂性的研究中讨论的简单复制过程的改编。基本上,我们采用通过从包含最近过去输出的缓冲区进行最大长度复制来对源输出的未来段进行编码的概念。传输的代码字由缓冲区地址和复制段的长度组成。通过缓冲区的预定初始负载和代码字中包含的信息,可以在解码过程的末端轻松地重构源数据。

The main drawback of the proposed algorithm is its susceptibility to error propagation in the event of a channel error.
所提出算法的主要缺点是易受信道错误传播的影响。

The proposed compression algorithm consists of a rule for parsing strings of symbols from a finite alphabet $A$$A$AA into substrings, or words, whose lengths do not exceed a prescribed integer $L_s$$L_s$L_(s)L_{s}, and a coding scheme which maps these substrings sequentially into uniquely decipherable codewords of fixed length $L_c$$L_c$L_(c)L_{c} over the same alphabet $A$$A$AA.
提议的压缩算法由以下两部分组成:一个将来自有限字母表 $A$$A$AA 的符号串解析为长度不超过预定整数 $L_s$$L_s$L_(s)L_{s} 的子串(或单词)的规则,以及一个将这些子串按顺序映射到同一字母表 $A$$A$AA 上的固定长度 $L_c$$L_c$L_(c)L_{c} 的唯一可解密编码字的编码方案。

The word-length bounds $L_s$$L_s$L_(s)L_{s} and $L_c$$L_c$L_(c)L_{c} allow for boundeddelay encoding and decoding, and they are related by
词长界限 $L_s$$L_s$L_(s)L_{s} 和 $L_c$$L_c$L_(c)L_{c} 允许有界延迟编码和解码,它们之间有如下关系

where $\lceil x\rceil$$\lceil x\rceil$|~x~|\lceil x\rceil is the least integer not smaller than $x$$x$xx, the logarithm base is the cardinality $\alpha$$\alpha$alpha\alpha of the alphabet $A$$A$AA, and $n$$n$nn is the length of a buffer, employed at the encoding end of the process, which stores the latest $n$$n$nn symbols emitted by the source. The exact relationship between $n$$n$nn and $L_s$$L_s$L_(s)L_{s} is discussed in Section III. Typically, $n\simeq L_s{\alpha }^{h{L}_s}$$n\simeq L_s{\alpha }^{h{L}_s}$n≃L_(s)alpha^(hL_(s))n \simeq L_{s} \alpha^{h L_{s}}, where 0 $<h<1$$<h<1$< h < 1<h<1. For on-line decoding, a buffer of similar length has to be employed at the decoding end also.
其中 $\lceil x\rceil$$\lceil x\rceil$|~x~|\lceil x\rceil 是不小于 $x$$x$xx 的最小整数,对数底数是字母表 $A$$A$AA 的基数 $\alpha$$\alpha$alpha\alpha , $n$$n$nn 是编码端使用的缓冲区长度,存储源最近输出的 $n$$n$nn 个符号。 $n$$n$nn 和 $L_s$$L_s$L_(s)L_{s} 之间的确切关系在第三节中讨论。通常, $n\simeq L_s{\alpha }^{h{L}_s}$$n\simeq L_s{\alpha }^{h{L}_s}$n≃L_(s)alpha^(hL_(s))n \simeq L_{s} \alpha^{h L_{s}} ,其中 0 $<h<1$$<h<1$< h < 1<h<1 。对于在线解码,解码端也需要使用类似长度的缓冲区。

To describe the exact mechanics of the parsing and coding procedures, we need some preparation by way of notation and definitions.
为了描述解析和编码过程的确切机制,我们需要通过符号和定义进行一些准备工作。

Consider a finite alphabet $A$$A$AA of $\alpha$$\alpha$alpha\alpha symbols, say $A=$$A=$A=A= $\{0,1,\cdots ,\alpha -1\}$$\{0,1,\cdots ,\alpha -1\}${0,1,cdots,alpha-1}\{0,1, \cdots, \alpha-1\}. A string, or word, $S$$S$SS of length $\ell (S)=k$$\ell (S)=k$ℓ(S)=k\ell(S)=k over $A$$A$AA is an ordered $k$$k$kk-tuple $S=s_1{s}_2\cdots s_k$$S=s_1{s}_2\cdots s_k$S=s_(1)s_(2)cdotss_(k)S=s_{1} s_{2} \cdots s_{k} of symbols from $A$$A$AA. To indicate a substring of $S$$S$SS which starts at position $i$$i$ii and ends at position $j$$j$jj, we write $S(i,j)$$S(i,j)$S(i,j)S(i, j). When $i\le j,S(i,j)=$$i\le j,S(i,j)=$i <= j,S(i,j)=i \leq j, S(i, j)= $s_i{s}_{i+1}\cdots s_j$$s_i{s}_{i+1}\cdots s_j$s_(i)s_(i+1)cdotss_(j)s_{i} s_{i+1} \cdots s_{j}, but when $i>j$$i>j$i > ji>j, we take $S(i,j)=\mathrm{\Lambda }$$S(i,j)=\mathrm{\Lambda }$S(i,j)=LambdaS(i, j)=\Lambda, the null string of length zero.
考虑一个有限字母表 $A$$A$AA ，其中有 $\alpha$$\alpha$alpha\alpha 个符号，如 $A=$$A=$A=A= $\{0,1,\cdots ,\alpha -1\}$$\{0,1,\cdots ,\alpha -1\}${0,1,cdots,alpha-1}\{0,1, \cdots, \alpha-1\} 。长度为 $\ell (S)=k$$\ell (S)=k$ℓ(S)=k\ell(S)=k 的字符串或单词 $S$$S$SS 是从 $A$$A$AA 中选择的符号的有序 $k$$k$kk 元组 $S=s_1{s}_2\cdots s_k$$S=s_1{s}_2\cdots s_k$S=s_(1)s_(2)cdotss_(k)S=s_{1} s_{2} \cdots s_{k} 。为了表示 $S$$S$SS 中从位置 $i$$i$ii 开始到位置 $j$$j$jj 结束的子字符串，我们写为 $S(i,j)$$S(i,j)$S(i,j)S(i, j) 。当 $i\le j,S(i,j)=$$i\le j,S(i,j)=$i <= j,S(i,j)=i \leq j, S(i, j)= $s_i{s}_{i+1}\cdots s_j$$s_i{s}_{i+1}\cdots s_j$s_(i)s_(i+1)cdotss_(j)s_{i} s_{i+1} \cdots s_{j} 时,但是当 $i>j$$i>j$i > ji>j 时,我们取 $S(i,j)=\mathrm{\Lambda }$$S(i,j)=\mathrm{\Lambda }$S(i,j)=LambdaS(i, j)=\Lambda ,即长度为零的空字符串。

The concatenation of strings $Q$$Q$QQ and $R$$R$RR forms a new string $S=QR$$S=QR$S=QRS=Q R; if $\ell (Q)=k$$\ell (Q)=k$ℓ(Q)=k\ell(Q)=k and $\ell (R)=m$$\ell (R)=m$ℓ(R)=m\ell(R)=m, then $\ell (S)=k+m,Q$$\ell (S)=k+m,Q$ℓ(S)=k+m,Q\ell(S)=k+m, Q $=S(1,k)$$=S(1,k)$=S(1,k)=S(1, k), and $R=S(k+1,k+m)$$R=S(k+1,k+m)$R=S(k+1,k+m)R=S(k+1, k+m). For each $j,0\le j\le$$j,0\le j\le$j,0 <= j <=j, 0 \leq j \leq
字符串 $Q$$Q$QQ 和 $R$$R$RR 的连接形成一个新的字符串 $S=QR$$S=QR$S=QRS=Q R ;如果 $\ell (Q)=k$$\ell (Q)=k$ℓ(Q)=k\ell(Q)=k 和 $\ell (R)=m$$\ell (R)=m$ℓ(R)=m\ell(R)=m ,则 $\ell (S)=k+m,Q$$\ell (S)=k+m,Q$ℓ(S)=k+m,Q\ell(S)=k+m, Q $=S(1,k)$$=S(1,k)$=S(1,k)=S(1, k) , $R=S(k+1,k+m)$$R=S(k+1,k+m)$R=S(k+1,k+m)R=S(k+1, k+m) 。对于每个 $j,0\le j\le$$j,0\le j\le$j,0 <= j <=j, 0 \leq j \leq
$\ell (S),S(1,j)$$\ell (S),S(1,j)$ℓ(S),S(1,j)\ell(S), S(1, j) is called a prefix of $S;S(1,j)$$S;S(1,j)$S;S(1,j)S ; S(1, j) is a proper prefix of $S$$S$SS if $j<\ell (S)$$j<\ell (S)$j < ℓ(S)j<\ell(S).
$\ell (S),S(1,j)$$\ell (S),S(1,j)$ℓ(S),S(1,j)\ell(S), S(1, j) 是 $S;S(1,j)$$S;S(1,j)$S;S(1,j)S ; S(1, j) 的前缀,如果 $j<\ell (S)$$j<\ell (S)$j < ℓ(S)j<\ell(S) ,则 $\ell (S),S(1,j)$$\ell (S),S(1,j)$ℓ(S),S(1,j)\ell(S), S(1, j) 是 $S;S(1,j)$$S;S(1,j)$S;S(1,j)S ; S(1, j) 的真前缀。

Given a proper prefix $S(1,j)$$S(1,j)$S(1,j)S(1, j) of a string $S$$S$SS and a positive integer $i$$i$ii such that $i\le j$$i\le j$i <= ji \leq j, let $L(i)$$L(i)$L(i)L(i) denote the largest nonnegative integer $\ell ⩽\ell (S)-j$$\ell ⩽\ell (S)-j$ℓ <= ℓ(S)-j\ell \leqslant \ell(S)-j such that
给定一个字符串 $S$$S$SS 的合适前缀 $S(1,j)$$S(1,j)$S(1,j)S(1, j) 和一个正整数 $i$$i$ii ,使得 $i\le j$$i\le j$i <= ji \leq j ,令 $L(i)$$L(i)$L(i)L(i) 表示最大的非负整数 $\ell ⩽\ell (S)-j$$\ell ⩽\ell (S)-j$ℓ <= ℓ(S)-j\ell \leqslant \ell(S)-j ,使得

and let $p$$p$pp be a position of $S(1,j)$$S(1,j)$S(1,j)S(1, j) for which
并且让 $p$$p$pp 成为 $S(1,j)$$S(1,j)$S(1,j)S(1, j) 的一个位置

The substring $S(j+1,j+L(p))$$S(j+1,j+L(p))$S(j+1,j+L(p))S(j+1, j+L(p)) of $S$$S$SS is called the reproducible extension of $S(1,j)$$S(1,j)$S(1,j)S(1, j) into $S$$S$SS, and the integer $p$$p$pp is called the pointer of the reproduction. For example, if $S$$S$SS $=00101011$$=00101011$=00101011=00101011 and $j=3$$j=3$j=3j=3, then $L(1)=1$$L(1)=1$L(1)=1L(1)=1 since $S(j+1,j+1)=$$S(j+1,j+1)=$S(j+1,j+1)=S(j+1, j+1)= $S(1,1)$$S(1,1)$S(1,1)S(1,1) but $S(j+1,j+2)\ne S(1,2)$$S(j+1,j+2)\ne S(1,2)$S(j+1,j+2)!=S(1,2)S(j+1, j+2) \neq S(1,2). Similarly, $L(2)=4$$L(2)=4$L(2)=4L(2)=4 and $L(3)=0$$L(3)=0$L(3)=0L(3)=0. Hence, $S(3+1,3+4)=0101$$S(3+1,3+4)=0101$S(3+1,3+4)=0101S(3+1,3+4)=0101 is the reproducible extension of $S(1,3)=001$$S(1,3)=001$S(1,3)=001S(1,3)=001 into $S$$S$SS with pointer $p=2$$p=2$p=2p=2.
$S(j+1,j+L(p))$$S(j+1,j+L(p))$S(j+1,j+L(p))S(j+1, j+L(p)) 是 $S$$S$SS 的可重复扩展到 $S$$S$SS ，整数 $p$$p$pp 是该重复的指针。例如，如果 $S$$S$SS $=00101011$$=00101011$=00101011=00101011 和 $j=3$$j=3$j=3j=3 ，那么 $L(1)=1$$L(1)=1$L(1)=1L(1)=1 ，因为 $S(j+1,j+1)=$$S(j+1,j+1)=$S(j+1,j+1)=S(j+1, j+1)= $S(1,1)$$S(1,1)$S(1,1)S(1,1) 但 $S(j+1,j+2)\ne S(1,2)$$S(j+1,j+2)\ne S(1,2)$S(j+1,j+2)!=S(1,2)S(j+1, j+2) \neq S(1,2) 。同样地， $L(2)=4$$L(2)=4$L(2)=4L(2)=4 和 $L(3)=0$$L(3)=0$L(3)=0L(3)=0 。因此， $S(3+1,3+4)=0101$$S(3+1,3+4)=0101$S(3+1,3+4)=0101S(3+1,3+4)=0101 是 $S(1,3)=001$$S(1,3)=001$S(1,3)=001S(1,3)=001 到 $S$$S$SS 的可重复扩展，指针为 $p=2$$p=2$p=2p=2 。

Now, to describe the encoding process, let $S=s_1{s}_2\dots$$S=s_1{s}_2\dots$S=s_(1)s_(2)dotsS=s_{1} s_{2} \ldots denote the string of symbols emitted by the source. The sequential encoding of $S$$S$SS entails parsing $S$$S$SS into successive source words, $S=S_1{S}_2\cdots$$S=S_1{S}_2\cdots$S=S_(1)S_(2)cdotsS=S_{1} S_{2} \cdots, and assigning a codeword $C_i$$C_i$C_(i)C_{i} for each $S_i$$S_i$S_(i)S_{i}. For bounded-delay encoding, the length ${\ell }_i$${\ell }_i$ℓ_(i)\ell_{i} of each $S_i$$S_i$S_(i)S_{i} is at most equal to a predetermined parameter $L_s$$L_s$L_(s)L_{s}, while each $C_i$$C_i$C_(i)C_{i} is of fixed length $L_c$$L_c$L_(c)L_{c} as given by (1).
现在,为了描述编码过程,让 $S=s_1{s}_2\dots$$S=s_1{s}_2\dots$S=s_(1)s_(2)dotsS=s_{1} s_{2} \ldots 表示源发出的符号串。 $S$$S$SS 的顺序编码涉及将 $S$$S$SS 解析为连续的源字, $S=S_1{S}_2\cdots$$S=S_1{S}_2\cdots$S=S_(1)S_(2)cdotsS=S_{1} S_{2} \cdots ,并为每个 $S_i$$S_i$S_(i)S_{i} 分配一个代码字 $C_i$$C_i$C_(i)C_{i} 。对于有界延迟编码,每个 $S_i$$S_i$S_(i)S_{i} 的长度 ${\ell }_i$${\ell }_i$ℓ_(i)\ell_{i} 最多等于预先确定的参数 $L_s$$L_s$L_(s)L_{s} ,而每个 $C_i$$C_i$C_(i)C_{i} 的长度 $L_c$$L_c$L_(c)L_{c} 是固定的,由(1)式给出。

To initiate the encoding process, we assume that the output $S$$S$SS of the source was preceded by a string $Z$$Z$ZZ of $n-$$n-$n-n- $L_s$$L_s$L_(s)L_{s} zeros, and we store the string $B_1=ZS(1,L_s)$$B_1=ZS\left(1,L_s\right)$B_(1)=ZS(1,L_(s))B_{1}=Z S\left(1, L_{s}\right) in the buffer. If $S(1,j)$$S(1,j)$S(1,j)S(1, j) is the reproducible extension of $Z$$Z$ZZ into $ZS(1,L_s-1)$$ZS\left(1,L_s-1\right)$ZS(1,L_(s)-1)Z S\left(1, L_{s}-1\right), then $S_1=S(1,j+1)$$S_1=S(1,j+1)$S_(1)=S(1,j+1)S_{1}=S(1, j+1) and ${\ell }_1=j+1$${\ell }_1=j+1$ℓ_(1)=j+1\ell_{1}=j+1. To determine the next source word, we shift out the first ${\ell }_1$