Construction of Fundamental Data Structures for Strings

ISBN-13: 9783030551070 / Angielski / Miękka / 2020 / 104 str.

Felipe A. Louza; Simon Gog; Guilherme P. Telles

Recenzje

"The book is clearly written and structured. The illustrations and examples help readers to understand the presented algorithms. ... The book is aimed at graduate and PhD students, researchers and practitioners interested in designing and implementing efficient structures for storing and querying string data." (Mihai Gabroveanu, zbMATH 1480.68004, 2022)

Spis treści

·       Part I Introduction and Preliminaries

 

              1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             1.2 Suffix sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

              1.3 Overview of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

              References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

              2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.1 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.1.1 Alphabets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.1.2 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.1.3 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

              2.2 Data Structures for Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.2.1 Suffix Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.2.2 LCP Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.2.3 Lyndon Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             2.2.4 Document Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

 

              3 Induced Suffix Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             

                             3.2 A brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             3.3 Induced suffix sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           3.3.1 SA in linear time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           3.3.2 SA in optimal time/space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             3.4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                            References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

·       Part II Augmented Suffix Sorting

             

              4 Inducing the LCP Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             4.2 Inducing the LCP array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           4.2.1 LCP array in linear time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           4.2.2 LCP array in optimal time/space . . . . . . . . . . . . . . . . . . . . . . . .

                             4.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                            References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

              5 Inducing the Document Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             5.2 Suffix Sorting for String Collections . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           5.2.1 Inducing SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           5.2.2 Inducing SA and DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             5.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           5.3.1 Computing SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           5.3.2 Computing SA and DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                            References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

              6 Inducing the Lyndon Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             6.2 Inducing the Lyndon array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           6.2.1 LA in linear time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                                           6.2.2 LA in optimal time/space . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             6.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                            References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

·       Part III Conclusions

 

              7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                             7.1 Contributions and Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

                            References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 

O autorze

Felipe Alves Louza, Dr., Prof., Faculdade de Engenharia Elétrica, Universidade Federal de Uberlândia, Uberlândia – MG, Brazil, 38400-902

Simon Gog, Dr., eBay Inc., San Jose – USA

Guilherme Pimentel Telles, Dr., Prof., Instituto de Computação, Universidade Estadual de Campinas, Campinas – SP, Brazil, 13083-852