A Block-sorting Lossless Data Compression Algorithm
一种块排序无损数据压缩算法
M. Burrows and D.J. Wheeler
M. Burrows 和 D.J. Wheeler

Systems Research Center 系统研究中心
130 Lytton Avenue 130 利顿大道
Palo Alto, California 94301
帕洛阿尔托，加利福尼亚 94301

The charter of SRC is to advance both the state of knowledge and the state of the art in computer systems. From our establishment in 1984, we have performed basic and applied research to support Digital’s business objectives. Our current work includes exploring distributed personal computing on multiple platforms, networking, programming technology, system modelling and management techniques, and selected applications.
, SRC 的章程是推进计算机系统的知识状态和技术状态。自 1984 年成立以来，我们进行了基础和应用研究，以支持 Digital 的商业目标。我们目前的工作包括探索多个平台上的分布式个人计算、网络、编程技术、系统建模和管理技术以及选定的应用。
Our strategy is to test the technical and practical value of our ideas by building hardware and software prototypes and using them as daily tools. Interesting systems are too complex to be evaluated solely in the abstract; extended use allows us to investigate their properties in depth. This experience is useful in the short term in refining our designs, and invaluable in the long term in advancing our knowledge. Most of the major advances in information systems have come through this strategy, including personal computing, distributed systems, and the Internet.
我们的策略是通过构建硬件和软件原型并使用它们作为日常工具来测试我们想法的技术和实践价值。有趣的系统过于复杂，不能仅仅在抽象层面进行评估；长期使用使我们能够深入了解它们的特性。这种经验在短期内有助于完善我们的设计，在长期内对提升我们的知识具有无价价值。信息系统的大部分重大进步都是通过这种策略实现的，包括个人计算、分布式系统和互联网。

We also perform complementary work of a more mathematical flavor. Some of it is in established fields of theoretical computer science, such as the analysis of algorithms, computational geometry, and logics of programming. Other work explores new ground motivated by problems that arise in our systems research.
我们还在数学味更浓的补充工作中发挥作用。其中一些工作在理论计算机科学已建立的领域，如算法分析、计算几何和程序逻辑。其他工作则探索由我们的系统研究中出现的问题所激发的新领域。
We have a strong commitment to communicating our results; exposing and testing our ideas in the research and development communities leads to improved understanding. Our research report series supplements publication in professional journals and conferences. We seek users for our prototype systems among those with whom we have common interests, and we encourage collaboration with university researchers.
我们对我们沟通结果有强烈的承诺；在研发社区中展示和测试我们的想法，有助于提高理解。我们的研究报告系列补充了在专业期刊和会议上的发表。我们在与我们共同感兴趣的人群中寻找原型系统的用户，并鼓励与大学研究人员合作。

Robert W. Taylor, Director
罗伯特·W·泰勒，总监

May 10, 1994 1994 年 5 月 10 日

David Wheeler is a Professor of Computer Science at the University of Cambridge, U.K. His electronic mail address is: djw3@cl.cam.ac.uk
David Wheeler 是英国剑桥大学计算机科学教授，他的电子邮件地址是：djw3@cl.cam.ac.uk
©Digital Equipment Corporation 1994.
©数字设备公司 1994.

This work may not be copied or reproduced in whole or in part for any commercial purpose. Permission to copy in whole or in part without payment of fee is granted for nonprofit educational and research purposes provided that all such whole or partial copies include the following: a notice that such copying is by permission of the Systems Research Center of Digital Equipment Corporation in Palo Alto, California; an acknowledgment of the authors and individual contributors to the work; and all applicable portions of the copyright notice. Copying, reproducing, or republishing for any other purpose shall require a license with payment of fee to the Systems Research Center. All rights reserved.
本作品不得全部或部分用于任何商业目的进行复制或再生产。为非营利性教育和研究目的，在全部或部分复制时无需支付费用，但须包括以下内容：注明此类复制已获得加州帕洛阿尔托数字设备公司系统研究中心的许可；承认本作品的作者和个别贡献者；以及所有适用的版权声明部分。为任何其他目的的复制、再生产或重新发布，均需向系统研究中心支付费用并取得许可。版权所有。

