Because of a lapse in government funding, the information on this website may not be up to date, transactions submitted via the website may not be processed, and the agency may not be able to respond to inquiries until appropriations are enacted. The NIH Clinical Center (the research hospital of NIH) is open. For more details about its operating status, please visit cc.nih.gov. Updates regarding government operating status and resumption of normal operations can be found at OPM.gov.
LVG Rules: Trie Introduction
I. Background
A trie algorithm is used in LVG to find inflection variants and derivation. Rules are:
II. Procedures
The high level algorithm flows are described as follows:
III. Trie and Tree
Tree:
Tree has been used as powerful search algorithm. It includes binary tree and B-tree. A binary tree (searching) stores all data into a tree structure with all nodes have 2 branches at most. The B-tree was invented by Bayer and McCreight in the early 70's. It's now part of every database system. A node in a B-tree may have multiple branches.
Trie:
Trie is derived from the middle letters of the word "retrieval.
Difference:
In real applications, tree stores a whole word as a node while trie break a word into characters and store each single character into the tree structure.
< Example >
Data: be, bed, beset, bess, best, bet, better.
Binary Tree:
root (bess)
|
+--- Node (bed)
| |
| +--- Node (be)
| |
| +--- Node (beset)
|
+--- Node (bet)
|
+--- Node (best)
|
+--- Node (better)
Trie:
root (b)
|
+--- Node (e *)
|
+--- Node (d *)
|
+--- Node (s)
| |
| +--- Node (e)
| | |
| | +--- Node (t *)
| |
| +--- Node (s *)
| |
| +--- Node (t *)
|
+--- Node (t *)
|
+--- Node (t)
|
+--- Node (e)
|
+--- Node (r *)