Step 1: Create a reverse priority queue  *************************** DONE
---------------------------------------
Partial path hypothesis are stored on stack, partially
ordered over time.

Each stack[timeslot] is implemented as a reverse priority queue
based on a min-heap data structure.

1. At start_t hypothesis in stack[t] are pruned if the
fall outside the beam Delta.

2. Pruned stack is extend in parallel.

Operations need to support
	Delete elements with lowest log probability
	
	After word is extended, hypothesis on stack are checked
	for language model equivalence. Equivalent paths are
	merged (using either viterbi approximation or adding in
	the log domain). This corresponds to changing the 	
	priority of and element in the priority queue.

	Hypothesis only added to stack if it has less than "s"
	entries. If the stack has "s" entries the least probable
	item is deleted. Effect of adaptively decreasing the
	beamwidth in areas of the search with many competing
	hypothesis.


Step 2:	*********************************************************** DONE
-------
Create lexical prefix tree builder.


Step 3: *********************************************************** DONE
------- 
Get single word extension working with optional word initial silence
and pronunciation which have option silence at end of utterance. This
system should be able to do the 8000 word task.

A. Token management (memory management)
	Need to grab from previously allocated tokens
	When node is deactive push token onto stack


Step 4 ************************************************************ DONE
------
At end of the utterance need a MAX heap to get the N-Best scores.
 Setup decoder for HMM and monophone using LVSEARCH.


Step 5 *********************************************************** DONE
------
Extending multiple partial paths over time (I.E. stack decoding)
Backtrace information stored using lattice cells.
When hypothesis is popped from the stack, create word
lattice entries.

	a. loop twice over time, not pipeline
	b. create stack of lattice cells --> not a true word lattice

Words are extended in parellel. All words try to enter the root node
of the tree. With current design this means only the best scoring path
is used. Words are extended based on acoustics only. All nodes which
fall below the beam are pruned. At the word ends, all active paths
which are being extended are now consulted and the language model
probability is applied.

Q: Not sure the impact of cross-word dependent modeling.


Step 6 ********************************************************** DONE
------
Path recombination
Lookup in hash table for equivalent path, and combine
(viterbi approximation/MAP)

The hash table needs to index the reverse priority queue. 
The reverse priority queue can also serve as a N-gram lattice, if
the same data structure is used. (I.E. no additional computation).

Entries in reverse priority queue point to hash table buckets.
Whenever an item is moved up the queue, the data value in
the corresponding hash bucket is changed.


Step 7 
------
Language modeling 1

Use lmtree package
	Build Resource Management LM model
	Build WSJ5k LM model

To take advantage of LM to reduce search space. Compute the maximum
LM probability for each node given the context. This involves
taking the maximum over the LM probabilities for all words that
use that node in their pronunciation given the hypothesis that
are extended. 

Use an approximate upper bound given a context. max_k P(k|j) where j
and k are thre previous and current words respectively. This set of
default words are computed offline and stored in a table.


Step 8 ****************************************************** DONE (!!!)
------
Pruning

Update lub[LP(t)] using simple depth-first process.??  Considers a
single path down the tree by always considering the most probable
successor node at any point, until all successors are outside the
beam. The initial estimate of lub(P(t)) is then updated by backtracing
from any complete word extension found on this path.

Q? How to do a simple depth-first search.
A: Activate, Update, prune all but max


  * a. Word End Pruning 
  * b. Initialize with online garbage model
	Averaged the likelihoods of the N-most probable phones (ranked by
	posterior probability and excluding the mode probable). Combine
	this result with a nominal Markov process score.

	I.E. add them as if it was one long word
	 Q? what is the effect of language models ??????????
	    seems possible that this envelope could ignore LM
	    and therefore have a better score.
	
  * c. Pruning using greedy strategy
  * d. Phone deactivation pruning (Posterior Pruning)
  e. Pruning using backtrace strategy.??????


Need to make sure all nodes in branch are pruned when top level
is pruned.


Step 8 ******************************************************** DONE
------
Duration modeling.
 Minimum duration constraints (maybe same as in old time)

If I use duration model instead of hmm transition probabilities then I
do not need three positions for each token.


Step 9 ******************************************************** DONE
------
Sentence end modeling

First implementation keeps a seperate stack of sentence hypothesis.
One for each time step.

NOTE: This is useful if you want to implement a sentence restart
mechanishm, which can be used for conversational type speech.

Second implementation?:
Do a backward search until path fall outs of beam.  If you assume this
is the sentence end, then you only need to do a backward search based
on word exit silence model. Cool idea.


Step 10 ******************************************************* DONE
------
Scaled likelihoods

Compute prior class probabilities from picked data


Step 11 ******************************************************* DONE
-------
Pipelining (do Last, since it is doable)


Step 12
------
Scaling

  a. Monophone RM task				************* DONE
  b. Monophone WSJ 5k task
  c. Triphone RM task				************* DONE
  d. Triphone WSJ 5k task

  e. Triphone WSJ 20k task



UNIQUE's
--------
Silence pruning combined with adaptive silence detector

Use FeedForward NNET for phone probability estimate

Duration modeling

NOTE: investigate lexical postfix as well, when alternate
pronunciations are proposed based on phonological rules.


NOTE: At the moment all paths in a stack are extended in parallel
      This mean each is popped of the stack and propegated. The
      effect of this is that only the best path is carried forward.
      This will result in a word dependent Nbest search. ???????

      Since word extension is based on acoustics only, what is
      the difference between propegating from a NULL hypothesis
      and then just adding each word which ends to the list
      of hypothesis created. 

      ANSWER: For non cross-word dependent modeling, this should be
      the same. For cross-word dependent modeling?

NOTE: If exact LM probabilities are not incorporated within words,
then within word log probabilities will be greater than word end log
probabilities. This can be taken advantage crudely by using a smaller
pruning beamwidth at the state level compared with the word level.

NOTE: Current implementation uses "cat" option in searchnode to
find the HMM model. 

If transition model probabilities are replaced by state duration
constraints, then "cat" can point directly to the likelihood
array. Therefore also need only one value for bt[] and s[], and need
not to index hmm array so often.

NOTE: Assume a regular structure for HMM models. This make life much
easier for computing state probabibilities since do not require all
these IF statements.


