Fully-Online Grammar Compression
Fully-Online Grammar Compression
复制标题
DOI：
10.1007/978-3-319-02432-5_25
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Shirou Maruyama;Yasuo Tabei;H. Sakamoto;K. Sadakane
中科院分区：
文献类型：
--
作者：
Shirou Maruyama;Yasuo Tabei;H. Sakamoto;K. Sadakane
提出了一种构造直线规划（slp）的全在线算法。一个包含变量的SLP的简单数组表示，其大小为σ。如[Tabei et al., CPM ' 13]所示，在离线设置下，该大小可以约为，其渐近等于信息论的下界。我们的算法在在线设置中实现了相同的大小，即输入字符串的字符逐个给定以更新当前的SLP。使用sizebits的辅助位置数组，我们的表示支持子字符串提取inO（(m+h)t）时间，其中eni是输入字符串的长度，miss是提取的子字符串的长度，是SLP的高度，t=O(1)在脱机情况下，在在线情况下。工作空间是由一个常数α∈(0,1)所限定的，这个常数是哈希表的一个负载因子。我们将我们的算法与LZend在使用真实世界重复文本的实验中进行了比较。
We present a fully-online algorithm for constructing straight-line programs (SLPs). A naive array representation of an SLP withnvariables on an alphabet of sizeσrequiresbits. As already shown in [Tabei et al., CPM’13], in offline setting, this size can be reduced to, which is asymptotically equal to the information-theoretic lower bound. Our algorithm achieves the same size in online setting, i.e., characters of an input string are given one by one to update the current SLP. With an auxiliary position array of sizebits, our representation supports substring extractions inO((m+h)t) time whereNis the length of the input string,mis the length of a substring extracted,is the height of the SLP,t=O(1) in offline case, andin online case. The working space is bounded bybits depending on a constantα∈ (0,1], which is a load factor of hash tables. We compared our algorithm to LZend in experiments using real world repetitive texts.