<commit_before>#include "HmmNetBaumWelch.hh"
#include "str.hh"


HmmNetBaumWelch::LLType HmmNetBaumWelch::loglikelihoods;


HmmNetBaumWelch::HmmNetBaumWelch(FeatureGenerator &fea_gen, HmmSet &model)
  : m_fea_gen(fea_gen), m_model(model)
{
  m_initial_node_id = -1;
  m_final_node_id = -1;
  m_epsilon_string = ",";
  m_first_frame = m_last_frame = 0;
  m_eof_flag = false;
  m_cur_buffer = 0;
  m_collect_transitions = 0;
  m_acoustic_scale = 1;

  // Default mode
  m_mode = MODE_BAUM_WELCH;

  m_custom_data_callback = NULL; // Not in use by default

  // Default pruning thresholds
  m_forward_beam = 15;
  m_backward_beam = 100;

  // Total statistics
  m_sum_total_loglikelihood = loglikelihoods.zero();
  m_sum_total_custom_score = 0;
}

HmmNetBaumWelch::~HmmNetBaumWelch()
{
  close();
}

void
HmmNetBaumWelch::open(std::string ref_file)
{
  FILE *fp = fopen(ref_file.c_str(), "r");
  if (fp == NULL)
    throw std::string("Could not open file ")+ref_file;
  read_fst(fp);
  fclose(fp);
}

void 
HmmNetBaumWelch::read_fst(FILE *file)
{
  close();
  m_initial_node_id = -1;
  m_final_node_id = -1;

  std::string line;
  std::vector<std::string> fields;
  bool ok = true;

  while (str::read_line(&line, file, true)) {
    str::split(&line, " \t", true, &fields);
    if (fields[0] == "#FSTBinary")
      throw std::string("FSTBinary format not supported");

    // Initial node
    // 
    if (fields[0] == "I") {
      if (fields.size() != 2)
        ok = false;
      else
        m_initial_node_id = str::str2long(&fields[1], &ok);
      if (!ok || m_initial_node_id < 0)
        throw std::string("invalid initial node specification: ") + line;
    }
    // Final node
    //
    else if (fields[0] == "F") {
      if (m_final_node_id != -1)
        throw std::string("final node redefined: ") + line;

      if (fields.size() != 2 && fields.size() != 3)
        ok = false;
      else {
        m_final_node_id = str::str2long(&fields[1], &ok);
      }

      if (!ok || m_final_node_id < 0)
        throw std::string("invalid final node specification: ") + line;

      while ((int)m_nodes.size() <= m_final_node_id)
        m_nodes.push_back(Node(m_nodes.size()));
    }

    // Transition
    //
    else if (fields[0] == "T") {
      int source = -1;
      int target = -1;
      int in = -1;
      std::string label = "";
      double score = loglikelihoods.one();

      if (fields.size() < 3 || fields.size() > 6)
        ok = false;
      else {
        source = str::str2long(&fields[1], &ok);
        target = str::str2long(&fields[2], &ok);
        if (fields.size() > 3) {
          if (fields[3] == m_epsilon_string)
            in = EPSILON;
          else
          {
            if (fields[3].substr(0, 1) == "#")
            {
              // Special epsilon arc with triphone label
              in = EPSILON;
              label = fields[3].substr(1);
            }
            else
            {
              int n = fields[3].find_first_of('-');
              if (n > 0 && n < (int)fields[3].size())
              {
                std::string num = fields[3].substr(0, n);
                in = str::str2long(&num, &ok);
                label = fields[3].substr(n+1);
              }
              else
                throw std::string("HmmNetBaumWelch: Invalid input symbol ") + fields[3];
            }
          }
        }
//         if (fields.size() > 4) {
//           if (fields[4] == m_epsilon_string)
//             out = "";
//           else
//             out = fields[4];
//         }
        if (fields.size() > 5)
          score = str::str2float(&fields[5], &ok);
      }

      if (!ok || source < 0 || target < 0)
        throw std::string("HmmNetBaumWelch: Invalid transition specification: ") + line;

      while ((int)m_nodes.size() <= source || (int)m_nodes.size() <= target)
        m_nodes.push_back(Node(m_nodes.size()));

      Node &src_node = m_nodes.at(source);
      Node &target_node = m_nodes.at(target);
      int arc_index = m_arcs.size();
      m_arcs.push_back(Arc(arc_index, source, target, in, label, score));
      src_node.out_arcs.push_back(arc_index);
      target_node.in_arcs.push_back(arc_index);
    }
  }

  if (m_initial_node_id < 0)
    throw std::string("initial node not specified");
  if (m_final_node_id < 0)
    throw std::string("final node not specified");

  check_network_structure();
}


