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 318 of file deterministic-fst-inl.h.

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

Referenced by main().

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

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

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