A Self-index on Block Trees
A Self-index on Block Trees
复制标题
块树上的自索引
DOI：
10.1007/978-3-319-67428-5_24
复制
发表时间：
2016
期刊：
影响因子：
1.1
通讯作者：
G. Navarro
中科院分区：
文献类型：
--
作者：
G. Navarro
块树是最近提出的数据结构，可在靠近Lempel-Ziv的压缩方面，同时支持有效直接访问文本子字符串。在本文中，我们展示了如何在块树的顶部建立自我指数，以便在使用与原始数据结构成比例的空间时提供有效的模式搜索。更确切地说，如果lempel-ziv解析将长度$ n $的文本剪切到$ z $非重叠短语中，则我们的索引使用$ o（z \ log（n/z））$单词并找到$ occ $ occ $时间$ o（M \ log n+occ \ log^\ epsilon n）$的长度$ m $ in Time $ m $的出现。
The Block Tree is a recently proposed data structure that reaches compression close to Lempel-Ziv while supporting efficient direct access to text substrings. In this paper we show how a self-index can be built on top of a Block Tree so that it provides efficient pattern searches while using space proportional to that of the original data structure. More precisely, if a Lempel-Ziv parse cuts a text of length $n$ into $z$ non-overlapping phrases, then our index uses $O(z\log(n/z))$ words and finds the $occ$ occurrences of a pattern of length $m$ in time $O(m\log n+occ\log^\epsilon n)$ for any constant $\epsilon>0$.
DOI：
--
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
R. Grossi;Ankur Gupta;J. Vitter
通讯作者：
R. Grossi;Ankur Gupta;J. Vitter
DOI：
10.1137/1.9781611972870.6
发表时间：
2006-09
期刊：
ArXiv
影响因子：
--
作者：
Daisuke Okanohara;K. Sadakane
通讯作者：
Daisuke Okanohara;K. Sadakane