void
HmmNetBaumWelch::close(void)
{
  clear_bw_scores();
  
  m_transition_prob.clear();
  m_active_transition_table.clear();
  m_pdf_prob.clear();
  m_active_pdf_table.clear();
  m_active_arcs.clear();
  m_active_node_table[0].clear();
  m_active_node_table[1].clear();
  m_nodes.clear();
  m_arcs.clear();
}


void
HmmNetBaumWelch::set_frame_limits(int first_frame, int last_frame) 
{
  m_first_frame = first_frame;
  m_last_frame = last_frame;
}


void
HmmNetBaumWelch::set_pruning_thresholds(double backward, double forward)
{
  if (backward > 0)
    m_backward_beam = backward;
  if (forward > 0)
    m_forward_beam = forward;
}


void
HmmNetBaumWelch::check_network_structure(void)
{
  for (int i = 0; i < (int)m_nodes.size(); i++)
  {
    bool epsilon_transitions = false;
    int non_eps_in_transitions = 0;
    bool self_transition = false;
    
    // Check the in arcs
    for (int j = 0; j < (int)m_nodes[i].in_arcs.size(); j++)
    {
      int arc_id = m_nodes[i].in_arcs[j];
      if (m_arcs[arc_id].epsilon())
      {
        if (m_arcs[arc_id].target == m_arcs[arc_id].source)
          throw std::string("HmmNetBaumWelch: Epsilon self loops are not allowed");
        if (non_eps_in_transitions > 0)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions to a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        epsilon_transitions = true;
      }
      else if (m_arcs[arc_id].target != m_arcs[arc_id].source)
      {
        if (epsilon_transitions)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions to a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        non_eps_in_transitions++;
      }
      else
        self_transition = true;
    }

    int eps_out_transitions = 0;
    int non_eps_out_transitions = 0;

    // Check the out arcs
    for (int j = 0; j < (int)m_nodes[i].out_arcs.size(); j++)
    {
      int arc_id = m_nodes[i].out_arcs[j];
      if (m_arcs[arc_id].epsilon())
      {
        if (m_arcs[arc_id].target == m_arcs[arc_id].source)
          throw std::string("HmmNetBaumWelch: Epsilon self loops are not allowed");
        if (non_eps_out_transitions > 0)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions from a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        eps_out_transitions++;
      }
      else if (m_arcs[arc_id].target != m_arcs[arc_id].source)
      {
        if (eps_out_transitions > 0)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions from a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        non_eps_out_transitions++;
      }
      else
        self_transition = true;
    }

    if (non_eps_out_transitions > 1)
      throw std::string("HmmNetBaumWelch: Only one non epsilon transition from a node is allowed");
    if (non_eps_in_transitions>1 && (!eps_out_transitions || self_transition))
      throw std::string("HmmNetBaumWelch: Multiple non epsilon transitions to a node are allowed only when the node has only epsilon out transitions");

    if (eps_out_transitions > 1 && self_transition)
      throw std::string("HmmNetBaumWelch: A node may not have a self transition if it has multiple (epsilon) out transitions");

    if (eps_out_transitions > 0)
    {
      assert( non_eps_out_transitions == 0 ); // This is checked above
      m_nodes[i].num_epsilon_out = eps_out_transitions;
    }
  }

  if (m_nodes[m_initial_node_id].num_epsilon_out == 0)
    throw std::string("HmmNetBaumWelch: Initial node must have only epsilon out arcs!");
  if (m_nodes[m_initial_node_id].in_arcs.size() > 0)
    throw std::string("HmmNetBaumWelch: Initial node may not have in arcs!");
  if (m_nodes[m_final_node_id].out_arcs.size() > 0)
    throw std::string("HmmNetBaumWelch: Final node may not have out arcs!");
}


