Dynamic construction of an antidictionary with linear complexity

DOI10.1016/J.TCS.2014.01.021MaRDI QIDQ2437769zbMATH OpenOpenAlexFDO

Authors Takahiro Ota, Hirotada Fukae, Hiroyoshi Morita

Publication date 13 March 2014

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

Full work available at URL https://doi.org/10.1016/j.tcs.2014.01.021

zbMATH Keywords

data compressionsuffix treelinear computational complexityincremental constructionantidictionary

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1305431
• Algorithms – ESA 2004
• Constructing Efficient Dictionaries in Close to Sorting Time
• Dynamic dictionaries for multisets and counting filters with constant time operations
• Dynamic dictionaries for multisets and counting filters with constant time operations
• scientific article; zbMATH DE number 1617245
• scientific article; zbMATH DE number 2038723
• Low redundancy in static dictionaries with constant query time
• A unified access bound on comparison-based dynamic dictionaries
• Constructing antidictionaries of long texts in output-sensitive space

Cites work

• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Automata and forbidden words
• Combinatorial Pattern Matching
• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• On suffix extensions in suffix trees
• On-line construction of suffix trees
• The smallest automaton recognizing the subwords of a text

Cited in

(6)

• Absent words in a sliding window with applications
• Analysis of the Size of Antidictionary in DCA
• Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
• Constructing antidictionaries of long texts in output-sensitive space
• Asymptotic Optimality of Antidictionary Codes
• scientific article; zbMATH DE number 2182423 (Why is no real title available?)

This page was built for publication: Dynamic construction of an antidictionary with linear complexity

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