tesseract::SearchColumn Class Reference

#include <search_column.h>

Public Member Functions
	SearchColumn (int col_idx, int max_node_cnt)
	~SearchColumn ()
int	ColIdx () const
int	NodeCount () const
SearchNode **	Nodes () const
void	Prune ()
SearchNode *	AddNode (LangModEdge *edge, int score, SearchNode *parent, CubeRecoContext *cntxt)
SearchNode *	BestNode ()
void	Sort ()
void	FreeHashTable ()

Detailed Description

Definition at line 37 of file search_column.h.

Constructor & Destructor Documentation

tesseract::SearchColumn::SearchColumn	(	int	col_idx,
		int	max_node_cnt
	)

Definition at line 25 of file search_column.cpp.

                                                    {
  col_idx_ = col_idx;
  node_cnt_ = 0;
  node_array_ = NULL;
  max_node_cnt_ = max_node;
  node_hash_table_ = NULL;
  init_ = false;
  min_cost_ = INT_MAX;
  max_cost_ = 0;
}

tesseract::SearchColumn::~SearchColumn

(

)

Definition at line 52 of file search_column.cpp.

                            {
  Cleanup();
}

Member Function Documentation

SearchNode * tesseract::SearchColumn::AddNode	(	LangModEdge *	edge,
		int	score,
		SearchNode *	parent,
		CubeRecoContext *	cntxt
	)

Definition at line 133 of file search_column.cpp.

                                                          {
  // init if necessary
  if (init_ == false && Init() == false) {
    return NULL;
  }

  // find out if we have an node with the same edge
  // look in the hash table
  SearchNode *new_node = node_hash_table_->Lookup(edge, parent_node);
  // node does not exist
  if (new_node == NULL) {
    new_node = new SearchNode(cntxt, parent_node, reco_cost, edge, col_idx_);
    if (new_node == NULL) {
      return NULL;
    }

    // if the max node count has already been reached, check if the cost of
    // the new node exceeds the max cost. This indicates that it will be pruned
    // and so there is no point adding it
    if (node_cnt_ >= max_node_cnt_ && new_node->BestCost() > max_cost_) {
      delete new_node;
      return NULL;
    }

    // expand the node buffer if necc
    if ((node_cnt_ % kNodeAllocChunk) == 0) {
      // alloc a new buff
      SearchNode **new_node_buff =
          new SearchNode *[node_cnt_ + kNodeAllocChunk];
      if (new_node_buff == NULL) {
        delete new_node;
        return NULL;
      }

      // free existing after copying contents
      if (node_array_ != NULL) {
        memcpy(new_node_buff, node_array_, node_cnt_ * sizeof(*new_node_buff));
        delete []node_array_;
      }

      node_array_ = new_node_buff;
    }

    // add the node to the hash table only if it is non-OOD edge
    // because the langmod state is not unique
    if (edge->IsOOD() == false) {
      if (!node_hash_table_->Insert(edge, new_node)) {
        tprintf("Hash table full!!!");
        delete new_node;
        return NULL;
      }
    }

    node_array_[node_cnt_++] = new_node;

  } else {
    // node exists before
    // if no update occurred, return NULL
    if (new_node->UpdateParent(parent_node, reco_cost, edge) == false) {
      new_node = NULL;
    }

    // free the edge
    if (edge != NULL) {
      delete edge;
    }
  }

  // update Min and Max Costs
  if (new_node != NULL) {
    if (min_cost_ > new_node->BestCost()) {
      min_cost_ = new_node->BestCost();
    }

    if (max_cost_ < new_node->BestCost()) {
      max_cost_ = new_node->BestCost();
    }
  }

  return new_node;
}

SearchNode * tesseract::SearchColumn::BestNode

(

)

Definition at line 217 of file search_column.cpp.

                                   {
  SearchNode *best_node = NULL;

  for (int node_idx = 0; node_idx < node_cnt_; node_idx++) {
    if (best_node == NULL ||
        best_node->BestCost() > node_array_[node_idx]->BestCost()) {
      best_node = node_array_[node_idx];
    }
  }

  return best_node;
}

int tesseract::SearchColumn::ColIdx ( ) const

inline

Definition at line 42 of file search_column.h.

{ return col_idx_; }

void tesseract::SearchColumn::FreeHashTable ( )

inline

Definition at line 57 of file search_column.h.

                       {
    if (node_hash_table_ != NULL) {
      delete node_hash_table_;
      node_hash_table_ = NULL;
    }
  }

int tesseract::SearchColumn::NodeCount ( ) const

inline

Definition at line 43 of file search_column.h.

{ return node_cnt_; }

SearchNode** tesseract::SearchColumn::Nodes ( ) const

inline

Definition at line 44 of file search_column.h.

{ return node_array_; }

void tesseract::SearchColumn::Prune

(

)

Definition at line 77 of file search_column.cpp.

                         {
  // no need to prune
  if (node_cnt_ <= max_node_cnt_) {
    return;
  }

  // compute the cost histogram
  memset(score_bins_, 0, sizeof(score_bins_));
  int cost_range = max_cost_ - min_cost_ + 1;
  for (int node_idx = 0; node_idx < node_cnt_; node_idx++) {
    int cost_bin = static_cast<int>(
        ((node_array_[node_idx]->BestCost() - min_cost_) *
         kScoreBins) / static_cast<double>(cost_range));
    if (cost_bin >= kScoreBins) {
      cost_bin = kScoreBins - 1;
    }
    score_bins_[cost_bin]++;
  }

  // determine the pruning cost by scanning the cost histogram from
  // least to greatest cost bins and finding the cost at which the
  // max number of nodes is exceeded
  int pruning_cost = 0;
  int new_node_cnt = 0;
  for (int cost_bin = 0; cost_bin < kScoreBins; cost_bin++) {
    if (new_node_cnt > 0 &&
        (new_node_cnt + score_bins_[cost_bin]) > max_node_cnt_) {
      pruning_cost = min_cost_ + ((cost_bin * cost_range) / kScoreBins);
      break;
    }
    new_node_cnt += score_bins_[cost_bin];
  }

  // prune out all the nodes above this cost
  for (int node_idx = new_node_cnt = 0; node_idx < node_cnt_; node_idx++) {
    // prune this node out
    if (node_array_[node_idx]->BestCost() > pruning_cost ||
        new_node_cnt > max_node_cnt_) {
      delete node_array_[node_idx];
    } else {
      // keep it
      node_array_[new_node_cnt++] = node_array_[node_idx];
    }
  }
  node_cnt_ = new_node_cnt;
}

void tesseract::SearchColumn::Sort

(

)

Definition at line 125 of file search_column.cpp.

                        {
  if (node_cnt_ > 0 && node_array_ != NULL) {
    qsort(node_array_, node_cnt_, sizeof(*node_array_),
          SearchNode::SearchNodeComparer);
  }
}

---

The documentation for this class was generated from the following files:

• cube/search_column.h
• cube/search_column.cpp