void
HmmNetBaumWelch::reset(void)
{
  m_eof_flag = false;
  m_current_frame = -1;
  // Clear the probabilities of the possibly active nodes
  for (int b = 0; b < 2; b++)
  {
    for (int i = 0; i < (int)m_active_node_table[b].size(); i++)
      m_nodes[m_active_node_table[b][i]].log_prob[b] = loglikelihoods.zero();
    m_active_node_table[b].clear();
  }
  m_transition_prob.clear();
  m_active_transition_table.clear();
  m_pdf_prob.clear();
  m_active_pdf_table.clear();
  m_active_arcs.clear();

  m_sum_total_loglikelihood = loglikelihoods.zero();
  m_sum_total_custom_score = 0;
}


bool
HmmNetBaumWelch::init_utterance_segmentation(void)
{
  reset();
  
  // Reserve a table for pdf occupancy probabilities
  m_pdf_prob.resize(m_model.num_emission_pdfs());

  if (m_collect_transitions)
    m_transition_prob.resize(m_model.num_transitions());

  // Fill the backward probabilities
  if (!fill_backward_probabilities())
    return false; // Backward beam should be increased

  // Compute the total likelihood and check the backward phase got
  // proper probabilities for the initial nodes
  compute_total_bw_scores();
  if (m_sum_total_loglikelihood <= loglikelihoods.zero())
    return false; // Backward beam should be increased
  
  return true;
}


bool
HmmNetBaumWelch::fill_backward_probabilities(void)
{
  int target_buffer = 0;
  double best_log_prob;
  //double prev_max_log_prob = loglikelihoods.one();
  
  clear_bw_scores();
  if (m_last_frame > 0)
    m_current_frame = m_last_frame + 1;
  else
    m_current_frame = m_fea_gen.last_frame() + 1;

  // Initialize the final node
  m_nodes[m_final_node_id].log_prob[target_buffer] = loglikelihoods.one();
  m_nodes[m_final_node_id].custom_score[target_buffer] = 0;
  assert( m_active_node_table[0].empty() );
  assert( m_active_node_table[1].empty() );
  m_active_node_table[target_buffer].push_back(m_final_node_id);

  // Propagate the epsilon arcs leading to the final node
  for (int i = 0; i < (int)m_active_node_table[target_buffer].size(); i++)
  {
    FeatureVec empty_fea_vec;
    backward_propagate_node_arcs(
      m_active_node_table[target_buffer][i],
      m_nodes[m_active_node_table[target_buffer][i]].log_prob[target_buffer],
      m_nodes[m_active_node_table[target_buffer][i]].custom_score[target_buffer],
      target_buffer, true, empty_fea_vec, loglikelihoods.zero());
  }

  while (m_current_frame > m_first_frame)
  {
    FeatureVec fea_vec = m_fea_gen.generate(--m_current_frame);
    int source_buffer = target_buffer;
    target_buffer ^= 1;

    best_log_prob = loglikelihoods.zero();

    m_model.reset_cache();

    // Iterate through active nodes and propagate the normal transitions.
    // Fill the backward probabilities for the arcs.
    for (int i = 0; i < (int)m_active_node_table[source_buffer].size(); i++)
    {
      double cur_node_score =
        m_nodes[m_active_node_table[source_buffer][i]].log_prob[source_buffer];

      // Propagate the node only if its loglikelihood is within the beam
//       if (loglikelihoods.divide(cur_node_score, prev_max_log_prob) >
//           -m_backward_beam)
//       {
      double temp = backward_propagate_node_arcs(
        m_active_node_table[source_buffer][i], cur_node_score,
        m_nodes[m_active_node_table[source_buffer][i]].custom_score[source_buffer],
        target_buffer, false, fea_vec, best_log_prob);
        
      if (temp > best_log_prob)
        best_log_prob = temp;
//      }

      // Reset the probability
      m_nodes[m_active_node_table[source_buffer][i]].log_prob[source_buffer] =
        loglikelihoods.zero();
    }

    // Clear the old active nodes
    m_active_node_table[source_buffer].clear();

//     if (m_active_node_table[target_buffer].empty())
//     {
//       // All tokens were pruned, backward beam should be increased
//       return false;
//     }

//     // Update the maximum probability used for pruning
//     prev_max_log_prob = max_log_prob;

    assert( !m_active_node_table[target_buffer].empty() );
    
    // Iterate through active nodes and propagate the epsilon transitions.
    // The new active nodes are appended to the end of m_active_node_table.
    // The previous probabilities are taken from the target buffer. Also
    // fills the backward probabilities of epsilon arcs.
    // Identifies the best active node which will be moved to the first
    // position.
    double temp_max_log_prob = loglikelihoods.zero();
    int best_log_prob_node_index = -1;
    for (int i = 0; i < (int)m_active_node_table[target_buffer].size(); i++)
    {
      double cur_node_score =
        m_nodes[m_active_node_table[target_buffer][i]].log_prob[target_buffer];
      // Propagate the node only if its loglikelihood is within the beam
      if (loglikelihoods.divide(cur_node_score, best_log_prob) >
          -m_backward_beam)
      {
        // No pruning during these propagations!
        backward_propagate_node_arcs(
          m_active_node_table[target_buffer][i], cur_node_score,
          m_nodes[m_active_node_table[target_buffer][i]].custom_score[target_buffer],
          target_buffer, true, fea_vec, loglikelihoods.zero());
      }
      if (cur_node_score > temp_max_log_prob &&
          (int)m_nodes[m_active_node_table[target_buffer][i]].out_arcs.size() >
          m_nodes[m_active_node_table[target_buffer][i]].num_epsilon_out)
      {
        // "The best node" is required to have non-epsilon arcs
        temp_max_log_prob = cur_node_score;
        best_log_prob_node_index = i;
      }
    }

    // Move the best node to the beginning of the active node table to
    // enhance pruning
    if (best_log_prob_node_index != -1)
    {
      int temp_active_node = m_active_node_table[target_buffer][0];
      m_active_node_table[target_buffer][0] =
        m_active_node_table[target_buffer][best_log_prob_node_index];
      m_active_node_table[target_buffer][best_log_prob_node_index] =
        temp_active_node;
    }

  }

  // Clear the active nodes
  for (int i = 0; i < (int)m_active_node_table[target_buffer].size(); i++)
    m_nodes[m_active_node_table[target_buffer][i]].log_prob[target_buffer] =
      loglikelihoods.zero();
  m_active_node_table[target_buffer].clear();
  
  // Reset the current frame for the forward phase
  m_current_frame = -1;
  m_eof_flag = false;
  return true;
}
<commit_msg>Some more pruning and comment removal<commit_after>#include "HmmNetBaumWelch.hh"
#include "str.hh"


