All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
"Classes and functions related to on-demand deterministic FST's"

Classes

class  DeterministicOnDemandFst< Arc >
 class DeterministicOnDemandFst is an "FST-like" base-class. More...
 
class  BackoffDeterministicOnDemandFst< Arc >
 This class wraps an Fst, representing a language model, using the interface for "BackoffDeterministicOnDemandFst". More...
 
class  ScaleDeterministicOnDemandFst
 Class ScaleDeterministicOnDemandFst takes another DeterministicOnDemandFst and scales the weights (like applying a language-model scale). More...
 
class  UnweightedNgramFst< Arc >
 The class UnweightedNgramFst is a DeterministicOnDemandFst whose states encode an n-gram history. More...
 
class  ComposeDeterministicOnDemandFst< Arc >
 
class  CacheDeterministicOnDemandFst< Arc >
 
class  LmExampleDeterministicOnDemandFst< Arc >
 This class is for didactic purposes, it does not really do anything. More...
 

Functions

template<class Arc >
void ComposeDeterministicOnDemand (const Fst< Arc > &fst1, DeterministicOnDemandFst< Arc > *fst2, MutableFst< Arc > *fst_composed)
 
template<class Arc >
void ComposeDeterministicOnDemandInverse (const Fst< Arc > &fst1, DeterministicOnDemandFst< Arc > *fst2, MutableFst< Arc > *fst_composed)
 This function does '*fst_composed = Compose(Inverse(*fst2), fst1)' Note that the arguments are reversed; this is unfortunate but it's because the fst2 argument needs to be non-const and non-const arguments must follow const ones. More...
 

Detailed Description

Function Documentation

void ComposeDeterministicOnDemand ( const Fst< Arc > &  fst1,
DeterministicOnDemandFst< Arc > *  fst2,
MutableFst< Arc > *  fst_composed 
)

Definition at line 317 of file deterministic-fst-inl.h.

References DeterministicOnDemandFst< Arc >::Final(), DeterministicOnDemandFst< Arc >::GetArc(), KALDI_ASSERT, DeterministicOnDemandFst< Arc >::Start(), and fst::Times().

Referenced by main().

319  {
320  typedef typename Arc::Weight Weight;
321  typedef typename Arc::StateId StateId;
322  typedef std::pair<StateId, StateId> StatePair;
323  typedef unordered_map<StatePair, StateId,
324  kaldi::PairHasher<StateId> > MapType;
325  typedef typename MapType::iterator IterType;
326 
327  fst_composed->DeleteStates();
328 
329  MapType state_map;
330  std::queue<StatePair> state_queue;
331 
332  // Set start state in fst_composed.
333  StateId s1 = fst1.Start(),
334  s2 = fst2->Start(),
335  start_state = fst_composed->AddState();
336  StatePair start_pair(s1, s2);
337  state_queue.push(start_pair);
338  fst_composed->SetStart(start_state);
339  // A mapping between pairs of states in fst1 and fst2 and the corresponding
340  // state in fst_composed.
341  std::pair<const StatePair, StateId> start_map(start_pair, start_state);
342  std::pair<IterType, bool> result = state_map.insert(start_map);
343  KALDI_ASSERT(result.second == true);
344 
345  while (!state_queue.empty()) {
346  StatePair q = state_queue.front();
347  StateId q1 = q.first,
348  q2 = q.second;
349  state_queue.pop();
350  // If the product of the final weights of the two fsts is non-zero then
351  // we can set a final-prob in fst_composed
352  Weight final_weight = Times(fst1.Final(q1), fst2->Final(q2));
353  if (final_weight != Weight::Zero()) {
354  KALDI_ASSERT(state_map.find(q) != state_map.end());
355  fst_composed->SetFinal(state_map[q], final_weight);
356  }
357 
358  // for each pair of edges from fst1 and fst2 at q1 and q2.
359  for (ArcIterator<Fst<Arc> > aiter(fst1, q1); !aiter.Done(); aiter.Next()) {
360  const Arc &arc1 = aiter.Value();
361  Arc arc2;
362  StatePair next_pair;
363  StateId next_state1 = arc1.nextstate,
364  next_state2,
365  next_state;
366  // If there is an epsilon on the arc of fst1 we transition to the next
367  // state but keep fst2 at the current state.
368  if (arc1.olabel == 0) {
369  next_state2 = q2;
370  } else {
371  bool match = fst2->GetArc(q2, arc1.olabel, &arc2);
372  if (!match) // There is no matching arc -> nothing to do.
373  continue;
374  next_state2 = arc2.nextstate;
375  }
376  next_pair = StatePair(next_state1, next_state2);
377  IterType sitr = state_map.find(next_pair);
378  // If sitr == state_map.end() then the state isn't in fst_composed yet.
379  if (sitr == state_map.end()) {
380  next_state = fst_composed->AddState();
381  std::pair<const StatePair, StateId> new_state(
382  next_pair, next_state);
383  std::pair<IterType, bool> result = state_map.insert(new_state);
384  // Since we already checked if state_map contained new_state,
385  // it should always be added if we reach here.
386  KALDI_ASSERT(result.second == true);
387  state_queue.push(next_pair);
388  // If sitr != state_map.end() then the next state is already in
389  // the state_map.
390  } else {
391  next_state = sitr->second;
392  }
393  if (arc1.olabel == 0) {
394  fst_composed->AddArc(state_map[q], Arc(arc1.ilabel, 0, arc1.weight,
395  next_state));
396  } else {
397  fst_composed->AddArc(state_map[q], Arc(arc1.ilabel, arc2.olabel,
398  Times(arc1.weight, arc2.weight), next_state));
399  }
400  }
401  }
402 }
fst::StdArc::StateId StateId
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
A hashing function-object for pairs of ints.
Definition: stl-utils.h:237
void ComposeDeterministicOnDemandInverse ( const Fst< Arc > &  fst1,
DeterministicOnDemandFst< Arc > *  fst2,
MutableFst< Arc > *  fst_composed 
)

