Combined Search and Encoding for Seeds,
with an Application to Minimal Perfect Hashing

Let $k\mathrm{₁},\mathrm{\dots },kₙ\mathrm{\in }\mathrm{\mathbb{N}}$ be a sequence of numbers.⁴⁴4It may help to imagine that $k_i\mathrm{\approx }{2}^{\epsilon }/p_i$. Consider the infinite tree visualised in Figure 1. It has $n+2$ layers, indexed from $0$ to $n+1$. The root in layer $0$ has an infinite number of children and nodes in layer $1\mathrm{\le }i\mathrm{\le }n$ have $k_i$ children each, with $0$-based indexing in both cases. Edges between layer $i$ and $i+1$ are associated with the variables $B^{(i)}\mathrm{₀},B^{(i)}\mathrm{₁},B^{(i)}\mathrm{₂},\mathrm{\dots }$ from top to bottom where $B_j^{(i)}=0$ indicates a broken edge depicted as a dotted line. For convenience, we make another definition. For any $0\mathrm{\le }\mathrm{\ell }\mathrm{\le }n$ and any sequence $(\sigma \mathrm{₀},\sigma \mathrm{₁},\mathrm{\dots },{\sigma }_{\mathrm{\ell }})\mathrm{\in }\mathrm{\mathbb{N}}\mathrm{₀}\mathrm{\times }\{0,\mathrm{\dots },k\mathrm{₁}-1\}\mathrm{\times }\mathrm{\dots }\mathrm{\times }\{0,\mathrm{\dots },k_{\mathrm{\ell }}-1\}$ consider the node reached from the root by taking in layer $0\mathrm{\le }i\mathrm{\le }\mathrm{\ell }$ the edge to the ${\sigma }_i$-th child. We define $\sigma \mathrm{₀}\mathrm{\circ }\mathrm{\dots }\mathrm{\circ }{\sigma }_{\mathrm{\ell }}$ to be the index of the reached node within layer $\mathrm{\ell }$.

In Consensus, we search for a non-broken path from the root of the tree to a leaf node using a DFS, see Algorithm 1. Note that such a path exists with probability $1$ because the root has infinitely many children. The path is given by the sequence of choices $(\sigma \mathrm{₀},\mathrm{\dots },\sigma ₙ)\mathrm{\in }\mathrm{\mathbb{N}}\mathrm{₀}\mathrm{\times }\{0,\mathrm{\dots },k\mathrm{₁}-1\}\mathrm{\times }\mathrm{\dots }\mathrm{\times }\{0,\mathrm{\dots },kₙ-1\}$ made in each layer. The returned sequence can be encoded as a bitstring $M$. Then $S_i≔\sigma \mathrm{₀}\mathrm{\circ }\mathrm{\dots }\mathrm{\circ }{\sigma }_i$ is a successful seed for each $i\mathrm{\in }[n]$ by construction. The merits of the approach are summarised in the following theorem.

The main issues with the simplified Consensus algorithm are that $(\sigma \mathrm{₀},\mathrm{\dots },\sigma ₙ)$ is awkward to encode in binary and that using $\sigma \mathrm{₀}\mathrm{\circ }\mathrm{\dots }\mathrm{\circ }{\sigma }_i$ directly as the seed $S_i$ makes for seeds of size $\mathrm{\Omega }(n)$ bits, which are inefficient to compute and handle. We solve these issues with three interventions.

1. 1.

   We introduce a word size $w\mathrm{\in }\mathrm{\mathbb{N}}$ and encode $\sigma \mathrm{₀}$ using $w$ bits (hoping that it does not overflow, see below).

2. 2.

   We demand that $k\mathrm{₁},\mathrm{\dots },kₙ\mathrm{\in }\mathrm{\mathbb{N}}$ are powers of two, i.e. $k_i=2^{{\mathrm{\ell }}_i}$ for ${\mathrm{\ell }}_i\mathrm{\in }\mathrm{\mathbb{N}}\mathrm{₀}$. With our definition of “$\mathrm{\circ }$”, the binary representation of the number $\sigma \mathrm{₀}\mathrm{\circ }\mathrm{\dots }\mathrm{\circ }{\sigma }_i$ now simply arises by concatenating the binary representations of $\sigma \mathrm{₀},\mathrm{\dots },{\sigma }_i$ (where ${\sigma }_j$ is encoded using ${\mathrm{\ell }}_j$ bits and $\sigma \mathrm{₀}$ is encoded using $w$ bits).

