PocketSphinx
5prealpha
|
Word graph search. More...
#include <assert.h>
#include <string.h>
#include <math.h>
#include <sphinxbase/ckd_alloc.h>
#include <sphinxbase/listelem_alloc.h>
#include <sphinxbase/strfuncs.h>
#include <sphinxbase/err.h>
#include <sphinxbase/pio.h>
#include "pocketsphinx_internal.h"
#include "ps_lattice_internal.h"
#include "ngram_search.h"
#include "dict.h"
Go to the source code of this file.
Macros | |
#define | MAX_PATHS 500 /* Max allowed active paths at any time */ |
#define | MAX_HYP_TRIES 10000 |
Functions | |
void | ps_lattice_link (ps_lattice_t *dag, ps_latnode_t *from, ps_latnode_t *to, int32 score, int32 ef) |
Create a directed link between "from" and "to" nodes, but if a link already exists, choose one with the best link_scr. | |
void | ps_lattice_penalize_fillers (ps_lattice_t *dag, int32 silpen, int32 fillpen) |
Insert penalty for fillers. | |
void | ps_lattice_delete_unreachable (ps_lattice_t *dag) |
Remove nodes marked as unreachable. | |
int32 | ps_lattice_write (ps_lattice_t *dag, char const *filename) |
Write a lattice to disk. More... | |
int32 | ps_lattice_write_htk (ps_lattice_t *dag, char const *filename) |
Write a lattice to disk in HTK format. More... | |
ps_lattice_t * | ps_lattice_read (ps_decoder_t *ps, char const *file) |
Read a lattice from a file on disk. More... | |
int | ps_lattice_n_frames (ps_lattice_t *dag) |
Get the number of frames in the lattice. More... | |
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. | |
ps_lattice_t * | ps_lattice_retain (ps_lattice_t *dag) |
Retain a lattice. More... | |
int | ps_lattice_free (ps_lattice_t *dag) |
Free a lattice. More... | |
logmath_t * | ps_lattice_get_logmath (ps_lattice_t *dag) |
Get the log-math computation object for this lattice. More... | |
ps_latnode_iter_t * | ps_latnode_iter (ps_lattice_t *dag) |
Start iterating over nodes in the lattice. More... | |
ps_latnode_iter_t * | ps_latnode_iter_next (ps_latnode_iter_t *itor) |
Move to next node in iteration. More... | |
void | ps_latnode_iter_free (ps_latnode_iter_t *itor) |
Stop iterating over nodes. More... | |
ps_latnode_t * | ps_latnode_iter_node (ps_latnode_iter_t *itor) |
Get node from iterator. | |
int | ps_latnode_times (ps_latnode_t *node, int16 *out_fef, int16 *out_lef) |
Get start and end time range for a node. More... | |
char const * | ps_latnode_word (ps_lattice_t *dag, ps_latnode_t *node) |
Get word string for this node. More... | |
char const * | ps_latnode_baseword (ps_lattice_t *dag, ps_latnode_t *node) |
Get base word string for this node. More... | |
int32 | ps_latnode_prob (ps_lattice_t *dag, ps_latnode_t *node, ps_latlink_t **out_link) |
Get best posterior probability and associated acoustic score from a lattice node. More... | |
ps_latlink_iter_t * | ps_latnode_exits (ps_latnode_t *node) |
Iterate over exits from this node. More... | |
ps_latlink_iter_t * | ps_latnode_entries (ps_latnode_t *node) |
Iterate over entries to this node. More... | |
ps_latlink_iter_t * | ps_latlink_iter_next (ps_latlink_iter_t *itor) |
Get next link from a lattice link iterator. More... | |
void | ps_latlink_iter_free (ps_latlink_iter_t *itor) |
Stop iterating over links. More... | |
ps_latlink_t * | ps_latlink_iter_link (ps_latlink_iter_t *itor) |
Get link from iterator. | |
int | ps_latlink_times (ps_latlink_t *link, int16 *out_sf) |
Get start and end times from a lattice link. More... | |
ps_latnode_t * | ps_latlink_nodes (ps_latlink_t *link, ps_latnode_t **out_src) |
Get destination and source nodes from a lattice link. More... | |
char const * | ps_latlink_word (ps_lattice_t *dag, ps_latlink_t *link) |
Get word string from a lattice link. More... | |
char const * | ps_latlink_baseword (ps_lattice_t *dag, ps_latlink_t *link) |
Get base word string from a lattice link. More... | |
ps_latlink_t * | ps_latlink_pred (ps_latlink_t *link) |
Get predecessor link in best path. More... | |
int32 | ps_latlink_prob (ps_lattice_t *dag, ps_latlink_t *link, int32 *out_ascr) |
Get acoustic score and posterior probability from a lattice link. More... | |
char const * | ps_lattice_hyp (ps_lattice_t *dag, ps_latlink_t *link) |
Get hypothesis string after bestpath search. | |
ps_seg_t * | ps_lattice_seg_iter (ps_lattice_t *dag, ps_latlink_t *link, float32 lwf) |
Get hypothesis segmentation iterator after bestpath search. | |
latlink_list_t * | latlink_list_new (ps_lattice_t *dag, ps_latlink_t *link, latlink_list_t *next) |
Create a new lattice link element. | |
void | ps_lattice_pushq (ps_lattice_t *dag, ps_latlink_t *link) |
Add an edge to the traversal queue. | |
ps_latlink_t * | ps_lattice_popq (ps_lattice_t *dag) |
Remove an edge from the traversal queue. | |
void | ps_lattice_delq (ps_lattice_t *dag) |
Clear and reset the traversal queue. | |
ps_latlink_t * | ps_lattice_traverse_edges (ps_lattice_t *dag, ps_latnode_t *start, ps_latnode_t *end) |
Start a forward traversal of edges in a word graph. More... | |
ps_latlink_t * | ps_lattice_traverse_next (ps_lattice_t *dag, ps_latnode_t *end) |
Get the next link in forward traversal. More... | |
ps_latlink_t * | ps_lattice_reverse_edges (ps_lattice_t *dag, ps_latnode_t *start, ps_latnode_t *end) |
Start a reverse traversal of edges in a word graph. More... | |
ps_latlink_t * | ps_lattice_reverse_next (ps_lattice_t *dag, ps_latnode_t *start) |
Get the next link in reverse traversal. More... | |
ps_latlink_t * | ps_lattice_bestpath (ps_lattice_t *dag, ngram_model_t *lmset, float32 lwf, float32 ascale) |
Do N-Gram based best-path search on a word graph. More... | |
int32 | ps_lattice_posterior (ps_lattice_t *dag, ngram_model_t *lmset, float32 ascale) |
Calculate link posterior probabilities on a word graph. More... | |
int32 | ps_lattice_posterior_prune (ps_lattice_t *dag, int32 beam) |
Prune all links (and associated nodes) below a certain posterior probability. More... | |
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. More... | |
ps_latpath_t * | ps_astar_next (ps_astar_t *nbest) |
Find next best hypothesis of A* on a word graph. More... | |
char const * | ps_astar_hyp (ps_astar_t *nbest, ps_latpath_t *path) |
Get hypothesis string from A* search. | |
ps_seg_t * | ps_astar_seg_iter (ps_astar_t *astar, ps_latpath_t *path, float32 lwf) |
Get hypothesis segmentation from A* search. | |
void | ps_astar_finish (ps_astar_t *nbest) |
Finish N-best search, releasing resources associated with it. | |
Word graph search.
Definition in file ps_lattice.c.
ps_latpath_t* ps_astar_next | ( | ps_astar_t * | nbest | ) |
Find next best hypothesis of A* on a word graph.
Definition at line 1771 of file ps_lattice.c.
References ps_lattice_s::end, ps_latnode_s::fef, ps_latpath_s::next, ps_latpath_s::node, and ps_latnode_s::sf.
Referenced by ps_nbest_next().
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.
sf | Starting frame for N-best search. |
ef | Ending frame for N-best search, or -1 for last frame. |
w1 | First context word, or -1 for none. |
w2 | Second context word, or -1 for none. |
Definition at line 1712 of file ps_lattice.c.
References ps_latnode_s::basewid, ps_lattice_s::end, ps_latnode_s::exits, ps_astar_s::latpath_alloc, ps_lattice_s::n_frames, ps_latnode_s::next, ps_latpath_s::node, ps_lattice_s::nodes, ps_latpath_s::parent, ps_latnode_s::rem_score, ps_latpath_s::score, SENSCR_SHIFT, ps_latnode_s::sf, and WORST_SCORE.
Referenced by ps_nbest().
char const* ps_latlink_baseword | ( | ps_lattice_t * | dag, |
ps_latlink_t * | link | ||
) |
Get base word string from a lattice link.
dag | Lattice to which node belongs. |
link | Link inquired about |
Definition at line 808 of file ps_lattice.c.
References ps_latnode_s::basewid, ps_lattice_s::dict, and ps_latlink_s::from.
void ps_latlink_iter_free | ( | ps_latlink_iter_t * | itor | ) |
Stop iterating over links.
itor | Link iterator. |
Definition at line 767 of file ps_lattice.c.
ps_latlink_iter_t* ps_latlink_iter_next | ( | ps_latlink_iter_t * | itor | ) |
Get next link from a lattice link iterator.
itor | Iterator. |
Definition at line 761 of file ps_lattice.c.
ps_latnode_t* ps_latlink_nodes | ( | ps_latlink_t * | link, |
ps_latnode_t ** | out_src | ||
) |
Get destination and source nodes from a lattice link.
link | Link inquired about |
out_src | Output: (optional) source node. |
Definition at line 793 of file ps_lattice.c.
References ps_latlink_s::from, and ps_latlink_s::to.
ps_latlink_t* ps_latlink_pred | ( | ps_latlink_t * | link | ) |
Get predecessor link in best path.
link | Link inquired about |
Definition at line 816 of file ps_lattice.c.
int32 ps_latlink_prob | ( | ps_lattice_t * | dag, |
ps_latlink_t * | link, | ||
int32 * | out_ascr | ||
) |
Get acoustic score and posterior probability from a lattice link.
dag | Lattice to which node belongs. |
link | Link inquired about |
out_ascr | Output: (optional) acoustic score. |
Definition at line 822 of file ps_lattice.c.
References ps_latlink_s::alpha, ps_latlink_s::ascr, ps_latlink_s::beta, ps_lattice_s::norm, and SENSCR_SHIFT.
int ps_latlink_times | ( | ps_latlink_t * | link, |
int16 * | out_sf | ||
) |
Get start and end times from a lattice link.
link | Link inquired about. |
out_sf | Output: (optional) start frame of this link. |
Definition at line 779 of file ps_lattice.c.
References ps_latlink_s::ef, ps_latlink_s::from, and ps_latnode_s::sf.
char const* ps_latlink_word | ( | ps_lattice_t * | dag, |
ps_latlink_t * | link | ||
) |
Get word string from a lattice link.
dag | Lattice to which node belongs. |
link | Link inquired about |
Definition at line 800 of file ps_lattice.c.
References ps_lattice_s::dict, ps_latlink_s::from, and ps_latnode_s::wid.
char const* ps_latnode_baseword | ( | ps_lattice_t * | dag, |
ps_latnode_t * | node | ||
) |
Get base word string for this node.
dag | Lattice to which node belongs. |
node | Node inquired about. |
Definition at line 726 of file ps_lattice.c.
References ps_latnode_s::basewid, and ps_lattice_s::dict.
ps_latlink_iter_t* ps_latnode_entries | ( | ps_latnode_t * | node | ) |
Iterate over entries to this node.
node | Node inquired about. |
Definition at line 755 of file ps_lattice.c.
References ps_latnode_s::entries.
ps_latlink_iter_t* ps_latnode_exits | ( | ps_latnode_t * | node | ) |
Iterate over exits from this node.
node | Node inquired about. |
Definition at line 749 of file ps_lattice.c.
References ps_latnode_s::exits.
ps_latnode_iter_t* ps_latnode_iter | ( | ps_lattice_t * | dag | ) |
Start iterating over nodes in the lattice.
dag | Lattice to iterate over. |
Definition at line 688 of file ps_lattice.c.
References ps_lattice_s::nodes.
void ps_latnode_iter_free | ( | ps_latnode_iter_t * | itor | ) |
Stop iterating over nodes.
itor | Node iterator. |
Definition at line 700 of file ps_lattice.c.
ps_latnode_iter_t* ps_latnode_iter_next | ( | ps_latnode_iter_t * | itor | ) |
Move to next node in iteration.
itor | Node iterator. |
Definition at line 694 of file ps_lattice.c.
References ps_latnode_s::next.
int32 ps_latnode_prob | ( | ps_lattice_t * | dag, |
ps_latnode_t * | node, | ||
ps_latlink_t ** | out_link | ||
) |
Get best posterior probability and associated acoustic score from a lattice node.
dag | Lattice to which node belongs. |
node | Node inquired about. |
out_link | Output: exit link with highest posterior probability |
Definition at line 732 of file ps_lattice.c.
References ps_latlink_s::alpha, ps_latlink_s::beta, ps_latnode_s::exits, ps_lattice_s::lmath, and ps_lattice_s::norm.
int ps_latnode_times | ( | ps_latnode_t * | node, |
int16 * | out_fef, | ||
int16 * | out_lef | ||
) |
Get start and end time range for a node.
node | Node inquired about. |
out_fef | Output: End frame of first exit from this node. |
out_lef | Output: End frame of last exit from this node. |
Definition at line 712 of file ps_lattice.c.
References ps_latnode_s::fef, ps_latnode_s::lef, and ps_latnode_s::sf.
char const* ps_latnode_word | ( | ps_lattice_t * | dag, |
ps_latnode_t * | node | ||
) |
Get word string for this node.
dag | Lattice to which node belongs. |
node | Node inquired about. |
Definition at line 720 of file ps_lattice.c.
References ps_lattice_s::dict, and ps_latnode_s::wid.
ps_latlink_t* ps_lattice_bestpath | ( | ps_lattice_t * | dag, |
ngram_model_t * | lmset, | ||
float32 | lwf, | ||
float32 | ascale | ||
) |
Do N-Gram based best-path search on a word graph.
This function calculates both the best path as well as the forward probability used in confidence estimation.
Definition at line 1215 of file ps_lattice.c.
References ps_latlink_s::alpha, ps_latlink_s::ascr, ps_latnode_s::basewid, BETTER_THAN, ps_search_s::dict, dict_filler_word(), ps_lattice_s::end, ps_latnode_s::entries, ps_latnode_s::exits, ps_lattice_s::final_node_ascr, ps_latlink_s::from, ps_latnode_s::lef, ps_lattice_s::lmath, ps_latnode_s::next, ps_lattice_s::nodes, ps_lattice_s::norm, ps_latlink_s::path_scr, ps_lattice_traverse_edges(), ps_lattice_traverse_next(), ps_lattice_s::search, SENSCR_SHIFT, ps_latnode_s::sf, ps_lattice_s::start, ps_latlink_s::to, and ps_latnode_s::wid.
int ps_lattice_free | ( | ps_lattice_t * | dag | ) |
Free a lattice.
Definition at line 665 of file ps_lattice.c.
References ps_lattice_s::dict, dict_free(), ps_lattice_s::hyp_str, ps_lattice_s::latlink_alloc, ps_lattice_s::latlink_list_alloc, ps_lattice_s::latnode_alloc, ps_lattice_s::lmath, and ps_lattice_s::refcount.
Referenced by ngram_search_lattice(), ps_search_base_free(), and ps_start_utt().
logmath_t* ps_lattice_get_logmath | ( | ps_lattice_t * | dag | ) |
Get the log-math computation object for this lattice.
Definition at line 682 of file ps_lattice.c.
References ps_lattice_s::lmath.
int ps_lattice_n_frames | ( | ps_lattice_t * | dag | ) |
Get the number of frames in the lattice.
dag | The lattice in question. |
Definition at line 633 of file ps_lattice.c.
References ps_lattice_s::n_frames.
int32 ps_lattice_posterior | ( | ps_lattice_t * | dag, |
ngram_model_t * | lmset, | ||
float32 | ascale | ||
) |
Calculate link posterior probabilities on a word graph.
This function assumes that bestpath search has already been done.
Definition at line 1446 of file ps_lattice.c.
References ps_latlink_s::ascr, ps_latnode_s::basewid, ps_latlink_s::beta, BETTER_THAN, ps_lattice_s::dict, dict_filler_word(), ps_lattice_s::end, ps_latnode_s::exits, ps_lattice_s::final_node_ascr, ps_latlink_s::from, ps_lattice_s::lmath, ps_latnode_s::next, ps_lattice_s::nodes, ps_lattice_s::norm, ps_latlink_s::path_scr, ps_lattice_reverse_edges(), ps_lattice_reverse_next(), SENSCR_SHIFT, ps_lattice_s::start, and ps_latlink_s::to.
int32 ps_lattice_posterior_prune | ( | ps_lattice_t * | dag, |
int32 | beam | ||
) |
Prune all links (and associated nodes) below a certain posterior probability.
This function assumes that ps_lattice_posterior() has already been called.
beam | Minimum posterior probability for links. This is expressed in the log-base used in the decoder. To convert from linear floating-point, use logmath_log(ps_lattice_get_logmath(), prob). |
Definition at line 1524 of file ps_lattice.c.
References ps_latlink_s::alpha, ps_latlink_s::beta, ps_lattice_s::end, ps_latnode_s::entries, ps_latnode_s::exits, ps_latlink_s::from, ps_lattice_s::latlink_alloc, ps_lattice_s::latlink_list_alloc, ps_lattice_s::norm, ps_lattice_delete_unreachable(), ps_lattice_traverse_edges(), ps_lattice_traverse_next(), ps_latnode_s::reachable, ps_lattice_s::start, and ps_latlink_s::to.
ps_lattice_t* ps_lattice_read | ( | struct ps_decoder_s * | ps, |
char const * | file | ||
) |
Read a lattice from a file on disk.
ps | Decoder to use for processing this lattice, or NULL. |
file | Path to lattice file. |
Definition at line 387 of file ps_lattice.c.
References BAD_S3WID, ps_latnode_s::basewid, ps_search_s::config, ps_decoder_s::config, ps_lattice_s::dict, ps_decoder_s::dict, dict_add_word(), dict_filler_word(), dict_init(), dict_retain(), dict_word2basestr(), dict_wordid(), ps_lattice_s::end, ps_latnode_s::entries, ps_latnode_s::exits, ps_latnode_s::fef, ps_lattice_s::frate, ps_latnode_s::id, ps_lattice_s::latlink_alloc, ps_lattice_s::latlink_list_alloc, ps_lattice_s::latnode_alloc, ps_latnode_s::lef, ps_lattice_s::lmath, ps_decoder_s::lmath, ps_lattice_s::n_frames, ps_latnode_s::next, ps_lattice_s::nodes, ps_lattice_delete_unreachable(), ps_lattice_link(), ps_lattice_penalize_fillers(), ps_latnode_s::reachable, ps_lattice_s::refcount, ps_lattice_s::search, ps_decoder_s::search, ps_latnode_s::sf, ps_lattice_s::silence, ps_lattice_s::start, ps_latnode_s::wid, WORSE_THAN, and WORST_SCORE.
ps_lattice_t* ps_lattice_retain | ( | ps_lattice_t * | dag | ) |
Retain a lattice.
This function retains ownership of a lattice for the caller, preventing it from being freed automatically. You must call ps_lattice_free() to free it after having called this function.
Definition at line 658 of file ps_lattice.c.
References ps_lattice_s::refcount.
ps_latlink_t* ps_lattice_reverse_edges | ( | ps_lattice_t * | dag, |
ps_latnode_t * | start, | ||
ps_latnode_t * | end | ||
) |
Start a reverse traversal of edges in a word graph.
dag | Lattice to be traversed. |
start | Start node (goal) of traversal. |
end | End node (source) of traversal. |
Definition at line 1148 of file ps_lattice.c.
References ps_lattice_s::end, ps_latnode_s::entries, ps_latnode_s::exits, ps_latnode_s::fanin, ps_latnode_s::next, ps_lattice_s::nodes, ps_lattice_delq(), ps_lattice_pushq(), and ps_lattice_reverse_next().
Referenced by ps_lattice_posterior().
ps_latlink_t* ps_lattice_reverse_next | ( | ps_lattice_t * | dag, |
ps_latnode_t * | start | ||
) |
Get the next link in reverse traversal.
dag | Lattice to be traversed. |
start | Start node (goal) of traversal. |
Definition at line 1173 of file ps_lattice.c.
References ps_latnode_s::entries, ps_latnode_s::fanin, ps_latlink_s::from, ps_lattice_delq(), ps_lattice_popq(), ps_lattice_pushq(), and ps_lattice_s::start.
Referenced by ps_lattice_posterior(), and ps_lattice_reverse_edges().
ps_latlink_t* ps_lattice_traverse_edges | ( | ps_lattice_t * | dag, |
ps_latnode_t * | start, | ||
ps_latnode_t * | end | ||
) |
Start a forward traversal of edges in a word graph.
dag | Lattice to be traversed. |
start | Start node (source) of traversal. |
end | End node (goal) of traversal. |
Definition at line 1091 of file ps_lattice.c.
References ps_latnode_s::exits, ps_latnode_s::fanin, ps_latnode_s::next, ps_lattice_s::nodes, ps_lattice_delq(), ps_lattice_pushq(), ps_lattice_traverse_next(), ps_lattice_s::start, and ps_latlink_s::to.
Referenced by ps_lattice_bestpath(), and ps_lattice_posterior_prune().
ps_latlink_t* ps_lattice_traverse_next | ( | ps_lattice_t * | dag, |
ps_latnode_t * | end | ||
) |
Get the next link in forward traversal.
dag | Lattice to be traversed. |
end | End node (goal) of traversal. |
Definition at line 1117 of file ps_lattice.c.
References ps_lattice_s::end, ps_latnode_s::exits, ps_latnode_s::fanin, ps_lattice_delq(), ps_lattice_popq(), ps_lattice_pushq(), and ps_latlink_s::to.
Referenced by ps_lattice_bestpath(), ps_lattice_posterior_prune(), and ps_lattice_traverse_edges().
int32 ps_lattice_write | ( | ps_lattice_t * | dag, |
char const * | filename | ||
) |
Write a lattice to disk.
Definition at line 210 of file ps_lattice.c.
References ps_latlink_s::ascr, BETTER_THAN, ps_lattice_s::dict, ps_lattice_s::end, ps_latnode_s::exits, ps_latnode_s::fef, ps_latnode_s::id, ps_latnode_s::lef, ps_lattice_s::lmath, ps_lattice_s::n_frames, ps_latnode_s::next, ps_latnode_s::node_id, ps_lattice_s::nodes, SENSCR_SHIFT, ps_latnode_s::sf, ps_lattice_s::start, ps_latlink_s::to, ps_latnode_s::wid, WORSE_THAN, and WORST_SCORE.
int32 ps_lattice_write_htk | ( | ps_lattice_t * | dag, |
char const * | filename | ||
) |
Write a lattice to disk in HTK format.
Definition at line 270 of file ps_lattice.c.
References ps_latlink_s::alpha, ps_latlink_s::ascr, ps_latlink_s::beta, BETTER_THAN, ps_lattice_s::dict, dict_filler_word(), ps_lattice_s::end, ps_latnode_s::exits, ps_lattice_s::frate, ps_latnode_s::id, ps_lattice_s::lmath, ps_latnode_s::next, ps_lattice_s::nodes, ps_lattice_s::norm, ps_latnode_s::reachable, SENSCR_SHIFT, ps_latnode_s::sf, ps_lattice_s::start, ps_latlink_s::to, ps_latnode_s::wid, WORSE_THAN, and WORST_SCORE.