迈尔斯的差异：为什么V [k − 1]< V [k + 1]是否保证选择其他D路径？ [英] Myers' diff: Why V[k − 1] < V[k + 1] guarantee to choose the further D-path?

问题描述

作为论文中的伪代码

  4。如果k ＝ -D或k≠D，并且V [k-1] ＜。 V [k + 1]然后
 5. x←V [k + 1] 
 6.其他
 7. x←V [k − 1] +1 
 8。 y←x − k 
  

第4行表明，如果k不是-D或D，则取x大于发现蛇的那一个。这让我感到困惑，我不应该同时计算v [k-1]和v [k + 1]并找出哪个路径更远吗？如果我选择一个较大的x作为起点，而事实证明我们的观点会引向更远的方向呢？

此外，据此：

即，进一步到达（x'，y'+ 1）和（x + 1，y）在对角线
中，然后跟随对角线边缘，直到不再可能
这样做或直到到达编辑图的边界为止。

我认为作者建议（x'，y'+ 1）和（x + 1，y）（在这种情况下，v [k- 1]和v [k + 1]）应该计算出来。

所以我有什么想法吗？

解决方案

我认为论文缺少证明，这很简单，但是我认为缺失会导致某些混乱（对我而言），因此在此提供此证明：

在第6页第4行中，代码如下：

  fk ＝ -D或k≠D并且V [k-1] ＜f。 V [k + 1]然后
x←V [k + 1] 
其他
x←V [k − 1] +1 
  给出对角线k + 1和k-1中最远到达（D − 1）路径的端点，例如（x'，y'）和（x，y）
，引理2给出了计算对角线k中最远到达D路径的端点的过程。 
即，在对角线k中进一步到达（x'，y'+ 1）和（x + 1，y），然后沿着对角线边缘直到
不再可能做因此，直到到达编辑图的边界为止。通常的方法是获取从 v [k-1] 和 v [k + 1] 并找出哪一条是更进一步的覆盖途径。但这将导致双重批评。这就是为什么只检查 V [k − 1]< V [k + 1] 的工作原理：
 
 
 
 lemma4：如果 v [k-1]< 
 ; v [k + 1] ，然后带有蛇形垂直边缘的 v [k + 1] 后面的路径将是重新布置的路径
 
 
 
证明：
让 v [k-1] 到 x1 和 v [k +1] 到 x2 。因此对角线k上紧跟 x1 的点是（x1 + 1，x1 + 1-k）（向右），后跟 x2 的点是（x2，x2-k）（下移）； y位置在这里没有用。 
，然后问题变为：如果x1< x2，然后x1 +1 <= x2  
因为 x1< x2-> x2-x1> 0  
假定 x1 + 1> x2 ，然后 x2-x1< 1 ，因此 0< x2-x1< 1 。但是在编辑图中，基本移动为1， 0< x2-x1< 1 永远不会发生，因此假设是错误的，因此 x1 + 1 <= x2 。 
 
 
 
我在 https://github.com/psionic12/Myers-Diff-in-c-/blob/master/README.md ，欢迎您讨论。 
 
As the pseudo code in the paper
4. If k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
5. x ← V[k + 1]
6. Else
7. x ← V[k − 1]+1
8. y ← x − k
the line 4 indicate that if k is not -D or D, than take the one which has a greater x, than find out the snake. This confused me, shouldn't I calculate both v[k-1] and v[k+1] and find out which path is further? What if I chose the one with bigger x as start point, while turns out that the our point will lead to a further path?

And what's more, according to this:

  
Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in
  diagonal k and then follow diagonal edges until it is no longer
  possible to do so or until the boundary of the edit graph is reached.
I think the author suggest that both (x’,y’+1) and (x"+1,y") (in this case, the v[k-1] and v[k+1]) should be calculate.

So any idea what I'm missing?
解决方案
I think the paper missed a proof, which is very simple, but I think the missing will lead to some confusion (for me), so I gives this proof here:

in page 6, line 4, the code is as below:
 f k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
    x ← V[k + 1]
 Else
    x ← V[k − 1]+1
I don't think lemma2 will lead to this, the purpose of lemma2 is to proof this problem can be solved with a greedy strategy. And according to Given the endpoints of the furthest reaching (D − 1)-paths in diagonal k+1 and k−1, say (x’,y’) and (x",y")
respectively, Lemma 2 gives a procedure for computing the endpoint of the furthest reaching D-path in diagonal k.
Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in diagonal k and then follow diagonal edges until it is
no longer possible to do so or until the boundary of the edit graph is reached. The normal way is to get both points which extends from v[k - 1] and v[k + 1] and figure out which is a further reach path. But this will lead a double-culculate. Here's proof why only check V[k − 1] < V[k + 1] works:

lemma4:
if v[k - 1] < v[k + 1], then path followed by v[k + 1] with a vertical edge with a snake will be the further rearched path in diagonal k.

proof:
let's make v[k - 1] to x1 and v[k + 1] to x2. so the point followed by x1 in diagonal k is (x1 + 1, x1 + 1 - k)(go right), the point followed by x2 is (x2, x2 - k)(go down); the y position is useless here.
then the problem changes to: if x1 < x2, then x1 + 1 <= x2
since x1 < x2 -> x2 - x1 > 0
assume that x1 + 1 > x2, then x2 - x1 < 1, so 0 < x2 - x1 < 1. But in edit graph, the basic move is 1, the 0 < x2 - x1 < 1 will never happen, so the assumption is wrong, so x1 + 1 <= x2.  

I'v post this and a implementation on https://github.com/psionic12/Myers-Diff-in-c-/blob/master/README.md, you are welcome to discuss.

                        
这篇关于迈尔斯的差异：为什么V [k − 1]&lt; V [k + 1]是否保证选择其他D路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！