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)