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