文章基本信息

标题：Document Listing on Repetitive Collections with Guaranteed Performance
本地全文：下载
作者：Gonzalo Navarro
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：78
页码：4:1-4:13
DOI：10.4230/LIPIcs.CPM.2017.4
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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,a] 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 O~(n + s), precisely O((n lg a + s lg^2 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(m^2 + m lg N (lg D + lg^e N) ndoc), for any constant e > 0.
关键词：repetitive string collections; document listing; grammar compression; range minimum queries; succinct data structures