PocketSphinx  5prealpha
ps_lattice_internal.h
Go to the documentation of this file.
1 /* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /* ====================================================================
3  * Copyright (c) 2008 Carnegie Mellon University. All rights
4  * reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  *
18  * This work was supported in part by funding from the Defense Advanced
19  * Research Projects Agency and the National Science Foundation of the
20  * United States of America, and the CMU Sphinx Speech Consortium.
21  *
22  * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
23  * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
24  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
26  * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33  *
34  * ====================================================================
35  *
36  */
37 
42 #ifndef __PS_LATTICE_INTERNAL_H__
43 #define __PS_LATTICE_INTERNAL_H__
44 
53 typedef struct latlink_list_s {
54  ps_latlink_t *link;
55  struct latlink_list_s *next;
57 
61 struct ps_lattice_s {
62  int refcount;
64  logmath_t *lmath;
67  int32 silence;
68  int32 frate;
75  int32 n_nodes;
77  int32 norm;
78  char *hyp_str;
80  listelem_alloc_t *latnode_alloc;
81  listelem_alloc_t *latlink_alloc;
82  listelem_alloc_t *latlink_list_alloc;
84  /* This will probably be replaced with a heap. */
87 };
88 
96 struct ps_latlink_s {
97  struct ps_latnode_s *from;
98  struct ps_latnode_s *to;
99  struct ps_latlink_s *best_prev;
100  int32 ascr;
101  int32 path_scr;
103  int32 alpha;
104  int32 beta;
105 };
106 
113 struct ps_latnode_s {
114  int32 id;
115  int32 wid;
116  int32 basewid;
117  /* FIXME: These are (ab)used to store backpointer indices, therefore they MUST be 32 bits. */
118  int32 fef;
119  int32 lef;
121  int16 reachable;
122  int32 node_id;
123  union {
124  glist_t velist;
125  int32 fanin;
126  int32 rem_score;
127  int32 best_exit;
128  } info;
132  struct ps_latnode_s *alt;
133  struct ps_latnode_s *next;
134 };
135 
139 typedef struct dag_seg_s {
142  int32 norm;
143  int16 n_links;
144  int16 cur;
146 
153 typedef struct ps_latpath_s {
156  struct ps_latpath_s *next;
157  int32 score;
159 
163 typedef struct ps_astar_s {
164  ps_lattice_t *dag;
165  ngram_model_t *lmset;
166  float32 lwf;
167 
168  frame_idx_t sf;
169  frame_idx_t ef;
170  int32 w1;
171  int32 w2;
172 
173  int32 n_hyp_tried;
174  int32 n_hyp_insert;
175  int32 n_hyp_reject;
176  int32 insert_depth;
177  int32 n_path;
178 
179  ps_latpath_t *path_list;
180  ps_latpath_t *path_tail;
181  ps_latpath_t *top;
182 
183  glist_t hyps;
184  listelem_alloc_t *latpath_alloc;
186 
190 typedef struct astar_seg_s {
191  ps_seg_t base;
192  ps_latnode_t **nodes;
193  int n_nodes;
194  int cur;
196 
200 ps_lattice_t *ps_lattice_init_search(ps_search_t *search, int n_frame);
201 
205 void ps_lattice_penalize_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen);
206 
211 
215 void ps_lattice_pushq(ps_lattice_t *dag, ps_latlink_t *link);
216 
221 
225 void ps_lattice_delq(ps_lattice_t *dag);
226 
231  latlink_list_t *next);
232 
236 char const *ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link);
237 
242  float32 lwf);
243 
254  ngram_model_t *lmset,
255  float32 lwf,
256  int sf, int ef,
257  int w1, int w2);
258 
265 
269 void ps_astar_finish(ps_astar_t *nbest);
270 
274 char const *ps_astar_hyp(ps_astar_t *nbest, ps_latpath_t *path);
275 
279 ps_seg_t *ps_astar_seg_iter(ps_astar_t *astar, ps_latpath_t *path, float32 lwf);
280 
281 
282 #endif /* __PS_LATTICE_INTERNAL_H__ */
int32 frame_idx_t
Type for frame index values.
Definition: hmm.h:64
char const * ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link)
Get hypothesis string after bestpath search.
Definition: ps_lattice.c:830
void ps_lattice_pushq(ps_lattice_t *dag, ps_latlink_t *link)
Add an edge to the traversal queue.
Definition: ps_lattice.c:1054
struct dag_seg_s dag_seg_t
Segmentation "iterator" for backpointer table results.
struct ps_astar_s ps_astar_t
A* search structure.
ps_latlink_t * ps_lattice_popq(ps_lattice_t *dag)
Remove an edge from the traversal queue.
Definition: ps_lattice.c:1066
void ps_lattice_penalize_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen)
Insert penalty for fillers.
Definition: ps_lattice.c:106
ps_lattice_t * ps_lattice_init_search(ps_search_t *search, int n_frame)
Construct an empty word graph with reference to a search structure.
Definition: ps_lattice.c:639
ps_latpath_t * ps_astar_next(ps_astar_t *nbest)
Find next best hypothesis of A* on a word graph.
Definition: ps_lattice.c:1771
void ps_lattice_delete_unreachable(ps_lattice_t *dag)
Remove nodes marked as unreachable.
Definition: ps_lattice.c:174
latlink_list_t * latlink_list_new(ps_lattice_t *dag, ps_latlink_t *link, latlink_list_t *next)
Create a new lattice link element.
Definition: ps_lattice.c:1042
struct astar_seg_s astar_seg_t
Segmentation "iterator" for A* search results.
struct ps_latpath_s ps_latpath_t
Partial path structure used in N-best (A*) search.
struct latlink_list_s latlink_list_t
Linked list of DAG link pointers.
ps_astar_t * ps_astar_start(ps_lattice_t *dag, ngram_model_t *lmset, float32 lwf, int sf, int ef, int w1, int w2)
Begin N-Gram based A* search on a word graph.
Definition: ps_lattice.c:1712
void ps_astar_finish(ps_astar_t *nbest)
Finish N-best search, releasing resources associated with it.
Definition: ps_lattice.c:1925
char const * ps_astar_hyp(ps_astar_t *nbest, ps_latpath_t *path)
Get hypothesis string from A* search.
Definition: ps_lattice.c:1804
ps_seg_t * ps_astar_seg_iter(ps_astar_t *astar, ps_latpath_t *path, float32 lwf)
Get hypothesis segmentation from A* search.
Definition: ps_lattice.c:1898
void ps_lattice_delq(ps_lattice_t *dag)
Clear and reset the traversal queue.
Definition: ps_lattice.c:1083
ps_seg_t * ps_lattice_seg_iter(ps_lattice_t *dag, ps_latlink_t *link, float32 lwf)
Get hypothesis segmentation iterator after bestpath search.
Definition: ps_lattice.c:1006
Segmentation "iterator" for A* search results.
Segmentation "iterator" for backpointer table results.
int16 cur
Current position in bpidx.
int16 n_links
Number of lattice links.
int32 norm
Normalizer for posterior probabilities.
ps_latlink_t ** links
Array of lattice links.
ps_seg_t base
Base structure.
a structure for a dictionary.
Definition: dict.h:76
A* search structure.
listelem_alloc_t * latpath_alloc
Path allocator for N-best search.
glist_t hyps
List of hypothesis strings.
latlink_list_t * entries
Links into this node.
frame_idx_t sf
Start frame.
int32 node_id
Node from fsg model, used to map lattice back to model.
latlink_list_t * exits
Links out of this node.
int32 fef
First end frame.
int32 lef
Last end frame.
int32 fanin
Number nodes with links to this node.
int32 id
Unique id for this node.
int32 best_exit
Best exit score (used for final nodes only)
struct ps_latnode_s * alt
Node with alternate pronunciation for this word.
int32 rem_score
Estimated best score from node.sf to end.
struct ps_latnode_s * next
Next node in DAG (no ordering implied)
int32 basewid
Dictionary base word id.
glist_t velist
List of history entries with different lmstate (tst only)
int16 reachable
From.
int32 wid
Dictionary word id.
Partial path structure used in N-best (A*) search.
struct ps_latpath_s * next
Pointer to next path in list of paths.
struct ps_latpath_s * parent
Previous element in this path.
int32 score
Exact score from start node up to node->sf.
ps_latnode_t * node
Node ending this path.
Word graph structure used in bestpath/nbest search.
ps_latnode_t * end
Ending node.
listelem_alloc_t * latnode_alloc
Node allocator for this DAG.
latlink_list_t * q_head
Queue of links for traversal.
logmath_t * lmath
Log-math object.
frame_idx_t n_frames
Number of frames for this utterance.
int32 frate
Frame rate.
latlink_list_t * q_tail
Queue of links for traversal.
ps_latnode_t * start
Starting node.
int32 norm
Normalizer for posterior probabilities.
int refcount
Reference count.
dict_t * dict
Dictionary for this DAG.
ps_latnode_t * nodes
List of all nodes.
listelem_alloc_t * latlink_list_alloc
List element allocator for this DAG.
ps_search_t * search
Search (if generated by search).
int32 final_node_ascr
Acoustic score of implicit link exiting final node.
char * hyp_str
Current hypothesis string.
int32 silence
Silence word ID.
int32 n_nodes
Number of nodes in this lattice.
listelem_alloc_t * latlink_alloc
Link allocator for this DAG.
Base structure for search module.
Base structure for hypothesis segmentation iterator.