Back to Search
Start Over
Approximate String Matching using a Bidirectional Index
- Source :
- LNCS, CPM 2014, CPM 2014, Jun 2014, Moscow, Russia. pp.222-231, ⟨10.1007/978-3-319-07566-2_23⟩, Theoretical Computer Science, Theoretical Computer Science, Elsevier, 2016, 638, pp.145-158. ⟨10.1016/j.tcs.2015.10.043⟩, Combinatorial Pattern Matching ISBN: 9783319075655, CPM
- Publication Year :
- 2013
-
Abstract
- International audience; 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.
- Subjects :
- FOS: Computer and information sciences
0301 basic medicine
Theoretical computer science
General Computer Science
Exploit
Computation
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
03 medical and health sciences
approximate pattern matching
Computer Science - Data Structures and Algorithms
0202 electrical engineering, electronic engineering, information engineering
Data Structures and Algorithms (cs.DS)
Pattern matching
030304 developmental biology
Mathematics
0303 health sciences
Probabilistic logic
Approximate string matching
Dynamic programming
Formalism (philosophy of mathematics)
030104 developmental biology
010201 computation theory & mathematics
020201 artificial intelligence & image processing
Algorithm
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-319-07565-5
- ISSN :
- 18792294 and 03043975
- ISBNs :
- 9783319075655
- Database :
- OpenAIRE
- Journal :
- LNCS, CPM 2014, CPM 2014, Jun 2014, Moscow, Russia. pp.222-231, ⟨10.1007/978-3-319-07566-2_23⟩, Theoretical Computer Science, Theoretical Computer Science, Elsevier, 2016, 638, pp.145-158. ⟨10.1016/j.tcs.2015.10.043⟩, Combinatorial Pattern Matching ISBN: 9783319075655, CPM
- Accession number :
- edsair.doi.dedup.....0f7a391a0eaabe354f603f14fcda4e77
- Full Text :
- https://doi.org/10.1007/978-3-319-07566-2_23⟩