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
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
|
/*=============================================================================*\
* File: gfsmPaths.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 gfsmPaths.h
* \brief Path discovery & enumeration
*/
#ifndef _GFSM_PATHS_H
#define _GFSM_PATHS_H
#include <gfsmAutomaton.h>
/*======================================================================
* Types: paths
*/
/// Type for an automaton path
typedef struct {
gfsmLabelVector *lo; /**< lower label sequence */
gfsmLabelVector *hi; /**< upper label sequence */
gfsmWeight w; /**< weight attached to this path */
} gfsmPath;
/*======================================================================
* Methods: Path Utilities
*/
///\name Path Utilities
//@{
//------------------------------
/** Copy gfsmLabelVector. \returns \a dst */
gfsmLabelVector *gfsm_label_vector_copy(gfsmLabelVector *dst, gfsmLabelVector *src);
/** Duplicate a gfsmLabelVector. \returns \a dst */
#define gfsm_label_vector_dup(src) \
gfsm_label_vector_copy(g_ptr_array_sized_new(src->len), src)
/** Reverse a gfsmLabelVector. \returns \a v */
gfsmLabelVector *gfsm_label_vector_reverse(gfsmLabelVector *v);
//------------------------------
/** Create and return a new gfsmPath, specifying components
* If either of \a lo or \a hi are NULL, a new vector will be created.
*/
gfsmPath *gfsm_path_new_full(gfsmLabelVector *lo, gfsmLabelVector *hi, gfsmWeight w);
/** Create and return a new empty gfsmPath, specifying semiring. */
#define gfsm_path_new(sr) \
gfsm_path_new_full(NULL,NULL,gfsm_sr_one(sr))
/** Create and return a new gfsmPath as a copy of an existing gfsmPath */
gfsmPath *gfsm_path_new_copy(gfsmPath *p1);
/** Create and return a new gfsmPath, appending to an existing path */
gfsmPath *gfsm_path_new_append(gfsmPath *p1, gfsmLabelVal lo, gfsmLabelVal hi, gfsmWeight w, gfsmSemiring *sr);
/** Create and return a new gfsmPath as a copy of an existing gfsmPath with weight multiplied by \a w */
gfsmPath *gfsm_path_new_times_w(gfsmPath *p1, gfsmWeight w, gfsmSemiring *sr);
/** Append an arc to a gfsmPath */
void gfsm_path_push(gfsmPath *p, gfsmLabelVal lo, gfsmLabelVal hi, gfsmWeight w, gfsmSemiring *sr);
/** Pop an arc from a gfsmPath */
void gfsm_path_pop(gfsmPath *p, gfsmLabelVal lo, gfsmLabelVal hi);
/** 3-way path comparison function. */
gint gfsm_path_compare_data(const gfsmPath *p1, const gfsmPath *p2, gfsmSemiring *sr);
/** Reverse a gfsmPath */
gfsmPath *gfsm_path_reverse(gfsmPath *p);
/** Destroy a gfsmPath */
void gfsm_path_free(gfsmPath *p);
//@}
/*======================================================================
* Methods: Automaton Serialization
*/
///\name Automaton Serialization
//@{
//------------------------------
/** Serialize a gfsmAutomaton to a set of (gfsmPath*)s.
* Really just a wrapper for gfsm_automaton_paths_full()
*
* \param fsm Acyclic automaton to be serializd
* \param paths output set or NULL
*
* \returns \a paths if non-NULL, otherwise a new gfsmSet*.
*/
gfsmSet *gfsm_automaton_paths(gfsmAutomaton *fsm, gfsmSet *paths);
/** Serialize a gfsmAutomaton to a set of (gfsmPath*)s.
*
* Causes deep recursion for cyclic automata.
* Returns a gfsmSet whose elements are (gfsmPath*)s.
* allocated with g_new(). It is the caller's responsibility to free the
* returned objects.
*
* \param fsm Acyclic automaton to be serializd
* \param which Which side of arc-labels to serialize
* \param paths output set or NULL
*
* \returns \a paths if non-NULL, otherwise a new gfsmSet*.
*/
gfsmSet *gfsm_automaton_paths_full(gfsmAutomaton *fsm, gfsmSet *paths, gfsmLabelSide which);
/** Recursive guts for gfsm_automaton_paths() */
gfsmSet *_gfsm_automaton_paths_r(gfsmAutomaton *fsm,
gfsmSet *paths,
gfsmLabelSide which,
gfsmStateId q,
gfsmPath *path);
//------------------------------
/** Convert a gfsmPathSet to a list of (char*)s.
* \a abet_lo and \a abet_hi should be (gfsmStringAlphabet*)s.
*/
GSList *gfsm_paths_to_strings(gfsmSet *paths,
gfsmAlphabet *abet_lo,
gfsmAlphabet *abet_hi,
gfsmSemiring *sr,
gboolean warn_on_undefined,
gboolean att_style,
GSList *strings);
/** \brief Utility struct for gfsm_paths_to_strings() */
typedef struct gfsmPathsToStringsOptions_ {
gfsmAlphabet *abet_lo; ///< should be a gfsmStringAlphabet*
gfsmAlphabet *abet_hi; ///< should be a gfsmStringAlphabet*
gfsmSemiring *sr; ///< semiring for weight-based set sorting
gboolean warn_on_undefined; ///< warn on undefined symbols?
gboolean att_style; ///< use ATT-style output?
GSList *strings; ///< output list
} gfsmPathsToStringsOptions;
/** backwards compatible type alias */
#define _gfsm_paths_to_strings_options gfsmPathsToStringsOptions_
/** Utility for gfsm_paths_to_strings() */
gboolean _gfsm_paths_to_strings_foreach_func(gfsmPath *path,
gpointer value_dummy,
gfsmPathsToStringsOptions *opts);
/** Append string for a single gfsmPath* to a GString,
* which may be NULL to allocate a new string.
* \returns \a gs if non-NULL, otherwise a new GString*.
* \warning it is the caller's responsibility to free the returned GString*.
*/
GString *gfsm_path_to_gstring(gfsmPath *path,
GString *gs,
gfsmAlphabet *abet_lo,
gfsmAlphabet *abet_hi,
gfsmSemiring *sr,
gboolean warn_on_undefined,
gboolean att_style);
/** Allocate and return a new string (char*) for a single gfsmPath*.
* \returns new (char*) representing \a path.
* \warning it is the callers responsibility to free the returned \a char*.
*/
char *gfsm_path_to_string(gfsmPath *path,
gfsmAlphabet *abet_lo,
gfsmAlphabet *abet_hi,
gfsmSemiring *sr,
gboolean warn_on_undefined,
gboolean att_style);
//------------------------------
/** Extract upper side of all paths from a Viterbi trellis.
*
* Returns a gfsmSet whose elements are (gfsmPath*)s.
* allocated with g_new(). It is the caller's responsibility to free the
* returned objects.
*
* \returns \a paths if non-NULL, otherwise a new gfsmSet*.
*/
#define gfsm_viterbi_trellis_paths(trellis,paths) \
gfsm_viterbi_trellis_paths_full((trellis),(paths),gfsmLSUpper)
/** Extract all paths from a Viterbi trellis.
*
* Returns a gfsmSet whose elements are (gfsmPath*)s.
* allocated with g_new(). It is the caller's responsibility to free the
* returned objects.
*
* \returns \a paths if non-NULL, otherwise a new gfsmSet*.
*/
gfsmSet *gfsm_viterbi_trellis_paths_full(gfsmAutomaton *trellis, gfsmSet *paths, gfsmLabelSide which);
/** Extract the upper-side of the best path from a Viterbi trellis.
* \returns \a path if non-NULL, otherwise a new gfsmPath*.
*/
#define gfsm_viterbi_trellis_bestpath(trellis,path) \
gfsm_viterbi_trellis_bestpath_full((trellis),(path),gfsmLSUpper)
/** Extract the best path from a Viterbi trellis.
* \returns \a path if non-NULL, otherwise a new gfsmPath*.
*/
gfsmPath *gfsm_viterbi_trellis_bestpath_full(gfsmAutomaton *trellis, gfsmPath *path, gfsmLabelSide which);
/** Guts for gfsm_viterbi_trellis_*path*() */
void _gfsm_viterbi_trellis_bestpath_r(gfsmAutomaton *trellis,
gfsmPath *path,
gfsmLabelSide which,
gfsmStateId qid);
//@}
#endif /* _GFSM_PATHS_H */
|
