Suffix-sorting via Shannon-Fano-Elias codes
Summary: Given a sequence \(T=t_0t_1\dots t_{n-1}\) of size \(n=| T|\), with symbols from a fixed alphabet \(\Sigma\), \((|\Sigma|\leq n)\), the suffix array provides a listing of all the suffixes of \(T\) in a lexicographic order. Given \(T\), the suffix sorting problem is to construct its suffix array. The direct suffix sorting problem is to construct the suffix array of \(T\) directly without using the suffix tree data structure. While algorithims for linear time, linear space direct suffix sorting have been proposed, the actual constant in the linear space is still a major concern, given that the applications of suffix trees and suffix arrays (such as in whole-genome analysis) often involve huge data sets. In this work, we reduce the gap between current results and the minimal space requirement. We introduce an algorithm for the direct suffix sorting problem with worst case time complexity in \(O(n)\), requiring only \((1\frac{2}{3}n\log n-n\log|\Sigma|+O(1))\) bits in memory space. This implies \(5\frac{2}{3}n+O(1)\) bytes for total space requirment, (including space for both the output suffix array and the input sequence \(T\)) assuming \(n\leq 2^{32}\), \(|\Sigma|\leq 256\), and 4 bytes per integer. The basis of our algorithm is an extension of Shannon-Fano-Elias codes used in source coding and information theory. This is the first time information-theoretic methods have been used as the basis for solving the suffix sorting problem.
- Algorithms on Strings, Trees and Sequences
- Asymptotic properties of data compression and suffix trees
- Breaking a time-and-space barrier in constructing full-text indices
- Combinatorial Pattern Matching
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Constructing suffix arrays in linear time
- Engineering a lightweight suffix array construction algorithm
- Fast lightweight suffix array construction and checking
- Faster suffix sorting
- scientific article; zbMATH DE number 107482 (Why is no real title available?)
- In-Place Suffix Sorting
- Linear Time Suffix Array Construction Using D-Critical Substrings
- Linear work suffix array construction
- New approaches for computer analysis of nucleic acid sequences.
- On the sorting-complexity of suffix tree construction
- Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets
- Replacing suffix trees with enhanced suffix arrays
- Space efficient linear time construction of suffix arrays
- Suffix Arrays: A New Method for On-Line String Searches
This page was built for publication: Suffix-sorting via Shannon-Fano-Elias codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662548)
