Approximate String Matching Using a Bidirectional Index

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01086206
Contributor : Admin Ligm <>
Submitted on : Sunday, November 23, 2014 - 9:39:45 AM
Last modification on : Wednesday, September 4, 2019 - 5:36:02 PM
Long-term archiving on : Tuesday, February 24, 2015 - 10:06:39 AM

File

Kucherov-Salikhov-Tsur-lncs-su...
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

189

Files downloads

389