Faster and Simpler Online/Sliding Rightmost Lempel-Ziv Factorizations

被引：0

作者：

Sumiyoshi, Wataru ^{[1
]}

Mieno, Takuya ^{[2
]}

Inenaga, Shunsuke ^{[3
]}

机构：

[1] Kyushu Univ, Dept Informat Sci & Technol, Fukuoka, Japan

[2] Univ Electrocommun, Dept Comp & Network Engn, Chofu, Tokyo, Japan

[3] Kyushu Univ, Dept Informat, Fukuoka, Japan

来源：

STRING PROCESSING AND INFORMATION RETRIEVAL, SPIRE 2024 | 2025年 / 14899卷

关键词：

suffix trees; Lempel-Ziv factorizations; closed factorizations; ONLINE; ALGORITHMS; COMPLEXITY;

D O I：

10.1007/978-3-031-72200-4_24

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We tackle the problems of computing the rightmost variant of the Lempel-Ziv factorizations in the online/sliding model. Previous best bounds for this problem are O(n log n) time with O(n) space, due to Amir et al. [IPL 2002] for the online model, and due to Larsson [CPM 2014] for the sliding model. In this paper, we present faster O(n log n/ log log n)-time solutions to both of the online/sliding models. Our algorithms are built on a simple data structure named BP-linked trees, and on a slightly improved version of the range minimum/maximum query (RmQ/RMQ) data structure on a dynamic list of integers. We also present other applications of our algorithms.

引用

页码：321 / 335

页数：15

共 34 条

[1] Marked ancestor problems
Alstrup, S
Husfeldt, T
Rauhe, T
[J]. 39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, : 534 - 543
[2] Off-line and on-line algorithms for closed string factorization
Alzamel, Mai
Iliopoulos, Costas S.
Smyth, W. F.
Sung, Wing-Kin
[J]. THEORETICAL COMPUTER SCIENCE, 2019, 792 : 12 - 19
[3] IMPROVED DYNAMIC DICTIONARY MATCHING
AMIR, A
FARACH, M
IDURY, RM
LAPOUTRE, JA
SCHAFFER, AA
[J]. INFORMATION AND COMPUTATION, 1995, 119 (02) : 258 - 282
[4] Online timestamped text indexing
Amir, A
Landau, GM
Ukkonen, E
[J]. INFORMATION PROCESSING LETTERS, 2002, 82 (05) : 253 - 259
[5] [Anonymous], 2016, 27 ANN ACM SIAM S DI, DOI DOI 10.1137/1.9781611974331.CH143
[6] Closed factorization
Badkobeh, Golnaz
Bannai, Hideo
Goto, Keisuke
Tomohiro, I
Iliopoulos, Costas S.
Inenaga, Shunsuke
Puglisi, Simon J.
Sugimoto, Shiho
[J]. DISCRETE APPLIED MATHEMATICS, 2016, 212 : 23 - 29
[7] BETTER OPM/L TEXT COMPRESSION
BELL, TC
[J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1986, 34 (12) : 1176 - 1182
[8] Bille P., 2017, LIPIcs, V78, P1
[9] Brodal GS, 2011, LECT NOTES COMPUT SC, V6844, P290, DOI 10.1007/978-3-642-22300-6_25
[10] Compressed Indexes for Dynamic Text Collections
Chan, Ho-Leung
Hon, Wing-Kai
Lam, Tak-Wah
Sadakane, Kunihiko
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (02)

← 1 2 3 4 →