On-line approximate string matching with bounded errors

Marcos Kiwi*, Gonzalo Navarro, Claudio Telha

*Autor correspondiente de este trabajo

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

2 Citas (Scopus)


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.
Idioma originalInglés
Título de la publicación alojadaCombinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
Número de páginas13
EstadoPublicada - 2008
Publicado de forma externa
Evento19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italia
Duración: 18 jun. 200820 jun. 2008

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen5029 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349


Conferencia19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008

Nota bibliográfica

© 2008 Springer-Verlag Berlin Heidelberg.

Palabras clave

  • Control theory
  • Military data processing
  • Pattern matching


Profundice en los temas de investigación de 'On-line approximate string matching with bounded errors'. En conjunto forman una huella única.

Citar esto