Truncated suffix trees and their application to data compression.

DOI10.1016/S0304-3975(03)00053-7MaRDI QIDQ1401392zbMATH OpenOpenAlexFDO

Authors Joong Chae Na, Alberto Apostolico, Costas S. Iliopoulos, Kunsoo Park

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

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

Recommendations

• Compressed suffix trees with full functionality
• Compact directed acyclic word graphs for a sliding window
• Engineering a compressed suffix tree implementation
• Compressed suffix trees, efficient computation and storage of LCP-values
• Fully-Compressed Suffix Trees

Cites work

• scientific article; zbMATH DE number 3913711 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Compression of individual sequences via variable-rate coding
• Data compression via textual substitution
• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• Linear Algorithm for Data Compression via String Matching
• On-line construction of suffix trees

Cited in

(17)

• Compact directed acyclic word graphs for a sliding window
• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• Dictionary matching with a few gaps
• Sliding suffix tree
• TREE COMPRESSION AND OPTIMIZATION WITH APPLICATIONS
• Sparse and truncated suffix trees on variable-length codes
• Elastic-degenerate string matching with 1 error
• Reverse-safe text indexing
• Small-space LCE data structure with constant-time queries
• Elastic-degenerate string matching with 1 error or mismatch
• A compressed dynamic self-index for highly repetitive text collections
• scientific article; zbMATH DE number 2127733 (Why is no real title available?)
• Irredundant tandem motifs
• Construction of a de Bruijn graph for assembly from a truncated suffix tree
• INDEXING GAPPED-FACTORS USING A TREE
• SOFSEM 2005: Theory and Practice of Computer Science
• Linking indexing data structures to de Bruijn graphs: construction and update

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401392)