Static and Dynamic Filtering Methods for Approximate String Matching

this paper improves on this by merging the filtering and the checking phase. It evaluates the statically derived filter information during the checking phase, strengthening it by information determined dynamically. Rather than using static information once to decide whether a (complete) region must be checked, it is consulted intermittently, in order to immediately abandon a region as soon it becomes clear that, due to a poor start, an approximate match is no longer possible. To understand how this works, recall that dynamic programming gives us information about actual differences of the subwords of T and P under consideration. As opposed to this, the statically derived information tells us where guaranteed differences occur. Of course, the actual differences occur before or at the guaranteed differences. Now suppose we have a subword s passing the static filter, and we know that, after reading a prefix v 1 of s, d actual differences have occurred. Now, if the remaining suffix v 2 of s contains more than k \Gamma