We describe a block-sorting, lossless data compression algorithm, and our implementation of that algorithm. We compare the performance of our implementation with widely available data compressors running on the same hardware.
我们描述了一种块排序、无损数据压缩算法，以及该算法的实现。我们比较了我们的实现与在相同硬件上运行的广泛可用的数据压缩器的性能。

The algorithm works by applying a reversible transformation to a block of input text. The transformation does not itself compress the data, but reorders it to make it easy to compress with simple algorithms such as move-to-front coding.
该算法通过将输入文本块应用可逆变换来工作。这种变换本身并不压缩数据，而是重新排列它，使其易于使用简单的算法（如前向移动编码）进行压缩。

Our algorithm achieves speed comparable to algorithms based on the techniques of Lempel and Ziv, but obtains compression close to the best statistical modelling techniques. The size of the input block must be large (a few kilobytes) to achieve good compression.
我们的算法在速度上与基于 Lempel 和 Ziv 技术的算法相当，但压缩效果接近最佳的统计建模技术。输入块的大小必须大（几 KB）才能实现良好的压缩。

1 Introduction … 1 1 引言 … 1
2 The reversible transformation … 2
2 可逆转换…2
3 Why the transformed string compresses well … 5
3 为什么转换后的字符串压缩得很好……5
4 An efficient implementation … 8
4 一个高效的实现……8
4.1 Compression … 8
4.1 压缩 … 8
4.2 Decompression … 12
4.2 解压缩 … 12
5 Algorithm variants … 13
5 算法变体 … 13
6 Performance of implementation … 15
6 实现性能 … 15
7 Conclusions … 16
7 结论 … 16

The most widely used data compression algorithms are based on the sequential data compressors of Lempel and Ziv [1, 2]. Statistical modelling techniques may produce superior compression [3], but are significantly slower.
最广泛使用的数据压缩算法基于 Lempel 和 Ziv 的顺序数据压缩器[1, 2]。统计建模技术可能产生更优的压缩[3]，但速度明显较慢。

In this paper, we present a technique that achieves compression within a percent or so of that achieved by statistical modelling techniques, but at speeds comparable to those of algorithms based on Lempel and Ziv’s.
在这篇论文中，我们介绍了一种技术，它实现的压缩效果与统计建模技术相当，但速度与基于 Lempel 和 Ziv 算法的速度相当。

Our algorithm does not process its input sequentially, but instead processes a block of text as a single unit. The idea is to apply a reversible transformation to a block of text to form a new block that contains the same characters, but is easier to compress by simple compression algorithms. The transformation tends to group characters together so that the probability of finding a character close to another instance of the same character is increased substantially. Text of this kind can easily be compressed with fast locally-adaptive algorithms, such as move-to-front coding [4] in combination with Huffman or arithmetic coding.
我们的算法不是按顺序处理输入，而是将一段文本作为一个整体进行处理。其思路是对一段文本应用可逆变换，形成一个包含相同字符的新块，但更容易通过简单的压缩算法进行压缩。这种变换倾向于将字符分组，从而显著增加找到与另一个相同字符实例相邻的字符的概率。这种类型的文本可以很容易地通过快速局部自适应算法进行压缩，例如与霍夫曼或算术编码结合的移动到前编码[4]。

