## 4 Test Data Generator  
Our data structures aim to fit data with low empirical entropy of higher order even if the empirical entropies of lower order are quite high. We created such data by a specific generator that we are going to describe next, which might be of independent interest. It produces bit vectors with lower order empirical entropies very close to 1 (\(H_{0}\approx H_{1}\approx\ldots\approx H_{k-1}\approx 1\)) and higher order empirical entropies significantly lower (\(1\gg H_{k}\geq H_{k+1}\geq\ldots\)).  
The test data generator rolls each bit with a probability \(P(\texttt{1}|s^{\prime})\) for a 1 dependent on \(s^{\prime}\), where \(s^{\prime}\) are the \(k\) preceding bits. We get these probabilities from a table. The first half of this table, containing probabilities for bit patterns starting with a 0, is filled with values close to \(1\) or close to \(0\) at random. By Lemma 1 and since our test data generator mimics the empirical predictability, this ensures a low \(H_{k}\). The second half is filled with exactly the opposite probabilities namely \(P(\texttt{1}|\texttt{0}s)=1-P(\texttt{1}|\texttt{1}s)\)  
Figure 2: Expected memory usage for the lookup table for a text with \(P_{k}=0.99\) and block size \(b=64\).  
for all bit patterns \(s\) of length \(k-1\). This ensures lower order empirical entropies to be \(1\), as shown in Lemma 2 below.  
From a different point of view this test data generator is a probabilistic finite state machine with one state for each bit pattern of length \(k\) and two state transitions out of each state, one with high probability and one with low probability. Due to filling the second half of the table opposite to the first, the two incoming state transitions of each state behave like the outgoing ones: One of them has a high probability and the other has a low probability. Thus we get circles of high probability edges and a low probability to switch the circle or jump within a circle. Figure 3 shows such a finite state machine, the according probability table, and an example output bit string.  
**Lemma 2**.: _An infinite text generated that way has \(H_{0}=\ldots=H_{k-1}=1\)._  
Proof.: We have to show that the finite state machine enters each state with the same probability in the long term, thus we have to show that the uniform distribution vector \(\mathcal{E}=(1,\ldots,1)\) is an eigenvector of the state transition matrix \(\mathcal{M}\) of the Markov process. For each \(s\in\{0,1\}^{k-1}\) we have:  
Figure 3: Example of a test data generation. (**a**) The associated finite state machine, low probability edges are shown gray. (**b**) Table of probabilities to roll a 1. (**c**) Output, low probability rolls are underlined.  
**suxVignaRank9** [PERSON]'s rank9-implementation [6].  
Figure 4 shows the compression and query times for example texts with \(n=250\)MB and \(H_{4}=0.044\) or \(H_{4}=0.112\), respectively (averaged over 10 repeats of \(10^{7}\) random queries). Other distributions of entropies yielded similar results. We can see that our data structures are significantly smaller than the others. At the extreme end, our smallest structure (canRnkBeg) uses less that 1/4 of the space used by the smallest existing structure (sdslv5). However, we trade this advantage for higher query times, in the example mentioned by a factor of 2.