00001 #include "PatternApplicationTrie.h"
00002
00003 #include "moses/Syntax/PVertex.h"
00004
00005 namespace Moses
00006 {
00007 namespace Syntax
00008 {
00009 namespace S2T
00010 {
00011
00012 int PatternApplicationTrie::Depth() const
00013 {
00014 if (m_parent) {
00015 return m_parent->Depth() + 1;
00016 }
00017 return 0;
00018 }
00019
00020 const PatternApplicationTrie *
00021 PatternApplicationTrie::GetHighestTerminalNode() const
00022 {
00023
00024 if (m_highestTerminalNode) {
00025 return m_highestTerminalNode;
00026 }
00027
00028 if (!m_parent) {
00029 return 0;
00030 }
00031
00032 if (!m_parent->m_parent) {
00033 if (IsTerminalNode()) {
00034 m_highestTerminalNode = this;
00035 return this;
00036 } else {
00037 return 0;
00038 }
00039 }
00040
00041 if (const PatternApplicationTrie *p = m_parent->GetHighestTerminalNode()) {
00042 m_highestTerminalNode = p;
00043 return p;
00044 }
00045
00046 if (IsTerminalNode()) {
00047 m_highestTerminalNode = this;
00048 }
00049 return m_highestTerminalNode;
00050 }
00051
00052 const PatternApplicationTrie *
00053 PatternApplicationTrie::GetLowestTerminalNode() const
00054 {
00055
00056 if (m_lowestTerminalNode) {
00057 return m_lowestTerminalNode;
00058 }
00059
00060 if (!m_parent) {
00061 return 0;
00062 }
00063
00064 if (IsTerminalNode()) {
00065 m_lowestTerminalNode = this;
00066 return this;
00067 }
00068
00069 if (!m_parent->m_parent) {
00070 return 0;
00071 }
00072
00073 return m_parent->GetLowestTerminalNode();
00074 }
00075
00076
00077
00078
00079
00080 void PatternApplicationTrie::DetermineStartRange(int sentenceLength,
00081 int &minStart,
00082 int &maxStart) const
00083 {
00084
00085 const PatternApplicationTrie *n = GetHighestTerminalNode();
00086 if (!n) {
00087
00088 minStart = 0;
00089 maxStart = sentenceLength-Depth();
00090 return;
00091 }
00092 assert(n->m_parent);
00093 if (!n->m_parent->m_parent) {
00094
00095
00096 minStart = n->m_start;
00097 maxStart = n->m_start;
00098 } else {
00099
00100
00101
00102 minStart = 0;
00103 maxStart = n->m_start - (n->Depth()-1);
00104 }
00105 }
00106
00107
00108
00109
00110
00111 void PatternApplicationTrie::DetermineEndRange(int sentenceLength,
00112 int &minEnd,
00113 int &maxEnd) const
00114 {
00115
00116 const PatternApplicationTrie *n = GetLowestTerminalNode();
00117 if (!n) {
00118
00119 minEnd = Depth()-1;
00120 maxEnd = sentenceLength-1;
00121 return;
00122 }
00123 if (n == this) {
00124
00125 minEnd = m_end;
00126 maxEnd = m_end;
00127 } else {
00128
00129
00130
00131 minEnd = n->m_end + (Depth()-n->Depth());
00132 maxEnd = sentenceLength-1;
00133 }
00134 }
00135
00136 void PatternApplicationTrie::Extend(const RuleTrieScope3::Node &node,
00137 int minPos, const SentenceMap &sentMap,
00138 bool followsGap)
00139 {
00140 const RuleTrieScope3::Node::TerminalMap &termMap = node.GetTerminalMap();
00141 for (RuleTrieScope3::Node::TerminalMap::const_iterator p = termMap.begin();
00142 p != termMap.end(); ++p) {
00143 const Word &word = p->first;
00144 const RuleTrieScope3::Node &child = p->second;
00145 SentenceMap::const_iterator q = sentMap.find(word);
00146 if (q == sentMap.end()) {
00147 continue;
00148 }
00149 for (std::vector<const PVertex *>::const_iterator r = q->second.begin();
00150 r != q->second.end(); ++r) {
00151 const PVertex *v = *r;
00152 std::size_t start = v->span.GetStartPos();
00153 std::size_t end = v->span.GetEndPos();
00154 if (start == (std::size_t)minPos ||
00155 (followsGap && start > (std::size_t)minPos) ||
00156 minPos == -1) {
00157 PatternApplicationTrie *subTrie =
00158 new PatternApplicationTrie(start, end, child, v, this);
00159 subTrie->Extend(child, end+1, sentMap, false);
00160 m_children.push_back(subTrie);
00161 }
00162 }
00163 }
00164
00165 const RuleTrieScope3::Node *child = node.GetNonTerminalChild();
00166 if (!child) {
00167 return;
00168 }
00169 int start = followsGap ? -1 : minPos;
00170 PatternApplicationTrie *subTrie =
00171 new PatternApplicationTrie(start, -1, *child, 0, this);
00172 int newMinPos = (minPos == -1 ? 1 : minPos+1);
00173 subTrie->Extend(*child, newMinPos, sentMap, true);
00174 m_children.push_back(subTrie);
00175 }
00176
00177 void PatternApplicationTrie::ReadOffPatternApplicationKey(
00178 PatternApplicationKey &key) const
00179 {
00180 const int depth = Depth();
00181 key.resize(depth);
00182 const PatternApplicationTrie *p = this;
00183 std::size_t i = depth-1;
00184 while (p->m_parent != 0) {
00185 key[i--] = p;
00186 p = p->m_parent;
00187 }
00188 }
00189
00190 }
00191 }
00192 }