Checking and producing word attractors

Marie-Pierre Béal, Maxime Crochemore, Giuseppe Romana · 2025

Read Checking and producing word attractors by Marie-Pierre Béal, Maxime Crochemore, Giuseppe Romana (2025) 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-2509-08503.txt.

Introduction

Marie-Pierre Béal and 2 co-authors give fast algorithms for a measure of how well a word compresses in a 2025 paper. The measure is the word attractor. An attractor is a small set of places in a word. Every distinct block of the word must touch one of those places, in a precise sense. The fewer places needed, the better the word compresses.

Two algorithms rest on suffix automata, compact machines that hold all blocks of a word. The first checks in linear time if a set of places is an attractor. The second builds one greedily. The smallest attractor is hard to find in general. Still, the greedy method gives tiny ones, and the true smallest for several classic word families. Storage systems live on compression, so sharp measures guide real design.

Catalog record

CREATORMarie-Pierre Béal, Maxime Crochemore, Giuseppe Romana
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-08503

Browse the full library · About the Tower of Babel

Full text

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

Checking and producing word attractors Marie-Pierre Béal, Maxime Crochemore, Giuseppe Romana Abstract The article focuses on word (or string) attractors, which are sets of positions related to the text compression efficiency of the underlying word. The article presents two combinatorial algorithms based on Suffix automata or Directed Acyclic Word Graphs. The first algorithm decides in linear time whether a set of positions on the word is an attractor of the word. The second algorithm generates an attractor for a given word in a greedy manner. Although this problem is NP-hard, the algorithm is efficient and produces very small attractors for several well-known families of words. 1 Introduction The notion of a word attractor , or simply an attractor, provides a unifying framework for known dictionary-based compressors, as introduced by Kempa and Prezza in [ 11 ] . A word attractor for a finite word w is a subset P of positions on w for which every non-empty factor u of w has an occurrence that includes at least one position in P . That is, there are positions i , j and t that satisfy u=w_{[i,j]} , t\in P and i\leq t\leq j . The combinatorial aspects of word attractors have been studied by various authors from a general combinatorics on words perspective and to describe their properties with respect to specific words [ 13 , 14 , 12 , 9 , 5 ] . Several articles, such as [ 11 , 10 , 15 ] , consider testing whether a set of positions on a word is a word attractor for it and provide efficient solutions. However, finding a word attractor of minimum size turns out to be NP-hard, even if the length of factors is bounded. The same holds for the variant of circular word attractors introduced by Mantaci et al. [ 13 , 15 ] . Checking whether a set of positions is a word attractor of a word can be performed in linear time in the size of the word [ 11 , 10 , 15 ] . Specifically, for a word of length n on an alphabet A , the algorithms in [ 11 , 10 ] run in O(n) time with O(n(\log|A|+\log n) bit space for integer alphabets of polynomial size in n , becoming O(n\log|A|) bit space when n is polynomial in the size of the alphabet. The algorithm in [ 15 ] runs in O(n) time with O(n\log n) bit space for integer alphabets of polynomial size in n . However, these algorithms use recent advances in compact data structures: compressed suffix arrays supporting constant-time LF (Last-to-First) function computation for the algorithm in [ 10 ] , and suffix arrays with the LCP (Longest Common Prefix) array in [ 15 ] . In this paper, Section 3 revisits the algorithmic question of whether a set of positions on a word is an attractor for the word, using only the Suffix automaton of the word, also called its Directed Acyclic Word Graph (DAWG) ( [ 3 , 6 ] ). Although suffix arrays can be converted into Suffix automata and vice versa, our algorithm is simpler because it checks the attractor property with a direct and simple computation on the DAWG. The time complexity for computing the DAWG with its suffix links is O(n) for a fixed-size alphabet, O(n\log|A|) for a general ordered alphabet A , and O(n) in [ 8 ] for an integer alphabet of polynomial size. Assuming that the DAWG and its attributes are computed, our algorithm runs in O(n) time, independently of the alphabet size. Its space complexity is the space complexity of the DAWG, that is, linear with respect to the word length. Section 4 describes a relatively simple algorithm to exhibit an attractor of a word. Since the question is NP-hard (see [ 11 ] ), the algorithm is based on a heuristic that works in a greedy fashion to successively produce the positions of the attractor. Additionally, our algorithm runs in linear time when the attractor is bounded. A general greedy quadratic algorithm to compute a small attractor is given in [ 16 , Definition 19] . Note that the hardness result does not necessarily apply to automatic sequences or to substitutive sequences generated by constant-length substitutions. Experiments on known families of words, carried over sufficiently long words, show that the output of our algorithm is often a small attractor, sometimes the smallest possible. An implementation is available on GitHub [ 2 ] . 2 Definitions Let A be an alphabet , a finite set of letters. A (finite) word w over A is denoted by w_{1}w_{1}\cdots w_{n} where all w_{i} are in A and n\geq 0 . Its length n is denoted by |w| and the set of positions on w is \llbracket 1,n\rrbracket . We denote the word w_{i}w_{i+1}\cdots w_{j} by w_{[i,j]} , for i,j\in\llbracket 1,n\rrbracket . By convention, it is the empty word \varepsilon if j<i . The word w_{[i,j]} is called a factor (or a block ) of w . It is a prefix of w when i=1 and a suffix of w when j=n . An occurrence of a non-empty factor u of w is a pair (i,j) , i\leq j , of positions satisfying u=w_{[i,j]} . The position i is the starting position of the occurrence, and j is its ending position. Note that j=i+|u|-1 . Let \EP(u) denote the set of ending positions of all occurrences of u in w , let \mbox{Suff\/}(w) denote the set of suffixes of w , and let \mathcal{S}(w) denote its suffix automaton, that is, the minimal automaton accepting \mbox{Suff\/}(w) . As such, the states of \mathcal{S} are (identified with) the equivalence classes of the set of factors of w under the equivalence u\equiv v\text{ if and only if }u^{-1}\mbox{Suff\/}(w)=v^{-1}\mbox{Suff\/}(w). Equivalently, a state q of \mathcal{S}(w) is the set of factors of w having the same set of ending positions. The smallest ending position of any factor u in q is indicated by \pos[q] . In this article, we consider all states of \mathcal{S}(w) to be terminal states, which transforms the structure into a factor automaton (which is not necessarily a minimal automaton [ 6 ] ). As such, it is also called a Directed Acyclic Word Graph (DAWG) after Blumer et al. [ 3 ] . The automaton \mathcal{S}(w) is a tuple (Q,I,\delta) , where Q is the set of states, I is its initial state, and \delta is its total transition function. 0 1 2 3 4 5 6 7 3^{\prime\prime} 3^{\prime} 4^{\prime\prime} \mathtt{a} \mathtt{a} \mathtt{b} \mathtt{b} \mathtt{a} \mathtt{b} \mathtt{b} \mathtt{b} \mathtt{b} \mathtt{b} \mathtt{a} \mathtt{b} \mathtt{a} Figure 1: The DAWG of w=\mathtt{aabbabb} . Its initial state is 0 . As a Suffix automaton, its terminal states are 0 , 3^{\prime} , 4^{\prime\prime} , and 7 . Figure 1 shows the DAWG of w=\mathtt{aabbabb} with states (or nodes) and arcs. Plain arcs, labelled by letters occurring in the word, represent the transition function. The paths from the initial state 0 are labelled by all the factors of w and only them. The dashed arcs of the DAWG correspond to a function F\colon Q\setminus\{I\}\rightarrow Q called its failure or suffix function. They are called

Read the complete text