Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach

DOI10.1016/0097-3165(94)90065-5zbMath0802.68097OpenAlexW1603682988MaRDI QIDQ1328400

Wojciech Szpankowski, Philippe Jacquet

Publication date: 30 November 1994

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(94)90065-5

zbMATH Keywords

data compressionsuffix treeBernoulli modeldigital tree

Mathematics Subject Classification ID

Combinatorics on words (68R15) Data structures (68P05)

Related Items

Context Trees, Variable Length Markov Chains and Dynamical Sources, On pattern occurrences in a random text, Analytical depoissonization and its applications, Analysis of the Size of Antidictionary in DCA, Joint string complexity for Markov sources: small data matters, Mellin transforms and asymptotics: Harmonic sums, Fast BWT in small space by blockwise suffix sorting, Statistical properties of factor oracles, On the shape of the fringe of various types of random trees, Statistical Properties of Factor Oracles, More on recurrence and waiting times, Asymptotic estimation of the average number of terminal states in DAWGs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the height of digital trees and related problems
• On the performance evaluation of extendible hashing and trie searching
• Asymptotical growth of a class of random trees
• The evaluation of an alternative sum with applications to the analysis of some data structures
• String overlaps, pattern matching, and nontransitive games
• Periods in strings
• A note on the average depth of trees
• Entropy and prefixes
• Average sizes of suffix trees and DAWGs
• Paths in a random digital tree: limiting distributions
• Some results on V-ary asymmetric tries
• A Note on the Height of Suffix Trees
• Self-alignments in words and their applications
• A Space-Economical Suffix Tree Construction Algorithm
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Maximal Prefix-Synchronized Codes
• A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
• Limiting Distribution for the Depth in PATRICIA Tries
• New results on the size of tries