Don't miss an insight. Subscribe to Techopedia for free.


Suffix Tree

What Does Suffix Tree Mean?

A suffix tree is a tool often used to analyze text strings. It is a type of digital tree that uses algorithmic methods to reveal the structure of a string and its subsets. It is a type of Patricia tree, a structure that is used to store a set of strings.


Techopedia Explains Suffix Tree

Suffix trees can be used for many things. Generally, these trees hold
all of the subsets of a given text string. With that in mind, other text
strings can be matched against the suffix tree to figure whether they are
included in the initial string input.

The suffix tree has been developed over time by such figures as Weiner and
McCreight in the 1970s, and Ukkonen in the 1990s. Visual adaptations of a
suffix tree show how the subsets of the text string are handled by the
algorithm. Alternately, a suffix tree can be shared in mathematical notation.

Suffix trees are generally used for finding specific sub-patterns within a
greater set of strings. Programmers use the suffix tree search to make searches
efficient, to find each instance where a given substring is represented in the
data structure. Suffix tree searches may be used to find DNA sequences,
research coordinates or any other kind of string data.


Related Terms