sparsetable

README

sparsetable

Go implementation of final state automata using sparse tables.

Documentation

Index

• type Builder
  • func NewBuilder() *Builder
  • func (b *Builder) Add(str string, data int32) error
  • func (b *Builder) Build() *DFA
• type Cell
  • func NewFinalCell(data int32, next byte) Cell
  • func NewNonFinalCell(next byte) Cell
  • func NewTransitionCell(target uint32, char byte, next byte) Cell
  • func (c Cell) Char() byte
  • func (c Cell) Empty() bool
  • func (c Cell) Final() (int32, bool)
  • func (c *Cell) GobDecode(bs []byte) error
  • func (c Cell) GobEncode() ([]byte, error)
  • func (c Cell) Next() uint32
  • func (c Cell) State() bool
  • func (c Cell) String() string
  • func (c Cell) Target() uint32
  • func (c Cell) Transition() bool
  • func (c Cell) Type() CellType
• type CellType
• type DFA
  • func NewDictionary(strs ...string) *DFA
  • func (d *DFA) CellAt(s State) Cell
  • func (d DFA) Delta(s State, c byte) State
  • func (d *DFA) EachCell(f func(Cell))
  • func (d *DFA) EachTransition(s State, f func(Cell))
  • func (d *DFA) EachUTF8Transition(s State, f func(rune, State))
  • func (d *DFA) Final(s State) (int32, bool)
  • func (d *DFA) GobDecode(bs []byte) error
  • func (d *DFA) GobEncode() ([]byte, error)
  • func (d *DFA) Initial() State
• type FinalStateCallback
• type FuzzyDFA
  • func NewFuzzyDFA(k int, dfa *DFA) *FuzzyDFA
  • func (d *FuzzyDFA) Delta(f *FuzzyStack, cb FinalStateCallback) bool
  • func (d *FuzzyDFA) Initial(str string) *FuzzyStack
  • func (d *FuzzyDFA) MaxError() int
• type FuzzyStack
• type SparseTable
  • func (t *SparseTable) Add(tmp TmpState) uint32
• type State
  • func (s State) Valid() bool
• type TmpState
  • func (t TmpState) String() string
• type TmpStateTransition
  • func (t TmpStateTransition) String() string

Types

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder is used to build a DFA.

func NewBuilder

func NewBuilder() *Builder

NewBuilder return a new instance of a Builder.

func (*Builder) Add

func (b *Builder) Add(str string, data int32) error

Add adds a (string, value) pair to the sparse table. Add returns an error iff the added strings are not in byte-wise lexicographical order.

func (*Builder) Build

func (b *Builder) Build() *DFA

Build finishes the building of the automaton and returns it.

type Cell

type Cell struct {
	// contains filtered or unexported fields
}

Cell represents either a final or non-final state cell or transition cell or an empty cell. Cells are used to repesent either transitions or states in a DFA.

func NewFinalCell

func NewFinalCell(data int32, next byte) Cell

NewFinalCell creates a final cell.

func NewNonFinalCell

func NewNonFinalCell(next byte) Cell

NewNonFinalCell creates a non-final cell.

func NewTransitionCell

func NewTransitionCell(target uint32, char byte, next byte) Cell

NewTransitionCell creates a transtion cell

func (Cell) Char

func (c Cell) Char() byte

Char returns the character (byte) that the transition cell represents.

func (Cell) Empty

func (c Cell) Empty() bool

Empty returns true iff the cell is empty.

func (Cell) Final

func (c Cell) Final() (int32, bool)

Final returns the asociated data of the cell and true if the cell represent a final state, Otherwise it returns 0, false.

func (*Cell) GobDecode

func (c *Cell) GobDecode(bs []byte) error

GobDecode decodes a cells from gob.

func (Cell) GobEncode

func (c Cell) GobEncode() ([]byte, error)

GobEncode encodes a cell to gob.

func (Cell) Next

func (c Cell) Next() uint32

Next returns the next transition cell in a states outgoing transitions.

func (Cell) State

func (c Cell) State() bool

State retruns true iff the cell is either a final or a non final state cell.

func (Cell) String

func (c Cell) String() string

String returns a string representation of the cell.

func (Cell) Target

func (c Cell) Target() uint32

Target returns the target position of transition cell.

func (Cell) Transition

func (c Cell) Transition() bool

Transition return true iff the cell represents a transtion.

func (Cell) Type

func (c Cell) Type() CellType

Type returns the type of this cell.

type CellType

type CellType byte

CellType represents the type of a cell.

