001 package org.maltparser.core.syntaxgraph; 002 003 import java.util.Iterator; 004 import java.util.NoSuchElementException; 005 import java.util.Observable; 006 import java.util.Set; 007 import java.util.SortedMap; 008 import java.util.SortedSet; 009 import java.util.TreeMap; 010 import java.util.TreeSet; 011 012 013 import org.maltparser.core.exception.MaltChainedException; 014 import org.maltparser.core.helper.SystemLogger; 015 import org.maltparser.core.pool.ObjectPoolList; 016 import org.maltparser.core.symbol.SymbolTable; 017 import org.maltparser.core.symbol.SymbolTableHandler; 018 import org.maltparser.core.syntaxgraph.ds2ps.LosslessMapping; 019 import org.maltparser.core.syntaxgraph.edge.Edge; 020 import org.maltparser.core.syntaxgraph.edge.GraphEdge; 021 import org.maltparser.core.syntaxgraph.node.ComparableNode; 022 import org.maltparser.core.syntaxgraph.node.DependencyNode; 023 import org.maltparser.core.syntaxgraph.node.Node; 024 import org.maltparser.core.syntaxgraph.node.NonTerminal; 025 import org.maltparser.core.syntaxgraph.node.NonTerminalNode; 026 import org.maltparser.core.syntaxgraph.node.PhraseStructureNode; 027 import org.maltparser.core.syntaxgraph.node.Root; 028 import org.maltparser.core.syntaxgraph.node.TokenNode; 029 /** 030 * 031 * 032 * @author Johan Hall 033 */ 034 public class MappablePhraseStructureGraph extends Sentence implements DependencyStructure, PhraseStructure { 035 private final ObjectPoolList<Edge> edgePool; 036 private final SortedSet<Edge> graphEdges; 037 private Root root; 038 private boolean singleHeadedConstraint; 039 private final SortedMap<Integer, NonTerminal> nonTerminalNodes; 040 private final ObjectPoolList<NonTerminal> nonTerminalPool; 041 private LosslessMapping mapping; 042 private RootLabels rootLabels; 043 044 public MappablePhraseStructureGraph(SymbolTableHandler symbolTables) throws MaltChainedException { 045 super(symbolTables); 046 setSingleHeadedConstraint(true); 047 root = new Root(); 048 root.setBelongsToGraph(this); 049 graphEdges = new TreeSet<Edge>(); 050 edgePool = new ObjectPoolList<Edge>() { 051 protected Edge create() { return new GraphEdge(); } 052 public void resetObject(Edge o) throws MaltChainedException { o.clear(); } 053 }; 054 055 nonTerminalNodes = new TreeMap<Integer,NonTerminal>(); 056 nonTerminalPool = new ObjectPoolList<NonTerminal>() { 057 protected NonTerminal create() throws MaltChainedException { return new NonTerminal(); } 058 public void resetObject(NonTerminal o) throws MaltChainedException { o.clear(); } 059 }; 060 clear(); 061 } 062 063 public DependencyNode addDependencyNode() throws MaltChainedException { 064 return addTokenNode(); 065 } 066 067 public DependencyNode addDependencyNode(int index) throws MaltChainedException { 068 if (index == 0) { 069 return root; 070 } 071 return addTokenNode(index); 072 } 073 074 public DependencyNode getDependencyNode(int index) throws MaltChainedException { 075 if (index == 0) { 076 return root; 077 } 078 return getTokenNode(index); 079 } 080 081 public int nDependencyNode() { 082 return nTokenNode() + 1; 083 } 084 085 public int getHighestDependencyNodeIndex() { 086 if (hasTokens()) { 087 return getHighestTokenIndex(); 088 } 089 return 0; 090 } 091 092 public Edge addDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException { 093 DependencyNode head = null; 094 DependencyNode dependent = null; 095 if (headIndex == 0) { 096 head = root; 097 } else if (headIndex > 0) { 098 head = getOrAddTerminalNode(headIndex); 099 } 100 101 if (dependentIndex > 0) { 102 dependent = getOrAddTerminalNode(dependentIndex); 103 } 104 return addDependencyEdge(head, dependent); 105 } 106 107 public Edge addDependencyEdge(DependencyNode head, DependencyNode dependent) throws MaltChainedException { 108 if (head == null || dependent == null || head.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) { 109 throw new SyntaxGraphException("Head or dependent node is missing."); 110 } else if (!dependent.isRoot()) { 111 if (singleHeadedConstraint && dependent.hasHead()) { 112 throw new SyntaxGraphException("The dependent already have a head. "); 113 } 114 DependencyNode hc = ((DependencyNode)head).findComponent(); 115 DependencyNode dc = ((DependencyNode)dependent).findComponent(); 116 if (hc != dc) { 117 link(hc, dc); 118 numberOfComponents--; 119 } 120 Edge e = edgePool.checkOut(); 121 e.setBelongsToGraph(this); 122 e.setEdge((Node)head, (Node)dependent, Edge.DEPENDENCY_EDGE); 123 graphEdges.add(e); 124 return e; 125 } else { 126 throw new SyntaxGraphException("Head node is not a root node or a terminal node."); 127 } 128 } 129 130 public Edge moveDependencyEdge(int newHeadIndex, int dependentIndex) throws MaltChainedException { 131 DependencyNode newHead = null; 132 DependencyNode dependent = null; 133 if (newHeadIndex == 0) { 134 newHead = root; 135 } else if (newHeadIndex > 0) { 136 newHead = terminalNodes.get(newHeadIndex); 137 } 138 139 if (dependentIndex > 0) { 140 dependent = terminalNodes.get(dependentIndex); 141 } 142 return moveDependencyEdge(newHead, dependent); 143 } 144 145 public Edge moveDependencyEdge(DependencyNode newHead, DependencyNode dependent) throws MaltChainedException { 146 if (dependent == null || !dependent.hasHead() || newHead.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) { 147 return null; 148 } 149 Edge headEdge = dependent.getHeadEdge(); 150 151 LabelSet labels = null; 152 if (headEdge.isLabeled()) { 153 labels = checkOutNewLabelSet(); 154 for (SymbolTable table : headEdge.getLabelTypes()) { 155 labels.put(table, headEdge.getLabelCode(table)); 156 } 157 } 158 headEdge.clear(); 159 headEdge.setBelongsToGraph(this); 160 headEdge.setEdge((Node)newHead, (Node)dependent, Edge.DEPENDENCY_EDGE); 161 if (labels != null) { 162 headEdge.addLabel(labels); 163 labels.clear(); 164 checkInLabelSet(labels); 165 } 166 return headEdge; 167 } 168 169 public void removeDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException { 170 Node head = null; 171 Node dependent = null; 172 if (headIndex == 0) { 173 head = root; 174 } else if (headIndex > 0) { 175 head = terminalNodes.get(headIndex); 176 } 177 178 if (dependentIndex > 0) { 179 dependent = terminalNodes.get(dependentIndex); 180 } 181 removeDependencyEdge(head, dependent); 182 } 183 184 protected void removeDependencyEdge(Node head, Node dependent) throws MaltChainedException { 185 if (head == null || dependent == null || head.getBelongsToGraph() != this || dependent.getBelongsToGraph() != this) { 186 throw new SyntaxGraphException("Head or dependent node is missing."); 187 } else if (!dependent.isRoot()) { 188 Iterator<Edge> ie = dependent.getIncomingEdgeIterator(); 189 while (ie.hasNext()) { 190 Edge e = ie.next(); 191 if (e.getSource() == head) { 192 ie.remove(); 193 graphEdges.remove(e); 194 edgePool.checkIn(e); 195 } 196 } 197 } else { 198 throw new SyntaxGraphException("Head node is not a root node or a terminal node."); 199 } 200 } 201 202 public Edge addSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException { 203 if (source == null || target == null || source.getBelongsToGraph() != this || target.getBelongsToGraph() != this) { 204 throw new SyntaxGraphException("Head or dependent node is missing."); 205 } else if (!target.isRoot()) { 206 Edge e = edgePool.checkOut(); 207 e.setBelongsToGraph(this); 208 e.setEdge((Node)source, (Node)target, Edge.SECONDARY_EDGE); 209 graphEdges.add(e); 210 return e; 211 } 212 return null; 213 } 214 215 public void removeSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException { 216 if (source == null || target == null || source.getBelongsToGraph() != this || target.getBelongsToGraph() != this) { 217 throw new SyntaxGraphException("Head or dependent node is missing."); 218 } else if (!target.isRoot()) { 219 Iterator<Edge> ie = ((Node)target).getIncomingEdgeIterator(); 220 while (ie.hasNext()) { 221 Edge e = ie.next(); 222 if (e.getSource() == source) { 223 ie.remove(); 224 graphEdges.remove(e); 225 edgePool.checkIn(e); 226 } 227 } 228 } 229 } 230 231 public boolean hasLabeledDependency(int index) throws MaltChainedException { 232 return (getDependencyNode(index).hasHead() && getDependencyNode(index).getHeadEdge().isLabeled()); 233 } 234 235 public boolean isConnected() { 236 return (numberOfComponents == 1); 237 } 238 239 public boolean isProjective() throws MaltChainedException { 240 for (int i : terminalNodes.keySet()) { 241 if (!terminalNodes.get(i).isProjective()) { 242 return false; 243 } 244 } 245 return true; 246 } 247 248 public boolean isTree() { 249 return isConnected() && isSingleHeaded(); 250 } 251 252 public boolean isSingleHeaded() { 253 for (int i : terminalNodes.keySet()) { 254 if (!terminalNodes.get(i).hasAtMostOneHead()) { 255 return false; 256 } 257 } 258 return true; 259 } 260 261 public boolean isSingleHeadedConstraint() { 262 return singleHeadedConstraint; 263 } 264 265 public void setSingleHeadedConstraint(boolean singleHeadedConstraint) { 266 this.singleHeadedConstraint = singleHeadedConstraint; 267 } 268 269 public int nNonProjectiveEdges() throws MaltChainedException { 270 int c = 0; 271 for (int i : terminalNodes.keySet()) { 272 if (!terminalNodes.get(i).isProjective()) { 273 c++; 274 } 275 } 276 return c; 277 } 278 279 public int nEdges() { 280 return graphEdges.size(); 281 } 282 283 public SortedSet<Integer> getDependencyIndices() { 284 SortedSet<Integer> indices = new TreeSet<Integer>(terminalNodes.keySet()); 285 indices.add(0); 286 return indices; 287 } 288 289 protected DependencyNode link(DependencyNode x, DependencyNode y) { 290 if (x.getRank() > y.getRank()) { 291 y.setComponent(x); 292 } else { 293 x.setComponent(y); 294 if (x.getRank() == y.getRank()) { 295 y.setRank(y.getRank()+1); 296 } 297 return y; 298 } 299 return x; 300 } 301 302 public void linkAllTerminalsToRoot() throws MaltChainedException { 303 clear(); 304 305 for (int i : terminalNodes.keySet()) { 306 DependencyNode node = terminalNodes.get(i); 307 addDependencyEdge(root,node); 308 } 309 } 310 311 public void linkAllTreesToRoot() throws MaltChainedException { 312 for (int i : terminalNodes.keySet()) { 313 if (!terminalNodes.get(i).hasHead()) { 314 Edge e = addDependencyEdge(root,terminalNodes.get(i)); 315 mapping.updatePhraseStructureGraph(this, e, false); 316 } 317 } 318 } 319 320 public String getDefaultRootEdgeLabelSymbol(SymbolTable table) throws MaltChainedException { 321 if (rootLabels == null) { 322 return null; 323 } 324 return rootLabels.getDefaultRootLabelSymbol(table); 325 } 326 327 public int getDefaultRootEdgeLabelCode(SymbolTable table) throws MaltChainedException { 328 if (rootLabels == null) { 329 return -1; 330 } 331 return rootLabels.getDefaultRootLabelCode(table); 332 } 333 334 public void setDefaultRootEdgeLabel(SymbolTable table, String defaultRootSymbol) throws MaltChainedException { 335 if (rootLabels == null) { 336 rootLabels = new RootLabels(); 337 } 338 rootLabels.setDefaultRootLabel(table, defaultRootSymbol); 339 } 340 341 public void setDefaultRootEdgeLabels(String rootLabelOption, SortedMap<String, SymbolTable> edgeSymbolTables) throws MaltChainedException { 342 if (rootLabels == null) { 343 rootLabels = new RootLabels(); 344 } 345 rootLabels.setRootLabels(rootLabelOption, edgeSymbolTables); 346 } 347 348 public void clear() throws MaltChainedException { 349 edgePool.checkInAll(); 350 graphEdges.clear(); 351 root.clear(); 352 root.setBelongsToGraph(this); 353 nonTerminalPool.checkInAll(); 354 nonTerminalNodes.clear(); 355 if (mapping != null) { 356 mapping.clear(); 357 } 358 super.clear(); 359 360 numberOfComponents++; 361 } 362 363 public DependencyNode getDependencyRoot() { 364 return root; 365 } 366 367 public PhraseStructureNode addTerminalNode() throws MaltChainedException { 368 return addTokenNode(); 369 } 370 371 public PhraseStructureNode addTerminalNode(int index) throws MaltChainedException { 372 return addTokenNode(index); 373 } 374 375 public PhraseStructureNode getTerminalNode(int index) { 376 return getTokenNode(index); 377 } 378 379 public int nTerminalNode() { 380 return nTokenNode(); 381 } 382 383 public PhraseStructureNode addNonTerminalNode(int index) throws MaltChainedException { 384 NonTerminal node = nonTerminalPool.checkOut(); 385 node.setIndex(index); 386 node.setBelongsToGraph(this); 387 nonTerminalNodes.put(index,node); 388 return node; 389 } 390 391 public PhraseStructureNode addNonTerminalNode() throws MaltChainedException { 392 int index = getHighestNonTerminalIndex(); 393 if (index > 0) { 394 return addNonTerminalNode(index+1); 395 } 396 return addNonTerminalNode(1); 397 } 398 399 public PhraseStructureNode getNonTerminalNode(int index) throws MaltChainedException { 400 return nonTerminalNodes.get(index); 401 } 402 403 public int getHighestNonTerminalIndex() { 404 try { 405 return nonTerminalNodes.lastKey(); 406 } catch (NoSuchElementException e) { 407 return 0; 408 } 409 } 410 411 public Set<Integer> getNonTerminalIndices() { 412 return new TreeSet<Integer>(nonTerminalNodes.keySet()); 413 } 414 415 public boolean hasNonTerminals() { 416 return !nonTerminalNodes.isEmpty(); 417 } 418 419 public int nNonTerminals() { 420 return nonTerminalNodes.size(); 421 } 422 423 public PhraseStructureNode getPhraseStructureRoot() { 424 return root; 425 } 426 427 public Edge addPhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException { 428 if (parent == null || child == null) { 429 throw new MaltChainedException("Parent or child node is missing in sentence "+getSentenceID()); 430 } else if (parent.getBelongsToGraph() != this || child.getBelongsToGraph() != this) { 431 throw new MaltChainedException("Parent or child node is not a member of the graph in sentence "+getSentenceID()); 432 } else if (parent == child) { 433 throw new MaltChainedException("It is not allowed to add a phrase structure edge connecting the same node in sentence "+getSentenceID()); 434 } else if (parent instanceof NonTerminalNode && !child.isRoot()) { 435 Edge e = edgePool.checkOut(); 436 e.setBelongsToGraph(this); 437 e.setEdge((Node)parent, (Node)child, Edge.PHRASE_STRUCTURE_EDGE); 438 graphEdges.add(e); 439 return e; 440 } else { 441 throw new MaltChainedException("Parent or child node is not of correct node type."); 442 } 443 } 444 445 public void update(Observable o, Object arg) { 446 if (o instanceof Edge && mapping != null) { 447 try { 448 mapping.update(this, (Edge)o, arg); 449 } catch (MaltChainedException ex) { 450 if (SystemLogger.logger().isDebugEnabled()) { 451 SystemLogger.logger().debug("",ex); 452 } else { 453 SystemLogger.logger().error(ex.getMessageChain()); 454 } 455 System.exit(1); 456 } 457 } 458 } 459 460 public LosslessMapping getMapping() { 461 return mapping; 462 } 463 464 public void setMapping(LosslessMapping mapping) { 465 this.mapping = mapping; 466 } 467 468 public void addLabel(Element element, String labelFunction, String label) throws MaltChainedException { 469 super.addLabel(element, labelFunction, label); 470 } 471 472 public void removePhraseStructureEdge(PhraseStructureNode parent, PhraseStructureNode child) throws MaltChainedException { 473 if (parent == null || child == null) { 474 throw new MaltChainedException("Parent or child node is missing."); 475 } else if (parent instanceof NonTerminalNode && !child.isRoot()) { 476 for (Edge e : graphEdges) { 477 if (e.getSource() == parent && e.getTarget() == child) { 478 e.clear(); 479 graphEdges.remove(e); 480 if (e instanceof GraphEdge) { 481 edgePool.checkIn(e); 482 } 483 } 484 } 485 } else { 486 throw new SyntaxGraphException("Head node is not a root node or a terminal node."); 487 } 488 } 489 490 public boolean isContinuous() { 491 for (int index : nonTerminalNodes.keySet()) { 492 NonTerminalNode node = nonTerminalNodes.get(index); 493 494 if (!node.isContinuous()) { 495 return false; 496 } 497 } 498 return true; 499 } 500 501 public boolean isContinuousExcludeTerminalsAttachToRoot() { 502 for (int index : nonTerminalNodes.keySet()) { 503 NonTerminalNode node = nonTerminalNodes.get(index); 504 if (!node.isContinuousExcludeTerminalsAttachToRoot()) { 505 return false; 506 } 507 } 508 return true; 509 } 510 511 // public void makeContinuous() throws MaltChainedException { 512 // if (root != null) { 513 // root.reArrangeChildrenAccordingToLeftAndRightProperDesendant(); 514 // } 515 // } 516 517 public String toStringTerminalNode(TokenNode node) { 518 final StringBuilder sb = new StringBuilder(); 519 final DependencyNode depnode = node; 520 521 sb.append(node.toString().trim()); 522 if (depnode.hasHead()) { 523 sb.append('\t'); 524 try { 525 sb.append(depnode.getHead().getIndex()); 526 sb.append('\t'); 527 sb.append(depnode.getHeadEdge().toString()); 528 } catch (MaltChainedException e) { 529 System.out.println(e); 530 } 531 } 532 sb.append('\n'); 533 534 return sb.toString(); 535 } 536 537 public String toStringNonTerminalNode(NonTerminalNode node) { 538 final StringBuilder sb = new StringBuilder(); 539 540 sb.append(node.toString().trim()); 541 sb.append('\n'); 542 Iterator<Edge> ie = ((Node)node).getOutgoingEdgeIterator(); 543 while (ie.hasNext()) { 544 Edge e = ie.next(); 545 if (e.getTarget() instanceof TokenNode) { 546 sb.append(" T"); 547 sb.append(e.getTarget().getIndex()); 548 } 549 if (e.getTarget() instanceof NonTerminalNode) { 550 sb.append(" N"); 551 sb.append(e.getTarget().getIndex()); 552 } 553 sb.append('\t'); 554 sb.append(e.toString()); 555 sb.append('\n'); 556 } 557 return sb.toString(); 558 } 559 560 public String toString() { 561 StringBuilder sb = new StringBuilder(); 562 for (int index : terminalNodes.keySet()) { 563 sb.append(toStringTerminalNode(terminalNodes.get(index))); 564 } 565 sb.append('\n'); 566 sb.append(toStringNonTerminalNode((NonTerminalNode)getPhraseStructureRoot())); 567 for (int index : nonTerminalNodes.keySet()) { 568 sb.append(toStringNonTerminalNode(nonTerminalNodes.get(index))); 569 } 570 return sb.toString(); 571 } 572 }