Approximate string matching using a bidirectional index

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

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Mathematical Logic and Theory of Algorithms
3 BGU - Ben-Gurion University of the Negev

We study strategies of approximate pattern matching that exploit bidirectional text indexes, extending and generalizing ideas of [9]. We introduce a formalism, called search schemes, to specify search strategies 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.

Mots clés: approximate pattern matching

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

Gregory Kucherov, Kamil Salikhov, Dekel Tsur. Approximate string matching using a bidirectional index. Theoretical Computer Science, 2016, 638, pp.145-158. ⟨10.1016/j.tcs.2015.10.043⟩. ⟨hal-01802942⟩