const (
	EmptyCell CellType = iota
	FinalCell
	NonFinalCell
	TransitionCell
)

There are four types of cells: empty (unused) cells, final state cells, non final state cells and transition cells. Final and non final state cells represent states in the automaton. Transition cells represent transtions between the different states in the automaton.

type DFA

type DFA struct {
	// contains filtered or unexported fields
}

DFA is a DFA implementation using a sparse table.

func NewDictionary

func NewDictionary(strs ...string) *DFA

NewDictionary builds a minimized sparse table DFA from a list of strings. NewDictionary panics if the build process fails.

func (*DFA) CellAt

func (d *DFA) CellAt(s State) Cell

CellAt returns the the cell of the given state.

func (DFA) Delta

func (d DFA) Delta(s State, c byte) State

Delta makes on transition from the given state s with the given byte c.

func (*DFA) EachCell

func (d *DFA) EachCell(f func(Cell))

EachCell calls the given callback function for each cell in the DFA's table.

func (*DFA) EachTransition

func (d *DFA) EachTransition(s State, f func(Cell))

EachTransition iterates over all transitions of the given state calling the callback function f for each transition cell.

func (*DFA) EachUTF8Transition

func (d *DFA) EachUTF8Transition(s State, f func(rune, State))

EachUTF8Transition iterates over all transition of the given state calling the callback function f for each transition. EachUTF8Transition follows UTF8 mutlibyte sequences to ensure that the callback is called for each valid unicode transition.

func (*DFA) Final

func (d *DFA) Final(s State) (int32, bool)

Final returns the (data, true) if the given state is final. If the given state is not final, (0, false) is returned.

func (*DFA) GobDecode

func (d *DFA) GobDecode(bs []byte) error

GobDecode decodes a DFA from gob.

func (*DFA) GobEncode

func (d *DFA) GobEncode() ([]byte, error)

GobEncode encods a DFA to gob.

func (*DFA) Initial

func (d *DFA) Initial() State

Initial returns the initial state of the DFA. The state of the DFA is a simple integer that give the position of the active cell in the DFA's cell table. Values less than 0 mark invalid states.

type FinalStateCallback

type FinalStateCallback func(int, int, int32)

FinalStateCallback is a callback function that is called on final states. It is called using the active error, the next position and the data.

type FuzzyDFA

type FuzzyDFA struct {
	// contains filtered or unexported fields
}

FuzzyDFA is the basic struct for approximate matching on a DFA.

func NewFuzzyDFA

func NewFuzzyDFA(k int, dfa *DFA) *FuzzyDFA

NewFuzzyDFA create a new FuzzyDFA with a given error limit k and a given DFA

func (*FuzzyDFA) Delta

func (d *FuzzyDFA) Delta(f *FuzzyStack, cb FinalStateCallback) bool

Delta make one transtion on the top of the stack. If a final state is encountered, the callback function is called. It returns false if no more transitions can be done with the active stack.

func (*FuzzyDFA) Initial

func (d *FuzzyDFA) Initial(str string) *FuzzyStack

Initial returns the initial active states of the approximate match for str.

func (*FuzzyDFA) MaxError

func (d *FuzzyDFA) MaxError() int

MaxError returns the maximum allowed error for the fuzzy DFA.

type FuzzyStack

type FuzzyStack struct {
	// contains filtered or unexported fields
}

FuzzyStack keeps track of the active states during the apporimxate search.

type SparseTable

type SparseTable struct {
	Cells []Cell
	// contains filtered or unexported fields
}

SparseTable is a sparse table of cells.

func (*SparseTable) Add

func (t *SparseTable) Add(tmp TmpState) uint32

Add adds a temporary state into the sparse table. It returns the absolute position where the state was inserted. The transitions of the temorary state must b sorted.

type State

type State int

State represents a the state of a DFA. It is a simple integer that points to the active state of the DFA's cell table.

func (State) Valid

func (s State) Valid() bool

Valid returns true if the state is still valid.

type TmpState

type TmpState struct {
	Transitions []TmpStateTransition
	Data        int32
	Final       bool
}

TmpState represents a state that should be inerter into a sparse table. It contains a sorted list of

func (TmpState) String

func (t TmpState) String() string

String returns a strin representation for a temporary state. It is used basically for hashing.

type TmpStateTransition

type TmpStateTransition struct {
	// contains filtered or unexported fields
}

TmpStateTransition represent an outgoing transition from a temporary state.

func (TmpStateTransition) String

func (t TmpStateTransition) String() string

String returns a strin representation for a temporary state transition. It is used basically for hashing.