Class VariableArrayTrie

java.lang.Object
  extended byVariableArrayTrie
All Implemented Interfaces:
Trie

public class VariableArrayTrie
extends java.lang.Object
implements Trie

An implementation of tries with arrays of variable size. Each node is an array of pointers on its sons. The label is carried by the following node. The size is bounded by the sum of lengths of the nodes. The algorithms are linear in the size of the word times the cardinality of the alphabet. Performances: the trie of the delaf dictionnary (a french dictionnary of all words at all forms -about 1M words) can be computed without memory extension. The result is a trie with about 2M nodes (which indicates that the arity of the nodes is in the avarage close to 2). To transform the trie into an IDFA requires an extension of the stack memory to 120M (using the option -Xmx120m).


Field Summary
 char label
           
 VariableArrayTrie[] next
           
 int num
           
 boolean terminal
           
 
Constructor Summary
VariableArrayTrie(char c)
          Creates a node with label c.
 
Method Summary
 void add(char c)
          Adds an entry in the next array to allow a transition by c.
 void addToTrie(java.lang.String s)
          Adds the word s to the trie.
 void addToTrieBis(java.lang.String s)
          A variant of addToTrie().
 void addToTrieTer(java.lang.String s)
          A variant of addToTrie().
 int copy(int p, DFA a)
           
 int copy(int p, IDFA a)
           
 void copybis(DFA a)
           
 void copybis(IDFA a)
           
 int enum(int p)
          Numbers the nodes of a trie through an initilization of the field num.
 void fromFile(java.lang.String name)
          Builds a trie representing the list of strings read from a file line by line.
 void fromFileBis(java.lang.String name)
          Builds a trie representing the list of the reverse of strings read from a file line by line.
 int index(char c)
          Returns the index of a node with label c if there is one and -1 otherwise.
 boolean isInTrie(java.lang.String s)
          Implements the function IsInTrie() of Section 1.3.1.
 boolean isLeaf()
          Returns true if the node p is a leaf of the trie.
 Pair longestPrefixInTrie(java.lang.String s, int j)
          Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix.
static void main(java.lang.String[] args)
           
 VariableArrayTrie next(char c)
          Returns the node Next(c) if it exists and null otherwise.
 void remove(int k)
          Removes the entry of index k of the array next.
 void removeFromTrie(java.lang.String s)
          Removes the string s from the trie.
 int size()
          Returns the number of nodes of the trie.
 Dawg toDawg()
           
 DFA toDFA(Alphabet alph)
           
 DFA toDFAbis(Alphabet alph)
           
 IDFA toIDFA(Alphabet alph)
           
 IDFA toIDFAbis(Alphabet alph)
          Creates an IDFA from a trie.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

terminal

public boolean terminal

label

public char label

num

public int num

next

public VariableArrayTrie[] next
Constructor Detail

VariableArrayTrie

public VariableArrayTrie(char c)
Creates a node with label c.

Method Detail

next

public VariableArrayTrie next(char c)
Returns the node Next(c) if it exists and null otherwise.


index

public int index(char c)
Returns the index of a node with label c if there is one and -1 otherwise.


add

public void add(char c)
Adds an entry in the next array to allow a transition by c.


remove

public void remove(int k)
Removes the entry of index k of the array next.


longestPrefixInTrie

public Pair longestPrefixInTrie(java.lang.String s,
                                int j)
Computes the pair composed of the length of the longest prefix of s[j..n-1] in the trie and the vertex reached by this prefix. Implements the function LongestPrefixInTrie() of Section 1.3.1.

Specified by:
longestPrefixInTrie in interface Trie
Parameters:
s - the input string
j - the starting index
Returns:
the computed pair

isInTrie

public boolean isInTrie(java.lang.String s)
Implements the function IsInTrie() of Section 1.3.1.

Specified by:
isInTrie in interface Trie

addToTrie

public void addToTrie(java.lang.String s)
Adds the word s to the trie. Implements the function AddToTrie() of Section 1.3.1.

Specified by:
addToTrie in interface Trie
Parameters:
s - the string to be added

addToTrieBis

public void addToTrieBis(java.lang.String s)
A variant of addToTrie(). Does not use longestPrefixInTrie() and thus more economical in space (?).


addToTrieTer

public void addToTrieTer(java.lang.String s)
A variant of addToTrie(). Adds the reverse of the word s


isLeaf

public boolean isLeaf()
Returns true if the node p is a leaf of the trie. Implements the function IsLeaf() of Section 1.3.1.

Specified by:
isLeaf in interface Trie

removeFromTrie

public void removeFromTrie(java.lang.String s)
Removes the string s from the trie. Implements the function RemoveFromTrie() of Section 1.3.1.

Specified by:
removeFromTrie in interface Trie
Parameters:
s - the string to be removed

fromFile

public void fromFile(java.lang.String name)
              throws java.io.IOException
Builds a trie representing the list of strings read from a file line by line.

Specified by:
fromFile in interface Trie
Parameters:
name - the name of the file
Throws:
java.io.IOException

fromFileBis

public void fromFileBis(java.lang.String name)
                 throws java.io.IOException
Builds a trie representing the list of the reverse of strings read from a file line by line.

Parameters:
name - the name of the file
Throws:
java.io.IOException

size

public int size()
Returns the number of nodes of the trie.


enum

public int enum(int p)
Numbers the nodes of a trie through an initilization of the field num. All leaves get the num = -1.

Parameters:
p - the name of the root
Returns:
p + the number of internal nodes of the trie.

toIDFAbis

public IDFA toIDFAbis(Alphabet alph)
Creates an IDFA from a trie. All leaves are merged in a unique state.


copybis

public void copybis(IDFA a)

toDFAbis

public DFA toDFAbis(Alphabet alph)

copybis

public void copybis(DFA a)

toIDFA

public IDFA toIDFA(Alphabet alph)

copy

public int copy(int p,
                IDFA a)

toDFA

public DFA toDFA(Alphabet alph)

copy

public int copy(int p,
                DFA a)

toDawg

public Dawg toDawg()

toString

public java.lang.String toString()

main

public static void main(java.lang.String[] args)
                 throws java.lang.Exception
Throws:
java.lang.Exception