The Prague Stringology Club Workshop '97

Jan Holub

Simulation of NFA in Approximate String and Sequence Matching

We present detailed description of simulation of nondeterministic finite automata (NFA) for approximate string matching. This simulation uses bit parallelism and used algorithm is called Shift-Or algorithm. Using knowledge of simulation of NFA by Shift-Or algorithm we design modification of Shift-Or algorithm for approximate string matching using generalized Levenshtein distance and modification for exact and approximate sequence matching.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF