Bibliography

[AT80]

L. Arnold and M. Theodosoopulu. Deterministic limit of the stochastic model of chemical reactions with diffusion. Advanced Applied Probability, 12:367-379, 1980.

[Blo96]

Douglas Blount. Diffusion limits for a nonlinear density dependent space-time population model. Annals of Probability, 24(2):639-659, 1996.

A population density process is constructed using approximately Niell particles performing rate N² random walks between N cells distributed on the unit interval. Particles give birth or die within cells, and particle death rates are a function of the occupied cell population. With suitable scaling, two possible limiting stochastic partial differential equations are obtained. Both are nonlinear perturbations of the equation satisfied by the density process of super Brownian motion.

[EK00]

William Evans and David Kirkpatrick. Restructuring ordered binary trees. In SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 477-486. Society for Industrial and Applied Mathematics, 2000.

We consider the problem of restructuring an ordered binary tree T, preserving the in-order sequence of its nodes, so as to reduce its height to some target value h. Such a restructuring necessarily involves the downward displacement of some of the nodes of T. Our results, focusing both on the maximum displacement over all nodes and on the maximum displacement over leaves only, prove (i) an explicit tradeoff between the worst-case displacement and the height restriction (including a family of trees that exhibit the worst case displacements) and (ii) efficient algorithms to achieve height-restricted restructuring while minimizing the maximum node displacement.

Keywords: optimal binary search trees

[Fal73]

N. Faller. An adaptive system for data compression. In Record of the 7th Asilomar Conferences on Circuits, Systems and Computers, pages 593-597, 1973.

[Gag03]

Travis Gagie. New ways to construct binary search trees. In Toshihide Ibaraki, Naoki Katoh, and Hirotaka Ono, editors, Proceedings of ISAAC 2003, volume 2906 of Lecture Notes in Computer Science, pages 537-543, 2003.

We give linear-time algorithms for re-ordering and height-restricting a binary search tree with only a small increase in cost, constructing a nearly optimal binary search tree given the rank by probability of each possible outcome, and height-restricting an optimal binary search tree when the increase in cost is restricted. Whereas most algorithms for constructing good binary search trees need the probabilities of outcomes as input, our algorithms do not.

Keywords: optimal binary search tree

[Gag04]

Travis Gagie. Dynamic shannon coding. In Susanne Albers and Tomasz Radzik, editors, Proceedings of 12th annual European Symposium on Algorithms 2004, volume 3221 of Lecture Notes in Computer Science, pages 359-370, 2004.

[Gal78]

R. G. Gallager. Variations on a theme by Huffman. IEEE Transations on Information Theory, IT-24:668-674, November 1978.

[HF98]

Haripriyan Hampapuram and Michael Fredman. Optimal biweighted binary trees and the complexity of maintaining partial sums. SIAM Journal on Computing, 28(1):1-9, 1998.

Let A be an array. The partial sum problem concerns the design of a data structure for implementing the following operations. The operation update(j,x) has the effect A[j]<- A[j]+x, and the query sum(j) returns the partial sum Σ_i=1^j A[i]. Our interest centers upon the optimal efficiency with which sequences of such operations can be performed, and we derive new upper and lower bounds in the semigroup model of computation. Our analysis relaates the optimal complexity of the partial sum problem to optimal binary trees relative to a type of weighting scheme that defines the notion of biweighted binary tree.

Keywords: data structures, partial sums, lower bounds

[HSS03]

Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung. Succinct data structures for searchable partial sums. In Toshihide Ibaraki, Naoki Katoh, and Hirotaka Ono, editors, Algorithms and Computation, 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings, volume 2906 of Lecture Notes in Computer Science, pages 505-516. Springer, 2003.

The Searchable Partial Sums is a data structure problem that maintains a sequence of n non-negative k-bit integers; in addition, it allows us to modify the entries by the update operation, while supporting two types of queries: sum and search. Recently, researchers focus on the succinct representation of the data structure in kn + o(kn) bits. They study the tradeoff in time between the query and the update operations, under the word RAM with word size O(log U) bits. For the special case where k=1 (which is known as Dynamic Bit Vector problem), Raman et al. showed that both queries can be supported in O(log_b n) time, while update requires O(b) amortized time for any b with log n/loglog n <= b <= n. This paper generalizes the study and shows that even for k = O(loglog n), both query and update operations can be maintained using the same time complexities. Also, the time for update becomes worst-case time.

For the general case when k = O(log U), we show a lower bound of Ω (sqrt(log n/loglog n)) time for the search query. On the other hand, we propose a data structure that supports sum in O(log_b n) time, search in O(τlog_b n) time, and update in O(b) time, where τ denotes the value of min{loglog nloglog U/logloglog U, sqrt(log n/loglog n)}. When b=n^ε, our data structure achieves optimal time bounds.

