An estimation of the size of non-compact suffix trees

DOI10.14232/ACTACYB.22.4.2016.6MaRDI QIDQ2973237zbMATH OpenOpenAlexFDO

Authors Bálint Vásárhelyi

Publication date 31 March 2017

Published in Acta Cybernetica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.01168

zbMATH Keywords

suffix trees

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: A suffix tree is a data structure used mainly for pattern matching. It is known that the space complexity of simple suffix trees is quadratic in the length of the string. By a slight modification of the simple suffix trees one gets the compact suffix trees, which have linear space complexity. The motivation of this paper is the question whether the space complexity of simple suffix trees is quadratic not only in the worst case, but also in expectation.

Recommendations

• A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
• Space efficient suffix trees
• Faster entropy-bounded compressed suffix trees
• Compressed suffix trees with full functionality
• An(other) Entropy-Bounded Compressed Suffix Tree

Cited in

(7)

• Average sizes of suffix trees and DAWGs
• scientific article; zbMATH DE number 5050583 (Why is no real title available?)
• On suffix tree breadth
• REACHABILITY ON SUFFIX TREE GRAPHS
• A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm
• scientific article; zbMATH DE number 742990 (Why is no real title available?)
• Tight upper and lower bounds on suffix tree breadth

This page was built for publication: An estimation of the size of non-compact suffix trees

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