String Representation in Suffixient Set Size Space

Hiroki Shibata, Hideo Bannai · 2026

Read String Representation in Suffixient Set Size Space by Hiroki Shibata, Hideo Bannai (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-04377.txt.

Introduction

Shibata and Bannai study compression via substring equation systems, which encode strings as solutions to substring-equality and character-assignment constraints. They show every string has such a system of size on the order of chi, the smallest suffixient set size. This settles chi's reachability, an open problem. They prove computing the smallest system's size is NP-hard and inapproximable within one plus epsilon. The smallest bidirectional macro scheme size lies between the smallest system size and four times it. The two schemes thus match up to a constant factor.

Catalog record

CREATORHiroki Shibata, Hideo Bannai
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34371
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.04377

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

String Representation in Suffixient Set Size Space Hiroki Shibata, Hideo Bannai Abstract Repetitiveness measures quantify how much repetitive structure a string contains and serve as parameters for compressed representations and indexing data structures. We study the measure χ \chi , defined as the size of the smallest suffixient set. Although χ \chi has been studied extensively, its reachability, whether every string w w admits a string representation of size O ⁡ ( χ ⁡ ( w ) ) O(\chi(w)) words, has remained an important open problem. We answer this question affirmatively by presenting the first such representation scheme. Our construction is based on a new model, the substring equation system (SES), and we show that every string admits an SES of size O ⁡ ( χ ⁡ ( w ) ) O(\chi(w)) . 1 Introduction Repetitiveness measures aim to quantify how much repetitive structure a string contains. They offer a unified way to compare strings and to reason about the space usage of compressed representations. Beyond repetitiveness measures that arise directly from compression techniques, such as LZ-style parsing [ 16 ] and the run-length encoded Burrows–Wheeler transform [ 2 ] , repetitiveness measures that are not derived from any specific compression technique have been proposed, notably string attractors [ 8 ] and normalized substring complexity [ 10 ] . These measures are widely used to analyze the size of existing compressed representations and indices, and they provide convenient parameters for stating space bounds for both representations and indexing data structures [ 14 ] . Reachability is a central notion for assessing the power of a repetitiveness measure. A repetitiveness measure f is reachable if there exists a representation scheme that, for every string w , encodes w in O(f(w)) machine words, i.e., O(f(w)\log|w|) bits. If f is reachable, then it can be used directly as a compressed representation. If f is not reachable, then f will strictly lower-bound the space of any universal representation scheme for some (infinite) subset of strings. Recently, suffixient sets [ 5 ] have been proposed as a repetitiveness measure not derived from any particular compression scheme. They were first introduced to support efficient random access and related queries together with compressed indexing in small space, and have since been studied in the context of space-efficient string indexes [ 3 ] . Owing to a one-to-one correspondence with super-maximal right extensions, the size of the smallest suffixient set, denoted by \chi , can be computed in linear time in the text length, and it has attracted attention as an easily computable repetitiveness measure [ 4 , 13 ] . Existing results already place \chi among the central repetitiveness measures [ 13 ] . For example, it is known that \chi(w)\leq 2r(w) for every string w , where r is the number of runs in the Burrows–Wheeler transform [ 2 ] , while there exist strings for which \chi is asymptotically smaller than more classical parsing measures such as the LZ factorization [ 16 ] size z and the lex-parse [ 12 ] size v . At the same time, it is not known whether every string w admits a bidirectional macro scheme (BMS) [ 15 ] of size O(\chi(w)) . Since BMS is a general framework that subsumes many existing schemes, compression based on suffixient sets might lead to new compression methods that cannot be expressed as BMS. Moreover, \chi upper bounds the smallest string attractor size \gamma , whose own reachability is a long-standing open problem, so proving \chi unreachable would immediately imply that \gamma is unreachable as well. For this reason, Navarro et al. [ 13 ] state the conjecture: “We conjecture, instead, that \chi is not reachable, proving which would imply that \gamma is also unreachable, a long-time open question.” In this paper, we disprove their conjecture by presenting the first string representation scheme that represents any string in O(\chi(w)) words. Our O(\chi(w)) representation can be computed in O(|w|) time, and since there exist instance where \chi(w)=o(z(w)) and \chi(w)=o(v(w)) [ 13 ] , our result advances the frontier of linearly computable compression. To this end, we introduce a general framework for representing strings by a substring equation system (SES). Our construction is an instance of SES, and we show that every string admits an SES of size O(\chi(w)) . Since any bidirectional macro scheme can be transformed into an SES of the same size, SES provides a unifying framework for several standard compression schemes that are known to be expressible as BMS. 2 Preliminaries Let \Sigma be an alphabet of size \sigma . An element of \Sigma is called a character. A string w of length |w|=n over the alphabet \Sigma is a sequence w[1]\cdots w[n] of characters where w[i]\in\Sigma for all 1\leq i\leq n . For any two strings x and y , we denote by xy=x[1]\cdots x[|x|]y[1]\cdots y[|y|] the concatenation of x and y . For any string x , we denote by x^{R}=x[|x|]\cdots x[1] its reversal. If w=xyz holds for some strings x,y,z\in\Sigma^{*} , then x , y , and z are called a prefix, a substring, and a suffix of w , respectively. For 1\leq i\leq j\leq n , we denote by w[i..j]=w[i]\cdots w[j] the substring of w from position i to j , and w[i..j)=w[i..j-1] . For convenience w[i..j] is the empty string when j<i . We will assume that the string w is terminated by an end of string symbol denoted by \$ , which does not occur elsewhere in the string. For every string w , we denote by \sigma(w) the number of distinct characters appearing in w , including the special character \$ . For any x\in\Sigma^{*} and c\in\Sigma , xc is a right extension in w if xc is a substring of w and for some c^{\prime}\neq c , xc^{\prime} is also a substring of w . A right extension in w is super-maximal if it is not a proper suffix of another right extension in w . The set of all right extensions and super-maximal right extensions in w is denoted by \mathit{RE}(w) and \mathit{SRE}(w) , respectively. Existing work establishes a one-to-one correspondence between smallest suffixient sets and super-maximal right extensions [ 3 , 4 ] . Using the notation of Navarro et al. [ 13 ] , we adopt the following definitions. Definition 1 . For a string w of length n , a set S\subseteq[1..n] is a suffixient set for w if for every right extension x\in\mathit{RE}(w) there exists j\in S such that x is a suffix of w[1..j] . Definition 2 . For a string w of length n , a set S\subseteq[1..n] is a smallest suffixient set for w if there exists a bijection \mathrm{pos}:\mathit{SRE}(w)\rightarrow S such that every super-maximal right extension x\in\mathit{SRE}(w) is a suffix of w[1..\mathrm{pos}(x)] . The repetitiveness measure \chi is defined as \chi(w)=|\mathit{SRE}(w)| . By the above definition, \chi(w) is exactly the size of a smallest suffixient set for w . Figure 1 shows an example of a smallest suffixient set and the corresponding super-maximal right extensions. Figure 1: An example of a smallest suffixient set and super-maximal right extensions for w=\texttt{aabbaababa}\$ . The blue boxes indicate the positions in the smallest suffixient set. The

Read the complete text