Library Name:
lib_search.a
Introduction:
The search library implements hierarchical search algorithms. Hierarchical search algorithms process a search structure with any number of search levels. All the levels provide the same capabilities (N-symbol probabilities, pruning, etc.) and extension to more levels requires no code modification. Full access to the internal search structure is provided.
Detailed description of the hierarchical search components can be found in the Production Decoder presentation.
Example:
001 // file: $isip/doc/examples/class/search/search_example_00/example.cc
002 // version: $Id: index.html 10272 2005-10-06 19:13:07Z srinivas $
003 //
004 // isip include files
005 //
006 #include
007 #include
008 // this example generates a word graph like this:
009 //
010 /* */
011 /* /-> boy -> runs ->\ */
012 /* START TERM */
013 /* \-> girl -> swims ->/ */
014 /* */
015 //
016 // and it finds all paths throug this graph
017 // main program starts here
018 //
019 int main(int argc, const char** argv) {
020 // generate word symbols
021 //
022 Vector word_syms(4);
023 word_syms(0).assign(L"boy");
024 word_syms(1).assign(L"runs");
025 word_syms(2).assign(L"girl");
026 word_syms(3).assign(L"swims");
027 // assing a search level to each symobl
028 //
029 SearchLevel slev;
030 slev.setSymbolTable(word_syms);
031 Vector search_nodes(4);
032 for(long i = 0; i<4; i++) {
033 search_nodes(i).setSearchLevel(&slev);
034 search_nodes(i).setSymbol(word_syms(i));
035 }
036 // generate a graph
037 //
038 DiGraph graph;
039 // START->boy->runs>TERM
040 //
041 GraphVertex* vertex_0 = graph.insertVertex(&search_nodes(0));
042 graph.insertArc(graph.getStart(), vertex_0);
043 GraphVertex* vertex_1 = graph.insertVertex(&search_nodes(1));
044 graph.insertArc(vertex_0, vertex_1);
045 graph.insertArc(vertex_1, graph.getTerm());
046
047 // START->girl->swims->TERM
048 //
049 GraphVertex* vertex_2 = graph.insertVertex(&search_nodes(2));
050 graph.insertArc(graph.getStart(), vertex_2);
051 GraphVertex* vertex_3 = graph.insertVertex(&search_nodes(3));
052 graph.insertArc(vertex_2, vertex_3);
053 graph.insertArc(vertex_3, graph.getTerm());
054 // create the start trace
055 //
056 Trace* tmp_trace = new Trace();
057 tmp_trace->setBackPointer((Trace*)NULL);
058 tmp_trace->getHistory()->setAllocationMode(DstrBase::USER);
059 tmp_trace->getHistory()->push((Context*)graph.getStart());
060 // add the start trace to the list
061 //
062 DoubleLinkedList trace_list;
063 trace_list.setAllocationMode(DstrBase::USER);
064 trace_list.insertLast(tmp_trace);
065 // declare the list of the final hypotheses
066 //
067 DoubleLinkedList final_hypotheses_list;
068 // declare useful variables
069 //
070 GraphVertex* curr_vert;
071 Trace* curr_trace;
072 Trace* next_trace;
073 History* curr_hist;
074 // loop over list of traces (paths) until it is not empty
075 //
076 trace_list.gotoFirst();
077 while(!(trace_list.length() < 1)) {
078 // get next trace off of the list
079 //
080 curr_trace = trace_list.getCurr();
081
082 // get the vertex of the trace
083 //
084 curr_hist = curr_trace->getHistory();
085 curr_vert = (GraphVertex*)curr_hist->peek();
086 if (curr_vert->getItem() == &DiGraph::TERM_OBJ) {
087 // if the trace reached end of the graph, remove it
088 //
089 trace_list.removeFirst(curr_trace);
090 }
091 else {
092 // get the children of that trace
093 //
094 for (boolean more_paths = curr_vert->gotoFirst(); more_paths;
095 more_paths = curr_vert->gotoNext()) {
096 // create a new traces
097 //
098 next_trace = new Trace(*curr_trace);
099 GraphArc* tmp_arc = curr_vert->getCurr();
100
101 // update the history of each child
102 //
103 next_trace->getHistory()->setAllocationMode(DstrBase::USER);
104 next_trace->getHistory()->push((Context*)tmp_arc->getVertex());
105
106 // add each child to the back of the list
107 //
108 trace_list.insertLast(next_trace);
109 // print the message
110 //
111 String message(L"trace generated from: ");
112 SearchSymbol sym;
113 if(curr_vert->getItem() == &DiGraph::START_OBJ) {
114 sym.assign(L"START");
115 }
116 else {
117 curr_vert->getItem()->getSymbol(sym);
118 }
119 message.concat(sym);
120 message.concat(L" to: ");
121 if(tmp_arc->getVertex()->getItem() == &DiGraph::TERM_OBJ) {
122 sym.assign(L"TERM");
123 // store this trace in the final hypotheses list
124 //
125 final_hypotheses_list.insertLast(next_trace);
126 }
127 else {
128 tmp_arc->getVertex()->getItem()->getSymbol(sym);
129 }
130 message.concat(sym);
131 Console::put(message);
132 }
133 // remove the trace
134 //
135 trace_list.removeFirst(curr_trace);
136 }
137 // move to the first trace
138 //
139 trace_list.gotoFirst();
140 }
141
142 // print the final hypotheses
143 //
144 Console::put(L"\nThe final paths through the graph are:");
145
146 for(boolean more_paths = final_hypotheses_list.gotoFirst();
147 more_paths; more_paths = final_hypotheses_list.gotoNext()) {
148
149 // reverse the history of the current trace (path)
150 //
151 curr_trace = final_hypotheses_list.getCurr();
152 curr_trace->getHistory()->reverse();
153 // loop through the history of trace end print it
154 //
155 String output;
156 while (!curr_trace->getHistory()->isEmpty()) {
157 SearchSymbol sym;
158 GraphVertex* temp = (GraphVertex*)curr_trace->getHistory()->pop();
159 if(temp->getItem() == &DiGraph::START_OBJ) {
160 sym.assign(L"START");
161 }
162 else if(temp->getItem() == &DiGraph::TERM_OBJ) {
163 sym.assign(L"TERM");
164 }
165 else {
166 temp->getItem()->getSymbol(sym);
167 output.concat(L" ");
168 output.concat(sym);
169 }
170 }
171 Console::put(output);
172 }
173 }
Explanation:
The above example shows a steps necessary to create a search structure
and to traverse it.
On lines 27 through 31 we prepare a Vector of SearchSymbols.
Then a SearchLevel is declared and word symbols are assigned to this level.
Since the search structure is represented as a directed graph of the
search nodes, we define the search nodes on the lines 38 through 42.
Each of the search nodes needs to know its search level and its word symbol.
On the lines 44 through 53 we create a search graph structure. It is done by
inserting vertices and making arcs between them.
The actual path through the graph is stored in the form of Trace.
Trace has a history stack, storing visited vertices.
On line 59 we create a starting path leading to the start
node of the search graph. We will store all the active paths (traces)
in the list defined on the line 62. All paths that have already reached
the terminal node of the graph are stored in the list defined on line
78. Now we start to traverse a search graph.
We expand all active paths by finding successive vertices of the last
reached vertex. Since a vertex is a list of arcs, we can loop through
this list as shown on lines 98 through 104 and get the successive vertex
associated with each arc (line 108) and add this vertex to the history
of the newly generated trace. After we print a message about the generated
trace and we accomplish the loop through all possible successive vertices,
we can remove the already extended (parent) trace, which is done on lines
139. We store all the paths that reached the terminal search
graph node in final hypotheses list.
After there are no more unexpanded traces, we can print all the paths,
as shown on lines 146 through 173. We print all the search nodes
visited by popping up the history of the trace.
The output of the example is:
$ example.exe
trace generated from: START to: boy
trace generated from: START to: girl
trace generated from: boy to: runs
trace generated from: girl to: swims
trace generated from: runs to: TERM
trace generated from: swims to: TERM
The final paths through the graph are:
boy runs
girl swims
$
Example:
The next "higher level"
example
demonstrates how to use a HierarchicalSearch class to decode a sentence.
01 // file: $isip/doc/examples/class/search/search_example_01/example.cc
02 // version: $Id: index.html 10272 2005-10-06 19:13:07Z srinivas $
03 //
04
05 // isip include files
06 //
07 #include <Console.h>
08 #include <FrontEnd.h>
09 #include <HierarchicalSearch.h>
10 #include <Filename.h>
11
12 int main(int argc, const char** argv) {
13
14 // configure FrontEnd
15 //
16 FrontEnd fe;
17
18 Sof front_end_sof;
19 front_end_sof.open(L"$ISIP_DEVEL/util/speech/isip_recognize/param.sof");
20 fe.read(front_end_sof, front_end_sof.first(fe.name()));
21 front_end_sof.close();
22
23 // configure HierarchicalSearch
24 //
25 HierarchicalSearch search_engine;
26 long num_levels = 3;
27 search_engine.setNumLevels(num_levels);
28
29 // read models
30 //
31 Sof model_sof;
32 model_sof.open(L"$ISIP_DEVEL/doc/examples/data/models/tidigit_preview.sof");
33
34 for (long curr_level = 0; curr_level < num_levels; curr_level++) {
35 SearchLevel& level = search_engine.getSearchLevel(curr_level);
36 level.load(model_sof);
37 }
38 model_sof.close();
39
40 // process the sentence
41 //
42 Filename speech_file(L"$ISIP_DEVEL/doc/examples/data/audio/bg_119oo39a.raw");
43
44 fe.open(speech_file);
45 search_engine.decode(fe);
46 fe.close();
47
48 // get the best hypothesis
49 //
50 String best_hypothesis;
51 float score = 0;
52 long num_frames = 0;
53 search_engine.getHypotheses(best_hypothesis, score, num_frames);
54
55 // print the hypotheses
56 //
57 Console::put(best_hypothesis);
58
59 }
Explanation:
We first configure a FrontEnd object by reading its parameters from the
parameter file (line 20). Then we configure a hierarchical search by
reading each level of the models from a model file (line 32). After we
decode a sentence (line 45), we find the best hypothesis (line 53) and
print it (line 58).
The search classes that are available include:
The software corresponding to the examples demonstrated in this document
can be found in our documentation directory
under class/search/.