Truncated suffix trees and their application to data compression.

DOI10.1016/S0304-3975(03)00053-7zbMath1044.68031OpenAlexW1975136411MaRDI QIDQ1401392

Joong Chae Na, Alberto Apostolico, Kun Soo Park, Costas S. Iliopoulos

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00053-7

zbMATH Keywords

Data compressionText processingData structureSuffix tree

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (11)

Reverse-Safe Text Indexing ⋮ Linking indexing data structures to de Bruijn graphs: construction and update ⋮ Elastic-degenerate string matching with 1 error ⋮ Irredundant tandem motifs ⋮ INDEXING GAPPED-FACTORS USING A TREE ⋮ Sparse and Truncated Suffix Trees on Variable-Length Codes ⋮ Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree ⋮ A compressed dynamic self-index for highly repetitive text collections ⋮ Small-space LCE data structure with constant-time queries ⋮ Dictionary matching with a few gaps ⋮ Space-efficient representation of truncated suffix trees, with applications to Markov order estimation

Cites Work

• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• On-line construction of suffix trees
• Linear Algorithm for Data Compression via String Matching
• Data compression via textual substitution
• A Space-Economical Suffix Tree Construction Algorithm
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Algorithms on Strings, Trees and Sequences
• Unnamed Item
• Unnamed Item

This page was built for publication: Truncated suffix trees and their application to data compression.