001package org.maltparser.parser.algorithm.twoplanar; 002 003import java.util.IdentityHashMap; 004import java.util.Iterator; 005import java.util.LinkedList; 006import java.util.List; 007import java.util.Map; 008import java.util.SortedSet; 009 010import org.maltparser.core.exception.MaltChainedException; 011import org.maltparser.core.syntaxgraph.DependencyStructure; 012import org.maltparser.core.syntaxgraph.edge.Edge; 013import org.maltparser.core.syntaxgraph.node.DependencyNode; 014import org.maltparser.parser.DependencyParserConfig; 015import org.maltparser.parser.Oracle; 016import org.maltparser.parser.ParserConfiguration; 017import org.maltparser.parser.history.GuideUserHistory; 018import org.maltparser.parser.history.action.GuideUserAction; 019/** 020 * @author Carlos Gomez Rodriguez 021 * 022 */ 023public class TwoPlanarArcEagerOracle extends Oracle { 024 025 public TwoPlanarArcEagerOracle(DependencyParserConfig manager, GuideUserHistory history) throws MaltChainedException { 026 super(manager, history); 027 setGuideName("Two-Planar"); 028 } 029 030 /** 031 * Give this map an edge in the gold standard data, and it will tell you whether, given the links already created by the oracle, it is possible 032 * to create the corresponding edge in one of the planes, in any plane, or in none at all (the latter will happen in non-2-planar structures). 033 */ 034 private static final int ANY_PLANE = 0; 035 private static final int FIRST_PLANE = 1; 036 private static final int SECOND_PLANE = 2; 037 private static final int NO_PLANE = 3; 038 private Map<Edge,Integer> linksToPlanes = new IdentityHashMap<Edge,Integer>(); 039 040 public GuideUserAction predict(DependencyStructure gold, ParserConfiguration config) throws MaltChainedException { 041 TwoPlanarConfig planarConfig = (TwoPlanarConfig)config; 042 DependencyStructure dg = planarConfig.getDependencyGraph(); 043 DependencyNode activeStackPeek = planarConfig.getActiveStack().peek(); 044 DependencyNode inactiveStackPeek = planarConfig.getInactiveStack().peek(); 045 int activeStackPeekIndex = activeStackPeek.getIndex(); 046 int inactiveStackPeekIndex = inactiveStackPeek.getIndex(); 047 int inputPeekIndex = planarConfig.getInput().peek().getIndex(); 048 049 //System.out.println("Initting crossings"); 050 051 if ( crossingsGraph == null ) initCrossingsGraph(gold); 052 053 //System.out.println("Crossings initted"); 054 055 if (!activeStackPeek.isRoot() && gold.getTokenNode(activeStackPeekIndex).getHead().getIndex() == inputPeekIndex 056 && !checkIfArcExists ( dg , inputPeekIndex , activeStackPeekIndex ) ) { 057 if ( planarConfig.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ) 058 { 059 propagatePlaneConstraint(gold.getTokenNode(activeStackPeekIndex).getHeadEdge(), FIRST_PLANE ); 060 } 061 else 062 { 063 propagatePlaneConstraint(gold.getTokenNode(activeStackPeekIndex).getHeadEdge(), SECOND_PLANE ); 064 } 065 //System.out.println("From " + inputPeekIndex + " to " + activeStackPeekIndex); 066 return updateActionContainers(TwoPlanar.LEFTARC, gold.getTokenNode(activeStackPeekIndex).getHeadEdge().getLabelSet()); 067 } 068 069 else if (gold.getTokenNode(inputPeekIndex).getHead().getIndex() == activeStackPeekIndex 070 && !checkIfArcExists ( dg , activeStackPeekIndex , inputPeekIndex ) ) { 071 if ( planarConfig.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ) 072 { 073 propagatePlaneConstraint(gold.getTokenNode(inputPeekIndex).getHeadEdge(), FIRST_PLANE ); 074 } 075 else 076 { 077 propagatePlaneConstraint(gold.getTokenNode(inputPeekIndex).getHeadEdge(), SECOND_PLANE ); 078 } 079 //System.out.println("From " + activeStackPeekIndex + " to " + inputPeekIndex); 080 return updateActionContainers(TwoPlanar.RIGHTARC, gold.getTokenNode(inputPeekIndex).getHeadEdge().getLabelSet()); 081 } 082 083 else if (!inactiveStackPeek.isRoot() && gold.getTokenNode(inactiveStackPeekIndex).getHead().getIndex() == inputPeekIndex 084 && !checkIfArcExists ( dg , inputPeekIndex , inactiveStackPeekIndex ) ) { 085 //need to create link, but on the other plane!! 086 //TODO is this if branch really necessary? i.e. will this happen? (later branches already switch) 087 //System.out.println("Switch one"); 088 return updateActionContainers(TwoPlanar.SWITCH, null); 089 } 090 091 else if (gold.getTokenNode(inputPeekIndex).getHead().getIndex() == inactiveStackPeekIndex 092 && !checkIfArcExists ( dg , inactiveStackPeekIndex , inputPeekIndex ) ) { 093 //need to create link, but on the other plane!! 094 //TODO is this if branch really necessary? i.e. will this happen? (later branches already switch) 095 //System.out.println("Switch two"); 096 return updateActionContainers(TwoPlanar.SWITCH, null); 097 } 098 099 else if ( getFirstPendingLinkOnActivePlane(planarConfig,gold) != null ) 100 { 101 //System.out.println("Reduce one"); 102 return updateActionContainers(TwoPlanar.REDUCE, null); 103 } 104 105 else if ( getFirstPendingLinkOnInactivePlane(planarConfig,gold) != null ) 106 { 107 //System.out.println("Switch for reducing"); 108 return updateActionContainers(TwoPlanar.SWITCH, null); 109 } 110 111 //TODO: double reduce somehow? (check if reduced node is not covered by links of the other plane, or something like that). 112 113 else 114 { 115 //System.out.println("Shift"); 116 return updateActionContainers(TwoPlanar.SHIFT, null); 117 } 118 119 } 120 121 private boolean checkIfArcExists ( DependencyStructure dg , int index1 , int index2 ) throws MaltChainedException 122 { 123 return dg.getTokenNode(index2).hasHead() && dg.getTokenNode(index2).getHead().getIndex() == index1; 124 } 125 126 public void finalizeSentence(DependencyStructure dependencyGraph) throws MaltChainedException { 127 crossingsGraph = null; 128 linksToPlanes.clear(); 129 } 130 131 public void terminate() throws MaltChainedException {} 132 133 134 135 private static boolean cross ( Edge e1 , Edge e2 ) 136 { 137 int xSource = e1.getSource().getIndex(); 138 int xTarget = e1.getTarget().getIndex(); 139 int ySource = e2.getSource().getIndex(); 140 int yTarget = e2.getTarget().getIndex(); 141 int xMin = Math.min(xSource,xTarget); 142 int xMax = Math.max(xSource,xTarget); 143 int yMin = Math.min(ySource,yTarget); 144 int yMax = Math.max(ySource,yTarget); 145 //System.out.println(xMin+":"+xMax+":"+yMin+":"+yMax); 146 return ( xMin < yMin && yMin < xMax && xMax < yMax ) || ( yMin < xMin && xMin < yMax && yMax < xMax ); 147 } 148 149 private Map<Edge,List<Edge>> crossingsGraph = null; 150 151 private void initCrossingsGraph ( DependencyStructure dg ) 152 { 153 crossingsGraph = new IdentityHashMap<Edge,List<Edge>>(); 154 SortedSet<Edge> edges = dg.getEdges(); 155 //System.out.println(edges.size()); 156 //System.out.println(dg.nEdges()); 157 for (Iterator<Edge> iterator1 = edges.iterator(); iterator1.hasNext();) { 158 Edge edge1 = iterator1.next(); 159 for (Iterator<Edge> iterator2 = edges.iterator(); iterator2.hasNext();) { 160 Edge edge2 = iterator2.next(); 161 if ( edge1.getSource().getIndex() < edge2.getSource().getIndex() && cross(edge1,edge2) ) 162 { 163 //System.out.println("Crossing!"); 164 List<Edge> crossingEdge1 = crossingsGraph.get(edge1); 165 if ( crossingEdge1 == null ) { crossingEdge1 = new LinkedList<Edge>(); crossingsGraph.put(edge1, crossingEdge1); } 166 crossingEdge1.add(edge2); 167 List<Edge> crossingEdge2 = crossingsGraph.get(edge2); 168 if ( crossingEdge2 == null ) { crossingEdge2 = new LinkedList<Edge>(); crossingsGraph.put(edge2 , crossingEdge2); } 169 crossingEdge2.add(edge1); 170 } 171 } 172 } 173 } 174 175 private List<Edge> getCrossingEdges ( Edge e ) 176 { 177 return crossingsGraph.get(e); 178 } 179 180 private void setPlaneConstraint ( Edge e , int requiredPlane ) 181 { 182 linksToPlanes.put(e, requiredPlane); 183 } 184 185 private int getPlaneConstraint ( Edge e ) 186 { 187 Integer constr = linksToPlanes.get(e); 188 if ( constr == null ) 189 { 190 setPlaneConstraint(e,ANY_PLANE); 191 return ANY_PLANE; 192 } 193 else return constr; 194 } 195 196 private void propagatePlaneConstraint ( Edge e , int requiredPlane ) 197 { 198 setPlaneConstraint(e,requiredPlane); 199 if ( requiredPlane == FIRST_PLANE || requiredPlane == SECOND_PLANE ) 200 { 201 List<Edge> crossingEdges = getCrossingEdges(e); 202 if ( crossingEdges != null ) 203 { 204 for (Iterator<Edge> iterator = crossingEdges.iterator(); iterator.hasNext();) 205 { 206 Edge crossingEdge = iterator.next(); 207 assert ( requiredPlane == FIRST_PLANE || requiredPlane == SECOND_PLANE ); 208 int crossingEdgeConstraint = getPlaneConstraint(crossingEdge); 209 if ( crossingEdgeConstraint == ANY_PLANE ) 210 { 211 if ( requiredPlane == FIRST_PLANE ) 212 propagatePlaneConstraint(crossingEdge,SECOND_PLANE); 213 else if ( requiredPlane == SECOND_PLANE ) 214 propagatePlaneConstraint(crossingEdge,FIRST_PLANE); 215 } 216 else if ( crossingEdgeConstraint == NO_PLANE ) ; 217 else if ( crossingEdgeConstraint == FIRST_PLANE ) 218 { 219 if ( requiredPlane == FIRST_PLANE ) 220 propagatePlaneConstraint(crossingEdge,NO_PLANE); 221 } 222 else if ( crossingEdgeConstraint == SECOND_PLANE ) 223 { 224 if ( requiredPlane == SECOND_PLANE ) 225 propagatePlaneConstraint(crossingEdge,NO_PLANE); 226 } 227 } 228 } 229 } 230 } 231 232 /** 233 * Decides in which plane link e should be created. 234 */ 235 private int getLinkDecision ( Edge e , TwoPlanarConfig config ) 236 { 237 int constraint = getPlaneConstraint ( e ); 238 if ( constraint == ANY_PLANE ) 239 { 240 //choose active plane 241 if ( config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ) 242 return FIRST_PLANE; 243 else 244 return SECOND_PLANE; 245 } 246 else return constraint; 247 } 248 249 250 /** 251 * Gets the shortest pending link between (to or from) the input node and a node to the left of the top of the active stack, 252 * such that the link can be established on the active plane. 253 */ 254 private Edge getFirstPendingLinkOnActivePlane ( TwoPlanarConfig config , DependencyStructure gold ) throws MaltChainedException 255 { 256 return getFirstPendingLinkOnPlane ( config , gold , config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ? FIRST_PLANE : SECOND_PLANE , 257 config.getActiveStack().peek().getIndex() ); 258 } 259 260 /** 261 * Gets the shortest pending link between (to or from) the input node and a node to the left of the top of the inactive stack, 262 * such that the link can be established on the inactive plane. 263 */ 264 private Edge getFirstPendingLinkOnInactivePlane ( TwoPlanarConfig config , DependencyStructure gold ) throws MaltChainedException 265 { 266 return getFirstPendingLinkOnPlane ( config , gold , config.getStackActivityState() == TwoPlanarConfig.FIRST_STACK ? SECOND_PLANE : FIRST_PLANE , 267 config.getInactiveStack().peek().getIndex() ); 268 } 269 270 private Edge getFirstPendingLinkOnAnyPlane ( TwoPlanarConfig config , DependencyStructure gold ) throws MaltChainedException 271 { 272 Edge e1 = getFirstPendingLinkOnActivePlane ( config , gold ); 273 Edge e2 = getFirstPendingLinkOnInactivePlane ( config , gold ); 274 int left1 = Math.min(e1.getSource().getIndex(), e1.getTarget().getIndex()); 275 int left2 = Math.min(e2.getSource().getIndex(), e2.getTarget().getIndex()); 276 if ( left1 > left2 ) return e1; 277 else return e2; 278 } 279 280 /** 281 * Gets the shortest pending link between (to or from) the input node and a node to the left of rightmostLimit, such that the link 282 * can be established on the given plane. 283 */ 284 private Edge getFirstPendingLinkOnPlane ( TwoPlanarConfig config , DependencyStructure gold , int plane , int rightmostLimit ) 285 throws MaltChainedException 286 { 287 TwoPlanarConfig planarConfig = (TwoPlanarConfig)config; 288 //DependencyStructure dg = planarConfig.getDependencyGraph(); -> no need, if rightmostLimit is well chosen, due to algorithm invariants 289 int inputPeekIndex = planarConfig.getInput().peek().getIndex(); 290 291 Edge current = null; 292 int maxIndex; 293 if ( planarConfig.getRootHandling() == TwoPlanarConfig.NORMAL ) 294 maxIndex = -1; //count links from dummy root 295 else 296 maxIndex = 0; //do not count links from dummy root 297 298 if ( gold.getTokenNode(inputPeekIndex).hasLeftDependent() && 299 gold.getTokenNode(inputPeekIndex).getLeftmostDependent().getIndex() < rightmostLimit) 300 { 301 SortedSet<DependencyNode> dependents = gold.getTokenNode(inputPeekIndex).getLeftDependents(); 302 for (Iterator<DependencyNode> iterator = dependents.iterator(); iterator.hasNext();) { 303 DependencyNode dependent = (DependencyNode) iterator.next(); 304 if ( dependent.getIndex() > maxIndex && dependent.getIndex() < rightmostLimit 305 && getLinkDecision(dependent.getHeadEdge(),config) == plane ) 306 { 307 maxIndex = dependent.getIndex(); 308 current = dependent.getHeadEdge(); 309 } 310 } 311 } 312 313 //at this point, current is the first left-pointing link, but we have to check right-pointing link as well 314 315 //System.out.println("in" + inputPeekIndex + " rl" + rightmostLimit); 316 if ( gold.getTokenNode(inputPeekIndex).getHead().getIndex() < rightmostLimit ) 317 { 318 //System.out.println(":"); 319 if ( gold.getTokenNode(inputPeekIndex).getHead().getIndex() > maxIndex && 320 getLinkDecision(gold.getTokenNode(inputPeekIndex).getHeadEdge(),config) == plane ) 321 { 322 //System.out.println("::"); 323 current = gold.getTokenNode(inputPeekIndex).getHeadEdge(); 324 } 325 } 326 327 return current; 328 329 330 } 331 332 333}