Gapped Suffix Arrays: a New Index Structure for Fast Approximate Matching

Maxime Crochemore (1, 2) , German Tischler (1)

1 Informatics
2 LIGM - Laboratoire d'Informatique Gaspard-Monge

Approximate searching using an index is an important application in many fields. In this paper we introduce a new data structure called the gapped suffix array for approximate searching in the Hamming distance model. Building on the well known filtration approach for approximate searching, the use of the gapped suffix array can improve search speed by avoiding the merging of position lists.

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore, German Tischler. Gapped Suffix Arrays: a New Index Structure for Fast Approximate Matching. SPIRE, 2010, Los Cabos, Mexico. pp.359-364, ⟨10.1007/978-3-642-16321-0_37⟩. ⟨hal-00742048⟩