Suffix Arrays in Theory and Practice: Combinatorics of and Algorithms on the Suffix Array Data Structure

 
9783639021004: Suffix Arrays in Theory and Practice: Combinatorics of and Algorithms on the Suffix Array Data Structure

The suffix array of a string is a permutation of all starting positions of the string's suffixes in lexicographical order. In this book, we investigate mathematical and algorithmical aspects of suffix arrays.The first part mainly deals with combinatorial properties of suffix arrays and their enumeration. For a fixed alphabet size and string length, we divide the set of all strings into equivalence classes of strings that share the same suffix array. For each such equivalence class, we count the number of strings contained in it and enumerate those strings. We also give exact formulas for computing the number of equivalence classes and efficient algorithms for enumerating them. The second part of the book deals with suffix array construction. We first present a new classification of suffix array construction algorithms and provide an in-depth review of the classified algorithms. After the survey of the previous algorithms, we present our practical algorithm for suffix array construction. We finally present an experimental study that compares our algorithm to other fast suffix array construction algorithms.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.

About the Author:

Dr. Klaus-Bernd Schürmann, Dipl.-Inform.: Studies of Mathematics and Computer Science at the Free University of Berlin and at the University of Massachusetts Dartmouth. Post-graduate studies of Bioinformatics at the University of Bielefeld. Consultant at IDS Scheer AG, Saarbrücken.Title

„Über diesen Titel“ kann sich auf eine andere Ausgabe dieses Titels beziehen.

(Keine Angebote verfügbar)

Buch Finden:



Kaufgesuch aufgeben

Sie kennen Autor und Titel des Buches und finden es trotzdem nicht auf ZVAB? Dann geben Sie einen Suchauftrag auf und wir informieren Sie automatisch, sobald das Buch verfügbar ist!

Kaufgesuch aufgeben