00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #pragma once
00021
00022 #include <cassert>
00023 #include "ChartHypothesis.h"
00024 #include "ScoreComponentCollection.h"
00025 #include "FF/InternalTree.h"
00026
00027 #include <boost/unordered_set.hpp>
00028 #include <boost/weak_ptr.hpp>
00029 #include <boost/shared_ptr.hpp>
00030
00031 #include <queue>
00032 #include <vector>
00033
00034 namespace Moses
00035 {
00036
00037
00038
00039
00040
00041
00042
00043 class ChartKBestExtractor
00044 {
00045 public:
00046 struct Vertex;
00047
00048 struct UnweightedHyperarc {
00049 boost::shared_ptr<Vertex> head;
00050 std::vector<boost::shared_ptr<Vertex> > tail;
00051 };
00052
00053 struct Derivation {
00054 Derivation(const UnweightedHyperarc &);
00055 Derivation(const Derivation &, std::size_t);
00056
00057 UnweightedHyperarc edge;
00058 std::vector<std::size_t> backPointers;
00059 std::vector<boost::shared_ptr<Derivation> > subderivations;
00060 float score;
00061 };
00062
00063 struct DerivationOrderer {
00064 bool operator()(const boost::weak_ptr<Derivation> &d1,
00065 const boost::weak_ptr<Derivation> &d2) const {
00066 boost::shared_ptr<Derivation> s1(d1);
00067 boost::shared_ptr<Derivation> s2(d2);
00068 return s1->score < s2->score;
00069 }
00070 };
00071
00072 struct Vertex {
00073 typedef std::priority_queue<boost::weak_ptr<Derivation>,
00074 std::vector<boost::weak_ptr<Derivation> >,
00075 DerivationOrderer> DerivationQueue;
00076
00077 Vertex(const ChartHypothesis &h) : hypothesis(h), visited(false) {}
00078
00079 const ChartHypothesis &hypothesis;
00080 std::vector<boost::weak_ptr<Derivation> > kBestList;
00081 DerivationQueue candidates;
00082 bool visited;
00083 };
00084
00085 typedef std::vector<boost::shared_ptr<Derivation> > KBestVec;
00086
00087
00088
00089 void Extract(const std::vector<const ChartHypothesis*> &topHypos,
00090 std::size_t k, KBestVec &);
00091
00092 static Phrase GetOutputPhrase(const Derivation &);
00093 static boost::shared_ptr<ScoreComponentCollection> GetOutputScoreBreakdown(const Derivation &);
00094 static TreePointer GetOutputTree(const Derivation &);
00095
00096 private:
00097 typedef boost::unordered_map<const ChartHypothesis *,
00098 boost::shared_ptr<Vertex> > VertexMap;
00099
00100 struct DerivationHasher {
00101 std::size_t operator()(const boost::shared_ptr<Derivation> &d) const {
00102 std::size_t seed = 0;
00103 boost::hash_combine(seed, d->edge.head);
00104 boost::hash_combine(seed, d->edge.tail);
00105 boost::hash_combine(seed, d->backPointers);
00106 return seed;
00107 }
00108 };
00109
00110 struct DerivationEqualityPred {
00111 bool operator()(const boost::shared_ptr<Derivation> &d1,
00112 const boost::shared_ptr<Derivation> &d2) const {
00113 return d1->edge.head == d2->edge.head &&
00114 d1->edge.tail == d2->edge.tail &&
00115 d1->backPointers == d2->backPointers;
00116 }
00117 };
00118
00119 typedef boost::unordered_set<boost::shared_ptr<Derivation>, DerivationHasher,
00120 DerivationEqualityPred> DerivationSet;
00121
00122 UnweightedHyperarc CreateEdge(const ChartHypothesis &);
00123 boost::shared_ptr<Vertex> FindOrCreateVertex(const ChartHypothesis &);
00124 void GetCandidates(Vertex &, std::size_t);
00125 void LazyKthBest(Vertex &, std::size_t, std::size_t);
00126 void LazyNext(Vertex &, const Derivation &, std::size_t);
00127
00128 VertexMap m_vertexMap;
00129 DerivationSet m_derivations;
00130 };
00131
00132 }