On Finite Memory Universal Data Compression and Classification of Individual Sequences

Details On Finite Memory Universal Data Compression and Classification of Individual Sequences On Finite Memory Universal Data Compression and Classification of Individual Sequences

2006-12-04

arxiv.org/abs/cs/0612019v4

Computer Science

Information Theory

Scientific paper

Consider the case where consecutive blocks of N letters of a semi-infinite individual sequence X over a finite-alphabet are being compressed into binary sequences by some one-to-one mapping. No a-priori information about X is available at the encoder, which must therefore adopt a universal data-compression algorithm. It is known that if the universal LZ77 data compression algorithm is successively applied to N-blocks then the best error-free compression for the particular individual sequence X is achieved, as $N$ tends to infinity. The best possible compression that may be achieved by any universal data compression algorithm for finite N-blocks is discussed. It is demonstrated that context tree coding essentially achieves it. Next, consider a device called classifier (or discriminator) that observes an individual training sequence X. The classifier's task is to examine individual test sequences of length N and decide whether the test N-sequence has the same features as those that are captured by the training sequence X, or is sufficiently different, according to some appropriatecriterion. Here again, it is demonstrated that a particular universal context classifier with a storage-space complexity that is linear in N, is essentially optimal. This may contribute a theoretical "individual sequence" justification for the Probabilistic Suffix Tree (PST) approach in learning theory and in computational biology.

Affiliated with

Also associated with

No associations

Rating

On Finite Memory Universal Data Compression and Classification of Individual Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Finite Memory Universal Data Compression and Classification of Individual Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Finite Memory Universal Data Compression and Classification of Individual Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-649464