Initialization of an array, out of which only a small initially unknown portion will eventually be used, is a frequent need in programming. A folklore solution for initializing an array of n entries in constant time uses 2n⌈log2n⌉ extra bits to realize a stack of back pointers to the actually used entries of the array. Navarro has given a succinct version of this technique, which requires only n + o(n) bits of auxiliary storage. We describe, analyze, and experimentally compare these solutions and their space-efficient but theoretically suboptimal alternatives based on a simple bitmap for keeping track of the array entries which have been assigned a value. Experimental results suggest that each of the methods has its niche of excellence, which are roughly as follows: the theoretically optimal solutions based on a stack of back pointers perform in general best on sparse arrays, whose access frequency is less than 1% of the number of their entries. Brute-force initialization of the entire array seems generally to give the best overall performance for dense arrays whose access frequency is over 10% of their size. For the remaining cases of arrays with 1–10% access frequency, the methods which use a simple bitmap appear to give the best performance. The experiments show that the choice of a suitable implementation may yield substantial, up to hundreds of times speed-ups in the performance of initializable array operations. Copyright © 2015 John Wiley & Sons Ltd.

Given a sequence S of n symbols over some alphabet Σ of size σ, we develop new compression methods that are (i) very simple to implement; (ii) provide O(1) time random access to any symbol (or short substring) of the original sequence. Our simplest solution uses at most 2h+o(h) bits of space, where h = n(H $_{0}$ (S)+1), and H $_{0}$ (S) is the zeroth-order empirical entropy of S. We discuss a number of improvements and trade-offs over the basic method. For example, we can achieve n(H $_{k}$ (S)+1)+o(n(H $_{k}$ (S)+1)) bits of space, for k = o(log $_{σ}$ (n)). Several applications are discussed, including text compression, (compressed) full-text indexing and string matching.

We consider the template matching problem, in which one wants to find all good enough occurrences of a pattern template P from a larger image I. The current standard of template matching is based on cross correlation computed in Fourier domain, using the fast Fourier transform (FFT). This can be extended to rotations of the template by a suitable rotational sampling of the template. An alternative approach, pursued here, is to solve the problem in the spatial domain using so-called filtering algorithms. Such algorithms scan the image quickly and find all promising areas for a more accurate (but slower) examination such that no good enough occurrences of the template are lost. The paper shows that the filtering approach can be orders of magnitude faster than the FFT based method. Especially in the 3D case the FFT is intolerably slow.

Fast rotation invariant filtering algorithms are presented for speeding-up the search for the position of a given pattern template from a large image. The algorithms work for several distance/similarity measures. The algorithms give useful correlation information as such, and can be used as filtering algorithms for more sophisticated methods. The results are presented in the 2D case, but extensions to 3D are straightforward. The algorithms are based on color histograms computed from the pattern. A technique is described for pruning the filtered positions incrementally, using a simple, yet effective boundary that divides the search space in two.

We consider the problem of defining and evaluating the distance between a three-dimensional pattern P[1..m, 1..m, 1..m] of voxels and a three-dimensional volume V[1..n, 1..n, 1..n] of voxels when rotations of P are also allowed. In particular we are interested in finding the orientation and location of P with respect of V that gives the minimum distance. We consider several distance measures. Our basic method works for all distance measures such that the voxels affect the distance between P and V only locally, that is, the distance between two voxels can be completed in unit time. The number of different orientations that P can have is analyzed. We give incremental algorithms to compute the distance, and several filtering algorithms to compute the upper and lower bounds for the distance. We conclude with experimental results on real data (three dimensional reconstruction of a biological virus).