我目前正在编写一个差异算法来检测树的两个修订版之间的插入、删除、更新和移动，而每个节点都有一个唯一的 ID，该 ID 不会因修订而改变。
我将按预序遍历每棵树，并动态生成两个节点之间的差异，然后移动cursors相应地（例如，在遇到删除的节点后，仅旧版本上的光标向前移动，对于插入的节点反之亦然）。
现在我的问题是，我必须在移动时检测剪切和粘贴点（其中移动的节点从旧版本中剪切并粘贴到新版本中），以便向前移动右侧光标并进行后续可视化聚合树表示。
我们有一个简单的parent/leftsibling/rightsibling/firstchild/currnode编码，而每个节点都有一个唯一的 ID，一个长值。因为这种编码不了解全局排序，所以我首先考虑按文档顺序在当前节点之后搜索新版本中的 oldNodeKey，并对旧版本上的光标执行反之亦然，并保存是否找到节点以及在多少个节点之后节点访问：
/**
* Search for the supplied node key in following nodes.
*
* @param paramRtx
* Treetank {@link IReadTransaction}
* @param paramNodeKey
* node key to search for
* @return {@code true} if found, {@code false} otherwise
*/
protected Result searchNode(final IReadTransaction paramRtx, final long paramNodeKey) {
checkNotNull(paramRtx);
checkArgument(paramNodeKey >= 0);
final long nodeKey = paramRtx.getNode().getNodeKey();
boolean found = false;
int sumNodes = 0;
for (final AbsAxis axis = new DescendantAxis(paramRtx); !found && axis.hasNext(); axis.next()) {
sumNodes++;
if (axis.getTransaction().getNode().getNodeKey() == paramNodeKey) {
found = true;
}
}
for (final AbsAxis axis = new FollowingAxis(paramRtx); !found && axis.hasNext(); axis.next()) {
sumNodes++;
if (axis.getTransaction().getNode().getNodeKey() == paramNodeKey) {
found = true;
}
}
paramRtx.moveTo(nodeKey);
return new Result(found, sumNodes);
}
本质上，如果 newResult.mSum > oldResult.mSum 则意味着该节点已被“粘贴”，反之亦然，并且 newResult.mSum == oldResult.mSum 是一种特殊情况，但我认为在剪切和修改过多的情况下这是不正确的粘贴点将无法被正确识别。我已经编写了很多代码来跟踪不同的情况，但我认为我必须重新考虑完整的移动检测内容:-(
例如我已经实现了这样的东西：
if (mMovedMap.get(newKey) == null && mMovedMap.get(oldKey) == null) {
final ExecutorService pool = Executors.newFixedThreadPool(2);
final Future<Result> foundNew = pool.submit(new Callable<Result>() {
@Override
public Result call() throws Exception {
return searchNode(paramNewRtx, oldKey);
}
});
final Future<Result> foundOld = pool.submit(new Callable<Result>() {
@Override
public Result call() throws Exception {
return searchNode(paramOldRtx, newKey);
}
});
pool.shutdown();
try {
final Result resultNew = foundNew.get();
final Result resultOld = foundOld.get();
paramNewRtx.moveTo(newKey);
paramOldRtx.moveTo(oldKey);
if (resultNew.mFound && resultOld.mFound && resultNew.mSumNodes > resultOld.mSumNodes) {
moveToNextRightNode(paramOldRtx, null);
if (paramOldRtx.getNode().getNodeKey() == newKey) {
diff = EDiff.MOVEDCUT;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedOldDiffs(paramOldRtx, paramNewRtx, oldKey, diff, paramDepth);
} else {
diff = EDiff.MOVEDPASTE;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedNewDiffs(paramOldRtx, paramNewRtx, newKey, diff, paramDepth);
}
} else if (resultNew.mFound && resultOld.mFound
&& resultNew.mSumNodes < resultOld.mSumNodes) {
moveToNextRightNode(paramNewRtx, null);
if (paramNewRtx.getNode().getNodeKey() == oldKey) {
diff = EDiff.MOVEDPASTE;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedNewDiffs(paramOldRtx, paramNewRtx, newKey, diff, paramDepth);
} else {
diff = EDiff.MOVEDCUT;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedOldDiffs(paramOldRtx, paramNewRtx, oldKey, diff, paramDepth);
}
} else {
assert foundOld.get() != null && foundOld.get().mFound;
assert foundNew.get() != null && foundNew.get().mFound;
assert foundNew.get().mSumNodes == foundOld.get().mSumNodes;
...
}
而 mMovedMap 是一个简单的 Map，用于在遇到移动节点后跟踪它们。
编辑：我尝试检测树中的插入/删除/更新和移动，而节点具有唯一的 ID。困难的部分似乎是检测动作。我正在进行两次预购遍历（一次在旧版本上，另一次在新版本上）。确定插入/删除和更新非常容易，但我很难检测移动，因为我总是比较两个节点（旧版本中的一个与新版本中的一个）我必须知道这两个节点中的哪一个实际上已移动（如果它是旧版本中的节点，则为剪切点，如果新版本中的节点已移动，则为粘贴点）。我还必须知道它是旧版本中的节点还是新版本中的节点已被移动以及如何移动，因为我正在创建一个聚合树表示，其中包含所有编辑操作以在专门的 Sunburst 视图中可视化差异。
编辑：我认为即使我有全局标识符，也无法确定哪一个是剪切的节点（或子树），哪一个是粘贴的节点（或子树）。由于其他修改，仅知道两个节点中哪一个先出现是不够的:(
编辑：有谁知道找出树中哪个节点已移动（比较两个节点）的问题是否是 NP 完全的？或者更一般地检测两个节点之一是否已被移动，考虑到旧版本中的节点上的光标和另一个光标位于新版本中的节点处，以及移动的节点是否已从旧树中删除，或者是否移动的节点是否已插入到新位置？ diff 算法的设计方式使我可以将两棵树聚集或融合在一起，以便它们共享公共节点，这对于插入/删除/相同节点/更新来说很好，而且很可能也适用于替换节点，但我认为它可以还没有完成动作吗？如果它是 NP 完全的或不可解的，我需要一个参考，因为它是我硕士论文的一部分，至少我想描述为什么我没有实现移动检测（或恢复非功能性实现;-)）。
编辑：也许解决方案是：
// Check if it has been INSERTED, DELETED or MOVED.
// ================================================================
final long nodeKeyOld = paramOldRtx.getNode().getNodeKey();
final long nodeKeyNew = paramNewRtx.getNode().getNodeKey();
final boolean movedOld = paramOldRtx.moveTo(nodeKeyNew);
final boolean movedNew = paramNewRtx.moveTo(nodeKeyOld);
if (!movedNew && mDiff == EDiff.DELETED) {
paramOldRtx.moveTo(nodeKeyOld);
if (paramOldRtx.getNode().getNodeKey() == mDeletedKey) {
movedNew = true;
}
}
if (movedOld && movedNew) {
diff = EDiff.MOVED;
} else if (movedOld) {
paramOldRtx.moveTo(nodeKeyOld);
mDeletedKey = paramOldRtx.getNode().getNodeKey();
diff = EDiff.DELETED;
} else {
diff = EDiff.INSERTED;
}
检测 MOVE 操作本身，就像我现在所做的那样（要检查的特殊情况!movedNew && mDiff == EDiff.DELETED树的末尾只需要删除，但节点也可能被移动）。在所有其他情况下，测试新修订版上的光标（事务）是否可以移动到旧修订版中的节点以及旧修订版上的光标是否可以移动到新修订版中的节点就足够了，对吗？
然后我必须跟踪所有即将发生的更改（或者相同的节点），如果检测到另一个移动，我必须检查两个节点键之一（来自旧版本中的节点和新版本中的节点） ）以前也遇到过。如果它是旧节点，则它一定是剪切，当前遇到的移动是粘贴，否则反之亦然）。如果它不是其中一个键，那么它一定是另一个移动操作。
你怎么认为？如果我不能至少 99% 确定它是否有效，我有点不愿意实施它。我花了大约 6 天的时间寻找一个不起作用的解决方案。
编辑：好吧，我认为这是一个坏主意，因为如果我当时不知道哪个是已移动的节点，我不知道如何向前移动光标。
亲切的问候，
约翰内斯
