Abstract
We introduce a new dimension to the widely studied on-line approximate string matching problem, by introducing an error threshold parameter ε so that the algorithm is allowed to miss occurrences with probability ε. This is particularly appropriate for this problem, as approximate searching is used to model many cases where exact answers are not mandatory. We show that the relaxed version of the problem allows us breaking the average-case optimal lower bound of the classical problem, achieving average case O(nlog σ m/m) time with any , where n is the text size, m the pattern length, k the number of errors for edit distance, and σ the alphabet size. Our experimental results show the practicality of this novel and promising research direction.
| Original language | English |
|---|---|
| Title of host publication | Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings |
| Pages | 130-142 |
| Number of pages | 13 |
| DOIs | |
| State | Published - 2008 |
| Externally published | Yes |
| Event | 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy Duration: 18 Jun 2008 → 20 Jun 2008 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 5029 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 |
|---|---|
| Country/Territory | Italy |
| City | Pisa |
| Period | 18/06/08 → 20/06/08 |
Bibliographical note
Funding Information:The first author gratefully acknowledges the support of CONICYT via FONDAP-Basal in Applied Mathematics, Anillo en Redes ACT08, and FONDECYT 1090227. The second author was funded in part by Fondecyt Grant 1-080019, Chile. The third author gratefully acknowledges the support of CONICYT via Anillo en Redes ACT08.