HmmNetBaumWelch::LLType HmmNetBaumWelch::loglikelihoods;


HmmNetBaumWelch::HmmNetBaumWelch(FeatureGenerator &fea_gen, HmmSet &model)
  : m_fea_gen(fea_gen), m_model(model)
{
  m_initial_node_id = -1;
  m_final_node_id = -1;
  m_epsilon_string = ",";
  m_first_frame = m_last_frame = 0;
  m_eof_flag = false;
  m_cur_buffer = 0;
  m_collect_transitions = 0;
  m_acoustic_scale = 1;

  // Default mode
  m_mode = MODE_BAUM_WELCH;

  m_custom_data_callback = NULL; // Not in use by default

  // Default pruning thresholds
  m_forward_beam = 15;
  m_backward_beam = 100;

  // Total statistics
  m_sum_total_loglikelihood = loglikelihoods.zero();
  m_sum_total_custom_score = 0;
}

HmmNetBaumWelch::~HmmNetBaumWelch()
{
  close();
}

void
HmmNetBaumWelch::open(std::string ref_file)
{
  FILE *fp = fopen(ref_file.c_str(), "r");
  if (fp == NULL)
    throw std::string("Could not open file ")+ref_file;
  read_fst(fp);
  fclose(fp);
}

void 
HmmNetBaumWelch::read_fst(FILE *file)
{
  close();
  m_initial_node_id = -1;
  m_final_node_id = -1;

  std::string line;
  std::vector<std::string> fields;
  bool ok = true;

  while (str::read_line(&line, file, true)) {
    str::split(&line, " \t", true, &fields);
    if (fields[0] == "#FSTBinary")
      throw std::string("FSTBinary format not supported");

    // Initial node
    // 
    if (fields[0] == "I") {
      if (fields.size() != 2)
        ok = false;
      else
        m_initial_node_id = str::str2long(&fields[1], &ok);
      if (!ok || m_initial_node_id < 0)
        throw std::string("invalid initial node specification: ") + line;
    }
    // Final node
    //
    else if (fields[0] == "F") {
      if (m_final_node_id != -1)
        throw std::string("final node redefined: ") + line;

      if (fields.size() != 2 && fields.size() != 3)
        ok = false;
      else {
        m_final_node_id = str::str2long(&fields[1], &ok);
      }

      if (!ok || m_final_node_id < 0)
        throw std::string("invalid final node specification: ") + line;

      while ((int)m_nodes.size() <= m_final_node_id)
        m_nodes.push_back(Node(m_nodes.size()));
    }

    // Transition
    //
    else if (fields[0] == "T") {
      int source = -1;
      int target = -1;
      int in = -1;
      std::string label = "";
      double score = loglikelihoods.one();

      if (fields.size() < 3 || fields.size() > 6)
        ok = false;
      else {
        source = str::str2long(&fields[1], &ok);
        target = str::str2long(&fields[2], &ok);
        if (fields.size() > 3) {
          if (fields[3] == m_epsilon_string)
            in = EPSILON;
          else
          {
            if (fields[3].substr(0, 1) == "#")
            {
              // Special epsilon arc with triphone label
              in = EPSILON;
              label = fields[3].substr(1);
            }
            else
            {
              int n = fields[3].find_first_of('-');
              if (n > 0 && n < (int)fields[3].size())
              {
                std::string num = fields[3].substr(0, n);
                in = str::str2long(&num, &ok);
                label = fields[3].substr(n+1);
              }
              else
                throw std::string("HmmNetBaumWelch: Invalid input symbol ") + fields[3];
            }
          }
        }
//         if (fields.size() > 4) {
//           if (fields[4] == m_epsilon_string)
//             out = "";
//           else
//             out = fields[4];
//         }
        if (fields.size() > 5)
          score = str::str2float(&fields[5], &ok);
      }

      if (!ok || source < 0 || target < 0)
        throw std::string("HmmNetBaumWelch: Invalid transition specification: ") + line;

      while ((int)m_nodes.size() <= source || (int)m_nodes.size() <= target)
        m_nodes.push_back(Node(m_nodes.size()));

      Node &src_node = m_nodes.at(source);
      Node &target_node = m_nodes.at(target);
      int arc_index = m_arcs.size();
      m_arcs.push_back(Arc(arc_index, source, target, in, label, score));
      src_node.out_arcs.push_back(arc_index);
      target_node.in_arcs.push_back(arc_index);
    }
  }

  if (m_initial_node_id < 0)
    throw std::string("initial node not specified");
  if (m_final_node_id < 0)
    throw std::string("final node not specified");

  check_network_structure();
}


