A crucial task in the design of an efficient ANS encoder consists in choosing a favourable symbol distribution. This task seems to be hard, due to its combinatorial nature, in particular for the tANS variant of ANS, which is the focus of this work. We present a fast technique that builds almost optimal symbol distributions for the stream variant of tANS.

Asymmetric Numeral Systems (ANS) are a family of entropy coders for information sources with a finite alphabet, and usually require approximating the source distribution to rational numbers to associate the source symbols with the internal states of ANS. In the range variant of ANS, each source symbol corresponds to a continuous interval of the state set. ANS assigns shorter codewords to states with smaller numbers and longer codewords to states with larger numbers. Therefore, it is not fair or valid to make the lengths of state intervals proportional to symbol probabilities. To overcome this problem, this paper proposes a new source approximation formula, and shows that it leads to an improvement of compression efficiency of ANS.

This paper proposes an approximation to the stationary distribution of the states in Duda's ABS entropy coder. While arithmetic coders represent a codeword by an interval of numbers, the ABS encoder represents its inner state by a single number. This paper proves that the proposed approximation to the state distribution converges to the true stationary distribution in the limit of a parameter of ABS. This leads to a rigorous proof of the fact that the rate of ABS asymptotically attains the source entropy.

A new lossless data compression technique called compression by substring enumeration (CSE) has recently been introduced. Two conjectures have been stated in the original paper and they have not been proved there nor in subsequent papers on CSE. The first conjecture says that CSE is universal for Markovian sources, provided an appropriate predictor is devised. The second one says that CSE has a linear complexity both in time and in space. In this paper, we present an appropriate predictor and demonstrate that CSE indeed becomes universal for any order-k Markovian source. Finally, we prove that the compacted substring tree on which CSE's linear complexity depends effectively has linear size.

This paper proposes an ideal compression method and embeds additional data by simply appending them at the end of the compressed data.

Mobile terminals such as cell phones are much more restricted in terms of input/output functionality and, therefore, some special techniques must be incorporated to enable them to be easily used for Web searching. Further, searching for a location name is related to a dazzling variety of topics. We relate these two factors to each other to yield a new search system for map and text information. Presenting search results as clusters is helpful for users, especially in a mobile environment. The system makes mobile web searching easier and more efficient.

Recurrence time of a symbol in a string is defined as the number of symbols that have appeared since the last previous occurrence of the same symbol. It is one of the most fundamental quantities that can be used in universal source coding. If we count only the minimum required number of symbols occurring in the recurrence period, we can reduce some redundancy contained in recurrence time coding. The move-to-front (MTF) scheme is a typical example that shares the idea. In this correspondence, we establish three such schemes, and make a basic comparison with one another from the viewpoint that they can be thought of as different attempts to realize the above idea

In digital watermarking, the original data, called host or cover data, is inevitably distorted by the insertion of a watermark or embedded data. However, there are a number of applications that require complete lossless recovery of original data. This paper introduces an information theoretical model to the lossless data embedding problem, and gives the maximum embedding rate of the model. The main contribution of the paper is to propose an embedding scheme, which can asymptotically attain the maximum rate without knowing the source of the host data. The proposed scheme divides the host data into fixed-length blocks and embeds a watermark by replacing a less significant component of each block with a new component of the same length. The new component represents both the replaced original component and a fragment of the watermark. This paper shows that as the block length tends to infinity, the embedding rate converges to the maximum rate that could be attained when we ideally compress the less significant components using complete knowledge on the source of the host data.

One-shot coding and repeated coding are considered for the class of almost instantaneous variable-to-fixed length (AIVF) codes, C/sub AIVF/, which includes some nonproper VF codes in addition to the class of proper VF codes, C/sub PVF/. An algorithm is given to construct the average-sense optimal (a-optimal) AIVF code in one-shot coding that attains the maximum average parse length in C/sub AIVF/. The algorithm can also be used to obtain an AIVF code with multiple parse trees, which can attain good performance for repeated coding. Generally, the a-optimal code for one-shot coding and the good code for repeated coding are more efficient than the Tunstall (1967) code in A-ary cases if A/spl ges/3 although they coincide with the Tunstall code in the binary case. The competitively optimal (c-optimal) VF code is also considered for one-shot coding, and it is shown that the c-optimal code does not always exist in C/sub PVF/ and in C/sub AIVF/. Furthermore, whenever the c-optimal code exists, the Tunstall code is c-optimal in C/sub PVF/ and the a-optimal code obtained by our algorithm is c-optimal in C/sub AIVF/ if A=2 or 3, but the a-optimal code is not always c-optimal in C/sub AIVF/ if A/spl ges/4.