Briefly, our algorithm transforms a string $S$$S$SS of $N$$N$NN characters by forming the $N$$N$NN rotations (cyclic shifts) of $S$$S$SS, sorting them lexicographically, and extracting the last character of each of the rotations. A string $L$$L$LL is formed from these characters, where the $i$$i$ii th character of $L$$L$LL is the last character of the $i$$i$ii th sorted rotation. In addition to $L$$L$LL, the algorithm computes the index $I$$I$II of the original string $S$$S$SS in the sorted list of rotations. Surprisingly, there is an efficient algorithm to compute the original string $S$$S$SS given only $L$$L$LL and $I$$I$II.
简要来说，我们的算法通过形成 $S$$S$SS 的 $N$$N$NN 次旋转（循环移位），按字典顺序排序，并提取每个旋转的最后字符，将 $N$$N$NN 个字符的字符串 $S$$S$SS 转换为字符串 $L$$L$LL ，其中 $L$$L$LL 的第 $i$$i$ii 个字符是第 $i$$i$ii 个排序旋转的最后字符。除了 $L$$L$LL 之外，算法还计算原始字符串 $S$$S$SS 在旋转排序列表中的索引 $I$$I$II 。令人惊讶的是，有一个高效的算法可以仅根据 $L$$L$LL 和 $I$$I$II 计算原始字符串 $S$$S$SS 。

The sorting operation brings together rotations with the same initial characters. Since the initial characters of the rotations are adjacent to the final characters, consecutive characters in $L$$L$LL are adjacent to similar strings in $S$$S$SS. If the context of a character is a good predictor for the character, $L$$L$LL will be easy to compress with a simple locally-adaptive compression algorithm.
排序操作将具有相同初始字符的旋转组合在一起。由于旋转的初始字符与最终字符相邻， $L$$L$LL 中的连续字符与 $S$$S$SS 中的相似字符串相邻。如果字符的上下文是字符的良好预测器，则使用简单的本地自适应压缩算法对 $L$$L$LL 进行压缩将变得容易。

In the following sections, we describe the transformation in more detail, and show that it can be inverted. We explain more carefully why this transformation tends to group characters to allow a simple compression algorithm to work more effectively. We then describe efficient techniques for implementing the transformation and its inverse, allowing this algorithm to be competitive in speed with Lempel-Ziv-based algorithms, but achieving better compression. Finally, we give the performance of our implementation of this algorithm, and compare it with well-known compression programmes.
在以下章节中，我们更详细地描述了这种转换，并展示了它是可以逆的。我们更仔细地解释了为什么这种转换倾向于将字符分组，以便简单的压缩算法能更有效地工作。然后，我们描述了实现这种转换及其逆变换的高效技术，使该算法在速度上与基于 Lempel-Ziv 的算法具有竞争力，但实现了更好的压缩。最后，我们给出了我们实现此算法的性能，并将其与著名的压缩程序进行了比较。

The algorithm described here was discovered by one of the authors (Wheeler) in 1983 while he was working at AT&T Bell Laboratories, though it has not previously been published.
该算法是由作者之一（Wheeler）在 1983 年当他还在 AT&T 贝尔实验室工作时发现的，尽管它之前尚未发表。

This section describes two sub-algorithms. Algorithm C performs the reversible transformation that we apply to a block of text before compressing it, and Algorithm D performs the inverse operation. A later section suggests a method for compressing the transformed block of text.
本节描述了两个子算法。算法 C 执行我们在压缩文本块之前应用的可逆变换，而算法 D 执行逆操作。后面的章节建议了一种压缩变换后的文本块的方法。

In the description below, we treat strings as vectors whose elements are characters.
在下面的描述中，我们将字符串视为元素为字符的向量。