void
HmmNetBaumWelch::close(void)
{
  clear_bw_scores();
  
  m_transition_prob.clear();
  m_active_transition_table.clear();
  m_pdf_prob.clear();
  m_active_pdf_table.clear();
  m_active_arcs.clear();
  m_active_node_table[0].clear();
  m_active_node_table[1].clear();
  m_nodes.clear();
  m_arcs.clear();
}


void
HmmNetBaumWelch::set_frame_limits(int first_frame, int last_frame) 
{
  m_first_frame = first_frame;
  m_last_frame = last_frame;
}


void
HmmNetBaumWelch::set_pruning_thresholds(double backward, double forward)
{
  if (backward > 0)
    m_backward_beam = backward;
  if (forward > 0)
    m_forward_beam = forward;
}


void
HmmNetBaumWelch::check_network_structure(void)
{
  for (int i = 0; i < (int)m_nodes.size(); i++)
  {
    bool epsilon_transitions = false;
    int non_eps_in_transitions = 0;
    bool self_transition = false;
    
    // Check the in arcs
    for (int j = 0; j < (int)m_nodes[i].in_arcs.size(); j++)
    {
      int arc_id = m_nodes[i].in_arcs[j];
      if (m_arcs[arc_id].epsilon())
      {
        if (m_arcs[arc_id].target == m_arcs[arc_id].source)
          throw std::string("HmmNetBaumWelch: Epsilon self loops are not allowed");
        if (non_eps_in_transitions > 0)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions to a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        epsilon_transitions = true;
      }
      else if (m_arcs[arc_id].target != m_arcs[arc_id].source)
      {
        if (epsilon_transitions)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions to a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        non_eps_in_transitions++;
      }
      else
        self_transition = true;
    }

    int eps_out_transitions = 0;
    int non_eps_out_transitions = 0;

    // Check the out arcs
    for (int j = 0; j < (int)m_nodes[i].out_arcs.size(); j++)
    {
      int arc_id = m_nodes[i].out_arcs[j];
      if (m_arcs[arc_id].epsilon())
      {
        if (m_arcs[arc_id].target == m_arcs[arc_id].source)
          throw std::string("HmmNetBaumWelch: Epsilon self loops are not allowed");
        if (non_eps_out_transitions > 0)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions from a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        eps_out_transitions++;
      }
      else if (m_arcs[arc_id].target != m_arcs[arc_id].source)
      {
        if (eps_out_transitions > 0)
          throw std::string("HmmNetBaumWelch: Both epsilon and normal transitions from a node (detected at ") + m_arcs[arc_id].label + std::string(")");
        non_eps_out_transitions++;
      }
      else
        self_transition = true;
    }

    if (non_eps_out_transitions > 1)
      throw std::string("HmmNetBaumWelch: Only one non epsilon transition from a node is allowed");
    if (non_eps_in_transitions>1 && (!eps_out_transitions || self_transition))
      throw std::string("HmmNetBaumWelch: Multiple non epsilon transitions to a node are allowed only when the node has only epsilon out transitions");

    if (eps_out_transitions > 1 && self_transition)
      throw std::string("HmmNetBaumWelch: A node may not have a self transition if it has multiple (epsilon) out transitions");

    if (eps_out_transitions > 0)
    {
      assert( non_eps_out_transitions == 0 ); // This is checked above
      m_nodes[i].num_epsilon_out = eps_out_transitions;
    }
  }

  if (m_nodes[m_initial_node_id].num_epsilon_out == 0)
    throw std::string("HmmNetBaumWelch: Initial node must have only epsilon out arcs!");
  if (m_nodes[m_initial_node_id].in_arcs.size() > 0)
    throw std::string("HmmNetBaumWelch: Initial node may not have in arcs!");
  if (m_nodes[m_final_node_id].out_arcs.size() > 0)
    throw std::string("HmmNetBaumWelch: Final node may not have out arcs!");
}


