package org.maltparser.transform.pseudo;
import java.util.Vector;
import org.apache.log4j.Logger;
import org.maltparser.core.exception.MaltChainedException;
import org.maltparser.core.symbol.SymbolTable;
import org.maltparser.core.symbol.SymbolTableHandler;
import org.maltparser.core.syntaxgraph.DependencyStructure;
import org.maltparser.core.syntaxgraph.node.DependencyNode;
/**
* This class contains methods for projectivizing and deprojectivizing
*
* @author Jens Nilsson
* @since 1.0
*/
public class PseudoProjectivity {
static int id = 0;
private enum PseudoProjectiveEncoding {
NONE, BASELINE, HEAD, PATH, HEADPATH, TRACE
};
private enum CoveredRootAttachment {
NONE, LEFT, RIGHT, HEAD
};
private enum LiftingOrder {
SHORTEST, DEEPEST
};
private PseudoProjectiveEncoding markingStrategy;
private CoveredRootAttachment rootAttachment;
private LiftingOrder liftingOrder;
private Logger configLogger;
private SymbolTable deprelSymbolTable;
private SymbolTable pppathSymbolTable;
private SymbolTable ppliftedSymbolTable;
private SymbolTable ppcoveredRootSymbolTable;
private Vector<Boolean> nodeLifted;
private Vector<Vector<DependencyNode>> nodeTrace;
private Vector<DependencyNode> headDeprel;
private Vector<Boolean> nodePath;
private Vector<Boolean> isCoveredRoot;
private Vector<Integer> nodeRelationLength;
private Vector<String> synacticHeadDeprel;
public PseudoProjectivity() { }
public void initialize(String markingStrategyString, String coveredRoot, String liftingOrder, Logger configLogger,
SymbolTableHandler symbolTables) throws MaltChainedException {
nodeLifted = new Vector<Boolean>();
nodeTrace = new Vector<Vector<DependencyNode>>();
headDeprel = new Vector<DependencyNode>();
nodePath = new Vector<Boolean>();
isCoveredRoot = new Vector<Boolean>();
nodeRelationLength = new Vector<Integer>();
synacticHeadDeprel = new Vector<String>();
this.configLogger = configLogger;
if (markingStrategyString.equalsIgnoreCase("none")) {
markingStrategy = PseudoProjectiveEncoding.NONE;
} else if (markingStrategyString.equalsIgnoreCase("baseline")) {
markingStrategy = PseudoProjectiveEncoding.BASELINE;
} else if (markingStrategyString.equalsIgnoreCase("head")) {
markingStrategy = PseudoProjectiveEncoding.HEAD;
} else if (markingStrategyString.equalsIgnoreCase("path")) {
markingStrategy = PseudoProjectiveEncoding.PATH;
} else if (markingStrategyString.equalsIgnoreCase("head+path")) {
markingStrategy = PseudoProjectiveEncoding.HEADPATH;
} else if (markingStrategyString.equalsIgnoreCase("trace")) {
markingStrategy = PseudoProjectiveEncoding.TRACE;
}
this.deprelSymbolTable = symbolTables.getSymbolTable("DEPREL");
if (markingStrategy == PseudoProjectiveEncoding.HEAD || markingStrategy == PseudoProjectiveEncoding.PATH
|| markingStrategy == PseudoProjectiveEncoding.HEADPATH) {
this.ppliftedSymbolTable = symbolTables.addSymbolTable("PPLIFTED", deprelSymbolTable);
if (this.markingStrategy == PseudoProjectiveEncoding.PATH) {
ppliftedSymbolTable.addSymbol("#true#");
ppliftedSymbolTable.addSymbol("#false#");
} else {
ppliftedSymbolTable.addSymbol("#false#");
}
}
if (markingStrategy == PseudoProjectiveEncoding.PATH || markingStrategy == PseudoProjectiveEncoding.HEADPATH) {
pppathSymbolTable = symbolTables.addSymbolTable("PPPATH", deprelSymbolTable);
pppathSymbolTable.addSymbol("#true#");
pppathSymbolTable.addSymbol("#false#");
}
if (coveredRoot.equalsIgnoreCase("none")) {
this.rootAttachment = CoveredRootAttachment.NONE;
} else if (coveredRoot.equalsIgnoreCase("left")) {
this.rootAttachment = CoveredRootAttachment.LEFT;
} else if (coveredRoot.equalsIgnoreCase("right")) {
this.rootAttachment = CoveredRootAttachment.RIGHT;
} else if (coveredRoot.equalsIgnoreCase("head")) {
this.rootAttachment = CoveredRootAttachment.HEAD;
}
if (this.rootAttachment != CoveredRootAttachment.NONE) {
this.ppcoveredRootSymbolTable = symbolTables.addSymbolTable("PPCOVERED", deprelSymbolTable);
ppcoveredRootSymbolTable.addSymbol("#true#");
ppcoveredRootSymbolTable.addSymbol("#false#");
}
if (liftingOrder.equalsIgnoreCase("shortest")) {
this.liftingOrder = LiftingOrder.SHORTEST;
} else if (liftingOrder.equalsIgnoreCase("deepest")) {
this.liftingOrder = LiftingOrder.DEEPEST;
}
}
private void initProjectivization(DependencyStructure pdg) throws MaltChainedException {
nodeLifted.clear();
nodeTrace.clear();
headDeprel.clear();
nodePath.clear();
isCoveredRoot.clear();
nodeRelationLength.clear();
for (int index : pdg.getDependencyIndices()) {
nodeLifted.add(false);
nodeTrace.add(new Vector<DependencyNode>());
headDeprel.add(null);
nodePath.add(false);
isCoveredRoot.add(false);
if (ppliftedSymbolTable != null && index != 0) {
pdg.getDependencyNode(index).getHeadEdge().getLabelSet().put(ppliftedSymbolTable, ppliftedSymbolTable.getSymbolStringToCode("#false#"));
}
if (pppathSymbolTable != null && index != 0) {
pdg.getDependencyNode(index).getHeadEdge().getLabelSet().put(pppathSymbolTable, pppathSymbolTable.getSymbolStringToCode("#false#"));
}
if (ppcoveredRootSymbolTable != null && index != 0) {
pdg.getDependencyNode(index).getHeadEdge().getLabelSet().put(ppcoveredRootSymbolTable, ppcoveredRootSymbolTable.getSymbolStringToCode("#false#"));
}
}
computeRelationLength(pdg);
}
public void projectivize(DependencyStructure pdg) throws MaltChainedException {
id++;
if (!pdg.isTree()) {
configLogger.info("\n[Warning: Sentence '" + id + "' cannot projectivize, because the dependency graph is not a tree]\n");
return;
}
DependencyNode deepestNonProjectiveNode;
initProjectivization(pdg);
if (markingStrategy != PseudoProjectiveEncoding.NONE) {
while (!pdg.isProjective()) {
if (liftingOrder == LiftingOrder.DEEPEST) {
deepestNonProjectiveNode = getDeepestNonProjectiveNode(pdg);
} else {
deepestNonProjectiveNode = getShortestNonProjectiveNode(pdg);
}
if (!attachCoveredRoots(pdg, deepestNonProjectiveNode)) {
nodeLifted.set(deepestNonProjectiveNode.getIndex(), true);
setHeadDeprel(deepestNonProjectiveNode, deepestNonProjectiveNode.getHead());
setPath(deepestNonProjectiveNode.getHead());
pdg.moveDependencyEdge(pdg.getDependencyNode(deepestNonProjectiveNode.getHead().getHead().getIndex()).getIndex(), deepestNonProjectiveNode.getIndex());
}
}
if (rootAttachment == CoveredRootAttachment.NONE) {
deattachCoveredRootsForProjectivization(pdg);
}
} else if (rootAttachment != CoveredRootAttachment.NONE) {
for (int index : pdg.getTokenIndices()) {
attachCoveredRoots(pdg, pdg.getTokenNode(index));
}
}
// collectTraceStatistics(pdg);
assignPseudoProjectiveDeprels(pdg);
}
public void mergeArclabels(DependencyStructure pdg) throws MaltChainedException {
assignPseudoProjectiveDeprelsForMerge(pdg);
}
public void splitArclabels(DependencyStructure pdg) throws MaltChainedException {
int pathLabelIndex = -1, movedLabelIndex = -1, coveredArcLabelIndex;
String label;
initDeprojeciviztion(pdg);
for (int index : pdg.getTokenIndices()) {
if (pdg.getTokenNode(index).getHeadEdge().hasLabel(deprelSymbolTable)) {
label = deprelSymbolTable.getSymbolCodeToString(pdg.getTokenNode(index).getHeadEdge().getLabelCode(deprelSymbolTable));
if (label != null && (pathLabelIndex = label.indexOf("%")) != -1) {
label = label.substring(0, pathLabelIndex);
setLabel(pdg.getTokenNode(index), label);
pdg.getTokenNode(index).getHeadEdge().addLabel(pppathSymbolTable, pppathSymbolTable.getSymbolStringToCode("#true#"));
}
if (label != null && (movedLabelIndex = label.indexOf("|")) != -1 && label.indexOf("|null") == -1) {
if (movedLabelIndex + 1 < label.length()) {
pdg.getTokenNode(index).getHeadEdge().addLabel(ppliftedSymbolTable, ppliftedSymbolTable.getSymbolStringToCode(label.substring(movedLabelIndex + 1)));
} else {
pdg.getTokenNode(index).getHeadEdge().addLabel(ppliftedSymbolTable, ppliftedSymbolTable.getSymbolStringToCode("#true#"));
}
label = label.substring(0, movedLabelIndex);
setLabel(pdg.getTokenNode(index), label);
}
}
}
for (int index : pdg.getTokenIndices()) {
if (pdg.getTokenNode(index).getHeadEdge().hasLabel(deprelSymbolTable)) {
label = deprelSymbolTable.getSymbolCodeToString(pdg.getTokenNode(index).getHeadEdge().getLabelCode(deprelSymbolTable));
if ((coveredArcLabelIndex = label.indexOf("|null")) != -1) {
label = label.substring(0, coveredArcLabelIndex);
setLabel(pdg.getTokenNode(index), label);
pdg.getTokenNode(index).getHeadEdge().addLabel(ppcoveredRootSymbolTable, ppcoveredRootSymbolTable.getSymbolStringToCode("#true#"));
}
}
}
}
private void setHeadDeprel(DependencyNode node, DependencyNode parent) {
if (headDeprel.get(node.getIndex()) == null) {
headDeprel.set(node.getIndex(), parent);
}
nodeTrace.set(node.getIndex(), headDeprel);
}
private void setPath(DependencyNode node) {
nodePath.set(node.getIndex(), true);
}
private boolean isCoveredRoot(DependencyNode node) {
return isCoveredRoot.get(node.getIndex());
}
private void deattachCoveredRootsForProjectivization(DependencyStructure pdg) throws MaltChainedException {
for (int index : pdg.getTokenIndices()) {
if (isCoveredRoot(pdg.getTokenNode(index))) {
pdg.moveDependencyEdge(pdg.getDependencyRoot().getIndex(), pdg.getTokenNode(index).getIndex());
}
}
}
private boolean attachCoveredRoots(DependencyStructure pdg, DependencyNode deepest) throws MaltChainedException {
int i;
boolean foundCoveredRoot = false;
DependencyNode coveredRootHead;
for (i = Math.min(deepest.getIndex(), deepest.getHead().getIndex()) + 1; i < Math.max(deepest.getIndex(), deepest.getHead()
.getIndex()); i++) {
int leftMostIndex = pdg.getDependencyNode(i).getLeftmostProperDescendantIndex();
if (leftMostIndex == -1) {
leftMostIndex = i;
}
int rightMostIndex = pdg.getDependencyNode(i).getRightmostProperDescendantIndex();
if (rightMostIndex == -1) {
rightMostIndex = i;
}
// if (!nodeLifted.get(i) && pdg.getDependencyNode(i).getHead().isRoot() && !deepest.getHead().isRoot()
// && Math.min(deepest.getIndex(), deepest.getHead().getIndex()) < pdg.getDependencyNode(i).getLeftmostDescendantIndex()
// && pdg.getDependencyNode(i).getRightmostDescendantIndex() < Math.max(deepest.getIndex(), deepest.getHead().getIndex())) {
if (!nodeLifted.get(i) && pdg.getDependencyNode(i).getHead().isRoot() && !deepest.getHead().isRoot()
&& Math.min(deepest.getIndex(), deepest.getHead().getIndex()) < leftMostIndex
&& rightMostIndex < Math.max(deepest.getIndex(), deepest.getHead().getIndex())) {
if (rootAttachment == CoveredRootAttachment.LEFT) {
if (deepest.getHead().getIndex() < deepest.getIndex()) {
coveredRootHead = deepest.getHead();
} else {
coveredRootHead = deepest;
}
} else if (rootAttachment == CoveredRootAttachment.RIGHT) {
if (deepest.getIndex() < deepest.getHead().getIndex()) {
coveredRootHead = deepest.getHead();
} else {
coveredRootHead = deepest;
}
} else {
coveredRootHead = deepest.getHead();
}
pdg.moveDependencyEdge(coveredRootHead.getIndex(), pdg.getDependencyNode(i).getIndex());
setCoveredRoot(pdg.getDependencyNode(i));
foundCoveredRoot = true;
}
}
return foundCoveredRoot;
}
private void setCoveredRoot(DependencyNode node) {
isCoveredRoot.set(node.getIndex(), true);
}
private DependencyNode getDeepestNonProjectiveNode(DependencyStructure pdg) throws MaltChainedException {
DependencyNode deepestNonProjectiveNode = null;
for (int index : pdg.getDependencyIndices()) {
if (!pdg.getDependencyNode(index).isProjective()
&& (deepestNonProjectiveNode == null
|| pdg.getDependencyNode(index).getDependencyNodeDepth() > pdg.getDependencyNode(deepestNonProjectiveNode.getIndex()).getDependencyNodeDepth())) {
deepestNonProjectiveNode = pdg.getDependencyNode(index);
}
}
return deepestNonProjectiveNode;
}
private DependencyNode getShortestNonProjectiveNode(DependencyStructure pdg) throws MaltChainedException {
DependencyNode shortestNonProjectiveNode = null;
for (int index : pdg.getDependencyIndices()) {
if (!pdg.getDependencyNode(index).isProjective()
&& (shortestNonProjectiveNode == null
|| nodeRelationLength.get(index) < nodeRelationLength.get(shortestNonProjectiveNode.getIndex())
|| (nodeRelationLength.get(index) == nodeRelationLength.get(shortestNonProjectiveNode.getIndex())))) {
shortestNonProjectiveNode = pdg.getDependencyNode(index);
}
}
return shortestNonProjectiveNode;
}
private void computeRelationLength(DependencyStructure pdg) throws MaltChainedException {
nodeRelationLength.add(0);
for (int index : pdg.getTokenIndices()) {
nodeRelationLength.add(Math.abs(pdg.getDependencyNode(index).getIndex() - pdg.getDependencyNode(index).getHead().getIndex()));
}
}
private void assignPseudoProjectiveDeprels(DependencyStructure pdg) throws MaltChainedException {
int newLabelCode;
for (int index : pdg.getTokenIndices()) {
if (!isCoveredRoot(pdg.getDependencyNode(index))) {
if (this.markingStrategy == PseudoProjectiveEncoding.HEAD || this.markingStrategy == PseudoProjectiveEncoding.PATH
|| this.markingStrategy == PseudoProjectiveEncoding.HEADPATH) {
if (this.markingStrategy == PseudoProjectiveEncoding.PATH) {
if (nodeLifted.get(index)) {
newLabelCode = ppliftedSymbolTable.getSymbolStringToCode("#true#");
} else {
newLabelCode = ppliftedSymbolTable.getSymbolStringToCode("#false#");
}
pdg.getDependencyNode(index).getHeadEdge().addLabel(ppliftedSymbolTable, newLabelCode);
} else {
if (nodeLifted.get(index)) {
newLabelCode = ppliftedSymbolTable.addSymbol(deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(
headDeprel.get(index).getIndex()).getHeadEdge().getLabelCode(deprelSymbolTable)));
} else {
newLabelCode = ppliftedSymbolTable.getSymbolStringToCode("#false#");
}
pdg.getDependencyNode(index).getHeadEdge().addLabel(ppliftedSymbolTable, newLabelCode);
}
}
if (this.markingStrategy == PseudoProjectiveEncoding.PATH || this.markingStrategy == PseudoProjectiveEncoding.HEADPATH) {
if (nodePath.get(index)) {
newLabelCode = pppathSymbolTable.getSymbolStringToCode("#true#");
} else {
newLabelCode = pppathSymbolTable.getSymbolStringToCode("#false#");
}
pdg.getDependencyNode(index).getHeadEdge().addLabel(pppathSymbolTable, newLabelCode);
}
// if (markingStrategy == PseudoProjectiveEncoding.TRACE) {
// if (nodeLifted.get(i)) {
// newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getNode(i).getLabelCode(deprelSymbolTable)) + "|";
// addArc(pdg, pdg.getNode(i), pdg.getNode(i).getHead(), newLabel);
// }
// }
} else if (rootAttachment != CoveredRootAttachment.NONE) {
pdg.getDependencyNode(index).getHeadEdge().addLabel(ppcoveredRootSymbolTable, ppcoveredRootSymbolTable.getSymbolStringToCode("#true#"));
}
}
}
private void setLabel(DependencyNode node, String label) throws MaltChainedException {
// node.getLabelCode().clear();
node.getHeadEdge().getLabelSet().put(deprelSymbolTable, deprelSymbolTable.addSymbol(label));
}
private void assignPseudoProjectiveDeprelsForMerge(DependencyStructure pdg) throws MaltChainedException {
Vector<String> originalDeprel = new Vector<String>();
String newLabel;
originalDeprel.add(null);
for (int index : pdg.getTokenIndices()) {
originalDeprel.add(deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)));
}
for (int index : pdg.getTokenIndices()) {
newLabel = null;
if (!isCoveredRoot(pdg.getDependencyNode(index))) {
if (markingStrategy == PseudoProjectiveEncoding.HEAD) {
if (nodeLifted.get(index)) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "|"
+ originalDeprel.get(headDeprel.get(index).getIndex());
// } else {
// newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable));
}
} else if (markingStrategy == PseudoProjectiveEncoding.PATH) {
if (nodeLifted.get(index) && nodePath.get(index)) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "|%";
} else if (nodeLifted.get(index) && !nodePath.get(index)) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "|";
} else if (!nodeLifted.get(index) && nodePath.get(index)) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "%";
}
} else if (markingStrategy == PseudoProjectiveEncoding.HEADPATH) {
if (nodeLifted.get(index) && nodePath.get(index)) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "|"
+ originalDeprel.get(headDeprel.get(index).getIndex()) + "%";
} else if (nodeLifted.get(index) && !nodePath.get(index)) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "|"
+ originalDeprel.get(headDeprel.get(index).getIndex());
} else if (!nodeLifted.get(index) && nodePath.get(index)) {
newLabel = originalDeprel.get(pdg.getDependencyNode(index).getIndex()) + "%";
}
} else if (markingStrategy == PseudoProjectiveEncoding.TRACE) {
if (nodeLifted.get(index)) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "|";
}
}
} else if (rootAttachment != CoveredRootAttachment.NONE) {
newLabel = deprelSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(deprelSymbolTable)) + "|null";
}
if (newLabel != null) {
setLabel(pdg.getDependencyNode(index), newLabel);
}
}
}
public void deprojectivize(DependencyStructure pdg) throws MaltChainedException {
initDeprojeciviztion(pdg);
for (int index : pdg.getTokenIndices()) {
if (pdg.getDependencyNode(index).getHeadEdge().hasLabel(deprelSymbolTable)) {
if (pdg.getDependencyNode(index).getHeadEdge().hasLabel(pppathSymbolTable)
&& pppathSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(pppathSymbolTable)).equals("#true#")) {
setPath(pdg.getDependencyNode(index));
}
if (pdg.getDependencyNode(index).getHeadEdge().hasLabel(ppliftedSymbolTable)
&& !ppliftedSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(ppliftedSymbolTable)).equals("#false#")) {
nodeLifted.set(index, true);
if (!ppliftedSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(ppliftedSymbolTable)).equals("#true#")) {
synacticHeadDeprel.set(index, ppliftedSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge()
.getLabelCode(ppliftedSymbolTable)));
}
}
}
}
deattachCoveredRootsForDeprojectivization(pdg);
if (markingStrategy == PseudoProjectiveEncoding.HEAD && needsDeprojectivizeWithHead(pdg)) {
deprojectivizeWithHead(pdg, pdg.getDependencyRoot());
} else if (markingStrategy == PseudoProjectiveEncoding.PATH) {
deprojectivizeWithPath(pdg, pdg.getDependencyRoot());
} else if (markingStrategy == PseudoProjectiveEncoding.HEADPATH) {
deprojectivizeWithHeadAndPath(pdg, pdg.getDependencyRoot());
// } else if (markingStrategy == PseudoProjectiveEncoding.TRACE) {
// deprojectivizeWithTrace(pdg, pdg.getRoot());
}
}
private void initDeprojeciviztion(DependencyStructure pdg) {
nodeLifted.clear();
nodePath.clear();
synacticHeadDeprel.clear();
for (int index : pdg.getDependencyIndices()) {
nodeLifted.add(false);
nodePath.add(false);
synacticHeadDeprel.add(null);
}
}
private void deattachCoveredRootsForDeprojectivization(DependencyStructure pdg) throws MaltChainedException {
for (int index : pdg.getTokenIndices()) {
if (pdg.getDependencyNode(index).getHeadEdge().hasLabel(deprelSymbolTable)) {
if (pdg.getDependencyNode(index).getHeadEdge().hasLabel(ppcoveredRootSymbolTable)
&& ppcoveredRootSymbolTable.getSymbolCodeToString(pdg.getDependencyNode(index).getHeadEdge().getLabelCode(ppcoveredRootSymbolTable)).equals(
"#true#")) {
pdg.moveDependencyEdge(pdg.getDependencyRoot().getIndex(), pdg.getDependencyNode(index).getIndex());
}
}
}
}
// Check whether there is at least one node in the specified dependency structure that can be lifted.
// If this is not the case, there is no need to call deprojectivizeWithHead.
private boolean needsDeprojectivizeWithHead(DependencyStructure pdg) throws MaltChainedException {
for (int index : pdg.getDependencyIndices()) {
if (nodeLifted.get(index)) {
DependencyNode node = pdg.getDependencyNode(index);
if (breadthFirstSearchSortedByDistanceForHead(pdg, node.getHead(), node, synacticHeadDeprel.get(index)) != null) {
return true;
}
}
}
return false;
}
private boolean deprojectivizeWithHead(DependencyStructure pdg, DependencyNode node) throws MaltChainedException {
boolean success = true, childSuccess = false;
int i, childAttempts = 2;
DependencyNode child, possibleSyntacticHead;
String syntacticHeadDeprel;
if (nodeLifted.get(node.getIndex())) {
syntacticHeadDeprel = synacticHeadDeprel.get(node.getIndex());
possibleSyntacticHead = breadthFirstSearchSortedByDistanceForHead(pdg, node.getHead(), node, syntacticHeadDeprel);
if (possibleSyntacticHead != null) {
pdg.moveDependencyEdge(possibleSyntacticHead.getIndex(), node.getIndex());
// addEdge(pdg, possibleSyntacticHead, node, node.getHeadEdge().getLabelSet());
nodeLifted.set(node.getIndex(), false);
} else {
success = false;
}
}
while (!childSuccess && childAttempts > 0) {
childSuccess = true;
Vector<DependencyNode> children = new Vector<DependencyNode>();
i = 0;
while ((child = node.getLeftDependent(i)) != null) {
children.add(child);
i++;
}
i = 0;
while ((child = node.getRightDependent(i)) != null) {
children.add(child);
i++;
}
for (i = 0; i < children.size(); i++) {
child = children.get(i);
if (!deprojectivizeWithHead(pdg, child)) {
childSuccess = false;
}
}
childAttempts--;
}
return childSuccess && success;
}
private DependencyNode breadthFirstSearchSortedByDistanceForHead(DependencyStructure dg, DependencyNode start, DependencyNode avoid, String syntacticHeadDeprel)
throws MaltChainedException {
DependencyNode dependent;
String dependentDeprel;
Vector<DependencyNode> nodes = new Vector<DependencyNode>();
nodes.addAll(findAllDependentsVectorSortedByDistanceToPProjNode(dg, start, avoid, false));
while (nodes.size() > 0) {
dependent = nodes.remove(0);
if (dependent.getHeadEdge().hasLabel(deprelSymbolTable)) {
dependentDeprel = deprelSymbolTable.getSymbolCodeToString(dependent.getHeadEdge().getLabelCode(deprelSymbolTable));
if (dependentDeprel.equals(syntacticHeadDeprel)) {
return dependent;
}
}
nodes.addAll(findAllDependentsVectorSortedByDistanceToPProjNode(dg, dependent, avoid, false));
}
return null;
}
private Vector<DependencyNode> findAllDependentsVectorSortedByDistanceToPProjNode(DependencyStructure dg, DependencyNode governor, DependencyNode avoid,
boolean percentOnly) {
int i, j;
Vector<DependencyNode> dependents = new Vector<DependencyNode>();
DependencyNode leftChild, rightChild;
i = governor.getLeftDependentCount() - 1;
j = 0;
leftChild = governor.getLeftDependent(i--);
rightChild = governor.getRightDependent(j++);
while (leftChild != null && rightChild != null) {
if (leftChild == avoid) {
leftChild = governor.getLeftDependent(i--);
} else if (rightChild == avoid) {
rightChild = governor.getRightDependent(j++);
} else if (Math.abs(leftChild.getIndex() - avoid.getIndex()) < Math.abs(rightChild.getIndex() - avoid.getIndex())) {
if (!percentOnly || (percentOnly && nodePath.get(leftChild.getIndex()))) {
dependents.add(leftChild);
}
leftChild = governor.getLeftDependent(i--);
} else {
if (!percentOnly || (percentOnly && nodePath.get(rightChild.getIndex()))) {
dependents.add(rightChild);
}
rightChild = governor.getRightDependent(j++);
}
}
while (leftChild != null) {
if (leftChild != avoid && (!percentOnly || (percentOnly && nodePath.get(leftChild.getIndex())))) {
dependents.add(leftChild);
}
leftChild = governor.getLeftDependent(i--);
}
while (rightChild != null) {
if (rightChild != avoid && (!percentOnly || (percentOnly && nodePath.get(rightChild.getIndex())))) {
dependents.add(rightChild);
}
rightChild = governor.getRightDependent(j++);
}
return dependents;
}
private boolean deprojectivizeWithPath(DependencyStructure pdg, DependencyNode node) throws MaltChainedException {
boolean success = true, childSuccess = false;
int i, childAttempts = 2;
DependencyNode child, possibleSyntacticHead;
if (node.hasHead() && node.getHeadEdge().isLabeled() && nodeLifted.get(node.getIndex()) && nodePath.get(node.getIndex())) {
possibleSyntacticHead = breadthFirstSearchSortedByDistanceForPath(pdg, node.getHead(), node);
if (possibleSyntacticHead != null) {
pdg.moveDependencyEdge(possibleSyntacticHead.getIndex(), node.getIndex());
// addEdge(pdg, possibleSyntacticHead, node, node.getHeadEdge().getLabelSet());
nodeLifted.set(node.getIndex(), false);
} else {
success = false;
}
}
if (node.hasHead() && node.getHeadEdge().isLabeled() && nodeLifted.get(node.getIndex())) {
possibleSyntacticHead = breadthFirstSearchSortedByDistanceForPath(pdg, node.getHead(), node);
if (possibleSyntacticHead != null) {
pdg.moveDependencyEdge(possibleSyntacticHead.getIndex(), node.getIndex());
// addEdge(pdg, possibleSyntacticHead, node, node.getHeadEdge().getLabelSet());
nodeLifted.set(node.getIndex(), false);
} else {
success = false;
}
}
while (!childSuccess && childAttempts > 0) {
childSuccess = true;
Vector<DependencyNode> children = new Vector<DependencyNode>();
i = 0;
while ((child = node.getLeftDependent(i)) != null) {
children.add(child);
i++;
}
i = 0;
while ((child = node.getRightDependent(i)) != null) {
children.add(child);
i++;
}
for (i = 0; i < children.size(); i++) {
child = children.get(i);
if (!deprojectivizeWithPath(pdg, child)) {
childSuccess = false;
}
}
childAttempts--;
}
return childSuccess && success;
}
private DependencyNode breadthFirstSearchSortedByDistanceForPath(DependencyStructure dg, DependencyNode start, DependencyNode avoid) {
DependencyNode dependent;
Vector<DependencyNode> nodes = new Vector<DependencyNode>(), newNodes;
nodes.addAll(findAllDependentsVectorSortedByDistanceToPProjNode(dg, start, avoid, true));
while (nodes.size() > 0) {
dependent = nodes.remove(0);
if (((newNodes = findAllDependentsVectorSortedByDistanceToPProjNode(dg, dependent, avoid, true)).size()) == 0) {
return dependent;
}
nodes.addAll(newNodes);
}
return null;
}
private boolean deprojectivizeWithHeadAndPath(DependencyStructure pdg, DependencyNode node) throws MaltChainedException {
boolean success = true, childSuccess = false;
int i, childAttempts = 2;
DependencyNode child, possibleSyntacticHead;
if (node.hasHead() && node.getHeadEdge().isLabeled() && nodeLifted.get(node.getIndex()) && nodePath.get(node.getIndex())) {
possibleSyntacticHead = breadthFirstSearchSortedByDistanceForHeadAndPath(pdg, node.getHead(), node, synacticHeadDeprel.get(node
.getIndex()));
if (possibleSyntacticHead != null) {
pdg.moveDependencyEdge(possibleSyntacticHead.getIndex(), node.getIndex());
// addEdge(pdg, possibleSyntacticHead, node, node.getHeadEdge().getLabelSet());
nodeLifted.set(node.getIndex(), false);
} else {
success = false;
}
}
if (node.hasHead() && node.getHeadEdge().isLabeled() && nodeLifted.get(node.getIndex())) {
possibleSyntacticHead = breadthFirstSearchSortedByDistanceForHeadAndPath(pdg, node.getHead(), node, synacticHeadDeprel.get(node
.getIndex()));
if (possibleSyntacticHead != null) {
pdg.moveDependencyEdge(possibleSyntacticHead.getIndex(), node.getIndex());
// addEdge(pdg, possibleSyntacticHead, node, node.getHeadEdge().getLabelSet());
nodeLifted.set(node.getIndex(), false);
} else {
success = false;
}
}
while (!childSuccess && childAttempts > 0) {
childSuccess = true;
Vector<DependencyNode> children = new Vector<DependencyNode>();
i = 0;
while ((child = node.getLeftDependent(i)) != null) {
children.add(child);
i++;
}
i = 0;
while ((child = node.getRightDependent(i)) != null) {
children.add(child);
i++;
}
for (i = 0; i < children.size(); i++) {
child = children.get(i);
if (!deprojectivizeWithHeadAndPath(pdg, child)) {
childSuccess = false;
}
}
childAttempts--;
}
return childSuccess && success;
}
private DependencyNode breadthFirstSearchSortedByDistanceForHeadAndPath(DependencyStructure dg, DependencyNode start, DependencyNode avoid, String syntacticHeadDeprelCode)
throws MaltChainedException {
DependencyNode dependent;
Vector<DependencyNode> nodes = new Vector<DependencyNode>(), newNodes = null, secondChance = new Vector<DependencyNode>();
nodes.addAll(findAllDependentsVectorSortedByDistanceToPProjNode(dg, start, avoid, true));
while (nodes.size() > 0) {
dependent = nodes.remove(0);
if (((newNodes = findAllDependentsVectorSortedByDistanceToPProjNode(dg, dependent, avoid, true)).size()) == 0
&& deprelSymbolTable.getSymbolCodeToString(dependent.getHeadEdge().getLabelCode(deprelSymbolTable)).equals(syntacticHeadDeprelCode)) {
return dependent;
}
nodes.addAll(newNodes);
if (deprelSymbolTable.getSymbolCodeToString(dependent.getHeadEdge().getLabelCode(deprelSymbolTable)).equals(syntacticHeadDeprelCode)
&& newNodes.size() != 0) {
secondChance.add(dependent);
}
}
if (secondChance.size() > 0) {
return secondChance.firstElement();
}
return null;
}
}