The Prague Stringology Club Workshop '97

Jan Holub

Simulation of NFA in Approximate String and Sequence Matching

Abstract:
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 article: Article in PostScript Article in PDF
 PostScript   PDF