com.raffaeleconforti.kazennikov.dafsa

Class IntDaciukAlgoIndexed

java.lang.Object

com.raffaeleconforti.kazennikov.dafsa.IntDaciukAlgoIndexed

Direct Known Subclasses:

AbstractIntDAFSA

public abstract class IntDaciukAlgoIndexed
extends java.lang.Object

Generic algorithm for constructing minimal DAFSA (deterministic acyclic finite state automata) or minimial tries.

Author:

Anton Kazennikov

Field Summary

Fields

Modifier and Type	Field and Description
protected int	startState Start state number

Constructor Summary

Constructors

Constructor and Description
IntDaciukAlgoIndexed()

Method Summary

Modifier and Type	Method and Description
void	add(java.util.ArrayList<java.lang.Integer> seq) Add sequence to trie
void	addMinWord(java.util.ArrayList<java.lang.Integer> seq) Add sequence to the DAFSA
abstract int	addState() Adds a new state to the automaton
protected java.util.ArrayList<java.lang.Integer>	addSuffix(java.util.ArrayList<java.lang.Integer> states, int s, java.util.ArrayList<java.lang.Integer> seq, int start, int end) Add suffix to given new state
abstract int	cloneState(int state) Clones given state.
abstract int	getNext(int state, int input) Find matching outbound transition for given state
abstract boolean	hasFinal(int state) Checks if state is final for this final feature
abstract boolean	isConfluence(int state) Checks a state for confluence (if in has more that 1 inbound transitions)
abstract void	regAdd(int state) Add state to register
abstract int	regGet(int state) Get equivalent state from register
abstract void	regRemove(int state) Remove given state from register.
abstract void	removeState(int state) Removes given state from the automaton
protected void	replaceOrRegister(java.util.ArrayList<java.lang.Integer> input, java.util.ArrayList<java.lang.Integer> stateList, int stop)
abstract boolean	setFinal(int state) public set final feature for state
abstract boolean	setNext(int src, int label, int dest) Adds a transition from src to dest on given label, if a transition from src with given label already exists, then change it to new destination state.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

startState

protected int startState

Start state number

Constructor Detail

IntDaciukAlgoIndexed

public IntDaciukAlgoIndexed()

Method Detail

getNext

public abstract int getNext(int state,
                            int input)

Find matching outbound transition for given state

Parameters:

state - source state

input - label

Returns:

dest state, or -1, if no such transition exists

isConfluence

public abstract boolean isConfluence(int state)

Checks a state for confluence (if in has more that 1 inbound transitions)

Parameters:

state - state to check

Returns:

true if state has more than one inbound transitions

cloneState

public abstract int cloneState(int state)

Clones given state. It clones:

• transitions
• final features

Parameters:

state -

Returns:

addState

public abstract int addState()

Adds a new state to the automaton

Returns:

index of the new state

setNext

public abstract boolean setNext(int src,
                                int label,
                                int dest)

Adds a transition from src to dest on given label, if a transition from src with given label already exists, then change it to new destination state.

Parameters:

src - source state

label - transition label

dest - destination state

Returns:

true, if state has changed

removeState

public abstract void removeState(int state)

Removes given state from the automaton

Parameters:

state - state index

setFinal

public abstract boolean setFinal(int state)

public set final feature for state

Parameters:

state - state number

Returns:

true, if state has changed, else false (this is possible then state is already final)

hasFinal

public abstract boolean hasFinal(int state)

Checks if state is final for this final feature

Parameters:

state - state number

Returns:

regAdd

public abstract void regAdd(int state)

Add state to register

Parameters:

state - state number

regGet

public abstract int regGet(int state)

Get equivalent state from register

Parameters:

state - reference state

Returns:

number of registered state, or -1 (INVALID_STATE) if no such state exist

regRemove

public abstract void regRemove(int state)

Remove given state from register. Removes exact state not equivalent one.

Parameters:

state - state to remove

addSuffix

protected java.util.ArrayList<java.lang.Integer> addSuffix(java.util.ArrayList<java.lang.Integer> states,
                                                           int s,
                                                           java.util.ArrayList<java.lang.Integer> seq,
                                                           int start,
                                                           int end)

Add suffix to given new state

Parameters:

states - state list

s - base state number

seq - sequence to add

fin - final state

addMinWord

public void addMinWord(java.util.ArrayList<java.lang.Integer> seq)

Add sequence to the DAFSA

Parameters:

seq - sequence to add

replaceOrRegister

protected void replaceOrRegister(java.util.ArrayList<java.lang.Integer> input,
                                 java.util.ArrayList<java.lang.Integer> stateList,
                                 int stop)

add

public void add(java.util.ArrayList<java.lang.Integer> seq)

Add sequence to trie

Parameters:

seq - sequence to add