On-line approximate string matching with bounded errors

Marcos Kiwi*, Gonzalo Navarro, Claudio Telha

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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 languageEnglish
Title of host publicationCombinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
Pages130-142
Number of pages13
DOIs
StatePublished - 2008
Externally publishedYes
Event19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy
Duration: 18 Jun 200820 Jun 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5029 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008
Country/TerritoryItaly
CityPisa
Period18/06/0820/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.

Fingerprint

Dive into the research topics of 'On-line approximate string matching with bounded errors'. Together they form a unique fingerprint.

Cite this