00001 #ifndef SEARCH_VERTEX__ 00002 #define SEARCH_VERTEX__ 00003 00004 #include "lm/left.hh" 00005 #include "search/types.hh" 00006 00007 #include <boost/unordered_set.hpp> 00008 00009 #include <queue> 00010 #include <vector> 00011 #include <cmath> 00012 #include <stdint.h> 00013 00014 namespace search { 00015 00016 class ContextBase; 00017 00018 struct HypoState { 00019 History history; 00020 lm::ngram::ChartState state; 00021 Score score; 00022 }; 00023 00024 class VertexNode { 00025 public: 00026 VertexNode() {} 00027 00028 void InitRoot() { hypos_.clear(); } 00029 00030 /* The steps of building a VertexNode: 00031 * 1. Default construct. 00032 * 2. AppendHypothesis at least once, possibly multiple times. 00033 * 3. FinishAppending with the number of words on left and right guaranteed 00034 * to be common. 00035 * 4. If !Complete(), call BuildExtend to construct the extensions 00036 */ 00037 // Must default construct, call AppendHypothesis 1 or more times then do FinishedAppending. 00038 void AppendHypothesis(const NBestComplete &best) { 00039 assert(hypos_.empty() || !(hypos_.front().state == *best.state)); 00040 HypoState hypo; 00041 hypo.history = best.history; 00042 hypo.state = *best.state; 00043 hypo.score = best.score; 00044 hypos_.push_back(hypo); 00045 } 00046 void AppendHypothesis(const HypoState &hypo) { 00047 hypos_.push_back(hypo); 00048 } 00049 00050 // Sort hypotheses for the root. 00051 void FinishRoot(); 00052 00053 void FinishedAppending(const unsigned char common_left, const unsigned char common_right); 00054 00055 void BuildExtend(); 00056 00057 // Should only happen to a root node when the entire vertex is empty. 00058 bool Empty() const { 00059 return hypos_.empty() && extend_.empty(); 00060 } 00061 00062 bool Complete() const { 00063 // HACK: prevent root from being complete. TODO: allow root to be complete. 00064 return hypos_.size() == 1 && extend_.empty(); 00065 } 00066 00067 const lm::ngram::ChartState &State() const { return state_; } 00068 bool RightFull() const { return right_full_; } 00069 00070 // Priority relative to other non-terminals. 0 is highest. 00071 unsigned char Niceness() const { return niceness_; } 00072 00073 Score Bound() const { 00074 return bound_; 00075 } 00076 00077 // Will be invalid unless this is a leaf. 00078 const History End() const { 00079 assert(hypos_.size() == 1); 00080 return hypos_.front().history; 00081 } 00082 00083 VertexNode &operator[](size_t index) { 00084 assert(!extend_.empty()); 00085 return extend_[index]; 00086 } 00087 00088 size_t Size() const { 00089 return extend_.size(); 00090 } 00091 00092 private: 00093 // Hypotheses to be split. 00094 std::vector<HypoState> hypos_; 00095 00096 std::vector<VertexNode> extend_; 00097 00098 lm::ngram::ChartState state_; 00099 bool right_full_; 00100 00101 unsigned char niceness_; 00102 00103 unsigned char policy_; 00104 00105 Score bound_; 00106 }; 00107 00108 class PartialVertex { 00109 public: 00110 PartialVertex() {} 00111 00112 explicit PartialVertex(VertexNode &back) : back_(&back), index_(0) {} 00113 00114 bool Empty() const { return back_->Empty(); } 00115 00116 bool Complete() const { return back_->Complete(); } 00117 00118 const lm::ngram::ChartState &State() const { return back_->State(); } 00119 bool RightFull() const { return back_->RightFull(); } 00120 00121 Score Bound() const { return index_ ? (*back_)[index_].Bound() : back_->Bound(); } 00122 00123 unsigned char Niceness() const { return back_->Niceness(); } 00124 00125 // Split into continuation and alternative, rendering this the continuation. 00126 bool Split(PartialVertex &alternative) { 00127 assert(!Complete()); 00128 back_->BuildExtend(); 00129 bool ret; 00130 if (index_ + 1 < back_->Size()) { 00131 alternative.index_ = index_ + 1; 00132 alternative.back_ = back_; 00133 ret = true; 00134 } else { 00135 ret = false; 00136 } 00137 back_ = &((*back_)[index_]); 00138 index_ = 0; 00139 return ret; 00140 } 00141 00142 const History End() const { 00143 return back_->End(); 00144 } 00145 00146 private: 00147 VertexNode *back_; 00148 unsigned int index_; 00149 }; 00150 00151 template <class Output> class VertexGenerator; 00152 00153 class Vertex { 00154 public: 00155 Vertex() {} 00156 00157 //PartialVertex RootFirst() const { return PartialVertex(right_); } 00158 PartialVertex RootAlternate() { return PartialVertex(root_); } 00159 //PartialVertex RootLast() const { return PartialVertex(left_); } 00160 00161 bool Empty() const { 00162 return root_.Empty(); 00163 } 00164 00165 Score Bound() const { 00166 return root_.Bound(); 00167 } 00168 00169 const History BestChild() { 00170 // left_ and right_ are not set at the root. 00171 PartialVertex top(RootAlternate()); 00172 if (top.Empty()) { 00173 return History(); 00174 } else { 00175 PartialVertex continuation; 00176 while (!top.Complete()) { 00177 top.Split(continuation); 00178 } 00179 return top.End(); 00180 } 00181 } 00182 00183 private: 00184 template <class Output> friend class VertexGenerator; 00185 template <class Output> friend class RootVertexGenerator; 00186 VertexNode root_; 00187 00188 // These will not be set for the root vertex. 00189 // Branches only on left state. 00190 //VertexNode left_; 00191 // Branches only on right state. 00192 //VertexNode right_; 00193 }; 00194 00195 } // namespace search 00196 #endif // SEARCH_VERTEX__