Package com.abstractkamen.datastructures.impl.trees.search

Class GenericUkkonenSuffixTree<T>

java.lang.Object

com.abstractkamen.datastructures.impl.trees.search.GenericUkkonenSuffixTree<T>

Type Parameters:

T - type of value a match can return

All Implemented Interfaces:

SuffixTree<T>

public class GenericUkkonenSuffixTree<T>
extends Object
implements SuffixTree<T>

The Generic suffix tree implementation using Ukkonen's Algorithm

Useful links:

• Esko Ukkonen On–line construction of suffix trees
• Good Implementation of generic suffix tree
• Ukkonen Algorithm Wiki
• Ukkonen algorithm visualisation by Brenden Kokoszka
• Baeldung Ukkonen Algorithm Explanation

Author:

kamen.hristov

Constructor Summary

Constructors

Constructor	Description
GenericUkkonenSuffixTree(Collection<UkkonenSuffixTreeInput<T>> input)	The only available constructor expects a list of UkkonenSuffixTreeInput without any null values.

Method Summary

Modifier and Type	Method	Description
boolean	contains(String pattern)	True if the provided substring is present in the suffix tree.
Collection<T>	findAllOccurrences(String pattern)	Returns the values for each string matching the provided pattern.
int	nodesCount()	The total nodes of this tree
String	prettyTreeString()	This is purely for debugging
int	textSize()	The total size of the text held by this tree.
String	toString()
int	valuesCount()	Total values inserted with their string keys into the tree.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Details

GenericUkkonenSuffixTree

public GenericUkkonenSuffixTree(Collection<UkkonenSuffixTreeInput<T>> input)

The only available constructor expects a list of UkkonenSuffixTreeInput without any null values.

Parameters:

input - list

Method Details

findAllOccurrences

public Collection<T> findAllOccurrences(String pattern)

Description copied from interface: SuffixTree

Returns the values for each string matching the provided pattern.

Specified by:

findAllOccurrences in interface SuffixTree<T>

Parameters:

pattern - string

Returns:

list of values

contains

public boolean contains(String pattern)

Description copied from interface: SuffixTree

True if the provided substring is present in the suffix tree.

Specified by:

contains in interface SuffixTree<T>

Parameters:

pattern - string

Returns:

true if present else false

textSize

public int textSize()

Description copied from interface: SuffixTree

The total size of the text held by this tree.

Specified by:

textSize in interface SuffixTree<T>

Returns:

text size

nodesCount

public int nodesCount()

Description copied from interface: SuffixTree

The total nodes of this tree

Specified by:

nodesCount in interface SuffixTree<T>

Returns:

node count

valuesCount

public int valuesCount()

Description copied from interface: SuffixTree

Total values inserted with their string keys into the tree.

Specified by:

valuesCount in interface SuffixTree<T>

Returns:

value count

toString

public String toString()

Overrides:

toString in class Object

prettyTreeString

public String prettyTreeString()

This is purely for debugging

Returns:

a string with the tree structure