Class VariableArrayTrie

java.lang.Object
  VariableArrayTrie

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