Artículo de revista
Document listing on repetitive collections with guaranteed performance
Fecha
2017Registro en:
Leibniz International Proceedings in Informatics, LIPIcs, Volumen 78,
18688969
10.4230/LIPIcs.CPM.2017.4
Autor
Navarro, Gonzalo
Institución
Resumen
We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [1, σ] is composed of D copies of a string of size n, and s single-character edits are applied on the copies. We introduce the first document listing index with size Õ(n+s), precisely O((n lg σ+s lg2 N) lg D) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the ndoc strings where it appears in time O(m2 + m lg N(lgD + lgϵ N).