PocketSphinx  0.6
src/libpocketsphinx/ps_lattice.c File Reference

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.

Defines

#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_bypass_fillers (ps_lattice_t *dag, int32 silpen, int32 fillpen)
 Bypass filler words.
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.
int32 ps_lattice_write_htk (ps_lattice_t *dag, char const *filename)
 Write a lattice to disk in HTK format.
ps_lattice_tps_lattice_read (ps_decoder_t *ps, char const *file)
 Read a lattice from a file on disk.
int ps_lattice_n_frames (ps_lattice_t *dag)
 Get the number of frames in the lattice.
ps_lattice_tps_lattice_init_search (ps_search_t *search, int n_frame)
 Construct an empty word graph with reference to a search structure.
ps_lattice_tps_lattice_retain (ps_lattice_t *dag)
 Retain a lattice.
int ps_lattice_free (ps_lattice_t *dag)
 Free a lattice.
logmath_t * ps_lattice_get_logmath (ps_lattice_t *dag)
 Get the log-math computation object for this lattice.
ps_latnode_iter_tps_latnode_iter (ps_lattice_t *dag)
 Start iterating over nodes in the lattice.
ps_latnode_iter_tps_latnode_iter_next (ps_latnode_iter_t *itor)
 Move to next node in iteration.
void ps_latnode_iter_free (ps_latnode_iter_t *itor)
 Stop iterating over nodes.
ps_latnode_tps_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.
char const * ps_latnode_word (ps_lattice_t *dag, ps_latnode_t *node)
 Get word string for this node.
char const * ps_latnode_baseword (ps_lattice_t *dag, ps_latnode_t *node)
 Get base word string for this node.
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.
ps_latlink_iter_tps_latnode_exits (ps_latnode_t *node)
 Iterate over exits from this node.
ps_latlink_iter_tps_latnode_entries (ps_latnode_t *node)
 Iterate over entries to this node.
ps_latlink_iter_tps_latlink_iter_next (ps_latlink_iter_t *itor)
 Get next link from a lattice link iterator.
void ps_latlink_iter_free (ps_latlink_iter_t *itor)
 Stop iterating over links.
ps_latlink_tps_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.
ps_latnode_tps_latlink_nodes (ps_latlink_t *link, ps_latnode_t **out_src)
 Get destination and source nodes from a lattice link.
char const * ps_latlink_word (ps_lattice_t *dag, ps_latlink_t *link)
 Get word string from a lattice link.
char const * ps_latlink_baseword (ps_lattice_t *dag, ps_latlink_t *link)
 Get base word string from a lattice link.
ps_latlink_tps_latlink_pred (ps_latlink_t *link)
 Get predecessor link in best path.
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.
char const * ps_lattice_hyp (ps_lattice_t *dag, ps_latlink_t *link)
 Get hypothesis string after bestpath search.
ps_seg_tps_lattice_seg_iter (ps_lattice_t *dag, ps_latlink_t *link, float32 lwf)
 Get hypothesis segmentation iterator after bestpath search.
latlink_list_tlatlink_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_tps_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_tps_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.
ps_latlink_tps_lattice_traverse_next (ps_lattice_t *dag, ps_latnode_t *end)
 Get the next link in forward traversal.
ps_latlink_tps_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.
ps_latlink_tps_lattice_reverse_next (ps_lattice_t *dag, ps_latnode_t *start)
 Get the next link in reverse traversal.
ps_latlink_tps_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.
int32 ps_lattice_posterior (ps_lattice_t *dag, ngram_model_t *lmset, float32 ascale)
 Calculate link posterior probabilities on a word graph.
int32 ps_lattice_posterior_prune (ps_lattice_t *dag, int32 beam)
 Prune all links (and associated nodes) below a certain posterior probability.
ps_astar_tps_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.
ps_latpath_tps_astar_next (ps_astar_t *nbest)
 Find next best hypothesis of A* on a word graph.
char const * ps_astar_hyp (ps_astar_t *nbest, ps_latpath_t *path)
 Get hypothesis string from A* search.
ps_seg_tps_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.

Detailed Description

Word graph search.

Definition in file ps_lattice.c.


Function Documentation

Find next best hypothesis of A* on a word graph.

Returns:
a complete path, or NULL if no more hypotheses exist.

Definition at line 1718 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.

Parameters:
sfStarting frame for N-best search.
efEnding frame for N-best search, or -1 for last frame.
w1First context word, or -1 for none.
w2Second context word, or -1 for none.
Returns:
0 for success, <0 on error.

Definition at line 1659 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.

Parameters:
dagLattice to which node belongs.
linkLink inquired about
Returns:
Base word string for this link

Definition at line 830 of file ps_lattice.c.

References ps_latnode_s::basewid, ps_lattice_s::dict, and ps_latlink_s::from.

Stop iterating over links.

Parameters:
itorLink iterator.

Definition at line 789 of file ps_lattice.c.

Get next link from a lattice link iterator.

Parameters:
itorIterator.
Returns:
Updated iterator, or NULL if finished.

Definition at line 783 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.

Parameters:
linkLink inquired about
out_srcOutput: (optional) source node.
Returns:
destination node

Definition at line 815 of file ps_lattice.c.

References ps_latlink_s::from, and ps_latlink_s::to.

