smile.nlp

Class Trie<K,V>

java.lang.Object

smile.nlp.Trie<K,V>

public class Trie<K,V>
extends java.lang.Object

A trie, also called digital tree or prefix tree, is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner node s that correspond to keys of interest.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	Trie.Node

Constructor Summary

Constructors

Constructor and Description
Trie() Constructor.
Trie(int initialCapacity) Constructor.

Method Summary

Modifier and Type	Method and Description
Trie.Node	get(K key) Returns the node of a given key.
V	get(K[] key) Returns the associated value of a given key.
void	put(K[] key, V value) Add a key with associated value to the trie.
int	size() Returns the number of entries.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Trie

public Trie()

Constructor.

Trie

public Trie(int initialCapacity)

Constructor.

Parameters:

initialCapacity - the initial capacity of root node.

Method Detail

put

public void put(K[] key,
                V value)

Add a key with associated value to the trie.

Parameters:

key - the key.

value - the value.

get

public V get(K[] key)

Returns the associated value of a given key. Returns null if the key doesn't exist in the trie.

Parameters:

key - the key.

Returns:

the associated value or null.

get

public Trie.Node get(K key)

Returns the node of a given key. Returns null if the key doesn't exist in the trie.

Parameters:

key - the key.

Returns:

the node of the given key or null.

size

public int size()

Returns the number of entries.

Returns:

the number of entries.