LLVM  14.0.0git
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
llvm::SuffixTree Class Reference

A data structure for fast substring queries. More...

#include "llvm/Support/SuffixTree.h"

Collaboration diagram for llvm::SuffixTree:
Collaboration graph
[legend]

Classes

struct  RepeatedSubstring
 A repeated substring in the tree. More...
 
struct  RepeatedSubstringIterator
 Iterator for finding all repeated substrings in the suffix tree. More...
 

Public Types

typedef RepeatedSubstringIterator iterator
 

Public Member Functions

 SuffixTree (const std::vector< unsigned > &Str)
 Construct a suffix tree from a sequence of unsigned integers. More...
 
iterator begin ()
 
iterator end ()
 

Public Attributes

llvm::ArrayRef< unsigned > Str
 Each element is an integer representing an instruction in the module. More...
 

Detailed Description

A data structure for fast substring queries.

Suffix trees represent the suffixes of their input strings in their leaves. A suffix tree is a type of compressed trie structure where each node represents an entire substring rather than a single character. Each leaf of the tree is a suffix.

A suffix tree can be seen as a type of state machine where each state is a substring of the full string. The tree is structured so that, for a string of length N, there are exactly N leaves in the tree. This structure allows us to quickly find repeated substrings of the input string.

In this implementation, a "string" is a vector of unsigned integers. These integers may result from hashing some data type. A suffix tree can contain 1 or many strings, which can then be queried as one large string.

The suffix tree is implemented using Ukkonen's algorithm for linear-time suffix tree construction. Ukkonen's algorithm is explained in more detail in the paper by Esko Ukkonen "On-line construction of suffix trees. The paper is available at

https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Definition at line 137 of file SuffixTree.h.

Member Typedef Documentation

◆ iterator

Definition at line 343 of file SuffixTree.h.

Constructor & Destructor Documentation

◆ SuffixTree()

SuffixTree::SuffixTree ( const std::vector< unsigned > &  Str)

Construct a suffix tree from a sequence of unsigned integers.

Parameters
StrThe string to construct the suffix tree for.

Definition at line 19 of file SuffixTree.cpp.

References llvm::EmptyIdx.

Member Function Documentation

◆ begin()

iterator llvm::SuffixTree::begin ( )
inline

Definition at line 344 of file SuffixTree.h.

◆ end()

iterator llvm::SuffixTree::end ( )
inline

Definition at line 345 of file SuffixTree.h.

Member Data Documentation

◆ Str

llvm::ArrayRef<unsigned> llvm::SuffixTree::Str

Each element is an integer representing an instruction in the module.

Definition at line 140 of file SuffixTree.h.


The documentation for this class was generated from the following files: