Package smile.nlp

Class Trie<K,V>

java.lang.Object
smile.nlp.Trie<K,V>
Type Parameters:
K - the data type of key.
V - the data type of value.
public class Trie<K,V> extends 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 nodes that correspond to keys of interest.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    class 
    Trie.Node
    The nodes in the trie.

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    Description
    Trie<K,V>.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

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

  • Constructor Details

    • Trie

      public Trie()
      Constructor.

    • Trie

      public Trie(int initialCapacity)
      Constructor.
      Parameters:
      initialCapacity - the initial capacity of root node.

  • Method Details

    • 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<K,V>.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.