On-line approximate string matching with bounded errors

Marcos Kiwi, Gonzalo Navarro, Claudio Telha*

*Autor correspondiente de este trabajo

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

1 Cita (Scopus)

Resumen

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(n log σ m/m) time with any ∈ = poly(k/m), where n is the text size, m the pattern length, k the number of differences for edit distance, and σ the alphabet size. Our experimental results show the practicality of this novel and promising research direction. Finally, we extend the proposed approach to the multiple approximate string matching setting, where the approximate occurrence of r patterns are simultaneously sought. Again, we can break the average-case optimal lower bound of the classical problem, achieving average case O(n logσ (rm)/m) time with any ∈ = poly(k/m).

Idioma originalInglés
Páginas (desde-hasta)6359-6370
Número de páginas12
PublicaciónTheoretical Computer Science
Volumen412
N.º45
DOI
EstadoPublicada - 21 oct. 2011
Publicado de forma externa

Huella

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

Citar esto