Get predecessor link in best path.

Parameters:
linkLink inquired about
Returns:
Best previous link from bestpath search, if any. Otherwise NULL

Definition at line 838 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.

Parameters:
dagLattice to which node belongs.
linkLink inquired about
out_ascrOutput: (optional) acoustic score.
Returns:
Posterior probability for this link. Log is expressed in the log-base used in the decoder. To convert to linear floating-point, use logmath_exp(ps_lattice_get_logmath(), pprob).

Definition at line 844 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.

Note:
these are inclusive - i.e. the last frame of this word is ef, not ef-1.
Parameters:
linkLink inquired about.
out_sfOutput: (optional) start frame of this link.
Returns:
End frame of this link.

Definition at line 801 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.

Parameters:
dagLattice to which node belongs.
linkLink inquired about
Returns:
Word string for this link (possibly a pronunciation variant).

Definition at line 822 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.

Parameters:
dagLattice to which node belongs.
nodeNode inquired about.
Returns:
Base word string for this node.

Definition at line 748 of file ps_lattice.c.

References ps_latnode_s::basewid, and ps_lattice_s::dict.

Iterate over entries to this node.

Parameters:
nodeNode inquired about.
Returns:
Iterator over entry links to this node.

Definition at line 777 of file ps_lattice.c.

References ps_latnode_s::entries.

Iterate over exits from this node.

Parameters:
nodeNode inquired about.
Returns:
Iterator over exit links from this node.

Definition at line 771 of file ps_lattice.c.

References ps_latnode_s::exits.

Start iterating over nodes in the lattice.

Note:
No particular order of traversal is guaranteed, and you should not depend on this.
Parameters:
dagLattice to iterate over.
Returns:
Iterator over lattice nodes.

Definition at line 710 of file ps_lattice.c.

References ps_lattice_s::nodes.

Stop iterating over nodes.

Parameters:
itorNode iterator.

Definition at line 722 of file ps_lattice.c.

Move to next node in iteration.

Parameters:
itorNode iterator.
Returns:
Updated node iterator, or NULL if finished

Definition at line 716 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.

Parameters:
dagLattice to which node belongs.
nodeNode inquired about.
out_linkOutput: exit link with highest posterior probability
Returns:
Posterior probability of the best link exiting this node. Log is expressed in the log-base used in the decoder. To convert to linear floating-point, use logmath_exp(ps_lattice_get_logmath(), pprob).

Definition at line 754 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.

Parameters:
nodeNode inquired about.
out_fefOutput: End frame of first exit from this node.
out_lefOutput: End frame of last exit from this node.
Returns:
Start frame for all edges exiting this node.

Definition at line 734 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.

Parameters:
dagLattice to which node belongs.
nodeNode inquired about.
Returns:
Word string for this node (possibly a pronunciation variant).

Definition at line 742 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 
)
int ps_lattice_free ( ps_lattice_t dag)

Free a lattice.

Returns:
new reference count (0 if dag was freed)

Definition at line 688 of file ps_lattice.c.

References 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_deinit(), and ps_start_utt().

logmath_t* ps_lattice_get_logmath ( ps_lattice_t dag)

Get the log-math computation object for this lattice.

Returns:
The log-math object for this lattice. The lattice retains ownership of this pointer, so you should not attempt to free it manually. Use logmath_retain() if you wish to reuse it elsewhere.

Definition at line 704 of file ps_lattice.c.

References ps_lattice_s::lmath.

Get the number of frames in the lattice.

Parameters:
dagThe lattice in question.
Returns:
Number of frames in this lattice.

Definition at line 656 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.

Returns:
Posterior probability of the utterance as a whole.

Definition at line 1395 of file ps_lattice.c.

References ps_latlink_s::ascr, ps_latnode_s::basewid, ps_latlink_s::beta, BETTER_THAN, 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(), ps_lattice_s::search, 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.

Parameters:
beamMinimum 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).
Returns:
number of arcs removed.

Definition at line 1464 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.

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.

Returns:
pointer to the retained lattice.

Definition at line 681 of file ps_lattice.c.

References ps_lattice_s::refcount.

Start a reverse traversal of edges in a word graph.

Note:
See ps_lattice_traverse_edges() for why this API is the way it is.
Parameters:
dagLattice to be traversed.
startStart node (goal) of traversal.
endEnd node (source) of traversal.
Returns:
First link in traversal.

Definition at line 1158 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().

Get the next link in reverse traversal.

Parameters:
dagLattice to be traversed.
startStart node (goal) of traversal.
Returns:
Next link in traversal.

Definition at line 1183 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().

Start a forward traversal of edges in a word graph.

Note:
A keen eye will notice an inconsistency in this API versus other types of iterators in PocketSphinx. The reason for this is that the traversal algorithm is much more efficient when it is able to modify the lattice structure. Therefore, to avoid giving the impression that multiple traversals are possible at once, no separate iterator structure is provided.
Parameters:
dagLattice to be traversed.
startStart node (source) of traversal.
endEnd node (goal) of traversal.
Returns:
First link in traversal.

Definition at line 1101 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().

Get the next link in forward traversal.

Parameters:
dagLattice to be traversed.
endEnd node (goal) of traversal.
Returns:
Next link in traversal.

Definition at line 1127 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().