Summary form only given. We present a new implementation of the context sorting data compression method (Yokoo, 1997), which is an on-line adaptive algorithm for text compression. Our key idea is to utilize a new data structure called a prefix list (Yokoo, 1999). The original context sorting compression method, which uses neither explicit modeling nor arithmetic coding can be viewed as a symbol ranking text compressor. In the method presented here, in contrast, we form a context model with the frequency distribution to predict the current symbol. Our context model can exploit contexts of unlimited length, and it is combined with arithmetic coding. In these respects, the proposed method can also be viewed as giving an implementation of PPM* (Cleary and Teahan, 1997). Our space requirement is linear in the string length without depending on the context order. The prefix list is a dynamic data structure, which was proposed primarily to maintain a set of contexts in reverse lexicographic order. We can easily gather previous contexts according to the similarity to the current context. Predicted symbols can also be enumerated as the following symbols in those contexts. While enumerating those predicted symbols, we can completely simulate PPM*. If a set of contexts whose similarities to the current context are d or larger gives only one prediction, then their common d-symbol suffix is said to be a deterministic context. In our method, we begin the PPM mechanism with the shortest deterministic context if any, or with the contexts most similar to the current one otherwise. An escape symbol is emitted each time the similarity between the current, context and the existing context pointed to by a pointer in the prefix list decreases.

This paper introduces the notion of a context table, which is a common basis for describing and analyzing text compression algorithms. A context table stores all substrings in a text as their lexicographic orders. Examples of compression algorithms described in terms of context table concepts include LZ77 and the block-sorting algorithm. Since these algorithms are designed to work with an arbitrary source distribution, they can be expected to serve as an entropy estimator. A primal use of a context table is to reveal the capability of estimating the entropy. A context table makes it easy to understand several characteristic quantities including the recurrence time of a substring, the conditional recurrence time, and the length of the shortest unique substring. With the help of these concepts, some relations among apparently independent algorithms are established.

Every symbol in the data can be predicted by taking its immediately preceding symbols, or context, into account. This paper proposes a new adaptive data compression method based on a technique of context sorting. The aim of context sorting is to sort a set of contexts in order to find previous contexts similar to the current one. The proposed method predicts the next symbol by ranking the previous context-symbol pairs in order of context similarity. The codeword for the next symbol represents the rank of the symbol in this ordered sequence. The compression performance is evaluated both analytically and empirically. Although the proposed method uses no probability distribution to make a prediction, it has comparable compression performance to the best known data compression utilities.

This paper discusses the compression of computer files of data whose statistical properties are not given in advance. A new lossless coding method for this purpose, which utilizes Adel'son-Vel'skii-Landis trees, is effective to any word length. Its application to the lossless compression of gray-scale images shows wider applicability to any ordered set of 18-bit or 36-bit data.>

A class of new floating-point representations of real numbers, based on representations of the integers, is described. In the class, every representation uses a self-delimiting representation of the integers as a variable length field of the exponent, and neither overflow nor underflow appears in practice. The adopted representations of the integers are defined systematically, so that representation's of numbers greater than one have both exponent-significant and integer-fraction interpretations. Since representation errors are characterized by the length function of an underlying representation of the integers, superior systems in precision can be easily selected from the proposed class.>

Several data compression algorithms relating existing important source coding algorithms, including Ziv-Lempel codes, Rissanen's Context, and Welch's LZW method, are presented. First, an intermediate algorithm between the two Ziv-Lempel methods for universal data compression is proposed, which has the same asymptotic optimality as the well-known method based on the incremental parsing. The proposed algorithm is then compared with the context gathering algorithm. Context, in terms of gathering direction and gathering frequency. It is shown that while the proposed algorithm and Context have the same gathering frequency, they have opposite directions of context gathering. Practical variations are also considered. By combining the proposed algorithm with Welch's device, two practical data compression methods are obtained. They, as well as Welch's LZW method, start with a small table of symbol strings and build the table during compression and decompression. In practical methods, higher compression efficiency can be gained by accelerating the growth of the table.>

A class of new floating-point representations of real numbers, based on representations of the integers, is described. In the class, every representation uses a self-delimiting representation of the integers as a variable length field, and neither overflow nor underflow appears in practice. The adopted representations of the integers are defined systematically, so that representations of numbers greater than one have both exponent-significant and integer-fraction interpretations. Since representation errors are characterized by the length function of an underlying representation of the integers, systems superior in precision can be easily selected from the proposed class.>

A mixed-mode file compression scheme that incorporates interval encoding for finding duplicate occurrences of strings without storing or parsing the past sequence and a one-pass scheme for dynamic Huffman codes is presented. Results from experiments performed on various types of files are discussed. The proposed method runs in linear time, and the memory requirement depends only on the alphabet size. The code efficiency is compared experimentally to that of other schemes.>