z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here