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;
145 } dag_seg_t;
146 
153 typedef struct ps_latpath_s {
156  struct ps_latpath_s *next;
157  int32 score;
158 } ps_latpath_t;
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;
185 } ps_astar_t;
186 
190 typedef struct astar_seg_s {
191  ps_seg_t base;
192  ps_latnode_t **nodes;
193  int n_nodes;
194  int cur;
195 } astar_seg_t;
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__ */
ps_latnode_s::rem_score
int32 rem_score
Estimated best score from node.sf to end.
Definition: ps_lattice_internal.h:126
ps_latnode_s::wid
int32 wid
Dictionary word id.
Definition: ps_lattice_internal.h:115
frame_idx_t
int32 frame_idx_t
Type for frame index values.
Definition: hmm.h:64
ps_astar_s
A* search structure.
Definition: ps_lattice_internal.h:163
dag_seg_s::n_links
int16 n_links
Number of lattice links.
Definition: ps_lattice_internal.h:143
ps_lattice_seg_iter
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
ps_latnode_s::velist
glist_t velist
List of history entries with different lmstate (tst only)
Definition: ps_lattice_internal.h:124
ps_lattice_s::frate
int32 frate
Frame rate.
Definition: ps_lattice_internal.h:68
ps_latnode_s::alt
struct ps_latnode_s * alt
Node with alternate pronunciation for this word.
Definition: ps_lattice_internal.h:132
dag_seg_s::cur
int16 cur
Current position in bpidx.
Definition: ps_lattice_internal.h:144
ps_lattice_s::latlink_list_alloc
listelem_alloc_t * latlink_list_alloc
List element allocator for this DAG.
Definition: ps_lattice_internal.h:82
ps_lattice_s::refcount
int refcount
Reference count.
Definition: ps_lattice_internal.h:62
ps_latnode_s::fanin
int32 fanin
Number nodes with links to this node.
Definition: ps_lattice_internal.h:125
ps_lattice_s::dict
dict_t * dict
Dictionary for this DAG.
Definition: ps_lattice_internal.h:66
ps_latpath_t
struct ps_latpath_s ps_latpath_t
Partial path structure used in N-best (A*) search.
ps_latnode_s::exits
latlink_list_t * exits
Links out of this node.
Definition: ps_lattice_internal.h:129
ps_latpath_s::score
int32 score
Exact score from start node up to node->sf.
Definition: ps_lattice_internal.h:157
ps_search_s
Base structure for search module.
Definition: pocketsphinx_internal.h:98
ps_lattice_s::search
ps_search_t * search
Search (if generated by search).
Definition: ps_lattice_internal.h:65
ps_seg_s
Base structure for hypothesis segmentation iterator.
Definition: pocketsphinx_internal.h:178
ps_latnode_s::id
int32 id
Unique id for this node.
Definition: ps_lattice_internal.h:114
ps_lattice_s::hyp_str
char * hyp_str
Current hypothesis string.
Definition: ps_lattice_internal.h:78
ps_latnode_s::next
struct ps_latnode_s * next
Next node in DAG (no ordering implied)
Definition: ps_lattice_internal.h:133
dag_seg_s::norm
int32 norm
Normalizer for posterior probabilities.
Definition: ps_lattice_internal.h:142
dag_seg_s
Segmentation "iterator" for backpointer table results.
Definition: ps_lattice_internal.h:139
ps_lattice_penalize_fillers
void ps_lattice_penalize_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen)
Insert penalty for fillers.
Definition: ps_lattice.c:106
ps_lattice_pushq
void ps_lattice_pushq(ps_lattice_t *dag, ps_latlink_t *link)
Add an edge to the traversal queue.
Definition: ps_lattice.c:1054
ps_astar_finish
void ps_astar_finish(ps_astar_t *nbest)
Finish N-best search, releasing resources associated with it.
Definition: ps_lattice.c:1925
ps_latnode_s::entries
latlink_list_t * entries
Links into this node.
Definition: ps_lattice_internal.h:130
ps_astar_s::latpath_alloc
listelem_alloc_t * latpath_alloc
Path allocator for N-best search.
Definition: ps_lattice_internal.h:184
ps_lattice_s::final_node_ascr
int32 final_node_ascr
Acoustic score of implicit link exiting final node.
Definition: ps_lattice_internal.h:76
ps_lattice_popq
ps_latlink_t * ps_lattice_popq(ps_lattice_t *dag)
Remove an edge from the traversal queue.
Definition: ps_lattice.c:1066
dag_seg_t
struct dag_seg_s dag_seg_t
Segmentation "iterator" for backpointer table results.
ps_lattice_hyp
const char * ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link)
Get hypothesis string after bestpath search.
Definition: ps_lattice.c:830
ps_lattice_delete_unreachable
void ps_lattice_delete_unreachable(ps_lattice_t *dag)
Remove nodes marked as unreachable.
Definition: ps_lattice.c:174
ps_latpath_s::parent
struct ps_latpath_s * parent
Previous element in this path.
Definition: ps_lattice_internal.h:155
latlink_list_new
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
ps_lattice_s::latnode_alloc
listelem_alloc_t * latnode_alloc
Node allocator for this DAG.
Definition: ps_lattice_internal.h:80
ps_lattice_init_search
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_lattice_s::lmath
logmath_t * lmath
Log-math object.
Definition: ps_lattice_internal.h:64
ps_lattice_delq
void ps_lattice_delq(ps_lattice_t *dag)
Clear and reset the traversal queue.
Definition: ps_lattice.c:1083
ps_latnode_s::reachable
int16 reachable
From.
Definition: ps_lattice_internal.h:121
ps_latnode_s::basewid
int32 basewid
Dictionary base word id.
Definition: ps_lattice_internal.h:116
ps_lattice_s::n_frames
frame_idx_t n_frames
Number of frames for this utterance.
Definition: ps_lattice_internal.h:74
ps_lattice_s::end
ps_latnode_t * end
Ending node.
Definition: ps_lattice_internal.h:72
ps_lattice_s::start
ps_latnode_t * start
Starting node.
Definition: ps_lattice_internal.h:71
ps_lattice_s::norm
int32 norm
Normalizer for posterior probabilities.
Definition: ps_lattice_internal.h:77
dag_seg_s::base
ps_seg_t base
Base structure.
Definition: ps_lattice_internal.h:140
ps_astar_s::hyps
glist_t hyps
List of hypothesis strings.
Definition: ps_lattice_internal.h:183
ps_astar_hyp
const char * ps_astar_hyp(ps_astar_t *nbest, ps_latpath_t *path)
Get hypothesis string from A* search.
Definition: ps_lattice.c:1804
latlink_list_t
struct latlink_list_s latlink_list_t
Linked list of DAG link pointers.
ps_latnode_s
DAG nodes.
Definition: ps_lattice_internal.h:113
ps_latnode_s::lef
int32 lef
Last end frame.
Definition: ps_lattice_internal.h:119
astar_seg_s
Segmentation "iterator" for A* search results.
Definition: ps_lattice_internal.h:190
ps_lattice_s::latlink_alloc
listelem_alloc_t * latlink_alloc
Link allocator for this DAG.
Definition: ps_lattice_internal.h:81
ps_astar_seg_iter
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
ps_latnode_s::best_exit
int32 best_exit
Best exit score (used for final nodes only)
Definition: ps_lattice_internal.h:127
ps_lattice_s
Word graph structure used in bestpath/nbest search.
Definition: ps_lattice_internal.h:61
ps_lattice_s::nodes
ps_latnode_t * nodes
List of all nodes.
Definition: ps_lattice_internal.h:70
ps_lattice_s::q_tail
latlink_list_t * q_tail
Queue of links for traversal.
Definition: ps_lattice_internal.h:86
dict_t
a structure for a dictionary.
Definition: dict.h:76
ps_latpath_s
Partial path structure used in N-best (A*) search.
Definition: ps_lattice_internal.h:153
ps_latnode_s::fef
int32 fef
First end frame.
Definition: ps_lattice_internal.h:118
ps_lattice_s::n_nodes
int32 n_nodes
Number of nodes in this lattice.
Definition: ps_lattice_internal.h:75
ps_lattice_s::q_head
latlink_list_t * q_head
Queue of links for traversal.
Definition: ps_lattice_internal.h:85
dag_seg_s::links
ps_latlink_t ** links
Array of lattice links.
Definition: ps_lattice_internal.h:141
ps_latpath_s::next
struct ps_latpath_s * next
Pointer to next path in list of paths.
Definition: ps_lattice_internal.h:156
ps_astar_next
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
ps_lattice_s::silence
int32 silence
Silence word ID.
Definition: ps_lattice_internal.h:67
ps_astar_start
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
ps_latnode_s::sf
frame_idx_t sf
Start frame.
Definition: ps_lattice_internal.h:120
ps_latnode_s::node_id
int32 node_id
Node from fsg model, used to map lattice back to model.
Definition: ps_lattice_internal.h:122
ps_latpath_s::node
ps_latnode_t * node
Node ending this path.
Definition: ps_lattice_internal.h:154
astar_seg_t
struct astar_seg_s astar_seg_t
Segmentation "iterator" for A* search results.
ps_astar_t
struct ps_astar_s ps_astar_t
A* search structure.