String processing and information retrieval : 28th international symposium, SPIRE 2021, Lille, France, October 4-6, 2021, proceedings

This book constitutes the refereed proceedings of the 27th International Symposium on String Processing and Information Retrieval, SPIRE 2021, held in Lille, France, in October 2021.\* The 14 full papers and 4 short papers presented together with 2 invited papers in this volume were carefully reviewed and selected from 30 submissions. They cover topics such as: data structures; algorithms; information retrieval; compression; combinatorics on words; and computational biology. \*The symposium was held virtually. Preface Organization Contents Invited Papers r-Indexing the eBWT 1 Introduction 2 Preliminaries 3 r-Indexing the eBWT 4 Constructing the r-Index of the eBWT 5 Conclusions References Unicode at Gigabytes per Second 1 Introduction 2 Related Work 3 The Unicode Formats 4 Algorithms 5 Experiments 6 Conclusion References Combinatorics Longest Common Rollercoasters 1 Introduction 1.1 Related Work 2 Preliminaries 3 Algorithms 3.1 O(nmk) Time and Space Algorithm 3.2 O(rklog3 mloglogm) Time and O(rk) Space Algorithm 4 Conclusion References Minimal Unique Palindromic Substrings After Single-Character Substitution 1 Introduction 2 Preliminaries 2.1 Notations 2.2 Tools 3 Changes of MUPSs After Single Character Substitution 4 Algorithms for Updating Set of MUPSs 4.1 Computing MUPSs to Be Removed 4.2 Computing MUPSs to Be Added References Permutation-Constrained Common String Partitions with Applications 1 Introduction 2 Preliminary Notions 3 Reduction to PCSP for Simple String Functions 4 FPT Algorithms for d-occurrence PCSP with Reversals 4.1 Bounded Occurrences and Reversal Functions 4.2 Constructing a Complete and Order-Consistent Fixed-Match Set 5 Conclusion References All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent 1 Introduction 2 Preliminaries 3 Perturbing Procedure 4 Equivalence of Instantiations 5 Conclusion References String Covers of a Tree 1 Introduction 2 Preliminaries 2.1 The Table of Prefixes 2.2 Summing Second Heights of All Nodes 3 Covers of Directed Trees 4 Covers of Undirected Trees 4.1 O(n2) Time and Space Solution 4.2 O(n2 logn) Time and O(n) Space References Compression Grammar Index by Induced Suffix Sorting 1 Introduction 1.1 Our Contribution 1.2 Related Work 2 Preliminaries 2.1 Induced Suffix Sorting 2.2 Constructing the Grammar 3 GCIS Index 4 Pattern Matching Algorithm 4.1 Cores 4.2 Matching with GST 5 Implementation and Experiments References An LMS-Based Grammar Self-index with Local Consistency Properties 1 Introduction 2 Related Concepts 2.1 Grammar Compression 2.2 A Grammar Self-index 2.3 Locally Consistent Parsing 2.4 Locally Consistent Grammars 2.5 Induced Suffix Sorting 3 A Grammar Self-index Based on LMS Parsing 3.1 LMS Parsing 3.2 Computing the Cuts During the Pattern Matching 4 Experiments 5 Results and Discussion 6 Concluding Remarks References On the Approximation Ratio of LZ-End to LZ77 1 Introduction 2 Preliminaries 2.1 Strings 2.2 Lempel-Ziv Factorizations 2.3 Period-Doubling Sequence 3 Properties on Period-Doubling Sequence 4 Factorizations of Period-Doubling Sequence 5 Conclusions and Further Work References Data Structures Computing the Original eBWT Faster, Simpler, and with Less Memory 1 Introduction 2 Preliminaries 3 Computing the eBWT and GCA 4 eBWT and PFP 5 Results and Discussion References Extracting the Sparse Longest Common Prefix Array from the Suffix Binary Search Tree 1 Introduction 2 Preliminaries 3 The Suffix AVL Tree 4 Computing the Sparse LCP Array 5 Future Work References findere: Fast and Precise Approximate Membership Query 1 Introduction 2 Method 2.1 Background 2.2 Decreasing the AMQ False-Positive Rate with ``Query Time Filtration'' 2.3 Querying K-mers with findere 3 Results 3.1 Experimental Data 3.2 Results on Genomics Data 3.3 Results on Natural Languages 3.4 Limit of the findere Approach 4 Conclusion References Repeats A Separation of and b via Thue–Morse Words 1 Introduction 2 Preliminaries 3 Important Characteristics of Thue–Morse Words 4 Upper and Lower Bounds on b 4.1 Upper Bound 4.2 Lower Bound 5 Conclusion References Lower Bounds for the Number of Repetitions in 2D Strings 1 Introduction 2 Preliminaries 3 Distinct Tandems 4 Distinct Quartics 4.1 Construction 4.2 Analysis 4.3 Reducing the Alphabet 5 Runs 5.1 Construction 5.2 Analysis References On Stricter Reachable Repetitiveness Measures 1 Introduction 2 Basic Concepts 2.1 Terminology 2.2 Parsing Based Schemes 2.3 Grammars and Generalizations 2.4 Lower Bounds 2.5 Morphisms over Strings 3 Macro Systems 4 Deterministic Lindenmayer Systems 5 NU-Systems 6 Future Work 7 Conclusions References Information Retrieval Improved Topic Modeling in Twitter Through Community Pooling 1 Introduction 2 Tweet Pooling for Topic Models 3 Twitter Dataset Construction 4 Evaluation 5 Results 6 Conclusions References TSXor: A Simple Time Series Compression Algorithm 1 Introduction 2 Background 3 TSXor 4 Experiments 5 Conclusion and Future Work References Pattern Matching Exploiting Pseudo-locality of Interchange Distance 1 Introduction 2 Preliminaries 3 Approximate NN-Search in High Dimensional Spaces 4 Approximate Pattern Matching 5 Conclusion and Open Problems References Position Heaps for Cartesian-Tree Matching on Strings and Tries 1 Introduction 2 Preliminaries 2.1 Strings and (Reversed) Tries 2.2 Cartesian-Tree Pattern Matching 2.3 Sequence Hash Trees 3 Cartesian-Tree Position Heaps for Strings 4 Cartesian-Tree Position Heaps for Tries 5 Cartesian-Tree Pattern Matching with Position Heaps 5.1 Pattern Matching on Text String S with CPH(S) 5.2 Pattern Matching on Text Trie with References Author Index