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.