    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    }