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

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

public class Simti
extends java.lang.Object

SIMTI(SIMple Trie Index) library.

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

Nested Class Summary
 class Simti.HEADI
          The header for SIMTI structure.
 class Simti.ST_FREE
          The structure for the free node list.
 class Simti.ST_NF
          The node for SIMTI structure.
 class Simti.ST_NODE
          Data node for SIMTI structure.
 
Field Summary
 Simti.HEADI head
          The head of SIMTI structure.
 Simti.ST_NF[] nf
          The array of ST_NF which the actual data is stored in.
 int search_end
          The end index for search_idx[].
 int[] search_idx
          The list of indices that have been found.
 char[] search_word
          The word to search in the SIMTI structure.
static int ST_MAX_WORD
          The maximum length of a word.
static int ST_NF_DEFAULT
          The maximum number of the ST_NF nodes.
 
Constructor Summary
Simti()
          Constructor.
 
Method Summary
 int alloc(int size)
          It allocates the available nodes and returns the first index of the list.
 int binary_search(int idx, char size, char key)
          Performs binary search.
 int delete(char[] word)
          Deletes the specified word in the SIMTI structure.
 int fetch(char[] word)
          It searches the word in the SIMTI structure, and returns the information for the word.
 int firstkey(char[] word)
          It finds a word by traversing the first key from the head until it founds a node with the information.
 int free(int idx, int size)
          Frees the nodes from the specified index.
 void init()
          Initializes the SIMTI structure.
 int insert(char[] word, int I)
          Inserts the word to the SIMTI structure with the specified information.
 int kcomp(Simti.ST_NODE a, Simti.ST_NODE b)
          Compares the keys of the specified two nodes.
 int lookup(char[] word, int[] I_buffer)
          Searches the specified word in the SIMTI structure, and stores the information found.
 int nextkey(char[] word)
          It finds a word by traversing the children, siblings, and parent of the last node of the previous search.
private  void node_copy(Simti.ST_NODE n1, Simti.ST_NODE n2)
          Copies a node.
 int replace(char[] word, short I)
          Replaces the information for the specified word.
 int search(char[] word)
          Searches the specified word in the SIMTI structure.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

ST_NF_DEFAULT

public static final int ST_NF_DEFAULT
The maximum number of the ST_NF nodes.

See Also:
Constant Field Values

ST_MAX_WORD

public static final int ST_MAX_WORD
The maximum length of a word.

See Also:
Constant Field Values

search_end

public int search_end
The end index for search_idx[].


search_word

public char[] search_word
The word to search in the SIMTI structure.


search_idx

public int[] search_idx
The list of indices that have been found.


head

public Simti.HEADI head
The head of SIMTI structure.


nf

public Simti.ST_NF[] nf
The array of ST_NF which the actual data is stored in.

Constructor Detail

Simti

public Simti()
Constructor.

Method Detail

alloc

public int alloc(int size)
It allocates the available nodes and returns the first index of the list.

Parameters:
size - - the number of nodes that should be allocated
Returns:
the index of the first node for the allocated list, if failed 0

fetch

public int fetch(char[] word)
It searches the word in the SIMTI structure, and returns the information for the word.

Parameters:
word - - search word
Returns:
information for the word, if failed 0

binary_search

public int binary_search(int idx,
                         char size,
                         char key)
Performs binary search.

Parameters:
idx - - index from the middle item
size - - size of the list
key - - key to find
Returns:
index of the item with the specified key, if failed 0

delete

public int delete(char[] word)
Deletes the specified word in the SIMTI structure.

Parameters:
word - - word to delete
Returns:
1: done successfully, -1: failed, 0: not found

firstkey

public int firstkey(char[] word)
It finds a word by traversing the first key from the head until it founds a node with the information.

Parameters:
word - - the character array to store the word found
Returns:
the length of the word found, 0: a word cannot be found in this way

free

public int free(int idx,
                int size)
Frees the nodes from the specified index.

Parameters:
idx - - the first index of the nodes to delete
size - - the number of nodes to delete
Returns:
0: done successfully, -1: failed

init

public void init()
Initializes the SIMTI structure.


insert

public int insert(char[] word,
                  int I)
Inserts the word to the SIMTI structure with the specified information.

Parameters:
word - - word to insert
I - - information to insert on the word
Returns:
-1: fail, 0: duplicated, 1: success

kcomp

public int kcomp(Simti.ST_NODE a,
                 Simti.ST_NODE b)
Compares the keys of the specified two nodes.

Parameters:
a - - the first node to compare
b - - the second node to compare
Returns:
a.key - b.key

lookup

public int lookup(char[] word,
                  int[] I_buffer)
Searches the specified word in the SIMTI structure, and stores the information found.

Parameters:
word - - word to search
I_buffer - - array to store the information found
Returns:
the number of words found, 0: no words were found

nextkey

public int nextkey(char[] word)
It finds a word by traversing the children, siblings, and parent of the last node of the previous search.

Parameters:
word - - found word
Returns:
the length of the word found, 0: no word can be found in this way

node_copy

private void node_copy(Simti.ST_NODE n1,
                       Simti.ST_NODE n2)
Copies a node.

Parameters:
n1 - - destination node to copy
n2 - - source node to copy

replace

public int replace(char[] word,
                   short I)
Replaces the information for the specified word.

Parameters:
word - - the word to change its information
I - - new information for the word
Returns:
1: done successfully, -1: failed

search

public int search(char[] word)
Searches the specified word in the SIMTI structure.

Parameters:
word - - word to search
Returns:
the number of words found, 0: not found