Efficient implementation of suffix trees

Arne Andersson and Stefan Nilsson

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.

Keywords: LC-trie, path compression, level compression, data compression, suffix tree, suffix array.