This function does '*fst_composed = Compose(Inverse(*fst2), fst1)' Note that the arguments are reversed; this is unfortunate but it's because the fst2 argument needs to be non-const and non-const arguments must follow const ones.

This is the counterpart to ComposeDeterministicOnDemand, used for the case where the DeterministicOnDemandFst is on the left. The reason why we need to make the left-hand argument to compose the inverse of 'fst2' (i.e. with the input and output symbols swapped), is that the DeterministicOnDemandFst interface only supports lookup by ilabel (see its function GetArc). This does not call Connect.

Definition at line 407 of file deterministic-fst-inl.h.

References DeterministicOnDemandFst< Arc >::Final(), DeterministicOnDemandFst< Arc >::GetArc(), KALDI_ASSERT, DeterministicOnDemandFst< Arc >::Start(), kaldi::swap(), and fst::Times().

409  {
410  typedef typename Arc::Weight Weight;
411  typedef typename Arc::StateId StateId;
412  typedef std::pair<StateId, StateId> StatePair;
413  typedef unordered_map<StatePair, StateId,
414  kaldi::PairHasher<StateId> > MapType;
415  typedef typename MapType::iterator IterType;
416 
417  fst_composed->DeleteStates();
418 
419  // the queue and map contain pairs (state-in-left, state-in-right)
420  MapType state_map;
421  std::queue<StatePair> state_queue;
422 
423  // Set start state in fst_composed.
424  StateId s_left = left->Start(),
425  s_right = right.Start(),
426  start_state = fst_composed->AddState();
427  StatePair start_pair(s_left, s_right);
428  state_queue.push(start_pair);
429  fst_composed->SetStart(start_state);
430  // A mapping between pairs of states in *left and right, and the corresponding
431  // state in fst_composed.
432  std::pair<const StatePair, StateId> start_map(start_pair, start_state);
433  std::pair<IterType, bool> result = state_map.insert(start_map);
434  KALDI_ASSERT(result.second == true);
435 
436  while (!state_queue.empty()) {
437  StatePair q = state_queue.front();
438  StateId q_left = q.first,
439  q_right = q.second;
440  state_queue.pop();
441  // If the product of the final weights of the two fsts is non-zero then
442  // we can set a final-prob in fst_composed
443  Weight final_weight = Times(left->Final(q_left), right.Final(q_right));
444  if (final_weight != Weight::Zero()) {
445  KALDI_ASSERT(state_map.find(q) != state_map.end());
446  fst_composed->SetFinal(state_map[q], final_weight);
447  }
448 
449  for (ArcIterator<Fst<Arc> > aiter(right, q_right); !aiter.Done(); aiter.Next()) {
450  const Arc &arc_right = aiter.Value();
451  Arc arc_left;
452  StatePair next_pair;
453  StateId next_state_right = arc_right.nextstate,
454  next_state_left,
455  next_state;
456  // If there is an epsilon on the input side of the rigth arc, we
457  // transition to the next state of the output but keep 'left' at the
458  // current state.
459  if (arc_right.ilabel == 0) {
460  next_state_left = q_left;
461  } else {
462  bool match = left->GetArc(q_left, arc_right.ilabel, &arc_left);
463  if (!match) // There is no matching arc -> nothing to do.
464  continue;
465  // the next 'swap' is because we are composing with the inverse of
466  // *left. Just removing the swap statement wouldn't let us compose
467  // with non-inverted *left though, because the GetArc function call
468  // above interprets the second argument as an ilabel not an olabel.
469  std::swap(arc_left.ilabel, arc_left.olabel);
470  next_state_left = arc_left.nextstate;
471  }
472  next_pair = StatePair(next_state_left, next_state_right);
473  IterType sitr = state_map.find(next_pair);
474  // If sitr == state_map.end() then the state isn't in fst_composed yet.
475  if (sitr == state_map.end()) {
476  next_state = fst_composed->AddState();
477  std::pair<const StatePair, StateId> new_state(
478  next_pair, next_state);
479  std::pair<IterType, bool> result = state_map.insert(new_state);
480  // Since we already checked if state_map contained new_state,
481  // it should always be added if we reach here.
482  KALDI_ASSERT(result.second == true);
483  state_queue.push(next_pair);
484  // If sitr != state_map.end() then the next state is already in
485  // the state_map.
486  } else {
487  next_state = sitr->second;
488  }
489  if (arc_right.ilabel == 0) {
490  // we didn't get an actual arc from the left FST.
491  fst_composed->AddArc(state_map[q], Arc(0, arc_right.olabel,
492  arc_right.weight,
493  next_state));
494  } else {
495  fst_composed->AddArc(state_map[q],
496  Arc(arc_left.ilabel, arc_right.olabel,
497  Times(arc_left.weight, arc_right.weight),
498  next_state));
499  }
500  }
501  }
502 }
fst::StdArc::StateId StateId
void swap(basic_filebuf< CharT, Traits > &x, basic_filebuf< CharT, Traits > &y)
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
A hashing function-object for pairs of ints.
Definition: stl-utils.h:237