Treffer: Row-wise tiling for the Myers' bit-parallel approximate string matching algorithm

Given a text T[1..n] and a pattern P[1..m] the classic dynamic programming algorithm for computing the edit distance between P and every location of T runs in time O(nm). The bit-parallel computation of the dynamic programming matrix [6] runs in time O(n [m/ω]), where w is the number of bits in computer word. We present a new method that rearranges the bit-parallel computations, achieving time O([n/ω] (m + σ log2(σ)) + n), where a is the size of the alphabet. The algorithm is then modified to solve the k differences problem. The expected running time is O([n/ω] (L(k) + σlog2(σ)) + R), where L(k) depends on k, and R is the number of occurrences. The space usage is O(a + m). It is in practice much faster than the existing O(n [k/ω]) algorithm [6]. The new method is applicable only for small (e.g. DNA) alphabets, but this becomes the fastest algorithm for small m, or moderate k/m. If we want to search multiple patterns in a row, the method becomes attractive for large alphabet sizes too. We also consider applying 128-bit vector instructions for bit-parallel computations.