LVG Rules: Persistent Trie

I. Persistent Data

A persistent data system is to store data in files instead of RAM. In addition, these data can be randomly accessed by address from files. This function can be performed by a Java class, RandomAccessFile( ). The key issue of using this technique is to define the format (protocol) of how the data is sorted and retrieved. Usually, a header is needed to put at the front of each segment of data to describe the Meta data of storing data.

II. Persistent List

A persistent link class is used to perform one dimension linked list through persistent files.

  • File Data format:
    header + node1 + node2 + ...
    where header is:
    • 0~3 : int : numbers of nodes
    • 4~11: long: next address (address will be used for next node)

    node:
    • 0~x: specific data (length x varies)
    • x+1~x+8: long: address for next node
  • One persistent file is capable of storing multiple linked lists.
  • All nodes belong to one linked list need to be added (stored) into persistent file at once (before storing next list) if multiple lists is stored in the same file.
  • The node must be the child class of PersistentListNode( ).
  • The data structure in a list node includes address for this node, address for next node, and other node specific data.
  • Only same type of node can be stored for one linked list.

III. Persistent Tree

A persistent tree class is used to perform tree operations (two dimensional) through persistent files.

  • File Data format:
    node1 + node2 + ...
    where node:
    • 0~3: int: level
    • 4~11: long: address for next node
    • 12~19: long: address for parent node
    • 20~27: long: address for child list
    • 27+: specific data (length varies)
  • One persistent file is capable of storing multiple trees. However, we use one file to store one tree in our trie application for simplification.
  • The node must be the child class of PersistentTreeNode( ).
  • The data structure in a tree node includes address for this node, address for next node, address for the child, address for the parent, level of the node, and other node specific data.
  • Only same type of node can be stored for one linked list.

IV. Persistent Trie A persistent trie is developed to get inflections and derivations in LVG.

    < pre-process >
  • It reads in all rules from flat files and then store trie, rules, and exceptions into persistent files.
  • It uses PersistentTree to store trie tree in the persistent file.
  • It uses PersistentList to store rules and exceptions in the persistent file.

< process >

  • It opens persistent files.
  • It retrieves data from persistent files.

< post-process >

  • It closes persistent files.

V. Notes

The persistent trie uses Java RandomAccessFile class, which is not buffered and thus is slow. Buffered RandamAccessFile will improve the performance. In a study in 2002 (for 2003 release), replace PersistentTrie with RamTrie (put all infromation in the memory) improve performance more than 50% without too much heap size increased. Thus. PersistentTrie is not used after Lexical Tool 2013 release (use RamTire instead).