fsa

README

* Fsa
Go-package for final state automata (FSA). FSA are represented using a
sparse table. Final states can hold string values and map input
strings to values.

Documentation

Index

• type CompactedTrieBuilder
  • func NewCompactedTrieBuilder(opts ...CompactedTrieBuilderOption) *CompactedTrieBuilder
  • func (b *CompactedTrieBuilder) Add(wf, v string) error
  • func (b *CompactedTrieBuilder) AddToAlphabet(chars string)
  • func (b *CompactedTrieBuilder) Build() (*FSA, error)
  • func (b *CompactedTrieBuilder) Statistics() Statistics
• type CompactedTrieBuilderOption
  • func CompactedTrieWithSeperator(enable bool) CompactedTrieBuilderOption
• type DFANodeBuilder
• type DFAState
  • func Determinize(initial NDFAState, b DFANodeBuilder) DFAState
• type FSA
  • func NewFSAFromNodes(initial DFAState) *FSA
  • func (a *FSA) Data(s uint32) uint32
  • func (a *FSA) Delta(s uint32, c byte) uint32
  • func (a *FSA) GobDecode(buf []byte) error
  • func (a *FSA) GobEncode() ([]byte, error)
  • func (a *FSA) Info(d uint32) string
  • func (a *FSA) Initial() uint32
• type NDFAState
• type Statistics

Types

type CompactedTrieBuilder

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

Builder for compacted tries.

func NewCompactedTrieBuilder

func NewCompactedTrieBuilder(opts ...CompactedTrieBuilderOption) *CompactedTrieBuilder

NewCompactedTrieBuilder creates a new builder that builds a compacted trie.

func (*CompactedTrieBuilder) Add

func (b *CompactedTrieBuilder) Add(wf, v string) error

Add adds a key-value pair to the builder. The resulting automaton then associates key wf with value v.

func (*CompactedTrieBuilder) AddToAlphabet

func (b *CompactedTrieBuilder) AddToAlphabet(chars string)

AddToAlphabet adds all characters (bytes) in str to the builder's internal alphabet.

All characters of keys added to the builder must be added to the alphabet before being added to the builder. The zero character \0 has special meaning and cannot be added to the builder's alphabet.

func (*CompactedTrieBuilder) Build

func (b *CompactedTrieBuilder) Build() (*FSA, error)

Build finishes the building process and returns the CFSA.

func (*CompactedTrieBuilder) Statistics

func (b *CompactedTrieBuilder) Statistics() Statistics

Statistics returns a Statistics struct.

type CompactedTrieBuilderOption

type CompactedTrieBuilderOption func(*CompactedTrieBuilder)

func CompactedTrieWithSeperator

func CompactedTrieWithSeperator(enable bool) CompactedTrieBuilderOption

Enables special handling of ` ` characters in the input strings. If this option is enabled and such a seperator is encountered in an input string, the resulting automaton accepts one or more sequences of ` ` within the accepted strings.

type DFANodeBuilder

type DFANodeBuilder interface {
	NewNode(string) DFAState            // Return a new DFANode instance.
	LinkNodes(DFAState, byte, DFAState) // Link the two nodes together with a specific byte.
}

DFANodeBuilder is used to build and link DFANodes by fsa.Determinize.

type DFAState

type DFAState interface {
	Final() (string, bool)  // Return if the state is final and additional data if the state is final.
	Target(c byte) DFAState // Target for the given transition
}

DFAState represents a state in a DFA. They can be used to construct a FSA instance.

Final states should return their rewrite data in the implementation of the Final() method. If a node has no target transition, nil should be returned.

func Determinize

func Determinize(initial NDFAState, b DFANodeBuilder) DFAState

Determinize determinizes a non-deterministic FSA.

type FSA

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

func NewFSAFromNodes

func NewFSAFromNodes(initial DFAState) *FSA

NewFSAFromNodes creates a new fsa from the given initial state. The function panics if the nodes do not represent a dfa.

func (*FSA) Data

func (a *FSA) Data(s uint32) uint32

Data returns the data of a cell if it is a data state.

func (*FSA) Delta

func (a *FSA) Delta(s uint32, c byte) uint32

Delta executes a transition from s using c and returns the target state. If no transition can be executed, 0 is returned.

func (*FSA) GobDecode

func (a *FSA) GobDecode(buf []byte) error

func (*FSA) GobEncode

func (a *FSA) GobEncode() ([]byte, error)

func (*FSA) Info

func (a *FSA) Info(d uint32) string

Info returns the stored info string for the given data pointer.

func (*FSA) Initial

func (a *FSA) Initial() uint32

Initial returns the inital state for this CFSA.

type NDFAState

type NDFAState interface {
	Final() (string, bool)      // Return if the state is final and additional final data if the state is final.
	Targets(c byte) []NDFAState // Targets for the given transitions.
	ID() uint64                 // The unique id for the node.
}

NDFAState represents a state in a NDFA. They can be used to construct an deterministic automaton and from there be converted into a FSA instance.

Final states should return their rewrite data in the implementation of the Final() method. If a node has no target transition, nil should be returned.

type Statistics

type Statistics struct {
	Words    int // Number of words.
	FreeCell int // Position of the first free cell.
	Cells    int // Number of cells.
	States   int // Number of state cells.
	Empty    int // Number of empty cells.
}

Statistics holds various metrics of the builder.