Approximate String Matching Using a Bidirectional Index

Gregory Kucherov (1, 2) , Kamil Salikhov (2, 3) , Dekel Tsur (1)

1 Department of Computer Science [Beer-Sheva]
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 MSU - Lomonosov Moscow State University

We study strategies of approximate pattern matching that exploit bidirectional text indexes, extending and generalizing ideas of [5]. We introduce a formalism, called search schemes, to specify search strate-gies of this type, then develop a probabilistic measure for the efficiency of a search scheme, prove several combinatorial results on efficient search schemes, and finally, provide experimental computations supporting the superiority of our strategies.

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

Gregory Kucherov, Kamil Salikhov, Dekel Tsur. Approximate String Matching Using a Bidirectional Index. CPM 2014, Jun 2014, Moscow, Russia. pp.222-231, ⟨10.1007/978-3-319-07566-2_23⟩. ⟨hal-01086206⟩