树/差异算法

我目前正在编写一个diff算法来检测树的两个修订版之间的插入，删除，更新和移动，而每个节点都有一个唯一的ID，它不会通过修订版进行更改。

我将按预先遍历每个树并在运行中在两个节点之间生成差异并相应地移动cursors （例如，在遇到删除的节点之后，只有旧版本上的光标向前移动，反之亦然，对于插入的节点） 。

现在我的问题是，我必须在移动的情况下检测剪切和粘贴点（其中移动的节点从旧版本切割并粘贴到新版本中），以便向前移动右光标并进行后续可视化聚集的树表示。

我们有一个简单的parent/leftsibling/rightsibling/firstchild/currnode编码，而每个节点都有一个唯一的ID，一个long值。 因为这个编码不了解全局排序，所以我首先考虑在文档顺序中的当前节点之后搜索新版本中的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 foundNew = pool.submit(new Callable() { @Override public Result call() throws Exception { return searchNode(paramNewRtx, oldKey); } }); final Future foundOld = pool.submit(new Callable() { @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完全或无法解决的，因为它是我的硕士论文的一部分，至少我想描述为什么我没有实现移动检测（或恢复非function实现;-)）。

编辑：也许解决方案是：

 // 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是树的末尾，只有DELETES已完成，但节点也可能被移动）。 在所有其他情况下，测试新版本中的游标（事务）是否可以移动到旧版本中的节点并且旧版本上的游标可以移动到新版本中的节点，这应该足够了，对吗？

然后我必须跟踪所有即将发生的变化（或者相同的节点），如果检测到另一个移动，我必须检查两个节点密钥中的一个（来自旧版本中的节点和新版本中的节点） ）以前遇到过。 如果它是旧节点，它必须是一个切割，当前遇到的移动是粘贴，否则反之亦然）。 如果它不是其中一个键，则必须是另一个移动操作。

你怎么看？ 如果我不是至少99％确定是否有效，我有点不愿意实施它。 我花了大约6天的时间来解决一个无法解决的问题。

编辑：好的，我认为这是一个坏主意，因为如果我当时不知道哪一个是被移动的节点，我不知道如何向前移动游标。

亲切的问候，
约翰内斯