Approximate String Matching Using a Bidirectional Index
From MaRDI portal
Abstract: We study strategies of approximate pattern matching that exploit bidirectional text indexes, extending and generalizing ideas of Lam et al. 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.
Recommendations
- Approximate string matching using a bidirectional index
- scientific article; zbMATH DE number 2011852
- Fast index for approximate string matching
- scientific article; zbMATH DE number 2185640
- scientific article; zbMATH DE number 2086228
- A metric index for approximate string matching
- Approximate string matching with compressed indexes
- scientific article; zbMATH DE number 3845091
- Cache-oblivious index for approximate string matching
- Cache-Oblivious Index for Approximate String Matching
Cited in
(10)- String indexing for top-\(k\) close consecutive occurrences
- Approximate search of short patterns with high error rates using the 01^ 0 lossless seeds
- Multi-pattern matching with bidirectional indexes
- Approximate string matching using a bidirectional index
- Approximate word sequence matching on an inverted file index
- Cache-Oblivious Index for Approximate String Matching
- Multi-pattern matching with bidirectional indexes
- Reversing the Error-Correction Scheme for a Fault-Tolerant Indexing
- b-move: faster bidirectional character extensions in a run-length compressed index
- Automated design of efficient search schemes for lossless approximate pattern matching
This page was built for publication: Approximate String Matching Using a Bidirectional Index
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5165608)
