On-line suffix tree construction with reduced branching

Classical suffix tree construction algorithms by McCreight and Ukkonen spend most of the time looking up the right branch to follow from the current node. However, not all these slow branching operations are necessary. A significant portion of them is used for implicit suffix link simulation and can be avoided by replacing the traditional top-down descent with bottom-up climbing.We describe the bottom-up approach and analyze its costs and benefits. An experimental evaluation on two standard data corpora shows that bottom-up climbing removes forty to sixty six percent of branching operations and consequently saves twenty one to thirty two percent of construction time. However, a theoretical analysis of the worst-case behavior reveals that the time complexity of the bottom-up approach is superlinear. This is remedied by a combination of both approaches that removes nearly as many branching operations as the bottom-up climb, but still runs in linear time like the top-down descent.