Compression by Substring Enumeration (CSE), which is one of lossless data compression algorithms, and various versions of CSE have been proposed. In encoding of CSE, substrings of given fixed length and their frequencies within circular string for an input string are output as a codeword. The circular string is made by connecting the first symbol and the last symbol of an input string. In decoding of CSE, the circular string is reconstructed from its substrings and their frequencies. Furthermore, the minimum length of substrings for which the decoding does reconstruct the circular string has been proved, together with a reconstruction algorithm. However, the algorithm requires substrings to have no errors. Therefore, in this paper, we propose an error correcting algorithm which can detect one of substrings having one bit-flipping, one bit-insertion, or one bit-deletion error and correct the bit error. By applying the proposed algorithm, we can reconstruct a circular string from a set of substrings and their frequencies including only one substring which has at most one bit error.

This paper proposes two variants of improved Compression by Substring Enumeration (CSE) with a finite alphabet. In previous studies on CSE, an encoder utilizes inequalities which evaluate the number of occurrences of a substring and a minimal forbidden word (MFW) to be encoded. Also, its codeword length is proportional to the difference between the upper and lower bounds deduced from the inequalities, but the lower bound is not tight. Therefore, in this paper, we derive a new tight lower bound and consequently propose a new CSE algorithm using the new inequality. We also propose a new encoding order of substrings and MFWs which are sorted by row and column marginal totals of the proper substrings and MFWs, instead of lexicographical order used in previous studies. We then propose a new CSE algorithm which is the first proposed CSE algorithm using the new encoding order. Experimental results show that compression ratios of all files of the Calgary corpus in the proposed algorithms are better than those of a previous study on CSE with a finite alphabet. Moreover, compression ratios under the second proposed CSE get better than or equal to that under a well-known compressor for 11 files amongst 14 files in the corpus.

A technique of lossless compression via substring enumeration (CSE) is a well-known lossless compression algorithm for a one-dimensional (1D) source. The CSE uses a probabilistic model built from the circular string of an input source for encoding the source. The CSE is applicable to two-dimensional (2D) sources such as images by dealing with a line of pixels of 2D source as a symbol of an extended alphabet. At the initial step of the CSE encoding process, we need to output number of occurrences of all symbols of the extended alphabet, so that the time complexity increases exponentially when the size of source becomes large. To reduce the time complexity, we propose a new CSE which can encode a 2D source in block-by-block instead of line-by-line. The proposed algorithm uses the flat torus of an input 2D source as a probabilistic model instead of the circular string of the source. Moreover, we prove the asymptotic optimality of the proposed algorithm for 2D general sources.

Antidictionaries are in particular useful for source coding. In one dimension, for an input string, there are fast construction algorithms of an antidictionary in which a suffix tree that stores all the substrings of the string is utilized. However, in two dimension (2D), for an n×n input square or rectangle, there is no fast construction algorithm of an antidictionary except a straight-forward algorithm in O(n8) time. In this paper, we propose a 2D suffix trie which stores all the subrectangles of an input rectangle and present an algorithm to construct a 2D suffix trie in O(n4log n) time. A 2D suffix trie consists of two suffix tries with suffix links rowwise and columnwise. Moreover, we propose a fast construction algorithm of a two-dimensional antidictionary using a 2D suffix trie in O(n5log n) time, and their effectivenesses are demonstrated by simulation results.

Lossless data compression via substring enumeration (CSE) has been proposed by Dubé and Beaudoin in 2010. The CSE outputs its encoder called compacted substring automaton as a codeword, and an efficient representation of the automaton is also proposed. In this paper, we prove an isomorphism between compacted substring automaton and antidictionary automaton, which is an encoder of antidictionary coding. Then we propose a new static antidictionary coding which uses the representation of compacted substring automaton instead of antidictionary. Moreover, we prove an asymptotic optimality of the proposed coding for a stationary ergodic source.

An antidictionary, a set of words that never appear in a given string, is a useful data structure for source coding as well as other fields of computer sciences. A fast and memory-efficient algorithm for constructing antidictionaries by means of suffix array is presented. We prove that the proposed algorithm constructs an antidictionary array with linear time and space.

An antidictionary is in particular useful for data compression. Static construction algorithms of antidictionaries with linear complexity have been proposed. However, the construction algorithms do not work in a dynamic manner with linear complexity. In this paper, we propose a dynamic construction algorithm of an antidictionary with linear complexity. The proposed algorithm uses two linear construction algorithms of suffix trees proposed by Weiner and Ukkonen, individually. It is proved that the proposed algorithm works with linear complexity. Moreover, its effectiveness is demonstrated by simulation results.

An antidictionary code is a lossless compression algorithm using an antidictionary which is a set of minimal words that do not occur as substrings in an input string. The code was proposed by Crochemore et al. in 2000, and its asymptotic optimality has been proved with respect to only a specific information source, called balanced binary source that is a binary Markov source in which a state transition occurs with probability 1/2 or 1. In this paper, we prove the optimality of both static and dynamic antidictionary codes with respect to a stationary ergodic Markov source on finite alphabet such that a state transition occurs with probability p (0 <; p ≤ 1).

This paper proposes a new on-line antidictionary code with linear time. The proposed algorithm uses a subset of antidictionary which length of the elements is at most a given fixed length. It is proved that the time complexity of this algorithm is linear with respect to the string length. Its effectiveness is demonstrated by simulation results.

An anti-dictionary is in particular useful for data compression, and it consists of minimal forbidden words for a given string. We derive the average length Mnof minimal forbidden words in strings of length n under a stationary ergodic source with entropy H which takes values on a finite alphabet. For the string length n, we prove, log n/Mn= H, in probability, as n rarr infin. We use the Wyner-Ziv result, with respect to connection between entropy and recurrence-time for ergodic processes, to prove the theorem. Its validity is shown by simulation results on a memoryless binary information source.

This paper proposes an on-line data compression based on antidictionaries with linear time. The proposed algorithm works using only suffix trees without constructing of antidictionaries, and we prove that the time complexity of this algorithm is linear with respect to the string length. Furthermore, the proposed algorithm produces the tree model based on antidictionaries. This tree model gives an efficient probabilistic model for entropy codings. Its effectiveness is demonstrated by simulation results.

An antidictionary of a binary string is a set of words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary for a binary string using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results