| 400 | |
| 401 | template <typename T, typename CTCBeamState, typename CTCBeamComparer> |
| 402 | Status CTCBeamSearchDecoder<T, CTCBeamState, CTCBeamComparer>::TopPaths( |
| 403 | int n, std::vector<std::vector<int>>* paths, std::vector<T>* log_probs, |
| 404 | bool merge_repeated) const { |
| 405 | CHECK_NOTNULL(paths)->clear(); |
| 406 | CHECK_NOTNULL(log_probs)->clear(); |
| 407 | if (n > beam_width_) { |
| 408 | return errors::InvalidArgument("requested more paths than the beam width."); |
| 409 | } |
| 410 | if (n > leaves_.size()) { |
| 411 | return errors::InvalidArgument( |
| 412 | "Less leaves in the beam search than requested."); |
| 413 | } |
| 414 | |
| 415 | gtl::TopN<BeamEntry*, CTCBeamComparer> top_branches(n); |
| 416 | |
| 417 | // O(beam_width_ * log(n)), space complexity is O(n) |
| 418 | for (auto it = leaves_.unsorted_begin(); it != leaves_.unsorted_end(); ++it) { |
| 419 | top_branches.push(*it); |
| 420 | } |
| 421 | // O(n * log(n)) |
| 422 | std::unique_ptr<std::vector<BeamEntry*>> branches(top_branches.Extract()); |
| 423 | |
| 424 | for (int i = 0; i < n; ++i) { |
| 425 | BeamEntry* e((*branches)[i]); |
| 426 | paths->push_back(e->LabelSeq(merge_repeated)); |
| 427 | log_probs->push_back(e->newp.total); |
| 428 | } |
| 429 | return Status::OK(); |
| 430 | } |
| 431 | |
| 432 | } // namespace ctc |
| 433 | } // namespace tensorflow |
no test coverage detected