linear (string) composition More...

#include <gfsmAutomaton.h>
#include <gfsmUtils.h>

Include dependency graph for gfsmLookup.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	gfsmLookupConfig
	Type for gfsm_automaton_lookup() computation state. More...

Typedefs
typedef GPtrArray	gfsmViterbiTable
typedef GTree	gfsmViterbiMap
typedef gfsmStateId	gfsmViterbiMapKey
typedef gfsmStateId	gfsmViterbiMapValue
typedef GSList	gfsmViterbiColumn
typedef gfsmState	gfsmViterbiNode

Variables
const gfsmStateId	gfsmLookupStateMapGet
const gfsmStateId	gfsmLookupMaxResultStates

Lookup
#define	gfsm_automaton_lookup(fst, input, result) gfsm_automaton_lookup_full((fst),(input),(result),NULL,gfsmLookupMaxResultStates)
gfsmAutomaton *	gfsm_automaton_lookup_full (gfsmAutomaton fst, gfsmLabelVector input, gfsmAutomaton result, gfsmStateIdVector statemap, gfsmStateId max_result_states)

Viterbi Lookup
#define	gfsm_automaton_lookup_viterbi(fst, input, trellis) gfsm_automaton_lookup_viterbi_full((fst),(input),(trellis),NULL)
gfsmAutomaton *	gfsm_automaton_lookup_viterbi_full (gfsmAutomaton fst, gfsmLabelVector input, gfsmAutomaton trellis, gfsmStateIdVector trellis2fst)

Viterbi Low-level Utilities
#define	gfsm_viterbi_map_new() g_tree_new_full((GCompareDataFunc)gfsm_uint_compare, NULL, NULL, NULL)
#define	gfsm_viterbi_map_free(vmap) g_tree_destroy(vmap)
#define	gfsm_viterbi_map_lookup(vmap, key) g_tree_lookup((vmap),(key))
#define	gfsm_viterbi_map_insert(vmap, key, val) g_tree_insert((vmap),(gpointer)(key),(gpointer)(val))
#define	gfsm_viterbi_node_arc(nod) gfsm_arclist_arc((nod)->arcs)
#define	gfsm_viterbi_node_best_prevstate(nod) gfsm_viterbi_node_arc(nod)->target
#define	gfsm_viterbi_node_best_weight(nod) gfsm_viterbi_node_arc(nod)->weight
void	_gfsm_viterbi_expand_column (gfsmAutomaton fst, gfsmAutomaton trellis, gfsmViterbiColumn col, gfsmStateIdVector trellis2fst, gfsmViterbiMap *fst2trellis)

Detailed Description

Macro Definition Documentation

#define gfsm_automaton_lookup	(	fst,
		input,
		result
	)	gfsm_automaton_lookup_full((fst),(input),(result),NULL,gfsmLookupMaxResultStates)

Compose string automaton specified by input with the transducer fst , storing result in result.

Parameters

fst	transducer (lower-upper)
input	input labels (lower)
result	output transducer or NULL

Returns: result if non-NULL, otherwise a new automaton.

#define gfsm_automaton_lookup_viterbi	(	fst,
		input,
		trellis
	)	gfsm_automaton_lookup_viterbi_full((fst),(input),(trellis),NULL)

Get the best path for input input in the transducer fst using the Viterbi algorithm.

Parameters

fst	transducer (lower-upper)
input	input labels (lower)
trellis	output fsm or NULL

Returns

trellis if non-NULL, otherwise a new automaton representing the (reversed) Viterbi trellis.

labels (lower & upper) in trellis represent upper labels of fst
arc-weights in trellis represent Viterbi algorithm weights (gamma)
arc-targets in trellis represent the best preceeding state (psi)

#define gfsm_viterbi_map_new ( ) g_tree_new_full((GCompareDataFunc)gfsm_uint_compare, NULL, NULL, NULL)

Create a new gfsmViterbiMap

#define gfsm_viterbi_map_free ( vmap ) g_tree_destroy(vmap)

Free a gfsmViterbiMap

#define gfsm_viterbi_map_lookup	(	vmap,
		key
	)	g_tree_lookup((vmap),(key))

Lookup stored value in a gfsmViterbiColumnMap

