Explaining and Extending the Bit-parallel Algorithm of Myers

Abstract: "The O([mn]/w), where m is pattern length, n is text length w is the the [sic] computer word size, bit-parallel algorithm of Myers [6] is one of the best current algorithms in the case of approximate string matching allowing insertions, deletions and substitutions. We begin this paper by deriving a practically equivalent version of the algorithm of Myers. This is done in a way, which we believe makes the logic behind the algorithm easier to understand than the original presentation. Then we show how to extend the algorithm to allow also a fourth kind of error, which is transposition of two adjacent characters. This is a very common type of error for example in typed text [5], but has typically been omitted from approximate string matching algorithms. Finally we present experimental results to show, what kind of effect adding transposition has on the performance of the algorithm."