## 4 An Improved \(q\)-samples Index
### Partial \(q\)-sample Matching  
Contrary to all previous work, let us assume that \(A\) in Lemma 2 is not only that part of an approximate occurrence \(O\) formed by full \(q\)-samples, but instead that \(A=O\), so that \(A_{1}\) is the suffix of a sample and \(A_{j}\) is the prefix of a sample. An advantage of this is that now the number of involved \(q\)-samples is at least \(j=\lceil(m-k)/q\rceil\), and therefore we can permit fewer errors per piece (_e.g.,_\(\lfloor k/j\rfloor\) using Lemma 1). On the other hand, we would like to allow fewer errors for the pieces \(A_{1}\) and \(A_{j}\). Yet, notice that any text \(q\)-sample can participate as \(A_{1}\), \(A_{j}\), or as a fully contained \(q\)-sample in different occurrences at different text positions. Lemma 2 tells us that we could allow \(k_{i}=(1+\epsilon)\cdot k\cdot|A_{i}|/|A|\) errors for \(A_{i}\), for any \(\epsilon>0\). Conservatively, this is \(k_{i}=(1+\epsilon)\cdot k\cdot q/(m-k)\) for \(1<i<j\), and less for the extremes.  
In order to adapt the trie searching technique to those partial \(q\)-samples, we should not only search all the text \(q\)-samples with \((1+\epsilon)\cdot k\cdot q/(m-k)\), but also all their prefixes and suffixes with fewer errors. This includes, for example, verifying all the \(q\)-samples whose first or last character appears in \(P\) (cases \(|A_{1}|=1\) and \(|A_{j}|=1\)). This is unaffordable. Our approach will be to redistribute the errors across \(A\) using Lemma 2 in a different way to ensure that only sufficiently long \(q\)-sample prefixes and suffixes are considered.  
Let \(v\) be a non-negative integer parameter. We associate to every letter of \(A\) a _weight_: the first and last \(v\) letters have weight \(0\) and the remaining letters have weight \((1+\epsilon)/(|A|-2v)\). We define \(|A_{i}|_{v}\) as the sum of the weights of the letters of \(A_{i}\). For example if \(A_{i}\) is within the first \(v\) letters of \(A\) then \(|A_{i}|_{v}=0\); if it does not contain any of the first or last \(v\) letters then \(|A_{i}|_{v}=(1+\epsilon)\cdot|A_{i}|/(|A|-2v)\). Notice that for this definition to be sound we need that \(|A|-2v>0\), _i.e._\(v<|A|/2\).  
We can now apply Lemma 2 with \(k_{i}=k\cdot|A_{i}|_{v}\) provided that \(k>0\). Note that \(\sum_{i=1}^{j}k_{i}=(1+\epsilon)\cdot k>k\). In this case, if \(|A_{1}|\leq v\) we have that \(k_{1}=0\) and therefore \(A_{1}\) can never be found with _strictly less_ than zero errors. The same holds for \(A_{j}\). This effectively relieves us from searching for any \(q\)-sample prefix or suffix of length at most \(v\).  
Parameter \(v\) is thus doing the job of discarding \(q\)-samples that have very little overlap with the occur rence \(O=A\), and maintaining the rest. It balances between two exponential costs: one due to verifying all the occurrences of too short prefixes/suffixes, and another due to permitting too many errors when searching for the pieces in the trie. In practice tuning this parameter will have a very significant impact on performance.  
Recall the application of Lemma 2 with \(k=9\), \(A=A_{1}.A_{2}.A_{3}\), \(A_{1}=ab\), \(A_{2}=cdefghijklm\), \(A_{3}=no\), \(k_{1}=k_{3}=1.2\), \(k_{2}=6.7\) and \(B=axbcxdxexfgxhixjkxkmnxo\). In this case we would need to search for all the \(q\)-samples that end in a string that is at edit distance \(1\) from \(A_{1}=ab\). This, in particular, includes all the \(q\)-samples that contain the suffix \(a\), all the \(q\)-samples that contain the suffix \(b\) and so on. This yields an excessive number of samples to verify. If we consider \(v=1\) in this example we will instead obtain \(k_{1}=k_{3}=(1+\epsilon)\cdot 9\times 1/13\approx 0.7\) and \(k_{2}=(1+\epsilon)\cdot 9\times 11/13\approx 7.7\). Note that \(k_{1}+k_{2}+k_{3}=9.1>9\). In our example we have that \(ed(A_{2},cdxexfgxhixjkxlm)=7<7.7\). Note that, in this example, we moved the errors to \(A_{2}\) since \(A_{1}\) and \(A_{3}\) are very small.