Premium
Efficient implementation of suffix trees
Author(s) -
Andersson Arne,
Nilsson Stefan
Publication year - 1995
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380250203
Subject(s) - substring , suffix tree , computer science , suffix , string (physics) , compressed suffix array , data structure , trie , generalized suffix tree , path (computing) , simple (philosophy) , data compression , string searching algorithm , compression (physics) , tree (set theory) , theoretical computer science , algorithm , mathematics , programming language , combinatorics , philosophy , linguistics , materials science , epistemology , composite material , mathematical physics
We study the problem of string searching using the traditional approach of storing all unique substrings of the text in a suffix tree. The methods of path compression, level compression and data compression are combined to build a simple, compact and efficient implementation of a suffix tree. Based on a comparative discussion and extensive experiments, we argue that our new data structure is superior to previous methods in many practical situations.