A faster implementation of online RLBWT and its application to LZ77 parsing
A faster implementation of online RLBWT and its application to LZ77 parsing
复制标题
在线RLBWT的更快实现及其在LZ77解析中的应用
DOI：
10.1016/j.jda.2018.11.002
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sakamoto Hiroshi
中科院分区：
文献类型：
--
作者：
Ohno Tatsuya;Sakai Kensuke;Takabatake Yoshimasa;I Tomohiro;Sakamoto Hiroshi
摘要行程编码的Burrows-Wheeler转换字符串，产生行程BWT（RLBWT），是处理高度重复字符串的强大工具。本文提出了一种新的运行压缩空间下的在线RLBWT算法，该算法的时间复杂度为O（nlg <$r），空间复杂度为O（rlg <$n），其中n为输入字符串S的长度，r为反向字符串S在BWT中的运行次数.我们改进了最先进的在线RLBWT算法的经验建设时间。采用动态链表来维护全序，通过动态链表中标签的直接比较，可以代替动态小波树中对游程压缩串的秩查询。利用所提出的在线RLBWT，我们可以在游程压缩空间中有效地计算LZ 77分解。实验结果表明，我们的在线RLBWT和LZ 77解析的效率，特别是对高度重复的字符串。
Abstract Run-length encoded Burrows–Wheeler Transformed strings, resulting in Run-Length BWT (RLBWT), is a powerful tool for processing highly repetitive strings. We propose a new algorithm for online RLBWT working in run-compressed space, which runs in O (n lg r) time and O (r lg n) bits of space, where n is the length of input string S received so far and r is the number of runs in the BWT of the reversed S. We improve the state-of-the-art algorithm for online RLBWT in terms of empirical construction time. Adopting the dynamic list for maintaining a total order, we can replace rank queries in a dynamic wavelet tree on a run-length compressed string by the direct comparison of labels in a dynamic list. Enlisting the proposed online RLBWT, we can efficiently compute the LZ77 factorization in run-compressed space. The empirical results show the efficiencies of both our online RLBWT and LZ77 parsing, especially for highly repetitive strings.
登录
查看更多内容
影响因子：
1.1
作者：
Philip Bille;Patrick Hagge Cording;Inge Li Gørtz;Frederik Rye Skjoldjensen;Hjalte Wedel Vildhøj;Søren Vind
通讯作者：
Søren Vind
字符串处理的动态数据结构框架
DOI：
--
发表时间：
2017
期刊：
The Sea
影响因子：
--
作者：
N. Prezza
通讯作者：
N. Prezza
基因组规模的算法设计：高通量测序时代的生物序列分析
DOI：
10.1017/cbo9781139940023
发表时间：
2015
期刊：
International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE
影响因子：
--
作者：
V. Mäkinen;Djamal Belazzougui;F. Cunial;Alexandru I. Tomescu
通讯作者：
Alexandru I. Tomescu
影响因子：
1.3
作者：
Navarro, Gonzalo;Sadakane, Kunihiko
通讯作者：
Sadakane, Kunihiko
在线游程Burrows-Wheeler变换的更快实现
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Tatsuya Ohno;Yoshimasa Takabatake;Tomohiro I;Hiroshi Sakamoto
通讯作者：
Hiroshi Sakamoto