3. 3.

   Instead of defining $S_i$ to be $\sigma \mathrm{₀}\mathrm{\circ }\mathrm{\dots }\mathrm{\circ }{\sigma }_i$, we define $S_i$ to be the $w$-bit suffix of $\sigma \mathrm{₀}\mathrm{\circ }\mathrm{\dots }\mathrm{\circ }{\sigma }_i$. We will show that this truncation is unlikely to cause collisions, i.e. any two sequences $(\sigma \mathrm{₀},\mathrm{\dots },{\sigma }_i)$ and $({\sigma }^{\prime }\mathrm{₀},\mathrm{\dots },{\sigma }_i^{\prime })$ we encounter have distinct suffixes $S_i\mathrm{\ne }{S}_i^{\prime }$. Intuitively, this guarantees that the search algorithm will always see “fresh” random variables and does not “notice” the change.

The full algorithm is given as Algorithm 2, using notation defined in Figure 2. Our formal result is as follows.

In particular the result guarantees that $S_i$ can be inferred efficiently given $M$ and $i$ provided that ${\sum }_{j=1}^i\log \mathrm{₂}(1/p_i)$ can be computed efficiently given $i$. In practice it is fine to use approximations of $p_i$.⁷⁷7Our implementation uses fixed point arithmetic (integers counting “microbits”) to avoid issues related to floating point arithmetic not being associative and distributive. Note that the expectation of $T_i$ is only bounded conditioned on a good event $E$, which is defined in Section 4. To obtain an unconditionally bounded expectation, Algorithm 2 should be modified to give up early in failure cases.⁸⁸8To do so we need not decide whether $E$ occurs. We can simply count the number of steps and abort when a limit is reached.

An important special case is $p\mathrm{₁}=\mathrm{\dots }=pₙ=p$. With $b=\log \mathrm{₂}1/p$ the space lower bound is then simply $M^{\mathrm{OPT}}=bn$ bits. If we apply Theorem 7 with $\epsilon \mathrm{\in }(0,1)$ then the lengths $\mathrm{\ell }\mathrm{₁},\mathrm{\dots },\mathrm{\ell }ₙ$ of the seed fragments $\sigma \mathrm{₁},\mathrm{\dots },\sigma ₙ$ are all either $\mathrm{\lceil }b+\epsilon \mathrm{\rceil }$ or $\mathrm{\lfloor }b+\epsilon \mathrm{\rfloor }$ with an average approaching $b+\epsilon$. Assuming $b\mathrm{\notin }\mathrm{\mathbb{N}}$ it may be tempting to use $\epsilon =\mathrm{\lceil }b\mathrm{\rceil }-b$ such that all seed fragments have the same length $b+\epsilon \mathrm{\in }\mathrm{\mathbb{N}}$. Similarly, we could pick $\epsilon$ such that $b+\epsilon$ is a “nice” rational number, e.g. $b+\epsilon =b^{\prime }+\frac{1}{2}$ for $b^{\prime }\mathrm{\in }\mathrm{\mathbb{N}}$ such that $\mathrm{\ell }\mathrm{₁},\mathrm{\dots },\mathrm{\ell }ₙ$ alternate between $b^{\prime }+1$ and $b^{\prime }$.

In some cases it may be reasonable to choose $\epsilon >1$. Even though Consensus ceases to be more space efficient than MIN, it still has the advantage that seeds are bitstrings of fixed lengths in predetermined locations. We decided against formally covering this case in Theorem 7, but argue for the following modification in the full version [24] of this paper.

It may also be worthwhile to consider variants of Consensus that use different values of the overhead parameter $\epsilon$ in different parts of $M$ to minimise some overall cost. Such an idea makes sense in general if we augment the SSEP to include specific costs $c_i$ associated with testing the Bernoulli random variables belonging to the $i$th family.

Consider the following natural coupling. Let $B_j^{(i)}$ for $i\mathrm{\in }[n]$ and $j\mathrm{\in }\mathrm{\mathbb{N}}\mathrm{₀}$ be the random variables underlying simplified Consensus and ${\tilde{B}}_S^{(i)}$ for $i\mathrm{\in }[n]$ and $S\mathrm{\in }{\{0,1\}}^w$ the random variables underlying full Consensus. The coupling should ensure that $B_{\mathrm{\Sigma }}^{(i)}={\tilde{B}}_{\mathrm{suffix}(\mathrm{\Sigma })}^{(i)}$ for all pairs $(i,\mathrm{\Sigma })$ such that simplified Consensus inspects $B_{\mathrm{\Sigma }}^{(i)}$ and does not at an earlier time inspect $B_{{\mathrm{\Sigma }}^{\prime }}^{(i)}$ with $\mathrm{suffix}({\mathrm{\Sigma }}^{\prime })=\mathrm{suffix}(\mathrm{\Sigma })$. In other words, for any pair $(i,S)$, if simplified consensus inspects at least one variable $B_{\mathrm{\Sigma }}^{(i)}$ with $\mathrm{suffix}(\mathrm{\Sigma })=S$ then ${\tilde{B}}_S^{(i)}$ equals the earliest such variable that is inspected.

