Substring Complexities on Run-length Compressed Strings
Substring Complexities on Run-length Compressed Strings
复制标题
运行长度压缩字符串的子字符串复杂性
DOI：
10.1007/978-3-031-20643-6_10
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Akiyoshi Kawamoto,Tomohiro I
中科院分区：
文献类型：
--
作者：
Jion Hirose;Junya Nakamura;Fukuhito Ooshita;and Michiko Inoue;Akiyoshi Kawamoto,Tomohiro I
设T是一个长度相同的不同子串的集合，则它的基数称为T的第k个子串复杂度。最近，已被证明是高度重复字符串的良好可压缩性度量。在本文中，我们给出了在游程长度压缩形式的大小中的长度T，证明了它可以在时间和空间上计算，即在具有字长的Word-RAM模型中，在空间上对每个比特的整数进行排序的时间复杂度。
Letdenote the set of distinct substrings of lengthkin a stringT, then its cardinalityis called thek-th substring complexity ofT. Recently,has been shown to be a good compressibility measure of highly-repetitive strings. In this paper, givenTof lengthnin the run-length compressed form of size, we show thatcan be computed intime andspace, whereis the time complexity for sortingintegers withbits each inspace in the Word-RAM model with word size.