void
HmmNetBaumWelch::reset(void)
{
  m_eof_flag = false;
  m_current_frame = -1;
  // Clear the probabilities of the possibly active nodes
  for (int b = 0; b < 2; b++)
  {
    for (int i = 0; i < (int)m_active_node_table[b].size(); i++)
      m_nodes[m_active_node_table[b][i]].log_prob[b] = loglikelihoods.zero();
    m_active_node_table[b].clear();
  }
  m_transition_prob.clear();
  m_active_transition_table.clear();
  m_pdf_prob.clear();
  m_active_pdf_table.clear();
  m_active_arcs.clear();

  m_sum_total_loglikelihood = loglikelihoods.zero();
  m_sum_total_custom_score = 0;
}


bool
HmmNetBaumWelch::init_utterance_segmentation(void)
{
  reset();
  
  // Reserve a table for pdf occupancy probabilities
  m_pdf_prob.resize(m_model.num_emission_pdfs());

  if (m_collect_transitions)
    m_transition_prob.resize(m_model.num_transitions());

  // Fill the backward probabilities
  if (!fill_backward_probabilities())
    return false; // Backward beam should be increased

  // Compute the total likelihood and check the backward phase got
  // proper probabilities for the initial nodes
  compute_total_bw_scores();
  if (m_sum_total_loglikelihood <= loglikelihoods.zero())
    return false; // Backward beam should be increased
  
  return true;
}


