Improvements to Burrows–Wheeler compression algorithm

In 1994 Burrows and Wheeler presented a new algorithm for lossless data compression. The compression ratio that can be achieved using their algorithm is comparable with the best known other algorithms, whilst its complexity is relatively small. In this paper we explain the internals of this algorithm and discuss its various modifications that have been presented so far. Then we propose new improvements for its effectiveness. They allow us to obtain a compression ratio equal to 2.271 bpc for the Calgary Corpus files, which is the best result in the class of Burrows–Wheeler transform based algorithms. Copyright © 2000 John Wiley & Sons, Ltd.     

Second step algorithms in the Burrows–Wheeler compression algorithm

In this paper we focus our attention on the second step algorithms of the Burrows–Wheeler compression algorithm, which in the original version is the Move To Front transform. We discuss many of its replacements presented so far, and compare compression results obtained using these replacements. Then we propose a new algorithm that yields a better compression ratio than the previous algorithms. Copyright © 2001 John Wiley & Sons, Ltd.     

Incremental frequency count—a post BWT‐stage for the Burrows–Wheeler compression algorithm

The stage after the Burrows–Wheeler transform (BWT) has a key function inside the Burrows–Wheeler compression algorithm as it transforms the BWT output from a local context into a global context. This paper presents the Incremental Frequency Count stage, a post‐BWT stage. The new stage is paired with a run length encoding stage between the BWT and the entropy coding stage of the algorithm. It offers high throughput similar to a Move To Front stage, and at the same time good compression rates like the strong but slow Weighted Frequency Count stage. The properties of the Incremental Frequency Count stage are compared to the Move To Front and Weighted Frequency Count stages by their compression rates and speeds on the Calgary and large Canterbury corpora. Copyright © 2006 John Wiley & Sons, Ltd.     

Burrows–Wheeler compression with variable length integer codes

The final coder in Burrows–Wheeler compression is usually either an adaptive Huffman coder (for speed) or a complex of arithmetic coders for better compression. This article describes the use of conventional pre‐defined variable length codes or universal codes and shows that they too can give excellent compression. The paper also describes a ‘sticky Move‐to‐Front’ modification which gives a useful improvement in compression for most files. Copyright © 2002 John Wiley & Sons, Ltd.     

Revisiting bounded context block‐sorting transformations

The Burrows–Wheeler Transform (BWT ) produces a permutation of a string X, denoted X^?, by sorting the n cyclic rotations of X into full lexicographical order and taking the last column of the resulting n×n matrix to be X^?. The transformation is reversible in time. In this paper, we consider an alteration to the process, called k‐BWT , where rotations are only sorted to a depth k. We propose new approaches to the forward and reverse transform, and show that the methods are efficient in practice. More than a decade ago, two algorithms were independently discovered for reversing k‐BWT , both of which run in time. Two recent algorithms have lowered the bounds for the reverse transformation to and, respectively. We examine the practical performance for these reversal algorithms. We find that the original approach is most efficient in practice, and investigates new approaches, aimed at further speeding reversal, which store precomputed context boundaries in the compressed file. By explicitly encoding the context boundaries, we present an reversal technique that is both efficient and effective. Finally, our study elucidates an inherently cache‐friendly – and hitherto unobserved – behavior in the reverse k‐BWT , which could lead to new applications of the k‐BWT transform. In contrast to previous empirical studies, we show that the partial transform can be reversed significantly faster than the full transform, without significantly affecting compression effectiveness. Copyright © 2011 John Wiley & Sons, Ltd.     

A simpler analysis of Burrows–Wheeler-based compression

In this paper, we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows–Wheeler Transform. We mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D.J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain the Burrows–Wheeler Transform of the text, (2) Convert the transform into a sequence of integers using the move-to-front algorithm, (3) Encode the integers using Arithmetic code or any order-0 encoding (possibly with run-length encoding).     

Symbol ranking text compressors: review and implementation

Methods used by Shannon in 1951 when investigating the information content of English text are shown to lead to a class of ‘symbol ranking’ text compressors. Included in this class are some recent compressors which combine high performance with completely novel techniques. These are described under the aegis of the symbol ranking classification. Some new compressors, deliberately designed as symbol ranking, are then described. One of these has operated at over 1 Mbyte per second in software, and should be suitable for hardware implementation at tens of megabytes per second, or higher. © 1998 John Wiley & Sons, Ltd.     

基于BWT改进的LZW算法在传感器网络中的应用

传感器网络能量有限,网内数据不易直接传输,需要进行压缩。针对有损数据压缩的局限性,基于数据分块和BWT变换思想,提出了一种改进的无损数据压缩算法-B-LZW,保证了数据的完整性。通过信息熵理论分析及实验仿真,比较了B-LZW算法与传统的LZW算法的性能。结果表明,在对实时性要求不高的传感器网络应用中,该算法能更有效地减轻网络节点存储负担,降低数据丢包率,提高压缩率2.75%～3%,节约网络能量,进一步延长网络寿命。     

Simple fast and adaptive lossless image compression algorithm

In this paper we present a new lossless image compression algorithm. To achieve the high compression speed we use a linear prediction, modified Golomb–Rice code family, and a very fast prediction error modeling method. We compare the algorithm experimentally with others for medical and natural continuous tone grayscale images of depths of up to 16 bits. Its results are especially good for large images, for natural images of high bit depths, and for noisy images. The average compression speed on Intel Xeon 3.06 GHz CPU is 47 MB/s. For large images the speed is over 60 MB/s, i.e. the algorithm needs less than 50 CPU cycles per byte of image. Copyright © 2006 John Wiley & Sons, Ltd.     

