An estimation of the size of non-compact suffix trees

DOI10.14232/ACTACYB.22.4.2016.6zbMATH Open1374.68132arXiv1604.01168OpenAlexW2964191618MaRDI QIDQ2973237FDOQ2973237

Authors: Bálint Vásárhelyi 

Publication date: 31 March 2017

Published in: Acta Cybernetica (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

suffix trees

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (7)

• On suffix tree breadth
• Title not available (Why is that?)
• Tight upper and lower bounds on suffix tree breadth
• A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm
• REACHABILITY ON SUFFIX TREE GRAPHS
• Average sizes of suffix trees and DAWGs
• Title not available (Why is that?)

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)