LVG Trie Tree

I. Trie Tree

A trie tree is a tree structure composed of trie nodes. The trie is organized with a reverse suffix order.

II. Trie Node

A trie node includes:

  • key: a character from suffix.
  • level: an integer to represent the distance from root node, root node is 0.
  • rules: a vector includes all rules belong to this node.
  • child: a vector links to the next level trie nodes.

III. Rules

A rule includes:

  • exceptions: use Hashtable for easy key value look up.

IV. Example

Suppose we have rules for the suffices er, ers, est, or, st, and CVC.


root ($)
|
+--- Node (C)
| |
| +--- Node (V)
| |
| +--- Node (C - Rules)
|
+--- Node (r)
| |
| +--- Node (e - Rules)
| |
| +--- Node (o - Rules)
|
+--- Node (s)
| |
| +--- Node (r)
| |
| +--- Node (e - Rules)
|
+--- Node (t)
|
+--- Node (s - Rules)
|
+--- Node (e - Rules)