Indexing Methods for Approximate String Matching
Gonzalo Navarro, Ricardo Baeza-Yates, Erkki Sutinen and Jorma Tarhio
Indexing for approximate text searching is a novel problem receiving much
attention because of its applications in signal processing, computational
biology and text retrieval, to name a few. We classify most indexing methods
in a taxonomy that helps understand their essential features. We show that the
existing methods, rather than completely different as they are regarded, form
a range of solutions whose optimum is usually somewhere in between.