bool
HmmNetBaumWelch::fill_backward_probabilities(void)
{
  int target_buffer = 0;
  double best_log_prob;
  //double prev_max_log_prob = loglikelihoods.one();
  
  clear_bw_scores();
  if (m_last_frame > 0)
    m_current_frame = m_last_frame + 1;
  else
    m_current_frame = m_fea_gen.last_frame() + 1;

  // Initialize the final node
  m_nodes[m_final_node_id].log_prob[target_buffer] = loglikelihoods.one();
  m_nodes[m_final_node_id].custom_score[target_buffer] = 0;
  assert( m_active_node_table[0].empty() );
  assert( m_active_node_table[1].empty() );
  m_active_node_table[target_buffer].push_back(m_final_node_id);

  // Propagate the epsilon arcs leading to the final node
  for (int i = 0; i < (int)m_active_node_table[target_buffer].size(); i++)
  {
    FeatureVec empty_fea_vec;
    backward_propagate_node_arcs(
      m_active_node_table[target_buffer][i],
      m_nodes[m_active_node_table[target_buffer][i]].log_prob[target_buffer],
      m_nodes[m_active_node_table[target_buffer][i]].custom_score[target_buffer],
      target_buffer, true, empty_fea_vec, loglikelihoods.zero());
  }

  while (m_current_frame > m_first_frame)
  {
    FeatureVec fea_vec = m_fea_gen.generate(--m_current_frame);
    int source_buffer = target_buffer;
    target_buffer ^= 1;

    best_log_prob = loglikelihoods.zero();

    m_model.reset_cache();

    // Iterate through active nodes and propagate the normal transitions.
    // Fill the backward probabilities for the arcs.
    for (int i = 0; i < (int)m_active_node_table[source_buffer].size(); i++)
    {
      if (m_active_node_table[source_buffer][i] != -1)
      {
        double cur_node_score =
          m_nodes[m_active_node_table[source_buffer][i]].log_prob[source_buffer];
        double temp = backward_propagate_node_arcs(
          m_active_node_table[source_buffer][i], cur_node_score,
          m_nodes[m_active_node_table[source_buffer][i]].custom_score[source_buffer],
          target_buffer, false, fea_vec, best_log_prob);
        
        if (temp > best_log_prob)
          best_log_prob = temp;

        // Reset the probability
        m_nodes[m_active_node_table[source_buffer][i]].log_prob[source_buffer]=
          loglikelihoods.zero();
      }
    }

    // Clear the old active nodes
    m_active_node_table[source_buffer].clear();

    assert( !m_active_node_table[target_buffer].empty() );
    
    // Iterate through active nodes and propagate the epsilon transitions.
    // The new active nodes are appended to the end of m_active_node_table.
    // The previous probabilities are taken from the target buffer. Also
    // fills the backward probabilities of epsilon arcs.
    // Identifies the best active node which will be moved to the first
    // position.
    double temp_max_log_prob = loglikelihoods.zero();
    int best_log_prob_node_index = -1;
    for (int i = 0; i < (int)m_active_node_table[target_buffer].size(); i++)
    {
      double cur_node_score =
        m_nodes[m_active_node_table[target_buffer][i]].log_prob[target_buffer];
      // Propagate the node only if its loglikelihood is within the beam
      if (loglikelihoods.divide(cur_node_score, best_log_prob) >
          -m_backward_beam)
      {
        // No pruning during these propagations!
        backward_propagate_node_arcs(
          m_active_node_table[target_buffer][i], cur_node_score,
          m_nodes[m_active_node_table[target_buffer][i]].custom_score[target_buffer],
          target_buffer, true, fea_vec, loglikelihoods.zero());

        if (cur_node_score > temp_max_log_prob &&
            (int)m_nodes[m_active_node_table[target_buffer][i]].out_arcs.size() >
            m_nodes[m_active_node_table[target_buffer][i]].num_epsilon_out)
        {
          // "The best node" is required to have non-epsilon arcs
          temp_max_log_prob = cur_node_score;
          best_log_prob_node_index = i;
        }
      }
      else
      {
        // Reset the probability
        m_nodes[m_active_node_table[target_buffer][i]].log_prob[target_buffer]=
          loglikelihoods.zero();
        // Do not propagate in the next frame
        m_active_node_table[target_buffer][i] = -1;
      }
    }

    // Move the best node to the beginning of the active node table to
    // enhance pruning
    if (best_log_prob_node_index != -1)
    {
      int temp_active_node = m_active_node_table[target_buffer][0];
      m_active_node_table[target_buffer][0] =
        m_active_node_table[target_buffer][best_log_prob_node_index];
      m_active_node_table[target_buffer][best_log_prob_node_index] =
        temp_active_node;
    }

  }

  // Clear the active nodes
  for (int i = 0; i < (int)m_active_node_table[target_buffer].size(); i++)
  {
    if (m_active_node_table[target_buffer][i] != -1)
      m_nodes[m_active_node_table[target_buffer][i]].log_prob[target_buffer] =
        loglikelihoods.zero();
  }
  m_active_node_table[target_buffer].clear();
  
  // Reset the current frame for the forward phase
  m_current_frame = -1;
  m_eof_flag = false;
  return true;
}

{'fraction_non_alphanumeric': 0.12158554117888684, 'fraction_numerical': 0.007359485178339152, 'mean_word_length': 3.0458385265198724, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 50, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1257888', 'n_tokens_mistral': 10512, 'n_tokens_neox': 10084, 'n_words': 2087}