TY - GEN
T1 - On-line approximate string matching with bounded errors
AU - Kiwi, Marcos
AU - Navarro, Gonzalo
AU - Telha, Claudio
N1 - 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.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Control theory
KW - Military data processing
KW - Pattern matching
UR - http://www.scopus.com/inward/record.url?scp=45849125018&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-69068-9_14
DO - 10.1007/978-3-540-69068-9_14
M3 - Conference contribution
AN - SCOPUS:45849125018
SN - 3540690662
SN - 9783540690665
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 130
EP - 142
BT - Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
T2 - 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008
Y2 - 18 June 2008 through 20 June 2008
ER -