Thermodynamic assessments of the Ni–Pt and Al–Ni–Pt systems

The Ni–Pt system is assessed using the CALPHAD method. The four fcc-based phases, i.e. disordered solid solution phase, Ni₃Pt–L1₂, NiPt–L1₀ and NiPt₃–L1₂, are described by a four-sublattice model. The calculated thermodynamic properties and order/disorder phase transformations are in good agreement with the experimental data. In order to facilitate the assessment, first-principles pseudopotential calculations are also performed to calculate the enthalpy of formation at 0 K, and comparison with the assessed values is discussed. By combining the assessments of Al–Ni and Al–Pt, the Al–Ni–Pt ternary system is assessed within a narrow temperature range, focusing on the fcc-based phases and their phase equilibria with B2 phase.     

A thermodynamic description of the Al–Ca–Zn ternary system

A comprehensive thermodynamic database of the Al–Ca–Zn ternary system is presented for the first time. Critical assessment of the experimental data and re-optimization of the binary Al–Zn and Al–Ca systems have been performed. The optimized model parameters of the third binary system, Ca–Zn, are taken from the previous assessment of the Mg–Ca–Zn system by the same authors. All available as well as reliable experimental data both for the thermodynamic properties and phase boundaries are reproduced within experimental error limits. In the present assessment, the modified quasichemical model in the pair approximation is used for the liquid phase and Al_FCC phase of the Al–Zn system to account for the presence of the short-range ordering properly. Two ternary compounds reported by most of the research works are considered in the present calculation. The liquidus projections and vertical sections of the ternary systems are also calculated, and the invariant reaction points are predicted using the constructed database.     

Thermodynamic modeling of the C–Pu–U system

The ternary C–Pu–U system is thermodynamically assessed to pursue the development of a thermodynamic database for future nuclear fuels. The substitution model was used for the liquid phase, and a two-sublattice model for the PuC–UC monocarbide, PuC₂–UC₂ dicarbide and Pu₂C₃–U₂C₃ sesquicarbide phases. Ternary interaction parameters were adjusted on the experimental information for the phase relationships. Isoplethal and isothermal ternary sections, as well as some liquidus temperatures are calculated and compared with the experimental data. The overall agreement is discussed, and shows that experimental uncertainties still remain.     

关于空间数据系统无损压缩算法的零值块研究

通过对CCSDS(国际空间数据系统咨询委员会)建议的无损数据压缩标准的研究,以及对目前常用压缩算法的调查,它阐述了一种具有延迟小速度快抗差错能力强等特点的无损数据压缩算法,即Rice压缩算法,压缩率超过50%以上,而且对多种类型的数据都会达到满意的效果.它对算法中的零值块部分作了较为详细地阐述,因为经过预处理过的数据通常都很小,对于图像来说有相当多的零值.因此,对零值较多的情况下采取零值块压缩处理,效果很好,经过软件测试,结果符合CCSDS的要求标准.     

On a computationally simple form of the generalized Campbell–Baker–Hausdorff–Dynkin formula

In this paper a computationally simple form of the generalized Campbell–Baker–Hausdorff–Dynkin formula (GCBHD) is given. Simplifications arise from both combinatorial (explicit) as well as algorithmic (implicit) arguments. On generating the Ph. Hall basis in a special form, and introducing a specific structure representation of the vector field, vector fields appearing in GCBHD are automatically transformed into the reduced Ph. Hall basis. The formula can be exploited in nonholonomic motion planning what is illustrated with examples.     

Thermodynamic modeling of the Mg–Ge–Pb system

All available thermodynamic and phase diagram data of the Mg–Ge and Mg–Pb binary systems, and the Mg–Ge–Pb ternary system have been critically evaluated and all reliable data have been simultaneously optimized to obtain one set of model parameters for the Gibbs energies of the liquid and all solid phases as functions of composition and temperature. The liquid phase was modeled using the Modified Quasichemical Model in order to describe the strong ordering in Mg–Ge and Mg–Pb liquid. Mg₂Ge–Mg₂Pb solid solution phase was modeled with consideration of a solid miscibility gap. All calculations were performed using the FactSage thermochemical software.     

Pre-control form of the generalized Campbell–Baker–Hausdorff–Dynkin formula for affine nonholonomic systems

In this paper a pre-control form of the generalized Campbell–Baker–Hausdorff–Dynkin (gCBHD) formula is presented. This form is dedicated to nonholonomic (affine) systems often encountered in robotics. The simplest possible expression for the pre-control gCBHD is obtained as control-dependent functions pre-multiply elements of the Ph. Hall basis. Algorithmic aspects of deriving the formula are highlighted. An application of the pre-control form of the gCBHD formula in motion planning of nonholonomic systems is also reported.     

抖动半调图像跳黑块无损压缩算法

提出了一种有序抖动半调图像跳黑块无损压缩方法。通过分析抖动半调图像特性,对半调图进行分块及块间异或预处理,使其转变为较大面积黑色区域中夹杂着零星白点的二值图像,接着运用跳黑块编码法对其无损压缩。在跳黑块编码中,对只有一个白像素的非黑块采用特定的短码字编码;对其余类型的非黑块采用直接编码。实验结果表明,改进的跳黑块编码能在一定程度上对非黑块进行有效压缩,且新算法不但具有较高的压缩效率,时间、空间复杂度也较低。