We construct the Compressed Form array data structure (CF array) that supports the array interface while requiring$\mathcal{O}(n)$bits of space to store$n$integers from the range$\{1,2, \ldots$, poly$(n)\}$, under the smoothness condition that large integers are spaced proportionally to their values:$\forall i \neq j,\lfloor\log \min \{A[i], A[j]\}\rfloor \leq\lfloor\log\vert j-i\vert \rfloor$.

We present several improvements for decoding canonical Huffman codes, a key component of many lossless compression systems. Based on the Moffat-Turpin algorithm, we redesign its data layout, bit-buffer handling, and decoding tables to reduce memory indirection and branch overhead. Additional speedups are achieved through partial table-based decoding and SIMD-assisted bitstream processing. Experiments on word-based English text compression demonstrate decoding speed improvements of$30-40 \%$compared to the baseline implementation, without compromising compression efficiency.

Adaptive encoding plays a central role in data compression, allowing symbol probabilities to be estimated and updated dynamically. This paper presents a detailed comparison between the forward model, which assumes prior knowledge of the symbol frequencies, and the backward adaptive model, which increments the frequencies during encoding and decoding. We derive an exact expression for the bit-length difference between the two and show that for data distributed by Zipf's law, the forward encoding is beneficial even when we count the cost of information about symbols' frequencies. Extensive experiments conducted on real-world text corpora of varying sizes support the new theoretical results.

We present two adaptive coding methods that perform especially well on large alphabets like those used in word-level text compression. The first is based on re-indexing a universal codeword set. The more evolved second method assumes that the underlying codeword set can be optimized and re-generated efficiently. Experiments show that this method, using the Binary Mixed-digit codes as an underlying solution, produces about 1% bigger compressed files than the classical Vitter's algorithm adapted to large alphabets, being more than an order of magnitude faster in encoding and decoding.

We propose a family of Fibonacci-style codes, combining the advantages of higher-order Fibonacci numeration systems and the flexibility of binary mixed-digit codes. We establish the theoretical foundation of these new codes, proving a generalization of the Kraft inequality for prefix-free codes on mixed-digit numeration systems and the completeness of the new family of Fibonacci codes. Experiments on natural language text show that the proposed codes provide a coding structure that can adapt to various data distributions and capable of achieving superior compression ratios.

This paper extends the forward-looking approach to handle alphabets of words, which leads to further compression savings. It introduces an efficient encoding for the header information, specifically the exact frequencies of the alphabet elements. Moreover, an alternative ordering method for compressing word-based dictionaries is proposed, emphasizing the benefits of forward-looking adaptive compression. Experimental results demonstrate the effectiveness of the proposed approach.

A compressed representation of integer sequences is the key element of different data compression techniques. The variable-length Reverse Multi-Delimiter codes [1] provide a simple and space-efficient solution to the given problem, combining a good compression ratio with fast decoding. In this research, we investigate another property of RMD-codes - the ability of direct access to codewords in the encoded bitstream. If integers are sorted and the deltas between them are small enough, the problem of direct access is reduced to performing the select operation on a bitmap. However, RMD-codes allow us to address the more general problem of direct access to elements of an unordered integer sequence given in a compressed form. We developed the method of extracting and decoding a codeword from an RMD-bitstream in almost constant time. In text compression, the solution is highly space-saving as the RMD-code size is close to the entropy and extra data structures are tiny.

A lossless data compression code based on a binary-coded ternary number representation is investigated. The code is synchronizable and supports a direct search in a compressed file. A simple monotonous encoding and very fast decoding algorithms are constructed owing to code properties. Experiments show that in natural language text compression the new code outperforms byte-aligned codes SCDC and RPBC either in compression ratio or in decoding speed.

An enhanced version of a recently introduced family of variable length binary codes with multiple pattern delimiters is presented and discussed. These codes are complete, universal, synchronizable, they have monotonic indexing and allow a standard search in compressed files. Comparing the compression rate on natural language texts demonstrates that introduced codes appear to be much superior to other known codes with similar properties. A fast byte-aligned decoding algorithm is constructed, which operates much faster than the one for Fibonacci codes.