Source author record

Jacob Ziv

Jacob Ziv appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT

Catalog footprint

What is connected

5works

2topics

1close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Efficient Compression of Long Arbitrary Sequences with No Reference at the Encoder

In a distributed information application an encoder compresses an arbitrary vector while a similar reference vector is available to the decoder as side information. For the Hamming-distance similarity measure, and when guaranteed perfect reconstruction is required, we present two contributions to the solution of this problem. One result shows that when a set of potential reference vectors is available to the encoder, lower compression rates can be achieved when the set satisfies a certain clustering property. Another result reduces the best known decoding complexity from exponential in the vector length $n$ to $O(n^{1.5})$ by generalized concatenation of inner coset codes and outer error-correcting codes. One potential application of the results is the compression of DNA sequences, where similar (but not identical) reference vectors are shared among senders and receivers.

preprint2015arXiv

A Constrained-Dictionary version of LZ78 asymptotically achieves the Finite-State Compressibility for any Individual Sequence with a Distortion measure

The unrestricted LZ78 universal data-compression algorithm (as well as the LZ77 and LZW versions) achieves asymptotically, as the block-length tends to infinity, the FS compressibility, namely the best compression-ratio that may be achieved by any Information-lossless(IL) block-to-variable finite-state(FS) algorithm, for any infinitely-long individual sequence. The encoder parses the sequence into distinct phrases where each newly generated phrase is a past phrase which is already stored in a dictionary, extended by one letter. The newly generated phrase is then added to the updated, ever-growing dictionary. One heuristic approach is the "Least Recently Utilized" (LRU) deletion approach, where only the most recent D entries are kept in the dictionary, thus yielding a constrained-dictionary version of LZ78 denoted by LZ78(LRU). In this note, for the sake of completeness, it is demonstrated again via a simple proof that the unrestricted LZ78 algorithm asymptotically achieves the FS-Compressibility. Then, it is demonstrated that the LZ78(LRU) information-lossless data-compression algorithm also achieves the FS compressibility, as the dictionary size D tends to infinity. Although this is perhaps not surprising, it does nevertheless yield a theoretical optimality argument for the popular LZ78(LRU) algorithm (and similarly, for the LZW(LRU) algorithm). In addition, the finite-state compressibility of an individual sequence under a constrained allowable distance measure between the original sequence and the decompressed sequence is defined. It is demonstrated that a particular adaptive vector-quantizer that sequentially replaces clusters of L-vectors onto a single, cluster-representative L-vector, followed by a constrained D-entries-dictionary version of LZ78(LRU) as above, is asymptotically optimal as D tends to infinity and L= log D .

preprint2014arXiv

A Note on the Compaction of long Training Sequences for Universal Classification -a Non-Probabilistic Approach

One of the central problems in the classification of individual test sequences (e.g. genetic analysis), is that of checking for the similarity of sample test sequences as compared with a set of much longer training sequences. This is done by a set of classifiers for test sequences of length N, where each of the classifiers is trained by the training sequences so as to minimize the classification error rate when fed with each of the training sequences. It should be noted that the storage of long training sequences is considered to be a serious bottleneck in the next generation sequencing for Genome analysis Some popular classification algorithms adopt a probabilistic approach, by assuming that the sequences are realizations of some variable-length Markov process or a hidden Markov process (HMM), thus enabling the imbeding of the training data onto a variable-length Suffix-tree, the size of which is usually linear in $N$, the length of the test sequence. Despite of the fact that it is not assumed here that the sequences are realizations of probabilistic processes (an assumption that does not seem to be fully justified when dealing with biological data), it is demonstrated that "feature-based" classifiers, where particular substrings (called "features" or markers) are sought in a set of "big data" training sequences may be based on a universal compaction of the training data that is contained in a set of $t$ (long) individual training sequences, onto a suffix-tree with no more than O(N) leaves, regardless of how long the training sequence is, at only a vanishing increase in the classification error rate.

preprint2013arXiv

On Finite Memory Universal Data Compression and Classification of Individual Sequences

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.

preprint2011arXiv

On the optimality of universal classifiers for finite-length individual test sequences

We consider pairs of finite-length individual sequences that are realizations of unknown, finite alphabet, stationary sources in a clas M of sources with vanishing memory (e.g. stationary Markov sources). The task of a universal classifier is to decide whether the two sequences are emerging from the same source or are emerging from two distinct sources in M, and it has to carry this task without any prior knowledge of the two underlying probability measures. Given a fidelity function and a fidelity criterion, the probability of classification error for a given universal classifier is defined. Two universal classifiers are defined for pairs of $N$ -sequence: A "classical" fixed-length (FL) universal classifier and an alternative variable-length (VL) universal classifier. Following Wyner and Ziv (1996) it is demonstrated that if the length of the individual sequences N is smaller than a cut-off value that is determined by the properties of the class M, any universal classifier will fail with high probability . It is demonstrated that for values of N larger than the cut-off rate, the classification error relative to either one of the two classifiers tends to zero as the length of the sequences tends to infinity. However, the probability of classification error that is associated with the variable-length universal classifier is uniformly smaller (or equal) to the one that is associated with the "classical" fixed-length universal classifier, for any finite length.