marytts.fst

Class Trie<Symbol>

java.lang.Object

marytts.fst.Trie<Symbol>

Direct Known Subclasses:

TransducerTrie

public class Trie<Symbol>
extends Object

This class represents a trie, i.e. a symbol (or 'letter') tree. Each trie node has arcs, to each of which a symbol is attached. The symbols guide the lookup of entries in the trie. The main purpose of this particular trie implementation is not the direct use of the trie (e.g. lookup) but its conversion to a finite-state machine that allows for an even more efficient storage and lookup. We are very thankful to Andreas Eisele who had the idea of using tries and transducers for our purposes and who provided us with c-code this particular implemention is based on.

Author:

benjaminroth

Field Summary

Fields

Modifier and Type	Field and Description
protected List<marytts.fst.Trie.TrieNode>	finalNodes
protected Map<Symbol,Integer>	label2id
protected List<Symbol>	labels
protected Map<marytts.fst.Trie.TrieNode,Integer>	reprs
protected List<marytts.fst.Trie.TrieNode>	rlist
protected marytts.fst.Trie.TrieNode	root

Constructor Summary

Constructors

Constructor and Description
Trie() Standard constructor for a trie.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(Symbol[] entry) This adds an entry to the trie.
void	computeMinimization() This computes the minimization of the trie, i.e.
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

root

protected marytts.fst.Trie.TrieNode root

finalNodes

protected List<marytts.fst.Trie.TrieNode> finalNodes

reprs

protected Map<marytts.fst.Trie.TrieNode,Integer> reprs

rlist

protected List<marytts.fst.Trie.TrieNode> rlist

label2id

protected Map<Symbol,Integer> label2id

labels

protected List<Symbol> labels

Constructor Detail

Trie

public Trie()

Standard constructor for a trie.

Method Detail

add

public void add(Symbol[] entry)

This adds an entry to the trie.

Parameters:

entry - entry

computeMinimization

public void computeMinimization()

This computes the minimization of the trie, i.e. equivalent nodes are identified. This is necessary to store a compact version of this trie as a minimal transducer. The trie itself is not represented more compactly.

toString

public String toString()

Overrides:

toString in class Object