Construction of Fundamental Data Structures for Strings

✍ Scribed by Felipe A. Louza, Simon Gog, Guilherme P. Telles

• Publisher: Springer International Publishing;Springer
• Year: 2020
• Tongue: English
• Leaves: 107
• Series: SpringerBriefs in Computer Science
• Edition: 1st ed.
• Category: Library

✦ Synopsis

This books reviews recent theoretical and practical advances on suffix sorting and introduces algorithmic solutions to problems of wide interest for the construction of fundamental data structures that operate efficiently on strings namely, constructing the suffix array, the longest common prefix (LCP) array, the document array and the Lyndon array.
These data structures are the cornerstone of many algorithmic solutions in Bioiformatics, Information Retrieval and Data Compression.
This book introduces the relevant problem areas, their importance, the notation and related algorithms and then presents the algorithmic solutions for indexing data structure constructions.
This book is intended for graduate students, researchers and practitioners from Computer Science and Bioinformatics with a strong interest in algorithmic aspects.

✦ Table of Contents

Front Matter ....Pages i-ix
Front Matter ....Pages 1-1
Introduction (Felipe A. Louza, Simon Gog, Guilherme P. Telles)....Pages 3-8
Background (Felipe A. Louza, Simon Gog, Guilherme P. Telles)....Pages 9-21
Induced Suffix Sorting (Felipe A. Louza, Simon Gog, Guilherme P. Telles)....Pages 23-40
Front Matter ....Pages 41-41
Inducing the LCP Array (Felipe A. Louza, Simon Gog, Guilherme P. Telles)....Pages 43-57
Inducing the Document Array (Felipe A. Louza, Simon Gog, Guilherme P. Telles)....Pages 59-80
Inducing the Lyndon Array (Felipe A. Louza, Simon Gog, Guilherme P. Telles)....Pages 81-95
Front Matter ....Pages 97-97
Conclusions (Felipe A. Louza, Simon Gog, Guilherme P. Telles)....Pages 99-101
Back Matter ....Pages 103-104

✦ Subjects

Computer Science; Data Structures, Cryptology and Information Theory; Theory of Computation; Bioinformatics