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 Cell
  • func MkCell(c byte, d uint32, isdata bool) Cell
  • func (c Cell) Char() byte
  • func (c Cell) Data() uint32
  • func (c Cell) Empty() bool
  • func (c Cell) IsData() bool
• 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 DFAState
  • func Determine(initial NDFAState, factory DFAStateFactory) (DFAState, error)
• type DFAStateFactory
• type FSA
  • func NewFSAFromDFA(initial DFAState) (*FSA, error)
  • 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 Cell

type Cell uint64

Cell represents a states / transitions in the table.

Cells are 64 bit unsigned integers with the following layout: 23 bit unused | 1 bit data marker | 8 bit character | 32 bit data

func MkCell

func MkCell(c byte, d uint32, isdata bool) Cell

MkCell creates a new cell. If isdata is true, a state-cell is created. Otherwise a transition-cell with the given character and target state is created. TODO: Check if it is correct to set c for data/state-cells.

func (Cell) Char

func (c Cell) Char() byte

Char returns the character of the transition-cell.

func (Cell) Data

func (c Cell) Data() uint32

Data returns the target state of a transition-cell or the target info string of a state-cell (if not 0).

func (Cell) Empty

func (c Cell) Empty() bool

Empty returns if a cell is empty (is equal to 0).

func (Cell) IsData

func (c Cell) IsData() bool

IsData returns if the cell is a data- or a transition-cell. TODO: Rename to State().

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)

CompactedTrieBuilderOptions defines options

func CompactedTrieWithSeperator

func CompactedTrieWithSeperator(enable bool) CompactedTrieBuilderOption

CompactedTrieWithSeperator enables/disables 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 DFAState

type DFAState interface {
	Final() (string, bool) // Return if the state is final and additional data if the state is final.
	Target(byte) DFAState  // Target for the given transition or nil for nonexistent transitions.
	LinkTo(byte, DFAState) // Link this state to a target state.
}

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 Determine

func Determine(initial NDFAState, factory DFAStateFactory) (DFAState, error)

Determine determines a non-deterministic FSA. The function returns the initial state of the resulting DFA and any errors encountered.

type DFAStateFactory

type DFAStateFactory interface {
	New(final bool, data string) DFAState // Create a new (non-) final state.
}

DFAStateFactory is used to create DFANodes. If `final` is true, data denotes the new state's final data, otherwise data should be ignored.

type FSA

type FSA struct {
	Infos []byte       // Holds the rewrite strings (null-terminated).
	Cells []Cell       // Cells of the automaton.
	Codec [nchars]byte // Codec maps -> external bytes to internal bytes.
}

func NewFSAFromDFA

func NewFSAFromDFA(initial DFAState) (*FSA, error)

NewFSAFromDFA creates a new fsa from a DFA with the given initial state. The function returns an error if the given nodes do not represent a valid 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 final.
	Targets(c byte) []NDFAState // Targets for the given transitions.
	ID() uint64                 // The unique id for this node.
}

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

Final states should return their rewrite data in the implementation of the Final() method. If a node has no target transition, nil (or an empty array) should be returned. Each distinct NDFAState must return a unique id with it's ID() method.

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.