Suffix-sorting via Shannon-Fano-Elias codes
type: Item
instance of: scholarly article
title: Suffix-sorting via Shannon-Fano-Elias codes
zbMATH Open document ID: 1461.68068
author: Fei Nan
author: Donald Adjeroh
published in: Algorithms
publication date: 2018-08-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6920517
zbMATH Keywords: suffix sorting
zbMATH Keywords: suffix arrays
zbMATH Keywords: suffix tree
zbMATH Keywords: Shannon-Fano-Elias codes
zbMATH Keywords: source coding
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a3020145
OpenAlex ID: W2175286270
cites work: Suffix Arrays: A New Method for On-Line String Searches
cites work: Faster suffix sorting
cites work: Engineering a lightweight suffix array construction algorithm
cites work: Algorithms on Strings, Trees and Sequences
cites work: Linear work suffix array construction
cites work: Space efficient linear time construction of suffix arrays
cites work: Asymptotic properties of data compression and suffix trees
cites work: Replacing suffix trees with enhanced suffix arrays
cites work: On the sorting-complexity of suffix tree construction
cites work: Constructing suffix arrays in linear time
cites work: Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets
cites work: Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
cites work: Combinatorial Pattern Matching
cites work: Fast Lightweight Suffix Array Construction and Checking
cites work: Linear Time Suffix Array Construction Using D-Critical Substrings
cites work: In-Place Suffix Sorting
cites work: Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
cites work: New approaches for computer analysis of nucleic acid sequences.
cites work: Q4023085
DOI: 10.3390/A3020145
description: scientific article; zbMATH DE number 6920517