This algorithm takes as input a string $S$$S$SS of $N$$N$NN characters $S[0],\dots ,S[N-1]$$S[0],\dots ,S[N-1]$S[0],dots,S[N-1]S[0], \ldots, S[N-1] selected from an ordered alphabet $X$$X$XX of characters. To illustrate the technique, we also give a running example, using the string $S=$$S=$S=S= ‘abraca’, $N=6$$N=6$N=6N=6, and the alphabet $X=\{{}^{\prime }{a}^{\prime },b^{\prime },{}^{\prime }{c}^{\prime },r^{\prime }\}$$X=\left\{{}^{\prime }{a}^{\prime },b^{\prime },{}^{\prime }{c}^{\prime },r^{\prime }\right\}$X={^(')a^('),b^('),^(')c^('),r^(')}X=\left\{{ }^{\prime} a^{\prime}, b^{\prime},{ }^{\prime} c^{\prime}, r^{\prime}\right\}.
此算法以一个字符串 $S$$S$SS 作为输入，该字符串由 $N$$N$NN 个字符 $S[0],\dots ,S[N-1]$$S[0],\dots ,S[N-1]$S[0],dots,S[N-1]S[0], \ldots, S[N-1] 组成，这些字符选自一个有序字符集 $X$$X$XX 。为了说明技术，我们还提供了一个运行示例，使用字符串 $S=$$S=$S=S= ‘abraca’， $N=6$$N=6$N=6N=6 ，以及字符集 $X=\{{}^{\prime }{a}^{\prime },b^{\prime },{}^{\prime }{c}^{\prime },r^{\prime }\}$$X=\left\{{}^{\prime }{a}^{\prime },b^{\prime },{}^{\prime }{c}^{\prime },r^{\prime }\right\}$X={^(')a^('),b^('),^(')c^('),r^(')}X=\left\{{ }^{\prime} a^{\prime}, b^{\prime},{ }^{\prime} c^{\prime}, r^{\prime}\right\} 。

Form a conceptual $N\times N$$N\times N$N xx NN \times N matrix $M$$M$MM whose elements are characters, and whose rows are the rotations (cyclic shifts) of $S$$S$SS, sorted in lexicographical order. At least one of the rows of $M$$M$MM contains the original string $S$$S$SS. Let $I$$I$II be the index of the first such row, numbering from zero.
构建一个概念矩阵，其元素为字符，行是 $S$$S$SS 的旋转（循环移位），按字典顺序排序。至少 $M$$M$MM 的一行包含原始字符串 $S$$S$SS 。令 $I$$I$II 为这样的第一行的索引，从零开始编号。
In our example, the index $I=1$$I=1$I=1I=1 and the matrix $M$$M$MM is
在我们的例子中，索引 $I=1$$I=1$I=1I=1 和矩阵 $M$$M$MM

C2. [find last characters of rotations]
C2. [找到旋转的最后几个字符]
Let the string $L$$L$LL be the last column of $M$$M$MM, with characters $L[0],\dots ,L[N-1]$$L[0],\dots ,L[N-1]$L[0],dots,L[N-1]L[0], \ldots, L[N-1] (equal to $M[0,N-1],\dots ,\mathrm{M}[N-1,N-1]$$M[0,N-1],\dots ,\mathrm{M}[N-1,N-1]$M[0,N-1],dots,M[N-1,N-1]M[0, N-1], \ldots, \mathrm{M}[N-1, N-1] ). The output of the transformation is the pair $(L,I)$$(L,I)$(L,I)(L, I).
让字符串 $L$$L$LL 成为 $M$$M$MM 的最后一列，字符 $L[0],\dots ,L[N-1]$$L[0],\dots ,L[N-1]$L[0],dots,L[N-1]L[0], \ldots, L[N-1] （等于 $M[0,N-1],\dots ,\mathrm{M}[N-1,N-1]$$M[0,N-1],\dots ,\mathrm{M}[N-1,N-1]$M[0,N-1],dots,M[N-1,N-1]M[0, N-1], \ldots, \mathrm{M}[N-1, N-1] ）。变换的输出是成对出现的 $(L,I)$$(L,I)$(L,I)(L, I) 。

In our example, $L=$$L=$L=L= ‘caraab’ and $I=1$$I=1$I=1I=1 (from step C1).
在我们的例子中， $L=$$L=$L=L= “caraab” 和 $I=1$$I=1$I=1I=1 （来自步骤 C1）。

