Redundancy is defined as the excess of the code length over the optimal (ideal) code length. We study the average redundancy of an idealized arithmetic coding (for memory less sources with unknown distributions) in which the Krichevsky and Trofimov estimator is followed by the Shannon-Fano code. We shall ignore here important practical implementation issues such as finite precisions and finite buffer sizes. In fact, our idealized arithmetic code can be viewed as an adaptive infinite precision implementation of arithmetic encoder that resembles Elias coding. However, we provide very precise results for the average redundancy that takes into account integer-length constraints. These findings are obtained by analytic methods of analysis of algorithms such as theory of distribution of sequences modulo 1 and Fourier series. These estimates can be used to study the average redundancy of codes for tree sources, and ultimately the context-tree weighting algorithms.

In this paper, we propose and study a pre-processing technique for improving performance of digital tree (trie)-based search algorithms under asymmetric memory less sources. This technique (which we call a symmetrization of the source) bijectively maps the sequences of symbols from the original (asymmetric) source into symbols of an output alphabet resulting in a more uniform distribution. We introduce a criterion of efficiency for such a mapping, and demonstrate that a problem of finding an optimal for a given source (or universal) symmetrization transform is equivalent to a problem of constructing a minimum redundancy variable-length-to-block code for this source (or class of sources). Based on this result, we propose search algorithms that incorporate known (optimal for a given source and universal) variable-length-to-block codes and study their asymptotic behavior. We complement our analysis with a description of an efficient algorithm for universal symmetrization of binary memory less sources, and compare the performance of the resulting search structure with the standard tries.

Information Warfare has emerged as a key joint warfighting mission area.  The explosive proliferation of of information-based technology significantly impacts warfighting across all phases, the range of military operations, and all levels of war.

Some modern computer systems are subject to \“infection\” of their programs by reproducing computer viruses.  While it has been shown that detecting such a virus in general is an undecidable problem, there may be large classes of viruses against which effective defenses can be made.  Before an examination of the defenses is possible, a more complete catalog of the capabilities of viruses is necessary in order to determine if such classes exist.