Breaking the -Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees

Area of Science:

• String data structures
• Computational complexity
• Bioinformatics algorithms

Background:

• Suffix arrays and suffix trees are fundamental for string processing but require significant space.
• Compressed Suffix Arrays (CSA) and FM-indexes offer space efficiency but have slow construction times.
• The construction time for these structures has remained a bottleneck for two decades.

Purpose of the Study:

• To develop novel compressed suffix array and compressed suffix tree structures.
• To achieve faster construction times for these space-efficient data structures.
• To maintain or improve existing space and query time complexities.

Main Methods:

• Proposed new compressed suffix array and compressed suffix tree structures.
• Developed algorithms with improved construction time complexity.
• Reduced the problem of optimizing CSA/CST parameters to prefix rank and prefix selection queries.

Main Results:

• Achieved O(n) construction time for compressed suffix arrays and trees, a significant improvement.
• New structures match existing space bounds (e.g., n log |Σ| bits) and query times (e.g., O(log |Σ|) or O(log log |Σ|) per operation).
• Demonstrated a general reduction from CSA/CST parameters to prefix rank/selection, enabling new pattern matching indexes.

Conclusions:

• The developed compressed suffix array and tree structures offer the first significant improvement in construction time in 20 years.
• These new structures provide a practical solution for space-critical applications in bioinformatics and data compression.
• The reduction to prefix rank/selection opens avenues for further research in efficient string indexing.