Hiroki Shibata 0001

dblp:128/4148-1 · DBLP profile ↗
← Back
9ranked-venue papers
4as first author
9since 2021 · last 2026
0009-0006-6502-7476ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 1 first-author · 4 since 2021Databases, data management, data science and information retrieval · 3 · 1 first-author · 3 since 2021Graphics, computer vision, multimedia, augmented reality and games · 1 · 1 first-author · 1 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2026 LZBE: An LZ-Style Compressor Supporting O(log n)-Time Random Access
abstract
An LZ-like factorization of a string divides it into factors, each being either a single character or a copy of a preceding substring. While grammar-based compression schemes support efficient random access with space linear in the compressed size, no comparable guarantees are known for general LZ-like factorizations. This limitation motivated restricted variants such as LZ-End [Kreft and Navarro, 2013] and height-bounded LZ (LZHB) [Bannai et al., 2024], which trade off some compression efficiency for faster access. In this paper, we introduce LZ-Begin-End (LZBE), a new LZ-like variant in which every copy factor must refer to a contiguous sequence of preceding factors. This structural restriction ensures that any context-free grammar can be transformed into an LZBE factorization of the same size. We further study the greedy LZBE factorization, which selects each copy factor to be as long as possible while processing the input from left to right, and show that it can be computed in linear time. Moreover, we exhibit a family of strings for which the greedy LZBE factorization is asymptotically smaller than the smallest grammar. These results demonstrate that the LZBE scheme is strictly more expressive than grammar-based compression in the worst case. To support fast queries, we propose a data structure for LZBE-compressed strings that permits O(log n)-time random access within space linear in the compressed size, where n is the length of the input string.
Hiroki Shibata 0001, Yuto Nakashima 0001, Yutaro Yamaguchi 0001, Shunsuke Inenaga
CPM1
2026 LZ78 Substring Compression in Compressed Space
Hiroki Shibata 0001, Dominik Köppl
Theory Comput. Syst.1
2026 Subsequence Matching and LCS under Cartesian-Tree Equivalence
Taketo Tsujimoto, Yuki Yonemoto, Hiroki Shibata 0001, Takuya Mieno, Yuto Nakashima 0001, Shunsuke Inenaga
Theory Comput. Syst.3
2025 Packed Acyclic Deterministic Finite Automata
Hiroki Shibata 0001, Masakazu Ishihata, Shunsuke Inenaga
SOFSEM (2)1
2025 Tight Additive Sensitivity on LZ-Style Compressors and String Attractors
Yuto Fujie, Hiroki Shibata 0001, Yuto Nakashima 0001, Shunsuke Inenaga
SPIRE2
2025 Counting Distinct (Non-)crossing Substrings
Haruki Umezaki, Hiroki Shibata 0001, Dominik Köppl, Yuto Nakashima 0001, Shunsuke Inenaga, Hideo Bannai
SPIRE2
2025 Bit Packed Encodings for Grammar-Compressed Strings Supporting Fast Random Access
Alan M. Cleary, Joseph Winjum, Jordan Dood, Hiroki Shibata 0001, Shunsuke Inenaga
SEA4
2024 Computing Longest Common Subsequence Under Cartesian-Tree Matching Model
Taketo Tsujimoto, Hiroki Shibata 0001, Takuya Mieno, Yuto Nakashima 0001, Shunsuke Inenaga
IWOCA2
2024 LZ78 Substring Compression with CDAWGs
Hiroki Shibata 0001, Dominik Köppl
SPIRE1