This paper also extends the Searchable Partial Sums with insert and operations, and provides succinct data structures for some cases.

[Huf52]

David A. Huffman. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Radio Engineers, volume 40, pages 1098-1101, 1952.

An optimum method of coding an ensemble of messages consisting of a finite number of members is developed. A minimum-redundancy code is one constructid in such a way that the average number of coding digits per message is minimized.

[KL02]

Michael A. Kouritzin and Hongwei Long. Convergence of markov chain approximations to stochastic reaction-diffusion equations. The Annals of Applied Probability, 12(3):1039-1070, 2002.

[Knu85]

Donald E. Knuth. Dynamic Huffman coding. Journal of Algorithms, 6:163-180, 1985.

This note shows how to maintain a prefix code that remains optimum as the weights change. A Huffman tree with nonnegative integer weights can be represented in such a way that any weight w at level l can be increased or decreased by unity in O(l) steps, preserving minimality of the weighted path length. One-pass algorithms for file compression can be based on such a representation.

Keywords: dynamic Huffman codes

[Meh77]

Kurt Mehlhorn. A best possible bound for the weighted path length of binary search trees. SIAM Journal on Computing, 6:235-239, 1977.

[ML97]

Ruy Luiz Milidiú and Eduardo Sany Laber. Improved bounds on the inefficiency of length-restricted prefix codes. Technical report, Pontificia Universidade Católica do Rio de Janeiro, September 1997.

Consider an alphabet Σ={a₁,...,a_n} with corresponding symbol probabilities p₁,...,p_n. The L-restricted prefix code is a prefix code where all the code lengths are not greater than L. The value L is a given integer such that L>= log n.

Define the average code length difference by ε = Σ_i=1ⁿ p_il_i - Σ_i=1ⁿ p_il_i where l₁,...,l_n are the code lengths of the optimal L-restricted prefix code for Σ and l₁,...,l_n are the code lengths of the optimal prefix code for Σ.

Let Ψ be the golden ratio 1,618. In this paper, we show that ε < 1/Ψ^{L-log(n+log n - L) - 1} when L >= log n. We also prove the sharp bound ε < log 1 - 1, when L = log n. By showing the lower bound 1/ψ^{L-log n + 2 + log (n/n-L)} -1 on the maximum value of ε, we guarantee that our bound is asymptotically tight in the range log n < L <= n/2.

Furtherbore, we present an O(n) time and space 1/Ψ^{L-log(n+log n - L) -1}-approximative algorithm to construct L-restricted prefix codes, considering that the given probabilites are already sorted. The results presented in this paper indicate that one can efficiently implement prefix codes with length restriction, obtaining also very effective codes.

Keywords: prefix codes, Huffman trees, adaptive algorithms

[MLP97]

Ruy Luiz Milidiú, Eduardo Sany Laber, and Artur Alves Pessoa. Improved analysis of FGK algorithm. Technical report, Pontificia Universidade Católica do Rio de Janeiro, September 1997.

An important issue related to coding schemes is their compression loss. A simple measure ε of the compression loss due to a coding scheme different than Huffman coding, is defined by ε = A_C - A_H where A_H is the average code length of a static Huffman encoding and A_C is the average code length of an encoding based on the compression scheme C.

When the scheme C is the FGK algorithm, Vitter conjectured tha ε <= K for some real constant K. Here, we use an amortized analysis to prove this conjecture. We show that ε < 2. Furthermore, we show through an example that our bound is asymptotically tight. This result explans the good performance of FGK that many authors have observed through practical experiments.

Keywords: dynamic Huffman codes, amortized analysis, data compression

[Mof99]

Alistair Moffat. An improved data structure for cumulative probability tables. Software - Practice and Experience, 29(7):647-659, 1999.

In 1994 Peter Fenwick at the University of Auckland devised an elegant mechanism for tracking the cumulative symbol frequency counts that are required for adaptive arithmetic coding. His structure spends O(log n) time per update when processing the sth symbol in an alphabet of n symbols. In this note we propose a small but significant alteration to the mechanism, and reduce the running time to O(log(1+s)) time per update. If a probability-sorted alphabet is maintained, so that simbol s in the alphabet is the sth most frequent, the cost of processing each symbol is then linear in the number of bits produced by the arithmetic coder.

Keywords: compression, adaptive coding; dynamic coding, arithmetic coding, data structure

[PD04]

Mihai Patrascu and Erik D. Demaine. Tight bounds for the partial-sums problem. In J. Ian Munro, editor, Proceedings of the 15th annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, January 11-13, 2004, pages 20-29. SIAM, 2004.

