kr.ac.kaist.swrc.jhannanum.plugin.MajorPlugin.MorphAnalyzer.ChartMorphAnalyzer
Class Trie

java.lang.Object
  extended by kr.ac.kaist.swrc.jhannanum.plugin.MajorPlugin.MorphAnalyzer.ChartMorphAnalyzer.Trie

public class Trie
extends java.lang.Object

TRIE data structure for morpheme dictionaries.

Author:
Sangwon Park (hudoni@world.kaist.ac.kr), CILab, SWRC, KAIST

Nested Class Summary
 class Trie.FREE
          This class is for managing free nodes in the trie structure.
 class Trie.INFO
          This class is for the information of morpheme
 class Trie.TNODE
          This class is for nodes of trie structure.
 
Field Summary
static int DEFAULT_TRIE_BUF_SIZE_SYS
          the default buffer size for the system dictionary
static int DEFAULT_TRIE_BUF_SIZE_USER
          the default buffer size for the user dictionary
 Trie.FREE free_head
          the head of free node list
static int FREE_NODE
          the index of the free node
 Trie.TNODE node_head
          the head of node list
 int search_end
          the length of search result
 int[] search_idx
          the list for storing the path searched
 char[] search_key
          the list of keys of the path searched
static int START_NODE
          the index of the start node
 Trie.TNODE[] trie_buf
          the array for trie nodes
 
Constructor Summary
Trie(int buf_size)
          Constructor.
 
Method Summary
 Trie.TNODE fetch(char[] word)
          Fetches the specified word.
 Trie.TNODE get_node(int idx)
          Gets the trie node on the specified index
 int node_alloc(int size)
          Allocates the trie nodes available as the specified size
 void node_free(int fidx, int size)
          It frees the nodes from the specified index.
 int node_look(char key, int idx)
          It checks the children of the node on the specified index whether a child has the key.
 void print_result(TagSet tagSet)
          It writes the data in trie structure to the specified file.
 void print_trie(java.io.PrintWriter pw, int idx, int depth, TagSet tagSet)
          It prints the trie structure by recursive call.
 void read_dic(java.lang.String dictionaryFileName, TagSet tagSet)
          It reads the morpheme dictionary file, and initializes the trie structure.
 int search(char[] word)
          It searches the specified word on the trie structure.
 int store(char[] word, Trie.INFO inode)
          It stores the specified word in the trie structure.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_TRIE_BUF_SIZE_SYS

public static final int DEFAULT_TRIE_BUF_SIZE_SYS
the default buffer size for the system dictionary

See Also:
Constant Field Values

DEFAULT_TRIE_BUF_SIZE_USER

public static final int DEFAULT_TRIE_BUF_SIZE_USER
the default buffer size for the user dictionary

See Also:
Constant Field Values

FREE_NODE

public static final int FREE_NODE
the index of the free node

See Also:
Constant Field Values

START_NODE

public static final int START_NODE
the index of the start node

See Also:
Constant Field Values

search_end

public int search_end
the length of search result


search_idx

public int[] search_idx
the list for storing the path searched


search_key

public char[] search_key
the list of keys of the path searched


trie_buf

public Trie.TNODE[] trie_buf
the array for trie nodes


free_head

public Trie.FREE free_head
the head of free node list


node_head

public Trie.TNODE node_head
the head of node list

Constructor Detail

Trie

public Trie(int buf_size)
Constructor.

Parameters:
buf_size - - the maximum number of trie nodes
Method Detail

fetch

public Trie.TNODE fetch(char[] word)
Fetches the specified word.

Parameters:
word - - the word to fetch
Returns:
the trie node for the specified word

get_node

public Trie.TNODE get_node(int idx)
Gets the trie node on the specified index

Parameters:
idx - - index on the trie structure
Returns:
the trie node on the index

node_alloc

public int node_alloc(int size)
Allocates the trie nodes available as the specified size

Parameters:
size - - the number of nodes to allocate
Returns:
the start index of the allocated nodes, 0: failed to allocate

node_free

public void node_free(int fidx,
                      int size)
It frees the nodes from the specified index.

Parameters:
fidx - - the start index of node group to free
size - - the number of nodes to free

node_look

public int node_look(char key,
                     int idx)
It checks the children of the node on the specified index whether a child has the key.

Parameters:
key - - key to search
idx - - the index of the parent node
Returns:
the index of the child node which has the key, 0: not found

print_result

public void print_result(TagSet tagSet)
It writes the data in trie structure to the specified file.

Parameters:
tagSet - - the morpheme tag set used in the trie structure

print_trie

public void print_trie(java.io.PrintWriter pw,
                       int idx,
                       int depth,
                       TagSet tagSet)
It prints the trie structure by recursive call.

Parameters:
pw - - for printing the trie structure
idx - - the index of trie node
depth - - the depth of current node
tagSet - - the morpheme tag set used in the trie structure

read_dic

public void read_dic(java.lang.String dictionaryFileName,
                     TagSet tagSet)
              throws java.io.IOException
It reads the morpheme dictionary file, and initializes the trie structure.

Parameters:
dictionaryFileName - - the file path of the morpheme dictionary
tagSet - - the morpheme tag set
Throws:
java.io.IOException

search

public int search(char[] word)
It searches the specified word on the trie structure.

Parameters:
word - - word to search
Returns:
the length of the path searched, 0: not found

store

public int store(char[] word,
                 Trie.INFO inode)
It stores the specified word in the trie structure.

Parameters:
word - - the word to store
inode - - the information of the word
Returns:
0: done, -1: failed to store