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 56 typedef arcID arc_token_lnk; 57 typedef 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 } 67 arc_token; 68 69 /** 70 * @todo document 71 */ 72 typedef 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 } 84 partial_path; 85 #define PARP_TERMINAL ((partial_path*)-1) 86 87 typedef 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 } 109 AstarStack; 110 111 typedef struct srec_t srec; 112 typedef srec* psrec; 113 114 int astar_stack_do_backwards_search(psrec rec, int request_nbest_len); 115 int astar_stack_prepare(AstarStack* stack, int request_nbest_len, psrec rec); 116 int astar_stack_prepare_from_active_search(AstarStack* stack, int request_nbest_len, psrec rec); 117 void astar_stack_clear(AstarStack* stack); 118 int astar_stack_flag_word_tokens_used(AstarStack* stack, psrec rec); 119 AstarStack* astar_stack_make(psrec rec, int max_nbest_len); 120 int astar_stack_destroy(psrec rec); 121 122 void free_partial_path(AstarStack* stack, partial_path* parp); 123 void print_path(partial_path* parp, psrec rec, char* msg); 124 125 arc_token* get_arc_for_word(arc_token* atoken, wordID word, void* context_void, 126 wordID terminal_word); 127 128 arc_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