Show simple item record

Authordc.contributor.authorRusso, Luís M. S. 
Authordc.contributor.authorNavarro, Gonzalo es_CL
Authordc.contributor.authorOliveira, Arlindo L. es_CL
Authordc.contributor.authorMorales, Pedro es_CL
Admission datedc.date.accessioned2014-01-08T20:26:37Z
Available datedc.date.available2014-01-08T20:26:37Z
Publication datedc.date.issued2009
Cita de ítemdc.identifier.citationAlgorithms 2009, 2, 1105-1136en_US
Identifierdc.identifier.issn1999-4893
Identifierdc.identifier.otherdoi:10.3390/a2031105
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/126086
Abstractdc.description.abstractA compressed full-text self-index for a text T is a data structure requiring reduced space and able to search for patterns P in T. It can also reproduce any substring of T, thus actually replacing T. Despite the recent explosion of interest on compressed indexes, there has not been much progress on functionalities beyond the basic exact search. In this paper we focus on indexed approximate string matching (ASM), which is of great interest, say, in bioinformatics. We study ASM algorithms for Lempel-Ziv compressed indexes and for compressed suffix trees/arrays. Most compressed self-indexes belong to one of these classes. We start by adapting the classical method of partitioning into exact search to self-indexes, and optimize it over a representative of either class of self-index. Then, we show that a Lempel- Ziv index can be seen as an extension of the classical q-samples index. We give new insights on this type of index, which can be of independent interest, and then apply them to a Lempel- Ziv index. Finally, we improve hierarchical verification, a successful technique for sequential searching, so as to extend the matches of pattern pieces to the left or right. Most compressed suffix trees/arrays support the required bidirectionality, thus enabling the implementation of the improved technique. In turn, the improved verification largely reduces the accesses to the text, which are expensive in self-indexes. We show experimentally that our algorithms are competitive and provide useful space-time tradeoffs compared to classical indexes.en_US
Lenguagedc.language.isoenen_US
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile*
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
Keywordsdc.subjectcompressed indexen_US
Títulodc.titleApproximate String Matching with Compressed Indexesen_US
Document typedc.typeArtículo de revista


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile