## 4 An Improved \(q\)-samples Index
### Varying the Error Distribution  
We will need to consider parts of samples in the sequel, as well as samples of different lengths. Lemma 1 gives the same number of errors to all the samples, which is disadvantageous when pieces are of different lengths. The next Lemma generalizes Lemma 1 to allow different numbers of errors in each piece. **Lemma 2**: _Let A and B be strings, let \(A=A_{1}.A_{2}\ldots A_{j}\), for strings \(A_{i}\) and some \(j\geq 1\). Let \(k_{i}\in\mathbb{R}\) such that \(\sum_{i=1}^{j}k_{i}>ed(A,B)\). Then there is a substring \(B^{\prime}\) of \(B\) and an \(i\) such that \(ed(A_{i},B^{\prime})<k_{i}\)._  
The edit distance between \(A\) and \(B\) corresponds to the shortest path in the edit graph of \(A\) and \(B\). The partition of \(A\) induces a partition in this graph and in particular splits the shortest path. Let \(B_{i}\) be the substring of \(B\) that shares the shortest path with \(A_{i}\). This means that \(\sum_{i=1}^{j}ed(A_{i},B_{i})=ed(A,B)\). Suppose, by absurd, that for every \(B^{\prime}\) substring of \(B\) and every \(i\) we have that \(ed(A_{i},B^{\prime})\geq k_{i}\). Therefore, this is also true for the \(B_{i}\)'s, _i.e._\(ed(A_{i},B_{i})\geq k_{i}\). This is absurd since that way \(ed(A,B)=\sum_{i=1}^{j}ed(A_{i},B_{i})\geq\sum_{i=1}^{j}k_{i}>ed(A,B)\). Therefore, there must exist an \(i\) such that \(ed(A_{i},B_{i})<k_{i}\). Note that \(B_{i}\) is the substring \(B^{\prime}\) we mention in the lemma. Figure 4 shows an illustration of this Lemma. Lemma 1 is a particular case of Lemma 2: set \(k_{i}=k/j+\epsilon\) for sufficiently small \(\epsilon>0\). Consider the application of Lemma 1 to \(k=9\), \(A=A_{1}.A_{2}.A_{3}\), \(A_{1}=ab\), \(A_{2}=cdefghijklm\), \(A_{3}=no\) and \(B=axbcxdexfgxhixjkxlxmnxo\) (see Figure 5). We can conclude that there is a substring \(B^{\prime}\) of \(B\) and an \(i\) such that \(ed(B^{\prime},A_{i})\leq\lfloor 9/3\rfloor=3\). In particular, we have that \(ed(A_{1},axb)=1\) and \(ed(A_{3},nxo)=2\). This number of errors (3) is excessively high for strings a as small as \(A_{1}\) and \(A_{3}\). Instead, we can use Lemma 2 with \(k_{1}=k_{3}=1.2\) and \(k_{2}=6.7\); note that \(k_{1}+k_{2}+k_{3}=9.1>9\). Using this lemma, we only allow for \(1\) error for \(A_{1}\) and \(A_{3}\). In this case we have that \(ed(A_{1},axb)=1<1.2\). We also have that \(ed(A_{3},nxo)=1<1.2\). Figure 4: A schematic edit distance graph between \(A\) and \(B\). The dashed lines show the division of \(A\) and \(B\) into the \(A_{i}\)’s and delimit \(B^{\prime}\). The shortest path in the graph is enclosed between two parallel lines. An early version of Lemma 2 was given in the context of hierarchical verification [39]. This result was later improved [4] as follows. **Lemma 3**: _Let A and B be strings, let \(A=A_{1}.A_{2}\ldots A_{j}\), for strings \(A_{i}\) and some \(j\geq 1\). Let \(k_{i}\in\mathbb{N}_{0}\) such that \(j\geq 1\) and \(\sum_{i=1}^{j}k_{i}\geq ed(A,B)-j+1\). Then there is a substring \(B^{\prime}\) of \(B\) and an \(i\) such that \(ed(A_{i},B^{\prime})\leq k_{i}\)._  
Proof. : We will prove this lemma using Lemma 2. Let \(k_{i}\) be the numbers referred in this lemma. Consider \(k^{\prime}_{i}=k_{i}+1\). The \(k^{\prime}_{i}\) numbers satisfy the conditions of Lemma 2, _i.e._\(\sum_{i=1}^{j}k^{\prime}_{i}=j+\sum_{i=1}^{j}k_{i}\geq j-j+1+k=k+1>k\). Therefore, by Lemma 2, we can conclude that there is a substring  
Figure 5: Dynamic programming table \(D\) for strings, \(B=P=axbcxdexxfgxhizjkxlxmnxo\) (vertical) and \(A=O=abcdefghijklmno\) (horizontal) with \(k=9\). The shortest path in the edit graph is shown in bold, we do not show inactive cells. of \(B\) and an \(i\) such that \(ed(A_{i},B^{\prime})<k_{i}^{\prime}=k_{i}+1\). Since \(ed(A_{i},B^{\prime})\) and \(k_{i}\) are integers we have that \(ed(A_{i},B^{\prime})\leq k_{i}\). The proof shows that Lemma 3 is a consequence of Lemma 2. In fact, both are equivalent. To prove that Lemma 3 implies Lemma 2 use the transformation \(k_{i}^{\prime}=\lceil k_{i}\rceil-1\) and reason as above.