We use the example and notation introduced in Algorithm C. Algorithm D uses the output ( $L,I$$L,I$L,IL, I ) of Algorithm C to reconstruct its input, the string $S$$S$SS of length $N$$N$NN.
我们使用在算法 C 中引入的示例和符号。算法 D 使用算法 C 的输出（ $L,I$$L,I$L,IL, I ）来重建其输入，长度为 $N$$N$NN 的字符串 $S$$S$SS 。

D1. [find first characters of rotations]
D1. [找到旋转的第一个字符]
This step calculates the first column $F$$F$FF of the matrix $M$$M$MM of Algorithm C. This is done by sorting the characters of $L$$L$LL to form $F$$F$FF. We observe that any column of the matrix $M$$M$MM is a permutation of the original string $S$$S$SS. Thus, $L$$L$LL and $F$$F$FF are both permutations of $S$$S$SS, and therefore of one another. Furthermore, because the rows of $M$$M$MM are sorted, and $F$$F$FF is the first column of $M$$M$MM, the characters in $F$$F$FF are also sorted.
这一步计算算法 C 的矩阵 $M$$M$MM 的第一列 $F$$F$FF 。这是通过排序 $L$$L$LL 中的字符来形成 $F$$F$FF 。我们观察到矩阵 $M$$M$MM 的任何一列都是原始字符串 $S$$S$SS 的排列。因此， $L$$L$LL 和 $F$$F$FF 都是 $S$$S$SS 的排列，因此也是彼此的排列。此外，因为 $M$$M$MM 的行已排序，且 $F$$F$FF 是 $M$$M$MM 的第一列，所以 $F$$F$FF 中的字符也是排序的。
In our example, $F=$$F=$F=F= ‘aaabcr’.
在我们的例子中， $F=$$F=$F=F= ‘aaabcr’。
D2. [build list of predecessor characters]
D2. [构建前驱字符列表]
To assist our explanation, we describe this step in terms of the contents of the matrix $M$$M$MM. The reader should remember that the complete matrix is not available to the decompressor; only the strings $F,L$$F,L$F,LF, L, and the index $I$$I$II (from the input) are needed by this step.
为了帮助我们的解释，我们用矩阵 $M$$M$MM 的内容来描述这一步。读者应记住，完整的矩阵对解压器不可用；这一步只需要字符串 $F,L$$F,L$F,LF, L 和索引 $I$$I$II （来自输入）。
Consider the rows of the matrix $M$$M$MM that start with some given character ch . Algorithm C ensured that the rows of matrix $M$$M$MM are sorted lexicographically, so the rows that start with $ch$$ch$chc h are ordered lexicographically.
考虑以某个给定字符 ch 开头的矩阵 $M$$M$MM 的行。算法 C 确保矩阵 $M$$M$MM 的行按字典顺序排序，因此以 $ch$$ch$chc h 开头的行按字典顺序排列。
We define the matrix $M^{\prime }$$M^{\prime }$M^(')M^{\prime} formed by rotating each row of $M$$M$MM one character to the right, so for each $i=0,\dots ,N-1$$i=0,\dots ,N-1$i=0,dots,N-1i=0, \ldots, N-1, and each $j=0,\dots ,N-1$$j=0,\dots ,N-1$j=0,dots,N-1j=0, \ldots, N-1,
我们定义由将 $M$$M$MM 的每一行向右旋转一个字符形成的矩阵 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} ，因此对于每个 $i=0,\dots ,N-1$$i=0,\dots ,N-1$i=0,dots,N-1i=0, \ldots, N-1 ，以及每个 $j=0,\dots ,N-1$$j=0,\dots ,N-1$j=0,dots,N-1j=0, \ldots, N-1 ，

