"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

◆ ComposeDeterministicOnDemand()

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:185
A hashing function-object for pairs of ints.
Definition: stl-utils.h:235

◆ ComposeDeterministicOnDemandInverse()

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().

Referenced by TrainingGraphCompiler::CompileGraph(), TrainingGraphCompiler::CompileGraphs(), fst::ComposeContext(), fst::ComposeContextLeftBiphone(), and fst::TestContextFst().

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