LCP Array Construction in External Memory

DOI10.1145/2851491zbMath1365.68183OpenAlexW2316621983MaRDI QIDQ5266615

Dominik Kempa, Juha Kärkkäinen

Publication date: 16 June 2017

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2851491

zbMATH Keywords

external memory algorithmssuffix arrayLCP array

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (8)

Engineering a lightweight external memory suffix array construction algorithm ⋮ Better External Memory LCP Array Construction ⋮ Lightweight BWT and LCP Merging via the Gap Algorithm ⋮ Burrows-Wheeler transform and LCP array construction in constant space ⋮ Unnamed Item ⋮ Bidirectional Text Compression in External Memory ⋮ Lightweight merging of compressed indices based on BWT variants ⋮ Faster Compressed Suffix Trees for Repetitive Collections

Uses Software

• MapReduce
• STXXL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Replacing suffix trees with enhanced suffix arrays
• Engineering a lightweight external memory suffix array construction algorithm
• Computing the longest common prefix array based on the Burrows-Wheeler transform
• Lightweight data indexing and compression in external memory
• RAM-Efficient External Memory Sorting
• Algorithms and Data Structures for External Memory
• Tighter Bounds for the Sum of Irreducible LCP Values
• Parallel External Memory Suffix Sorting
• Compressed representations of sequences and full-text indexes
• Suffix Arrays: A New Method for On-Line String Searches
• Linear work suffix array construction
• Sampled Longest Common Prefix Array
• Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
• Linear Time Suffix Array Construction Using D-Critical Substrings
• Permuted Longest-Common-Prefix Array
• Lightweight LCP Construction for Next-Generation Sequencing Datasets
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• External Memory Generalized Suffix and LCP Arrays Construction
• Inducing the LCP-Array
• Inducing Suffix and LCP Arrays in External Memory
• Fast and Lightweight LCP-Array Construction Algorithms
• Lazy Lempel-Ziv Factorization Algorithms
• Better external memory suffix array construction
• Two Efficient Algorithms for Linear Time Suffix Array Construction
• Algorithm Theory - SWAT 2004

This page was built for publication: LCP Array Construction in External Memory