001 package org.maltparser.parser.algorithm.stack;
002
003 import java.util.ArrayList;
004 import java.util.Stack;
005
006 import org.maltparser.core.exception.MaltChainedException;
007 import org.maltparser.core.syntaxgraph.DependencyStructure;
008 import org.maltparser.core.syntaxgraph.node.DependencyNode;
009 import org.maltparser.parser.DependencyParserConfig;
010 import org.maltparser.parser.Oracle;
011 import org.maltparser.parser.ParserConfiguration;
012 import org.maltparser.parser.history.GuideUserHistory;
013 import org.maltparser.parser.history.action.GuideUserAction;
014 /**
015 * @author Johan Hall
016 *
017 */
018 public class SwapLazyOracle extends Oracle {
019 private ArrayList<Integer> swapArray;
020 private boolean swapArrayActive = false;
021
022 public SwapLazyOracle(DependencyParserConfig manager, GuideUserHistory history) throws MaltChainedException {
023 super(manager, history);
024 setGuideName("swaplazy");
025 swapArray = new ArrayList<Integer>();
026 }
027
028 public GuideUserAction predict(DependencyStructure gold, ParserConfiguration configuration) throws MaltChainedException {
029 final StackConfig config = (StackConfig)configuration;
030 final Stack<DependencyNode> stack = config.getStack();
031
032 if (!swapArrayActive) {
033 createSwapArray(gold);
034 swapArrayActive = true;
035 }
036 if (stack.size() < 2) {
037 return updateActionContainers(NonProjective.SHIFT, null);
038 } else {
039 final DependencyNode left = stack.get(stack.size()-2);
040 final DependencyNode right = stack.get(stack.size()-1);
041 final int leftIndex = left.getIndex();
042 final int rightIndex = right.getIndex();
043 if (swapArray.get(leftIndex) > swapArray.get(rightIndex) && necessarySwap(gold, config.getDependencyGraph(), right, config.getInput())) {
044 return updateActionContainers(NonProjective.SWAP, null);
045 } else if (!left.isRoot() && gold.getTokenNode(leftIndex).getHead().getIndex() == rightIndex
046 && nodeComplete(gold, config.getDependencyGraph(), leftIndex)) {
047 return updateActionContainers(NonProjective.LEFTARC, gold.getTokenNode(leftIndex).getHeadEdge().getLabelSet());
048 } else if (gold.getTokenNode(rightIndex).getHead().getIndex() == leftIndex
049 && nodeComplete(gold, config.getDependencyGraph(), rightIndex)) {
050 return updateActionContainers(NonProjective.RIGHTARC, gold.getTokenNode(rightIndex).getHeadEdge().getLabelSet());
051 } else {
052 return updateActionContainers(NonProjective.SHIFT, null);
053 }
054 }
055 }
056
057 private boolean nodeComplete(DependencyStructure gold, DependencyStructure parseDependencyGraph, int nodeIndex) {
058 final DependencyNode goldNode = gold.getTokenNode(nodeIndex);
059 final DependencyNode parseNode = parseDependencyGraph.getTokenNode(nodeIndex);
060 if (goldNode.hasLeftDependent()) {
061 if (!parseNode.hasLeftDependent()) {
062 return false;
063 } else if (goldNode.getLeftmostDependent().getIndex() != parseNode.getLeftmostDependent().getIndex()) {
064 return false;
065 }
066 }
067 if (goldNode.hasRightDependent()) {
068 if (!parseNode.hasRightDependent()) {
069 return false;
070 } else if (goldNode.getRightmostDependent().getIndex() != parseNode.getRightmostDependent().getIndex()) {
071 return false;
072 }
073 }
074 return true;
075 }
076
077 private boolean necessarySwap(DependencyStructure gold, DependencyStructure parse, DependencyNode node, Stack<DependencyNode> input) throws MaltChainedException {
078 DependencyNode left = node;
079 int index = input.size() - 1;
080 if (index < 0) {
081 return true;
082 }
083 DependencyNode right = input.peek();
084
085 int rc = -1;
086 while (projectiveInterval(parse, left, right)) {
087 if (rc == right.getIndex()) {
088 return false;
089 }
090 if (gold.getDependencyNode(node.getIndex()).getHead().getIndex() == right.getIndex()) {
091 return !leftComplete(gold, node);
092 }
093 if (gold.getDependencyNode(right.getIndex()).getHead().getIndex() == node.getIndex()) {
094 if (gold.getDependencyNode(right.getIndex()).hasRightDependent()) {
095 rc = gold.getDependencyNode(right.getIndex()).getRightmostProperDescendantIndex();
096 }
097 else {
098 return false;
099 }
100 }
101 if (index > 0) {
102 left = right;
103 right = input.get(--index);
104 } else {
105 break;
106 }
107 }
108
109 return true;
110 }
111
112 private boolean projectiveInterval(DependencyStructure parse, DependencyNode left, DependencyNode right) throws MaltChainedException {
113 final int l = swapArray.get(left.getIndex());
114 final int r = swapArray.get(right.getIndex());
115 DependencyNode node = null;
116 if (l > r) {
117 return false;
118 } else {
119 for (int i = l + 1; i < r; i++) {
120 for (int j = 0; j < swapArray.size(); j++) {
121 if (swapArray.get(j) == i) {
122 node = parse.getDependencyNode(j);
123 break;
124 }
125 }
126 while (node.hasHead()) {
127 node = node.getHead();
128 }
129 if (!(node == left || node == right)) {
130 return false;
131 }
132 }
133 return true;
134 }
135 }
136
137 private boolean leftComplete(DependencyStructure gold, DependencyNode right) throws MaltChainedException {
138 final DependencyNode goldNode = gold.getDependencyNode(right.getIndex());
139 if (!goldNode.hasLeftDependent()) {
140 return true;
141 } else if (!right.hasLeftDependent()) {
142 return false;
143 } else if (goldNode.getLeftmostDependent().getIndex() == right.getLeftmostDependent().getIndex()) {
144 return true;
145 }
146 return false;
147 }
148
149 public void finalizeSentence(DependencyStructure dependencyGraph) throws MaltChainedException {
150 swapArrayActive = false;
151 }
152
153 public void terminate() throws MaltChainedException {
154
155 }
156
157 private void createSwapArray(DependencyStructure goldDependencyGraph) throws MaltChainedException {
158 swapArray.clear();
159 final int n = goldDependencyGraph.getHighestDependencyNodeIndex();
160 for (int i = 0; i <= n; i++) {
161 swapArray.add(new Integer(i));
162 }
163 createSwapArray(goldDependencyGraph.getDependencyRoot(), 0);
164 }
165
166 private int createSwapArray(DependencyNode node, int order) {
167 int o = order;
168 if (node != null) {
169 for (int i=0; i < node.getLeftDependentCount(); i++) {
170 o = createSwapArray(node.getLeftDependent(i), o);
171 }
172 swapArray.set(node.getIndex(), o++);
173 for (int i=node.getRightDependentCount(); i >= 0; i--) {
174 o = createSwapArray(node.getRightDependent(i), o);
175 }
176 }
177 return o;
178 }
179 }