In our example, $M$$M$MM and $M^{\prime }$$M^{\prime }$M^(')M^{\prime} are:
在我们的例子中， $M$$M$MM 和 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 是：

Like $M$$M$MM, each row of $M^{\prime }$$M^{\prime }$M^(')M^{\prime} is a rotation of $S$$S$SS, and for each row of $M$$M$MM there is a corresponding row in $M^{\prime }$$M^{\prime }$M^(')M^{\prime}. We constructed $M^{\prime }$$M^{\prime }$M^(')M^{\prime} from $M$$M$MM so that the rows
类似于 $M$$M$MM ， $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 的每一行都是 $S$$S$SS 的旋转，并且对于 $M$$M$MM 的每一行，在 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 中都有对应的行。我们从 $M$$M$MM 构建了 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} ，以便行
of $M^{\prime }$$M^{\prime }$M^(')M^{\prime} are sorted lexicographically starting with their second character. So, if we consider only those rows in $M^{\prime }$$M^{\prime }$M^(')M^{\prime} that start with a character $ch$$ch$chc h, they must appear in lexicographical order relative to one another; they have been sorted lexicographically starting with their second characters, and their first characters are all the same and so do not affect the sort order. Therefore, for any given character $ch$$ch$chc h, the rows in $M$$M$MM that begin with $ch$$ch$chc h appear in the same order as the rows in $M^{\prime }$$M^{\prime }$M^(')M^{\prime} that begin with $ch$$ch$chc h.
$M^{\prime }$$M^{\prime }$M^(')M^{\prime} 中的元素按字典顺序排序，从第二个字符开始。因此，如果我们只考虑 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 中以字符 $ch$$ch$chc h 开头的行，它们必须按字典顺序相互排列；它们已经按第二个字符的字典顺序排序，并且第一个字符都相同，因此不影响排序顺序。因此，对于任何给定的字符 $ch$$ch$chc h ， $M$$M$MM 中以 $ch$$ch$chc h 开头的行与 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 中以 $ch$$ch$chc h 开头的行以相同的顺序出现。

In our example, this is demonstrated by the rows that begin with ’ $a$$a$aa '. The rows ‘aabrac’, ‘abraca’, and ‘acaabr’ are rows $0,1,2$$0,1,2$0,1,20,1,2 in $M$$M$MM and correspond to rows $1,3,4$$1,3,4$1,3,41,3,4 in $M^{\prime }$$M^{\prime }$M^(')M^{\prime}.
在我们的例子中，这通过以’ $a$$a$aa ‘开头的行来展示。行‘aabrac’、‘abraca’和‘acaabr’是 $M$$M$MM 中的 $0,1,2$$0,1,2$0,1,20,1,2 行，对应于 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 中的 $1,3,4$$1,3,4$1,3,41,3,4 行。

Using $F$$F$FF and $L$$L$LL, the first columns of $M$$M$MM and $M^{\prime }$$M^{\prime }$M^(')M^{\prime} respectively, we calculate a vector $T$$T$TT that indicates the correspondence between the rows of the two matrices, in the sense that for each $j=0,\dots ,N-1$$j=0,\dots ,N-1$j=0,dots,N-1j=0, \ldots, N-1, row $j$$j$jj of $M^{\prime }$$M^{\prime }$M^(')M^{\prime} corresponds to row $T[j]$$T[j]$T[j]T[j] of $M$$M$MM.
使用 $F$$F$FF 和 $L$$L$LL ，分别计算 $M$$M$MM 和 $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 的第一列，得到一个向量 $T$$T$TT ，该向量指示两个矩阵行之间的对应关系，即对于每个 $j=0,\dots ,N-1$$j=0,\dots ,N-1$j=0,dots,N-1j=0, \ldots, N-1 ， $M^{\prime }$$M^{\prime }$M^(')M^{\prime} 的第 $j$$j$jj 行对应于 $M$$M$MM 的第 $T[j]$$T[j]$T[j]T[j] 行。
If $L[j]$$L[j]$L[j]L[j] is the $k$$k$kk th instance of $ch$$ch$chc h in $L$$L$LL, then $T[j]=i$$T[j]=i$T[j]=iT[j]=i where $F[i]$$F[i]$F[i]F[i] is the $k$$k$kk th instance of $ch$$ch$chc h in $F$$F$FF. Note that $T$$T$TT represents a one-to-one correspondence between elements of $F$$F$FF and elements of $L$$L$LL, and $F[T[j]]=L[j]$$F[T[j]]=L[j]$F[T[j]]=L[j]F[T[j]]=L[j].
如果 $L[j]$$L[j]$L[j]L[j] 是 $L$$L$LL 中 $ch$$ch$chc h 的第 $k$$k$kk 个实例，那么 $T[j]=i$$T[j]=i$T[j]=iT[j]=i ，其中 $F[i]$$F[i]$F[i]F[i] 是 $F$$F$FF 中 $ch$$ch$chc h 的第 $k$$k$kk 个实例。注意， $T$$T$TT 代表 $F$$F$FF 的元素与 $L$$L$LL 和 $F[T[j]]=L[j]$$F[T[j]]=L[j]$F[T[j]]=L[j]F[T[j]]=L[j] 的元素之间的一对一对应。

In our example, $T$$T$TT is: $\left(\begin{array}{llllll}4& 0& 5& 1& 2& 3\end{array}\right)$$\left(\begin{array}{llllll}4& 0& 5& 1& 2& 3\end{array}\right)$quad([4,0,5,1,2,3])\quad\left(\begin{array}{llllll}4 & 0 & 5 & 1 & 2 & 3\end{array}\right).
在我们的例子中， $T$$T$TT 是： $\left(\begin{array}{cccccc}4& 0& 5& 1& 2& 3\end{array}\right)$$\left(\begin{array}{cccccc}4& 0& 5& 1& 2& 3\end{array}\right)$quad([4,0,5,1,2,3])\quad\left(\begin{array}{llllll}4 & 0 & 5 & 1 & 2 & 3\end{array}\right) 。
D3. [form output $S$$S$SS ]
D3. [表输出 $S$$S$SS ]
Now, for each $i=0,\dots ,N-1$$i=0,\dots ,N-1$i=0,dots,N-1i=0, \ldots, N-1, the characters $L[i]$$L[i]$L[i]L[i] and $F[i]$$F[i]$F[i]F[i] are the last and first characters of the row $i$$i$ii of $M$$M$MM. Since each row is a rotation of $S$$S$SS, the character $L[i]$$L[i]$L[i]L[i] cyclicly precedes the character $F[i]$$F[i]$F[i]F[i] in $S$$S$SS. From the construction of $T$$T$TT, we have $F[T[j]]=L[j]$$F[T[j]]=L[j]$F[T[j]]=L[j]F[T[j]]=L[j]. Substituting $i=T[j]$$i=T[j]$i=T[j]i=T[j], we have $L[T[j]]$$L[T[j]]$L[T[j]]L[T[j]] cyclicly precedes $L[j]$$L[j]$L[j]L[j] in $S$$S$SS.
现在，对于每个 $i=0,\dots ,N-1$$i=0,\dots ,N-1$i=0,dots,N-1i=0, \ldots, N-1 ，字符 $L[i]$$L[i]$L[i]L[i] 和 $F[i]$$F[i]$F[i]F[i] 分别是 $i$$i$ii 行中 $M$$M$MM 的最后一和第一个字符。由于每一行都是 $S$$S$SS 的旋转，字符 $L[i]$$L[i]$L[i]L[i] 在 $S$$S$SS 中循环先于字符 $F[i]$$F[i]$F[i]F[i] 。从 $T$$T$TT 的构造中，我们有 $F[T[j]]=L[j]$$F[T[j]]=L[j]$F[T[j]]=L[j]F[T[j]]=L[j] 。代入 $i=T[j]$$i=T[j]$i=T[j]i=T[j] ，我们得到 $L[T[j]]$$L[T[j]]$L[T[j]]L[T[j]] 在 $S$$S$SS 中循环先于