This implies that the runs of simplified and full Consensus behave identically as long as, firstly, $\sigma \mathrm{₀}$ never reaches $2^w$ and, secondly, simplified Consensus never repeats a suffix, by which we mean inspecting $B_{\mathrm{\Sigma }}^{(i)}$ for some pair $(i,\mathrm{\Sigma })$ such that $B_{{\mathrm{\Sigma }}^{\prime }}^{(i)}$ with $\mathrm{suffix}(\mathrm{\Sigma })=\mathrm{suffix}({\mathrm{\Sigma }}^{\prime })$ was previously inspected. In the following, by a step of Consensus we mean one iteration of its main while-loop, which involves inspecting exactly one random variable.

Assume simplified Consensus is about to inspect $B_{{\mathrm{\Sigma }}^{\ast }}^{(i)}$. Call $S\mathrm{\in }{\{0,1\}}^w$ a blocked suffix if there exists $\mathrm{\Sigma }\mathrm{\in }{\{0,1\}}^{\ast }$ such that $S=\mathrm{suffix}(\mathrm{\Sigma })$ and $B_{\mathrm{\Sigma }}^{(i)}$ was previously inspected. This necessitates . Clearly, step $t$ repeats a suffix if $\mathrm{suffix}({\mathrm{\Sigma }}^{\ast })$ is blocked. A crucial observation is that the DFS has exhaustively explored all branches of the tree associated with any prefix less than ${\mathrm{\Sigma }}^{\ast }$ and the order in which this exploration has been carried out is no longer relevant. The symmetry between all nodes of the same layer therefore implies that every suffix is blocked with the same probability. Since at most $t$ suffixes can be blocked at step $t$, the probability that ${\mathrm{\Sigma }}^{\ast }$ is blocked (given our knowledge of $(i,{\mathrm{\Sigma }}^{\ast })$) is at most $\frac{t}{2^w}$. $\mathrm{⊲}$

First note that the choice of $(\mathrm{\ell }\mathrm{₁},\mathrm{\dots },\mathrm{\ell }ₙ)$ made in Theorem 7 amounts to a valid choice of $(k\mathrm{₁}=2^{\mathrm{\ell }\mathrm{₁}},\mathrm{\dots },kₙ=2^{\mathrm{\ell }ₙ})$ for applying Theorem 6. Indeed, for each $i\mathrm{\in }[n]$ there exists some ${\mathrm{err}}_i\mathrm{\in }[1,2)$ related to rounding up such that

as required. The number $T={\sum }_{i=1}^n{T}_i$ of steps taken by simplified Consensus satisfies $\mathrm{𝔼}[T]=\mathrm{𝒪}({\sum }_{i=1}^n\frac{1}{p_i\epsilon })=\mathrm{𝒪}(n^{1+2c})$. By Markov’s inequality $T$ exceeds its expectation by a factor of $n^c$ with probability at most $n^{-c}$ so with probability at least $1-\mathrm{𝒪}(n^{-c})$ simplified Consensus terminates within $T_{\mathrm{limit}}=n^{1+3c}$ steps.

By Claim 11 and a union bound the probability that simplified Consensus repeats a suffix within its first $T_{\mathrm{limit}}$ steps is at most ${\sum }_{t=1}^{T_{\mathrm{limit}}}t/2^w=\mathrm{𝒪}(T_{\mathrm{limit}}\mathrm{²}/2^w)=\mathrm{𝒪}(n^{2+6c}/2^w)$. By choosing $w\mathrm{\ge }(2+7c)\log \mathrm{₂}n$ this probability is $\mathrm{𝒪}(n^{-c})$. This choice also guarantees that $\sigma \mathrm{₀}$ never exceeds $2^w$ during the first $T_{\mathrm{limit}}$ steps. Let now $E=\{T\mathrm{\le }{T}_{\mathrm{limit}}\}\mathrm{\cap }\{\text{no repeated suffix in the first }{T}_{\mathrm{limit}}\text{ steps}\}$. By a union bound $\mathrm{Pr}[E]=1-\mathrm{𝒪}(n^{-c})$ and by our coupling $E$ implies that simplified and full Consensus explore the same sequence of nodes in their DFS and terminate with the same sequence $\sigma \mathrm{₀},\mathrm{\dots },\sigma ₙ$ with . In particular full Consensus succeeds in that case as claimed.

The updated bound on $|M|$ simply reflects that $\sigma \mathrm{₀}$, which in simplified Consensus had expected length $\log \mathrm{₂}1/\epsilon +\mathrm{𝒪}(1)$ now has fixed length $w=\mathrm{𝒪}(\log n)$. Lastly, if $T_i$ and ${\tilde{T}}_i$ denote the number of Bernoulli trials from the $i$-th family inspected by simplified and full Consensus, respectively, then conditioned on $E$ we have $T_i={\tilde{T}}_i$ so

$◀$