We close the gaps between known lower and upper bounds for the online partial-sums problem in ithe RAM and group models of computation. If elements are chosen from an abstract group, we prove an Ω(log n) lower bound on the number of algebraic operations that must be performed, matching a well-known upper bound. In the RAM model with b-bit registers, we consider the well-studied case when the elements of the array can be changed additively by δ-bit integers. We give a RAM algorithm that achieves a running time of Θ(1+log n/log(b/δ)) and prove a matching lower bound in the cell-probe model. Our lower bound is for the amortized complexity, and makes minimal assumptions about the relations between n, b, and δ. The best previous lower bound was Ω(log n/(loglog n + log b)), and the best previous upper bound matche only in the special case b=Θ(log n) and δ = O(log log n)

[RRR01]

Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct dynamic data structures. In Frank K. H. A. Dehne, Jörg-Rüdiger Sack, and Roberto Tamassia, editors, Proceedings of 7th International Workshop on Algorithms and Data Structures, Providence, RI, August 8-10, 2001, volume 2125 of Lecture Notes in Computer Science, pages 426-437, 2001.

We develop succinct data structures to represent (i) a sequence of values to support partial sum and select queries and update (changing values) and (ii) a dynamic array consisting of a sequence of elements which supports insertion, deletion and access of an element at any given index.

For the partial sums problem on n non-negative integers of k bits each, we support update operations on O(b) time and sum in O(log_b n) time, for any parameter b, log n / loglog n <= b <= n^ε for any fixed positive ε < 1. The space used is kn+o(kn) bits and the time bounds are optimal. When b = log n / log log n or k = 1 (i.e., when we are dealing with a bit-vector), we can also support the select operation in the same time as the sum operation, but the update time becomes amortized.

For the dynamic array problem, we give two structures both using o(n) bits of extra space whene n is the number of elements in the array: one supports lookup in constant worst case time and updates in O(n^ε) worst case time, and the other supports all operations in O(log n / log log n) amortized time. The time bounds of both theses structures are optimal.

[TM05]

Andrew Turpin and Alistair Moffat. On-line adaptive canonical prefix coding with bounded compression loss. IEEE Transactions on Information Technology, 47(1):88-98, January 2005.

Semistatic minimum-redundancy prefix (MRP) coding is fast compared with rival coding methods, but requires two passes during encoding. Its adaptive counterpart, dynamic Huffman coding, requires only one pass over the input message for encoding and decoding, and is asymptotically efficient. Dynamic Huffman coding is, however, notoriously slow in practice. By removing the restriction that the code used for each message symbol must have minimum-redundancy and thereby admitting some compression loss, it is possible to improve the speed of adaptive MRP coding. This paper presents a controlled method for trading compression loss for coding speed by approximating symbol frequencies with a geometric distribution. The result is an adaptive MRP coding that is asymptotically efficient and also fast in practice.

Keywords: adaptive coding, Huffman coding, minimum-redundancy coding, on-line coding

[Vit87]

Jeffrey Scott Vitter. Design and analysis of dynamic Huffman codes. Journal of the Association for Computing Machinery, 34(4):825-845, October 1987.

A new one-pass algorithm for constructing dynamic Huffman codes is introduced and analyzed. We also analyze the one-pass algorithm due to Faller, Gallager, and Knuth. In each algorithm, both the sender and receiver maintain equivalent dynamically varying Huffman trees, and the coding is done in real time. We show that a the number of bits used by the new algorithm to encode a message containing t letters is < t bits more than that used by the conventional two-pass Huffman scheme, independent of the alphabet size. This is the best possible in the worst case, for any one-pass Huffman method. Tight upper and lower bounds are derived. Empirical tests show that the encodings produced by the new algorithm are shorter than those of the other one-pass algorithm and, except for long messages, are shorter than those of the two-pass method. The new algorithm is well suited for online encoding/decoding in data networks and for file compression.

Keywords: distributed computing, entropy, dynamic Huffman codes

[Vit89]

Jeffrey Scott Vitter. Dynamic huffman coding. ACM Transactions on Mathematical Software, 15(2):158-167, 1989.

We present a Pascal implementation of the one-pass algorithm for constructing dynamic Huffman codes that is described and analyzed in a companion paper [Vit87]. The program runs in real time; that is, the processing time for each letter of the message is proportional to the length of its codeword. The number of bits used to encode a message of t letters is less than t bits more than that used by the well-known two-pass algorithm. This is best possible for any one-pass Huffman scheme. In practice it uses fewer bits than all other Huffman schemes. The algorithm has applications in file compression and network transmission.

This file has been generated by bibtex2html 1.76