1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
/*=============================================================================*\
* File: gfsmLookup.h
* Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
* Description: finite state machine library
*
* Copyright (c) 2005-2007 Bryan Jurish.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*=============================================================================*/
/** \file gfsmLookup.h
* \brief Linear composition
*/
#ifndef _GFSM_LOOKUP_H
#define _GFSM_LOOKUP_H
#include <gfsmAutomaton.h>
#include <gfsmUtils.h>
/*======================================================================
* Types: lookup
*/
/** \brief Type for gfsm_automaton_lookup() computation state */
typedef struct {
gfsmStateId qt; /**< current state in transducer */
gfsmStateId qr; /**< current state in result acceptor */
guint32 i; /**< current position in input vector */
} gfsmLookupConfig;
//------------------------------
/** Type for gfsm_automaton_lookup_viterbi(): Trellis (1 per call) */
typedef GPtrArray gfsmViterbiTable;
/** Viterbi algorithm best-successor accumulator
* \arg key is a gfsmStateId (state in fst)
* \arg value is a gfsmStateId (state in trellis)
*/
typedef GTree gfsmViterbiMap;
/** Key type for gfsmViterbiMap (state-id in fst) */
typedef gfsmStateId gfsmViterbiMapKey;
/** Value type for gfsmViterbiMap (state-id in trellis) */
typedef gfsmStateId gfsmViterbiMapValue;
/** Type for Viterbi trellis column (1 per input index)
* \arg data is a gfsmStateId in trellis automaton
*/
typedef GSList gfsmViterbiColumn;
/** Type for Viterbi trellis nodes: state in trellis automaton
* \arg state \a q has exactly one outgoing arc \a arc=((gfsmArc*)a->ars->data)
* \arg best preceeding state in trellis is \a arc->target
* \arg label of best arc from best preceeding state in trellis is \a arc->lower
* \arg total weight of best path to this state is \a arc->weight
*/
typedef gfsmState gfsmViterbiNode;
/*======================================================================
* Constants
*/
/** Number of states to pre-allocate when extending state-map vector on lookup_full() (>= 1) */
extern const gfsmStateId gfsmLookupStateMapGet;
/*======================================================================
* Methods: lookup
*/
///\name Lookup
//@{
//------------------------------
/** Compose linear automaton specified by \a input with the transducer
* \a fst , storing result in \a result.
* \param fst transducer (lower-upper)
* \param input input labels (lower)
* \param result output transducer or NULL
* \returns \a result if non-NULL, otherwise a new automaton.
*/
#define gfsm_automaton_lookup(fst,input,result) \
gfsm_automaton_lookup_full((fst),(input),(result),NULL)
//------------------------------
/** Compose linear automaton specified by \a input with the transducer
* \a fst , storing result in \a result , and storing state-translation map \a statemap.
* \param fst transducer (lower-upper)
* \param input input labels (lower)
* \param result output transducer or NULL
* \param statemap if non-NULL, maps \a result StateIds (indices) to \a fst StateIds (values) on return.
* Not implicitly created or cleared.
* \returns \a result if non-NULL, otherwise a new automaton.
*/
gfsmAutomaton *gfsm_automaton_lookup_full(gfsmAutomaton *fst,
gfsmLabelVector *input,
gfsmAutomaton *result,
gfsmStateIdVector *statemap);
//@}
/*======================================================================
* Methods: Viterbi
*/
///\name Viterbi Lookup
//@{
//------------------------------
/** Get the best path for input \a input in the transducer \a fst using the Viterbi algorithm.
* \param fst transducer (lower-upper)
* \param input input labels (lower)
* \param trellis output fsm or NULL
* \returns \a trellis if non-NULL, otherwise a new automaton representing the (reversed) Viterbi trellis.
* \arg labels (lower & upper) in \a trellis represent upper labels of \a fst
* \arg arc-weights in \a trellis represent Viterbi algorithm weights (gamma)
* \arg arc-targets in \a trellis represent the best preceeding state (psi)
*/
#define gfsm_automaton_lookup_viterbi(fst,input,trellis) \
gfsm_automaton_lookup_viterbi_full((fst),(input),(trellis),NULL)
//------------------------------
/** Get the best path for input \a input in the transducer \a fst using the Viterbi algorithm.
* \param fst transducer (lower-upper)
* \param input input labels (lower)
* \param trellis output fsm or NULL
* \param trellis2fst if non-NULL, maps \a trellis StateIds (indices) to \a fst StateIds (values) on return.
* If NULL, a temporary vector will be created & freed.
* \returns \a trellis if non-NULL, otherwise a new automaton representing the (reversed) Viterbi trellis.
* \arg lower-labels in \a trellis represent \a input labels
* \arg upper-labels of \a trellis represent upper labels of \a fst
* \arg arc-weights in \a trellis represent Viterbi algorithm weights (gamma)
* \arg arc-targets in \a trellis represent the best preceeding state (psi)
* \arg root state of \a trellis has arcs sorted by total path weight (best-first)
*/
gfsmAutomaton *gfsm_automaton_lookup_viterbi_full(gfsmAutomaton *fst,
gfsmLabelVector *input,
gfsmAutomaton *trellis,
gfsmStateIdVector *trellis2fst);
//@}
/*======================================================================
* Viterbi: Utilities
*/
///\name Viterbi Low-level Utilities
//@{
//------------------------------
// expand_column()
/** Expand lower-epsilon arcs from \a fst into \a col. */
void _gfsm_viterbi_expand_column(gfsmAutomaton *fst,
gfsmAutomaton *trellis,
gfsmViterbiColumn *col,
gfsmStateIdVector *trellis2fst,
gfsmViterbiMap *fst2trellis);
//------------------------------
// gfsmViterbiMap
/** Create a new gfsmViterbiMap */
#define gfsm_viterbi_map_new() \
g_tree_new_full((GCompareDataFunc)gfsm_uint_compare, NULL, NULL, NULL)
/** Free a gfsmViterbiMap */
#define gfsm_viterbi_map_free(vmap) g_tree_destroy(vmap)
/** Lookup stored value in a gfsmViterbiColumnMap
* \returns gpointer to the stored value for \a key in \a vmap
*/
#define gfsm_viterbi_map_lookup(vmap,key) g_tree_lookup((vmap),(key))
/** Insert a literal value into a gfsmViterbiColumnMap */
#define gfsm_viterbi_map_insert(vmap,key,val) g_tree_insert((vmap),(gpointer)(key),(gpointer)(val))
//------------------------------
// gfsmViterbiNode
/** gfsmViterbiNode: Accessor: unique outgoing arc for \a nod */
//#define gfsm_viterbi_node_arc(nod) ((gfsmArc*)((nod)->arcs->data))
#define gfsm_viterbi_node_arc(nod) gfsm_arclist_arc((nod)->arcs)
/** gfsmViterbiNode: Accessor: Best preceeding state accessor for \a nod */
#define gfsm_viterbi_node_best_prevstate(nod) gfsm_viterbi_node_arc(nod)->target
/** gfsmViterbiNode: Accessor: Total weight of best path to \a nod */
#define gfsm_viterbi_node_best_weight(nod) gfsm_viterbi_node_arc(nod)->weight
//@}
#endif /* _GFSM_LOOKUP_H */
|
