SUMMARY A significant cost in PPM data compression (and often the major cost) is the provision and efficient coding of escapes while building contexts. This paper presents some recent, preliminary, work on a new technique for eliminating escapes in PPM compression, using bit‐wise compression with binary contexts. It shows that PPM without escapes can achieve averages of 2.5 bits per character on the Calgary Corpus and 2.2 bpc on the Canterbury Corpus, both values comparing well with accepted good compressors. Copyright © 2011 John Wiley & Sons, Ltd.

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.

Abstract 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.

This article introduces a new family of variable-length codes for the integers, initially based on the Goldbach conjecture that every even integer is the sum of two primes. For an even integer we decompose the value into its two constituent primes and encode the ordinal numbers of those primes with an Elias (1975) /spl gamma/ code. The method is then elaborated to handle odd integers. The article then develops a more general method of encoding any integer as the sum of two integers and developing suitable basis sets of integers. Although the codes which are generated by these methods are characterized by widely varying and unpredictable lengths, they are over some ranges shorter than most other variable-length codes.

Abstract We present a string matching or pattern matching method which is especially useful when a single block of text must be searched repeatedly for different patterns. The method combines linking the text according to digrams, searching on the least‐frequent digram, and probing selected characters as a preliminary filter before full pattern comparison. Tests on real alphabetic data show that the number of character comparisons may be decreased by two orders of magnitude compared with Knuth–Morris–Pratt and similar searching, but with an initialization overhead comparable to five to ten conventional searches. Copyright © 2001 John Wiley & Sons, Ltd.

Abstract Recent experience with string searching or pattern matching algorithms revealed wide discrepancies between predicted and observed performance. Further observations on a variety of computers revealed even greater variations between those algorithms on different computers. These observations are collected here as an example of problems in real‐world comparison of algorithms. Copyright © 2001 John Wiley & Sons, Ltd.

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.

Summary form only given. The increasing importance of unicode for text files, for example with Java and in some modern operating systems, implies a possible increase of data storage space and data transmission time, with a corresponding need for data compression. However data compressors designed for traditional 8-bit byte data are not necessarily well matched to the peculiarities of unicode data. Different "standard" text compression methods behave in different ways, as compared with the performance already known from ASCII or other 8-bit data. A small corpus of unicode files has been compressed on several widely-available text compressors of the various types, confirming that unicode files have different compression characteristics from those known for 8-bit data. Tests with a simple LZ-77 compressor designed to operate in both 8-bit and 16-bit modes indicate that it may be useful to design compressors specifically for unicode data.

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.

A recent development in text compression is a ‘block sorting’ algorithm which permutes the input text according to a special sort procedure and then processes the permuted text with Move-To-Front (MTF) and a final statistical compressor. The technique combines good speed with excellent compression performance. This paper investigates the fundamental operation of the algorithm and presents some improvements based on that analysis. Although block sorting is clearly related to previous compression techniques, it appears that it is best described by techniques derived from work by Shannon on the prediction and entropy of English text. A simple model is developed which relates the compression to the proportion of zeros after the MTF stage.

A recent paper presented a new efficient data structure, the ‘binary endexed tree’, for maintaining the cumulative frequencies for arithmetic data compression. Although algorithms were presented for all of the necessary operations, significant problems remained with the method for determining the symbol corresponging to a known frequemcy. This communication corrects that deficiency.

The efficiency of noiseless coding may be improved by coding extensions of the source; for large extensions the efficiency is arbitrarily close to unity. The paper shows that the efficiency is not always improved just by coding the next extension. In some cases the code of a larger extension is markedly less efficient than its predecessor, although always within the theoretical limits of efficiency. The author shows how the phenomenon arises from changes to the Huffman coding tree as the source probabilities change and investigates it for binary and ternary codes.>

Abstract A new method (the ‘binary indexed tree’) is presented for maintaining the cumulative frequencies which are needed to support dynamic arithmetic data compression. It is based on a decomposition of the cumulative frequencies into portions which parallel the binary representation of the index of the table element (or symbol). The operations to traverse the data structure are based on the binary coding of the index. In comparison with previous methods, the binary indexed tree is faster, using more compact data and simpler code. The access time for all operations is either constant or proportional to the logarithm of the table size. In conjunction with the compact data structure, this makes the new method particularly suitable for large symbol alphabets.

LZ77 and more recently LZSS text compression use one-bit flags to identify a following pointer or literal. This paper investigates the use of multi-bit flags to allow a greater variety of entities in the compressed data stream. Two approaches are described. The first uses flags of 2 or 3 bits with operands constrained to be 1, 2 or 3 bytes long. The other codes entirely in units of 2 or 3 bits (instead of the more usual single bits). Both methods are shown to yield compressors of good performance.>

A composite Ethernet has been constructed by linking two conventional Ethernets via a 39 km optical link. This paper presents the results of some performance measurements on this combined network. It is found that the performance is dominated by the computers themselves and aspects of the associated network software. The effect of the 39 km optical link and associated Long-Range Bridge is relatively small. Extrapolating the results shows that reasonable performance may be obtained from linked Ethernets over distances of several hundred kilometres. A simple model has been developed for the prediction of data transfer rates and shows an accuracy in accord with the observations.

A parallel adder due to Kilburn uses a carry path with cascaded switches instead of more conventional logic gates. It is shown that a similar adder using CMOS transmission gates in the carry path combines high performance with a simple and economical design which should be suitable for integration.

In a computer system with a cache memory, the cache is effectively empty following a job switch, leading to a low hit rate and consequently lowered performance until the cache becomes reasonably full. The analysis shows that a job must run for several milliseconds before the average performance approaches that expected from a steady-state analysis. Care may therefore be needed in designing memory systems which have very high page-fault rates from main memory, or which include many levels in the memory hierarchy.

With a suitable adder organization it is possible to overlap the adder operation during a binary multiplication and significantly decrease the overall multiplication time. The method is explained and a prototype multiplier described. The new technique provides a very economical method of obtaining a reasonably fast multiplier.