The Experts below are selected from a list of 201 Experts worldwide ranked by ideXlab platform

Elad Verbin - One of the best experts on this subject based on the ideXlab platform.

  • a simpler analysis of burrows wheeler based compression
    Theoretical Computer Science, 2007
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper, we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D.J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain the Burrows-Wheeler Transform of the text, (2) Convert the transform into a sequence of integers using the move-to-front algorithm, (3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We achieve a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and @m>1, the length of the compressed string is bounded by @m@?|s|H"k(s)+log(@z(@m))@?|s|+@mg"k+O(logn) where H"k is the kth order empirical entropy, g"k is a constant depending only on k and on the size of the alphabet, and @z(@m)=11^@m+12^@m+... is the standard zeta function. As part of the analysis, we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler Transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286@?|s|H"k(s)+g"k+O(logn). This bound is better than the bound we give for bw0.

  • a simpler analysis of burrows wheeler based compression
    Combinatorial Pattern Matching, 2006
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and Wheeler in their first paper on the subject [6], called bw0. This algorithm consists of the following three steps: 1) Compute the Burrows-Wheeler transform of the text, 2) Convert the transform into a sequence of integers using the move-to-front algorithm, 3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We prove a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ> 1, the length of the compressed string is bounded by μ|s| Hk(s) + log(ζ(μ)) |s| + gk where Hk is the k-th order empirical entropy, gk is a constant depending only on k and on the size of the alphabet, and $\zeta(\mu) = \frac{1}{1^\mu} + \frac{1}{2^\mu} + \ldots $ is the standard zeta function. As part of the analysis we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286 |s| Hk(s) + gk. This bound is better than the bound we give for bw0.

  • a simpler analysis of burrows wheeler based compression
    Lecture Notes in Computer Science, 2006
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and Wheeler in their first paper on the subject [6], called BW0. This algorithm consists of the following three steps: 1) Compute the Burrows-Wheeler transform of the text, 2) Convert the transform into a sequence of integers using the move-to-front algorithm, 3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We prove a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ > 1, the length of the compressed string is bounded by μ, |s|H k (s) + log(ζ(μ Is + g k where H k is the k-th order empirical entropy, g k is a constant depending only on k and on the size of the alphabet, and ζ(μ) = 1 1μ + 1 2μ +... is the standard zeta function. As part of the analysis we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286 |s|H k (s) + g k . This bound is better than the bound we give for BW0.

Haim Kaplan - One of the best experts on this subject based on the ideXlab platform.

  • a simpler analysis of burrows wheeler based compression
    Theoretical Computer Science, 2007
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper, we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D.J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain the Burrows-Wheeler Transform of the text, (2) Convert the transform into a sequence of integers using the move-to-front algorithm, (3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We achieve a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and @m>1, the length of the compressed string is bounded by @m@?|s|H"k(s)+log(@z(@m))@?|s|+@mg"k+O(logn) where H"k is the kth order empirical entropy, g"k is a constant depending only on k and on the size of the alphabet, and @z(@m)=11^@m+12^@m+... is the standard zeta function. As part of the analysis, we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler Transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286@?|s|H"k(s)+g"k+O(logn). This bound is better than the bound we give for bw0.

  • a simpler analysis of burrows wheeler based compression
    Combinatorial Pattern Matching, 2006
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and Wheeler in their first paper on the subject [6], called bw0. This algorithm consists of the following three steps: 1) Compute the Burrows-Wheeler transform of the text, 2) Convert the transform into a sequence of integers using the move-to-front algorithm, 3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We prove a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ> 1, the length of the compressed string is bounded by μ|s| Hk(s) + log(ζ(μ)) |s| + gk where Hk is the k-th order empirical entropy, gk is a constant depending only on k and on the size of the alphabet, and $\zeta(\mu) = \frac{1}{1^\mu} + \frac{1}{2^\mu} + \ldots $ is the standard zeta function. As part of the analysis we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286 |s| Hk(s) + gk. This bound is better than the bound we give for bw0.

  • a simpler analysis of burrows wheeler based compression
    Lecture Notes in Computer Science, 2006
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and Wheeler in their first paper on the subject [6], called BW0. This algorithm consists of the following three steps: 1) Compute the Burrows-Wheeler transform of the text, 2) Convert the transform into a sequence of integers using the move-to-front algorithm, 3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We prove a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ > 1, the length of the compressed string is bounded by μ, |s|H k (s) + log(ζ(μ Is + g k where H k is the k-th order empirical entropy, g k is a constant depending only on k and on the size of the alphabet, and ζ(μ) = 1 1μ + 1 2μ +... is the standard zeta function. As part of the analysis we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286 |s|H k (s) + g k . This bound is better than the bound we give for BW0.

Shir Landau - One of the best experts on this subject based on the ideXlab platform.

  • a simpler analysis of burrows wheeler based compression
    Theoretical Computer Science, 2007
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper, we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D.J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain the Burrows-Wheeler Transform of the text, (2) Convert the transform into a sequence of integers using the move-to-front algorithm, (3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We achieve a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and @m>1, the length of the compressed string is bounded by @m@?|s|H"k(s)+log(@z(@m))@?|s|+@mg"k+O(logn) where H"k is the kth order empirical entropy, g"k is a constant depending only on k and on the size of the alphabet, and @z(@m)=11^@m+12^@m+... is the standard zeta function. As part of the analysis, we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler Transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286@?|s|H"k(s)+g"k+O(logn). This bound is better than the bound we give for bw0.

  • a simpler analysis of burrows wheeler based compression
    Combinatorial Pattern Matching, 2006
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and Wheeler in their first paper on the subject [6], called bw0. This algorithm consists of the following three steps: 1) Compute the Burrows-Wheeler transform of the text, 2) Convert the transform into a sequence of integers using the move-to-front algorithm, 3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We prove a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ> 1, the length of the compressed string is bounded by μ|s| Hk(s) + log(ζ(μ)) |s| + gk where Hk is the k-th order empirical entropy, gk is a constant depending only on k and on the size of the alphabet, and $\zeta(\mu) = \frac{1}{1^\mu} + \frac{1}{2^\mu} + \ldots $ is the standard zeta function. As part of the analysis we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286 |s| Hk(s) + gk. This bound is better than the bound we give for bw0.

  • a simpler analysis of burrows wheeler based compression
    Lecture Notes in Computer Science, 2006
    Co-Authors: Haim Kaplan, Shir Landau, Elad Verbin
    Abstract:

    In this paper we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows-Wheeler Transform. We deal mainly with the algorithm purposed by Burrows and Wheeler in their first paper on the subject [6], called BW0. This algorithm consists of the following three steps: 1) Compute the Burrows-Wheeler transform of the text, 2) Convert the transform into a sequence of integers using the move-to-front algorithm, 3) EnCode the integers using Arithmetic Code or any order-0 encoding (possibly with run-length encoding). We prove a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ > 1, the length of the compressed string is bounded by μ, |s|H k (s) + log(ζ(μ Is + g k where H k is the k-th order empirical entropy, g k is a constant depending only on k and on the size of the alphabet, and ζ(μ) = 1 1μ + 1 2μ +... is the standard zeta function. As part of the analysis we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows-Wheeler transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1.7286 |s|H k (s) + g k . This bound is better than the bound we give for BW0.

William A Pearlman - One of the best experts on this subject based on the ideXlab platform.

  • a new fast and efficient image Codec based on set partitioning in hierarchical trees
    IEEE Transactions on Circuits and Systems for Video Technology, 1996
    Co-Authors: Amir Said, William A Pearlman
    Abstract:

    Embedded zerotree wavelet (EZW) coding, introduced by Shapiro (see IEEE Trans. Signal Processing, vol.41, no.12, p.3445, 1993), is a very effective and computationally simple technique for image compression. We offer an alternative explanation of the principles of its operation, so that the reasons for its excellent performance can be better understood. These principles are partial ordering by magnitude with a set partitioning sorting algorithm, ordered bit plane transmission, and exploitation of self-similarity across different scales of an image wavelet transform. Moreover, we present a new and different implementation based on set partitioning in hierarchical trees (SPIHT), which provides even better performance than our previously reported extension of EZW that surpassed the performance of the original EZW. The image coding results, calculated from actual file sizes and images reconstructed by the decoding algorithm, are either comparable to or surpass previous results obtained through much more sophisticated and computationally complex methods. In addition, the new coding and decoding procedures are extremely fast, and they can be made even faster, with only small loss in performance, by omitting entropy coding of the bit stream by the Arithmetic Code.

Susumu Itoh - One of the best experts on this subject based on the ideXlab platform.

  • a lossless coding scheme using adaptive predictors and Arithmetic Code optimized for each image
    Systems and Computers in Japan, 2007
    Co-Authors: Ichiro Matsuda, Yuji Umezu, Nau Ozaki, Joji Maeda, Susumu Itoh
    Abstract:

    A highly efficient lossless encoding method for static images is proposed. In this method, multiple linear predictors are created for each image and adaptive prediction that responds to the local structure of images such as edges and textures is achieved by switching between these predictors at the block level. Furthermore, the probability density functions of the prediction errors are categorized by context modeling and modeled by generalized Gaussian functions, and adaptive Arithmetic encoding of the prediction errors is performed by using probability tables that are generated for each pixel from this model. Parameters that are needed in the coding such as the prediction coefficients, the predictor selection data for each block, and the shapes of the generalized Gaussian functions are optimized by repeatedly minimizing a cost function that includes the Code length of the parameters themselves in addition to the Code length of the prediction errors that are calculated from the probability model above, and the parameters are then enCoded separately as side data for each image. A procedure is introduced to improve prediction accuracies by using quadtree segmentation to segment the image into variable-sized blocks between which the predictor can change. Coding experiments are conducted and the proposed method is found to produce coding rates of 6 to 44p lower than the international standard JPEG-LS method, with the proposed method achieving superior coding performance that surpasses existing coding methods for all of the images used in the experiments. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(4): 1–11, 2007; Published online in Wiley InterScience (). DOI 10.1002sscj.20630

  • lossless coding using predictors and Arithmetic Code optimized for each image
    Lecture Notes in Computer Science, 2003
    Co-Authors: Ichiro Matsuda, Noriyuki Shirai, Susumu Itoh
    Abstract:

    This paper proposes an efficient lossless coding scheme for still images. The scheme utilizes a block-adaptive prediction technique to effectively remove redundancy in a given image. The resulting prediction errors are enCoded using a kind of context-adaptive Arithmetic coding method. In order to improve coding efficiency, a generalized Gaussian function is used as a probability distribution model of the prediction errors in each context. Moreover, not only the predictors but also parameters of the probability distribution models are iteratively optimized for each image so that a coding rate of the prediction errors can have a minimum. Experimental results show that an average coding rate of the proposed coding scheme is close to 90% of that of JPEG-LS and is lower than that of TMW.