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