PocketSphinx 5prealpha
ps_lattice_internal.h File Reference

Word graph search implementation. More...

Go to the source code of this file.

Data Structures

struct  latlink_list_s
 Linked list of DAG link pointers. More...
 
struct  ps_lattice_s
 Word graph structure used in bestpath/nbest search. More...
 
struct  ps_latlink_s
 Links between DAG nodes. More...
 
struct  ps_latnode_s
 DAG nodes. More...
 
struct  dag_seg_s
 Segmentation "iterator" for backpointer table results. More...
 
struct  ps_latpath_s
 Partial path structure used in N-best (A*) search. More...
 
struct  ps_astar_s
 A* search structure. More...
 
struct  astar_seg_s
 Segmentation "iterator" for A* search results. More...
 

Typedefs

typedef struct latlink_list_s latlink_list_t
 Linked list of DAG link pointers. More...
 
typedef struct dag_seg_s dag_seg_t
 Segmentation "iterator" for backpointer table results.
 
typedef struct ps_latpath_s ps_latpath_t
 Partial path structure used in N-best (A*) search. More...
 
typedef struct ps_astar_s ps_astar_t
 A* search structure.
 
typedef struct astar_seg_s astar_seg_t
 Segmentation "iterator" for A* search results.
 

Functions

ps_lattice_tps_lattice_init_search (ps_search_t *search, int n_frame)
 Construct an empty word graph with reference to a search structure. More...
 
void ps_lattice_penalize_fillers (ps_lattice_t *dag, int32 silpen, int32 fillpen)
 Insert penalty for fillers. More...
 
void ps_lattice_delete_unreachable (ps_lattice_t *dag)
 Remove nodes marked as unreachable. More...
 
void ps_lattice_pushq (ps_lattice_t *dag, ps_latlink_t *link)
 Add an edge to the traversal queue. More...
 
ps_latlink_tps_lattice_popq (ps_lattice_t *dag)
 Remove an edge from the traversal queue. More...
 
void ps_lattice_delq (ps_lattice_t *dag)
 Clear and reset the traversal queue. More...
 
latlink_list_tlatlink_list_new (ps_lattice_t *dag, ps_latlink_t *link, latlink_list_t *next)
 Create a new lattice link element. More...
 
char const * ps_lattice_hyp (ps_lattice_t *dag, ps_latlink_t *link)
 Get hypothesis string after bestpath search. More...
 
ps_seg_tps_lattice_seg_iter (ps_lattice_t *dag, ps_latlink_t *link, float32 lwf)
 Get hypothesis segmentation iterator after bestpath search. More...
 
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. More...
 
ps_latpath_tps_astar_next (ps_astar_t *nbest)
 Find next best hypothesis of A* on a word graph. More...
 
void ps_astar_finish (ps_astar_t *nbest)
 Finish N-best search, releasing resources associated with it. More...
 
char const * ps_astar_hyp (ps_astar_t *nbest, ps_latpath_t *path)
 Get hypothesis string from A* search. More...
 
ps_seg_tps_astar_seg_iter (ps_astar_t *astar, ps_latpath_t *path, float32 lwf)
 Get hypothesis segmentation from A* search. More...
 

Detailed Description

Word graph search implementation.

Definition in file ps_lattice_internal.h.

Typedef Documentation

◆ latlink_list_t

Linked list of DAG link pointers.

Because the same link structure is used for forward and reverse links, as well as for the agenda used in bestpath search, we can't store the list pointer inside latlink_t. We could use glist_t here, but it wastes 4 bytes per entry on 32-bit machines.

◆ ps_latpath_t

typedef struct ps_latpath_s ps_latpath_t

Partial path structure used in N-best (A*) search.

Each partial path (latpath_t) is constructed by extending another partial path–parent–by one node.

Function Documentation

◆ 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 at line 1042 of file ps_lattice.c.

References ps_lattice_s::latlink_list_alloc.

Referenced by ps_lattice_pushq().

◆ ps_astar_finish()

void ps_astar_finish ( ps_astar_t nbest)

Finish N-best search, releasing resources associated with it.

Definition at line 1925 of file ps_lattice.c.

References ps_astar_s::hyps, and ps_astar_s::latpath_alloc.

Referenced by ps_nbest_free().

◆ ps_astar_hyp()

char const * ps_astar_hyp ( ps_astar_t nbest,
ps_latpath_t path 
)

Get hypothesis string from A* search.

Definition at line 1804 of file ps_lattice.c.

References ps_latnode_s::basewid, ps_astar_s::hyps, ps_latpath_s::node, ps_latpath_s::parent, and ps_lattice_s::search.

Referenced by ps_nbest_hyp().

◆ ps_astar_next()

ps_latpath_t * ps_astar_next ( ps_astar_t nbest)

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

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

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_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 at line 1898 of file ps_lattice.c.

References ps_seg_s::lwf, ps_latpath_s::node, ps_latpath_s::parent, ps_seg_s::search, ps_lattice_s::search, and ps_seg_s::vt.

Referenced by ps_nbest_seg().

◆ 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.

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 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().

◆ ps_lattice_delete_unreachable()

void ps_lattice_delete_unreachable ( ps_lattice_t dag)

Remove nodes marked as unreachable.

Definition at line 174 of file ps_lattice.c.

References ps_latnode_s::id, ps_latnode_s::next, ps_lattice_s::nodes, and ps_latnode_s::reachable.

Referenced by ngram_search_lattice(), ps_lattice_posterior_prune(), and ps_lattice_read().

◆ ps_lattice_delq()

void ps_lattice_delq ( ps_lattice_t dag)

Clear and reset the traversal queue.

Definition at line 1083 of file ps_lattice.c.

References ps_lattice_popq().

Referenced by ps_lattice_reverse_edges(), ps_lattice_reverse_next(), ps_lattice_traverse_edges(), and ps_lattice_traverse_next().

◆ ps_lattice_hyp()

char const * ps_lattice_hyp ( ps_lattice_t dag,
ps_latlink_t link 
)

Get hypothesis string after bestpath search.

Definition at line 830 of file ps_lattice.c.

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

◆ ps_lattice_init_search()

◆ ps_lattice_penalize_fillers()

void ps_lattice_penalize_fillers ( ps_lattice_t dag,
int32  silpen,
int32  fillpen 
)

◆ ps_lattice_popq()

ps_latlink_t * ps_lattice_popq ( ps_lattice_t dag)

Remove an edge from the traversal queue.

Definition at line 1066 of file ps_lattice.c.

References ps_lattice_s::latlink_list_alloc, ps_lattice_s::q_head, and ps_lattice_s::q_tail.

Referenced by ps_lattice_delq(), ps_lattice_reverse_next(), and ps_lattice_traverse_next().

◆ ps_lattice_pushq()

void ps_lattice_pushq ( ps_lattice_t dag,
ps_latlink_t link 
)

◆ 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 at line 1006 of file ps_lattice.c.

References dag_seg_s::base, dag_seg_s::links, ps_seg_s::lwf, dag_seg_s::n_links, ps_lattice_s::norm, dag_seg_s::norm, ps_seg_s::search, ps_lattice_s::search, and ps_seg_s::vt.