Summary form only given. The Burrows Wheeler transform is a relatively new approach to text compression and has already proven to produce excellent results. However, there has been much research directed towards improving the efficiency of the move to front algorithm with varying degrees of complexity. A relatively simple technique was examined using a dual modeling system and achieves very promising results. Information loss during the Burrows Wheeler transform is also examined using deterministic information theory measuring techniques. By utilizing the information measurement tools developed by Titchener a clearer understanding of informational changes over BWT has been established. Most importantly, MTF loses information making it amenable for compression, however it also contains little contextual structure and closely resembles the data stream after applying the BWT algorithm.

Summary form only given. Titchener (see Proc. DCC00, IEEE Society Press, p.353-62, 2000, and IEEE-ISIT, , MIT, Boston, August 1998) defined a computable grammar-based entropy measure (T-entropy) for finite strings, Ebeling, Steuer and Titchener (see Stochastics and Dynamics, vol.1, no.1, 2000) and Titchener and Ebeling (see Proc. DCC01, IEEE Society Press, p.520, 2001) demonstrated against the known results for the logistic map, to be a practical way to compute the Shannon information content for data files. A range of binary encodings of the logistic map dynamics have been prepared from a generating bi-partition and with selected normalised entropies, 0.1-1.0 bits/symbol, in steps of 0.1. This corpus of ten test files has been used to evaluate the 'absolute' performance of a series of popular compressors.

Modern information theory is founded on the ideas of Hartley and Shannon, amongst others. From a practitioners standpoint. Shannon's probabilistic framework carries certain impediments for the practical measurement of information, such as requiring a priori knowledge of a source's characteristics. Moreover, such a statistical formulation of entropy is an asymptotic limit, meaningful only within the context of an ensemble of messages. It thus fails to address the notion of an individual string having information content in of itself. However Cherry (1953) demonstrated that Shannon's entropy could be viewed equivalently as a measure of the average number of selections required to identify each message symbol from the alphabet. Here the terminology contrasts with Shannon's probabilistic formulation. With the process of counting selection steps appearing to be meaningful for individual, isolated, finite strings. We explore this alternative approach in the context of a recursive hierarchical pattern copying (RHPC) algorithm. We use the measure of the complexity of finite strings, in terms of the number of steps required to recursively construct the string from its alphabet. From this we compute an effective rate of steps-per-symbol required for linearly constructing the string. By Cherry's interpretation of Shannon's entropy we infer this as giving asymptotic equivalence between the two approaches, but perhaps the real significance of this new way to measure information, is its applicability and usefulness in respect of evaluating individual finite strings.

Summary form only given. A mini-corpus of twelve 'calibrated' binary-data files have been produced for systematic evaluation of compression algorithms. These are generated within the framework of a deterministic theory of string complexity. Here the T-complexity of a string x (measured in taugs) is defined as C/sub T/(x/sub i/)=/spl Sigma//sub i/log/sub 2/(k/sub i/+1), where the positive integers k/sub i/ are the T-expansion parameters for the corresponding string production process. C/sub T/(x) is observed to be the logarithmic integral of the total information content I/sub x/ of x (measured in nats), i.e., C/sub T/(x)=li(I/sub x/). The average entropy is H~/sub x/=I/sub x//|x|, i.e., the total information content divided by the length of x. Thus C/sub T/(x)=li(H~/sub x//spl times/|x|). Alternatively, the information rate along a string may be described by an entropy function H/sub x/(n),0/spl les/n/spl les/|x| for the string. Assuming that H/sub x/(n) is continuously integrable along the length of the x, then I/sub x/=/spl int//sub 0//sup |/x|H/sub x/(n)/spl delta/n. Thus C/sub T/(x)=li(/spl int//sub 0//sup |/x|H/sub x/(n)/spl delta/n). Solving for H/sub x/(n): that is differentiating both sides and rearranging, we get: H/sub x/(n)=(/spl delta/C/sub T/(x|n)//spl delta/n)/spl times/log/sub e/(li/sup -1/(C/sub T/(x|/sub n/))). With x being in fact discrete, and the T-complexity function being computed in terms of the discrete T-augmentation steps, we may accordingly re-express the equation in terms of the T-prefix increments: /spl delta/n/spl ap//spl Delta//sub i/|x|=k/sub i/|p/sub i/|; and from the definition of C/sub T/(x): /spl delta/C/sub T/(x) is replaced by /spl Delta//sub i/C/sub T/(x)=log/sub 2/(k/sub i/+1). The average slope over the i-th T-prefix p/sub i/ increment is then simply (/spl Delta//sub i/C/sub T/(x))/(/spl Delta//sub i/|x|)=(log/sub 2/(k/sub i/+1))/(k/sub i/|p/sub i/|). The entropy function is now replaced by a discrete approximation.

Many variable-length codes exhibit a tendency for resynchronization to occur automatically following any error. However, attempts to identify an underlying synchronization mechanism, and to accurately predict the expected synchronization delay, for even quite specific variable-length codes, appear to have been largely unsuccessful. The present paper explores a novel method for estimating the synchronization performance for a wide variety of variable-length codes, based on the T-Codes. T-Codes are a class of self-synchronizing codes, which typically synchronize within 2-3 codewords by a mechanism that derives from a recursive T-augmentation construction. It is observed that the T-Code mechanism for synchronization is followed, more or less, by other variable-length codes wherever substantial numbers of codewords are shared with a T-Code set. T-augmentation itself provides a means for assessing the contribution individual codewords make to the overall synchronization process for a T-Code set. Thus codeword differences between sets may be specifically evaluated to estimate the synchronization performance of a variable-length code set from a closely related T-Code set.