00001 #pragma once
00002
00003 #include <algorithm>
00004 #include <vector>
00005
00006 #include "moses/Syntax/PHyperedge.h"
00007
00008 #include "TailLattice.h"
00009 #include "moses/TargetPhraseCollection.h"
00010 namespace Moses
00011 {
00012 namespace Syntax
00013 {
00014 namespace S2T
00015 {
00016
00017 template<typename Callback>
00018 class TailLatticeSearcher
00019 {
00020 public:
00021 TailLatticeSearcher(const TailLattice &lattice,
00022 const PatternApplicationKey &key,
00023 const std::vector<SymbolRange> &ranges)
00024 : m_lattice(lattice)
00025 , m_key(key)
00026 , m_ranges(ranges) {}
00027
00028 void Search(const std::vector<int> &labels,
00029 const TargetPhraseCollection::shared_ptr tpc,
00030 Callback &callback) {
00031 m_labels = &labels;
00032 m_matchCB = &callback;
00033 m_hyperedge.head = 0;
00034 m_hyperedge.tail.clear();
00035 m_hyperedge.label.translations = tpc;
00036 SearchInner(0, 0, 0);
00037 }
00038
00039 private:
00040 void SearchInner(int offset, std::size_t i, std::size_t nonTermIndex) {
00041 assert(m_hyperedge.tail.size() == i);
00042
00043 const PatternApplicationTrie *patNode = m_key[i];
00044 const SymbolRange &range = m_ranges[i];
00045
00046 if (patNode->IsTerminalNode()) {
00047 const int width = range.minEnd - range.minStart + 1;
00048 const PVertex *v = m_lattice[offset][0][width][0];
00049
00050 m_hyperedge.tail.push_back(const_cast<PVertex*>(v));
00051 if (i == m_key.size()-1) {
00052 (*m_matchCB)(m_hyperedge);
00053 } else {
00054 SearchInner(offset+width, i+1, nonTermIndex);
00055 }
00056 m_hyperedge.tail.pop_back();
00057 return;
00058 }
00059
00060 const int absStart = m_ranges[0].minStart + offset;
00061 const int minWidth = std::max(1, range.minEnd - absStart + 1);
00062 const std::size_t maxWidth = range.maxEnd - absStart + 1;
00063
00064 const std::vector<std::vector<const PVertex *> > &innerVec =
00065 m_lattice[offset][nonTermIndex+1];
00066
00067 std::size_t labelIndex = (*m_labels)[nonTermIndex];
00068
00069
00070 for (std::size_t width = minWidth; width <= maxWidth; ++width) {
00071 const PVertex *v = innerVec[width][labelIndex];
00072 if (!v) {
00073 continue;
00074 }
00075
00076 m_hyperedge.tail.push_back(const_cast<PVertex*>(v));
00077 if (i == m_key.size()-1) {
00078 (*m_matchCB)(m_hyperedge);
00079 } else {
00080 SearchInner(offset+width, i+1, nonTermIndex+1);
00081 }
00082 m_hyperedge.tail.pop_back();
00083 }
00084 }
00085
00086 const TailLattice &m_lattice;
00087 const PatternApplicationKey &m_key;
00088 const std::vector<SymbolRange> &m_ranges;
00089 const std::vector<int> *m_labels;
00090 Callback *m_matchCB;
00091 PHyperedge m_hyperedge;
00092 };
00093
00094 }
00095 }
00096 }