Returns: gpointer to the stored value for key in vmap

#define gfsm_viterbi_map_insert	(	vmap,
		key,
		val
	)	g_tree_insert((vmap),(gpointer)(key),(gpointer)(val))

Insert a literal value into a gfsmViterbiColumnMap

#define gfsm_viterbi_node_arc ( nod ) gfsm_arclist_arc((nod)->arcs)

gfsmViterbiNode: Accessor: unique outgoing arc for nod

#define gfsm_viterbi_node_best_prevstate ( nod ) gfsm_viterbi_node_arc(nod)->target

gfsmViterbiNode: Accessor: Best preceeding state accessor for nod

#define gfsm_viterbi_node_best_weight ( nod ) gfsm_viterbi_node_arc(nod)->weight

gfsmViterbiNode: Accessor: Total weight of best path to nod

Typedef Documentation

typedef GPtrArray gfsmViterbiTable

Type for gfsm_automaton_lookup_viterbi(): Trellis (1 per call)

typedef GTree gfsmViterbiMap

Viterbi algorithm best-successor accumulator

key is a gfsmStateId (state in fst)
value is a gfsmStateId (state in trellis)

typedef gfsmStateId gfsmViterbiMapKey

Key type for gfsmViterbiMap (state-id in fst)

typedef gfsmStateId gfsmViterbiMapValue

Value type for gfsmViterbiMap (state-id in trellis)

typedef GSList gfsmViterbiColumn

Type for Viterbi trellis column (1 per input index)

data is a gfsmStateId in trellis automaton

typedef gfsmState gfsmViterbiNode

Type for Viterbi trellis nodes: state in trellis automaton

state q has exactly one outgoing arc arc=((gfsmArc*)a->ars->data)
best preceeding state in trellis is arc->target
label of best arc from best preceeding state in trellis is arc->lower
total weight of best path to this state is arc->weight

Function Documentation

gfsmAutomaton* gfsm_automaton_lookup_full	(	gfsmAutomaton *	fst,
		gfsmLabelVector *	input,
		gfsmAutomaton *	result,
		gfsmStateIdVector *	statemap,
		gfsmStateId	max_result_states
	)

Compose string automaton specified by input with the transducer fst , storing result in result , and storing state-translation map statemap.

Parameters

fst	transducer (lower-upper)
input	input labels (lower)
result	output transducer or NULL
statemap	if non-NULL, maps result StateIds (indices) to fst StateIds (values) on return. Not implicitly created or cleared.

Returns: result if non-NULL, otherwise a new automaton.

gfsmAutomaton* gfsm_automaton_lookup_viterbi_full	(	gfsmAutomaton *	fst,
		gfsmLabelVector *	input,
		gfsmAutomaton *	trellis,
		gfsmStateIdVector *	trellis2fst
	)

Get the best path for input input in the transducer fst using the Viterbi algorithm.

Parameters

fst	transducer (lower-upper)
input	input labels (lower)
trellis	output fsm or NULL
trellis2fst	if non-NULL, maps trellis StateIds (indices) to fst StateIds (values) on return. If NULL, a temporary vector will be created & freed.

Returns

trellis if non-NULL, otherwise a new automaton representing the (reversed) Viterbi trellis.

lower-labels in trellis represent input labels
upper-labels of trellis represent upper labels of fst
arc-weights in trellis represent Viterbi algorithm weights (gamma)
arc-targets in trellis represent the best preceeding state (psi)
root state of trellis has arcs sorted by total path weight (best-first)

void _gfsm_viterbi_expand_column	(	gfsmAutomaton *	fst,
		gfsmAutomaton *	trellis,
		gfsmViterbiColumn *	col,
		gfsmStateIdVector *	trellis2fst,
		gfsmViterbiMap *	fst2trellis
	)

Expand lower-epsilon arcs from fst into col.

Variable Documentation

const gfsmStateId gfsmLookupStateMapGet

Number of states to pre-allocate when extending state-map vector on lookup_full() (>= 1)

const gfsmStateId gfsmLookupMaxResultStates

Default maximum number of result states for lookup

Data Structures

Typedefs

Variables

Lookup

Viterbi Lookup

Viterbi Low-level Utilities

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation