1/*---------------------------------------------------------------------------* 2 * astar.h * 3 * * 4 * Copyright 2007, 2008 Nuance Communciations, Inc. * 5 * * 6 * Licensed under the Apache License, Version 2.0 (the 'License'); * 7 * you may not use this file except in compliance with the License. * 8 * * 9 * You may obtain a copy of the License at * 10 * http://www.apache.org/licenses/LICENSE-2.0 * 11 * * 12 * Unless required by applicable law or agreed to in writing, software * 13 * distributed under the License is distributed on an 'AS IS' BASIS, * 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 15 * See the License for the specific language governing permissions and * 16 * limitations under the License. * 17 * * 18 *---------------------------------------------------------------------------*/ 19 20#ifndef __ASTAR_H__ 21#define __ASTAR_H__ 22 23#include "search_network.h" 24#include "srec_sizes.h" 25#include "sizes.h" 26 27/********************************************************************* 28 * * 29 * Word Graph for Astar * 30 * * 31 *********************************************************************/ 32 33/* #define DEBUG_ASTAR 1 */ 34 35/* an arc_token is used for the word graph, this implementation 36 removes the need for nodes, and allows arc_tokens to be 37 freed and re-used easily for dynamic grammar creation. 38 Why do away with nodes? Nodes need a list of outgoing arcs, 39 or arc pointers. Rather than store this arc list as an array, 40 we can store it as a linked list, for easy addition/removal. 41 Nodes are now just a pointer to the first arc in a linked list. 42 But further, why not just reference the "first_arc" instead of 43 a node? That's what we're doing here. The "end_node" is 44 really an arc, whose arc->first_next_arc is NULL. 45 46 This experimental implementation is working for the moment! 47*/ 48 49/* VxWorks 5.4 does not support unnamed struct/union yet */ 50/* here we use indices to link one arc token to the next */ 51#define ARC_TOKEN_LNK(bAsE,iDx) ((arcID)iDx) 52#define ARC_TOKEN_PTR(bAsE,atp) (atp==MAXarcID?NULL:bAsE+atp) 53#define ARC_TOKEN_PTR2LNK(bAsE,atp) (atp==NULL?MAXarcID:(arcID)(atp-bAsE)) 54#define ARC_TOKEN_IDX(bAsE,atp) (atp) 55#define ARC_TOKEN_NULL MAXarcID 56typedef arcID arc_token_lnk; 57typedef struct arc_token_t 58{ 59#ifdef DEBUG_ASTAR 60 char* label, debug[64]; 61#endif 62 wordID ilabel; /* input label */ 63 labelID olabel; /* output label */ 64 arc_token_lnk first_next_arc; 65 arc_token_lnk next_token_index; 66} 67arc_token; 68 69/** 70 * @todo document 71 */ 72typedef struct partial_path_t 73{ 74 wtokenID token_index; 75 wordID word; /* quick access to word (wta[token_index].word) */ 76 bigcostdata costsofar; /* quick access to total score, frwd+bkwd */ 77 struct partial_path_t* next; 78 struct partial_path_t* first_prev_arc; 79 struct partial_path_t* linkl_prev_arc; 80 arc_token* arc_for_wtoken; 81 short refcount; 82 struct partial_path_t* hashlink; 83} 84partial_path; 85#define PARP_TERMINAL ((partial_path*)-1) 86 87typedef struct 88{ 89 90 partial_path* free_parp_list; 91 partial_path* partial_path_array; 92 int partial_path_array_size; 93 94 /* todo: replace these pointers with partial_path_token type things */ 95 int max_active_paths; 96 int num_active_paths; 97 partial_path** active_paths; /* partial paths, sorted by score */ 98 99 int max_complete_paths; 100 int num_complete_paths; 101 partial_path** complete_paths; 102 int* complete_path_confidences; 103 partial_path* root_path; /* root is the rightmost partial path 104 to be used for as root of a tree 105 for checking paths already visited */ 106 costdata prune_delta; 107 void* pphash; 108} 109AstarStack; 110 111typedef struct srec_t srec; 112typedef srec* psrec; 113 114int astar_stack_do_backwards_search(psrec rec, int request_nbest_len); 115int astar_stack_prepare(AstarStack* stack, int request_nbest_len, psrec rec); 116int astar_stack_prepare_from_active_search(AstarStack* stack, int request_nbest_len, psrec rec); 117void astar_stack_clear(AstarStack* stack); 118int astar_stack_flag_word_tokens_used(AstarStack* stack, psrec rec); 119AstarStack* astar_stack_make(psrec rec, int max_nbest_len); 120int astar_stack_destroy(psrec rec); 121 122void free_partial_path(AstarStack* stack, partial_path* parp); 123void print_path(partial_path* parp, psrec rec, char* msg); 124 125arc_token* get_arc_for_word(arc_token* atoken, wordID word, void* context_void, 126 wordID terminal_word); 127 128arc_token* get_arc_for_word_without_slot_annotation(arc_token* atoken, const char* word, 129 void* context_void, wordID terminal_word); 130 131#endif 132