ps_lattice_internal.h
Go to the documentation of this file.
/* -*- c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* ====================================================================
* Copyright (c) 2008 Carnegie Mellon University. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* This work was supported in part by funding from the Defense Advanced
* Research Projects Agency and the National Science Foundation of the
* United States of America, and the CMU Sphinx Speech Consortium.
*
* THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
* ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
* NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* ====================================================================
*
*/
#ifndef __PS_LATTICE_INTERNAL_H__
#define __PS_LATTICE_INTERNAL_H__
typedef struct latlink_list_s {
ps_latlink_t *link;
struct latlink_list_s *next;
} latlink_list_t;
struct ps_lattice_s {
int refcount;
logmath_t *lmath;
ps_search_t *search;
dict_t *dict;
int32 silence;
int32 frate;
ps_latnode_t *nodes;
ps_latnode_t *start;
ps_latnode_t *end;
frame_idx_t n_frames;
int32 n_nodes;
int32 final_node_ascr;
int32 norm;
char *hyp_str;
listelem_alloc_t *latnode_alloc;
listelem_alloc_t *latlink_alloc;
listelem_alloc_t *latlink_list_alloc;
/* This will probably be replaced with a heap. */
latlink_list_t *q_head;
latlink_list_t *q_tail;
};
struct ps_latlink_s {
struct ps_latnode_s *from;
struct ps_latnode_s *to;
struct ps_latlink_s *best_prev;
int32 ascr;
int32 path_scr;
frame_idx_t ef;
int32 alpha;
int32 beta;
};
struct ps_latnode_s {
int32 id;
int32 wid;
int32 basewid;
/* FIXME: These are (ab)used to store backpointer indices, therefore they MUST be 32 bits. */
int32 fef;
int32 lef;
frame_idx_t sf;
int16 reachable;
int32 node_id;
union {
glist_t velist;
int32 fanin;
int32 rem_score;
int32 best_exit;
} info;
latlink_list_t *exits;
latlink_list_t *entries;
struct ps_latnode_s *alt;
struct ps_latnode_s *next;
};
typedef struct dag_seg_s {
ps_seg_t base;
ps_latlink_t **links;
int32 norm;
int16 n_links;
int16 cur;
} dag_seg_t;
typedef struct ps_latpath_s {
ps_latnode_t *node;
struct ps_latpath_s *parent;
struct ps_latpath_s *next;
int32 score;
} ps_latpath_t;
typedef struct ps_astar_s {
ps_lattice_t *dag;
ngram_model_t *lmset;
float32 lwf;
frame_idx_t sf;
frame_idx_t ef;
int32 w1;
int32 w2;
int32 n_hyp_tried;
int32 n_hyp_insert;
int32 n_hyp_reject;
int32 insert_depth;
int32 n_path;
ps_latpath_t *path_list;
ps_latpath_t *path_tail;
ps_latpath_t *top;
glist_t hyps;
listelem_alloc_t *latpath_alloc;
} ps_astar_t;
typedef struct astar_seg_s {
ps_seg_t base;
ps_latnode_t **nodes;
int n_nodes;
int cur;
} astar_seg_t;
ps_lattice_t *ps_lattice_init_search(ps_search_t *search, int n_frame);
void ps_lattice_penalize_fillers(ps_lattice_t *dag, int32 silpen, int32 fillpen);
void ps_lattice_delete_unreachable(ps_lattice_t *dag);
void ps_lattice_pushq(ps_lattice_t *dag, ps_latlink_t *link);
ps_latlink_t *ps_lattice_popq(ps_lattice_t *dag);
void ps_lattice_delq(ps_lattice_t *dag);
latlink_list_t *latlink_list_new(ps_lattice_t *dag, ps_latlink_t *link,
latlink_list_t *next);
char const *ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link);
ps_seg_t *ps_lattice_seg_iter(ps_lattice_t *dag, ps_latlink_t *link,
float32 lwf);
ps_astar_t *ps_astar_start(ps_lattice_t *dag,
ngram_model_t *lmset,
float32 lwf,
int sf, int ef,
int w1, int w2);
ps_latpath_t *ps_astar_next(ps_astar_t *nbest);
void ps_astar_finish(ps_astar_t *nbest);
char const *ps_astar_hyp(ps_astar_t *nbest, ps_latpath_t *path);
ps_seg_t *ps_astar_seg_iter(ps_astar_t *astar, ps_latpath_t *path, float32 lwf);
#endif /* __PS_LATTICE_INTERNAL_H__ */
frame_idx_t
int32 frame_idx_t
Type for frame index values.
Definition: hmm.h:64
ps_lattice_hyp
char const * ps_lattice_hyp(ps_lattice_t *dag, ps_latlink_t *link)
Get hypothesis string after bestpath search.
Definition: ps_lattice.c:830
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
dag_seg_t
struct dag_seg_s dag_seg_t
Segmentation "iterator" for backpointer table results.
ps_astar_t
struct ps_astar_s ps_astar_t
A* search structure.
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
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_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_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_delete_unreachable
void ps_lattice_delete_unreachable(ps_lattice_t *dag)
Remove nodes marked as unreachable.
Definition: ps_lattice.c:174
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
astar_seg_t
struct astar_seg_s astar_seg_t
Segmentation "iterator" for A* search results.
ps_latpath_t
struct ps_latpath_s ps_latpath_t
Partial path structure used in N-best (A*) search.
latlink_list_t
struct latlink_list_s latlink_list_t
Linked list of DAG link pointers.
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_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_astar_hyp
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_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_lattice_delq
void ps_lattice_delq(ps_lattice_t *dag)
Clear and reset the traversal queue.
Definition: ps_lattice.c:1083
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
astar_seg_s
Segmentation "iterator" for A* search results.
Definition: ps_lattice_internal.h:190
dag_seg_s
Segmentation "iterator" for backpointer table results.
Definition: ps_lattice_internal.h:139
dag_seg_s::cur
int16 cur
Current position in bpidx.
Definition: ps_lattice_internal.h:144
dag_seg_s::n_links
int16 n_links
Number of lattice links.
Definition: ps_lattice_internal.h:143
dag_seg_s::norm
int32 norm
Normalizer for posterior probabilities.
Definition: ps_lattice_internal.h:142
dag_seg_s::links
ps_latlink_t ** links
Array of lattice links.
Definition: ps_lattice_internal.h:141
dag_seg_s::base
ps_seg_t base
Base structure.
Definition: ps_lattice_internal.h:140
dict_t
a structure for a dictionary.
Definition: dict.h:76
latlink_list_s
Linked list of DAG link pointers.
Definition: ps_lattice_internal.h:53
ps_astar_s
A* search structure.
Definition: ps_lattice_internal.h:163
ps_astar_s::latpath_alloc
listelem_alloc_t * latpath_alloc
Path allocator for N-best search.
Definition: ps_lattice_internal.h:184
ps_astar_s::hyps
glist_t hyps
List of hypothesis strings.
Definition: ps_lattice_internal.h:183
ps_latlink_s
Links between DAG nodes.
Definition: ps_lattice_internal.h:96
ps_latlink_s::beta
int32 beta
Backward probability of this link P(w|o_{ef+1}^T)
Definition: ps_lattice_internal.h:104
ps_latlink_s::ef
frame_idx_t ef
Ending frame of this word
Definition: ps_lattice_internal.h:102
ps_latlink_s::path_scr
int32 path_scr
Best path score from root of DAG.
Definition: ps_lattice_internal.h:101
ps_latlink_s::to
struct ps_latnode_s * to
To node.
Definition: ps_lattice_internal.h:98
ps_latlink_s::from
struct ps_latnode_s * from
From node.
Definition: ps_lattice_internal.h:97
ps_latlink_s::alpha
int32 alpha
Forward probability of this link P(w,o_1^{ef})
Definition: ps_lattice_internal.h:103
ps_latlink_s::ascr
int32 ascr
Score for from->wid (from->sf to this->ef)
Definition: ps_lattice_internal.h:100
ps_latnode_s
DAG nodes.
Definition: ps_lattice_internal.h:113
ps_latnode_s::entries
latlink_list_t * entries
Links into this node.
Definition: ps_lattice_internal.h:130
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_latnode_s::exits
latlink_list_t * exits
Links out of this node.
Definition: ps_lattice_internal.h:129
ps_latnode_s::fef
int32 fef
First end frame.
Definition: ps_lattice_internal.h:118
ps_latnode_s::lef
int32 lef
Last end frame.
Definition: ps_lattice_internal.h:119
ps_latnode_s::fanin
int32 fanin
Number nodes with links to this node.
Definition: ps_lattice_internal.h:125
ps_latnode_s::id
int32 id
Unique id for this node.
Definition: ps_lattice_internal.h:114
ps_latnode_s::best_exit
int32 best_exit
Best exit score (used for final nodes only)
Definition: ps_lattice_internal.h:127
ps_latnode_s::alt
struct ps_latnode_s * alt
Node with alternate pronunciation for this word.
Definition: ps_lattice_internal.h:132
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::next
struct ps_latnode_s * next
Next node in DAG (no ordering implied)
Definition: ps_lattice_internal.h:133
ps_latnode_s::basewid
int32 basewid
Dictionary base word id.
Definition: ps_lattice_internal.h:116
ps_latnode_s::velist
glist_t velist
List of history entries with different lmstate (tst only)
Definition: ps_lattice_internal.h:124
ps_latnode_s::reachable
int16 reachable
From.
Definition: ps_lattice_internal.h:121
ps_latnode_s::wid
int32 wid
Dictionary word id.
Definition: ps_lattice_internal.h:115
ps_latpath_s
Partial path structure used in N-best (A*) search.
Definition: ps_lattice_internal.h:153
ps_latpath_s::next
struct ps_latpath_s * next
Pointer to next path in list of paths.
Definition: ps_lattice_internal.h:156
ps_latpath_s::parent
struct ps_latpath_s * parent
Previous element in this path.
Definition: ps_lattice_internal.h:155
ps_latpath_s::score
int32 score
Exact score from start node up to node->sf.
Definition: ps_lattice_internal.h:157
ps_latpath_s::node
ps_latnode_t * node
Node ending this path.
Definition: ps_lattice_internal.h:154
ps_lattice_s
Word graph structure used in bestpath/nbest search.
Definition: ps_lattice_internal.h:61
ps_lattice_s::end
ps_latnode_t * end
Ending node.
Definition: ps_lattice_internal.h:72
ps_lattice_s::latnode_alloc
listelem_alloc_t * latnode_alloc
Node allocator for this DAG.
Definition: ps_lattice_internal.h:80
ps_lattice_s::q_head
latlink_list_t * q_head
Queue of links for traversal.
Definition: ps_lattice_internal.h:85
ps_lattice_s::lmath
logmath_t * lmath
Log-math object.
Definition: ps_lattice_internal.h:64
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::frate
int32 frate
Frame rate.
Definition: ps_lattice_internal.h:68
ps_lattice_s::q_tail
latlink_list_t * q_tail
Queue of links for traversal.
Definition: ps_lattice_internal.h:86
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
ps_lattice_s::refcount
int refcount
Reference count.
Definition: ps_lattice_internal.h:62
ps_lattice_s::dict
dict_t * dict
Dictionary for this DAG.
Definition: ps_lattice_internal.h:66
ps_lattice_s::nodes
ps_latnode_t * nodes
List of all nodes.
Definition: ps_lattice_internal.h:70
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::search
ps_search_t * search
Search (if generated by search).
Definition: ps_lattice_internal.h:65
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_s::hyp_str
char * hyp_str
Current hypothesis string.
Definition: ps_lattice_internal.h:78
ps_lattice_s::silence
int32 silence
Silence word ID.
Definition: ps_lattice_internal.h:67
ps_lattice_s::n_nodes
int32 n_nodes
Number of nodes in this lattice.
Definition: ps_lattice_internal.h:75
ps_lattice_s::latlink_alloc
listelem_alloc_t * latlink_alloc
Link allocator for this DAG.
Definition: ps_lattice_internal.h:81
ps_search_s
Base structure for search module.
Definition: pocketsphinx_internal.h:98
ps_seg_s
Base structure for hypothesis segmentation iterator.
Definition: pocketsphinx_internal.h:178