迈尔斯差分算法--代码与交互式可视化

     Below you will find example source code and interactive visualizations that are intended to complement the paper 'An O(ND) Difference Algorithm and Its Variations' by Eugene W. Myers[1].  Multiple variants of the algorithms discussed in Myers' paper are presented in this article, along with working source code versions of the pseudo-code presented in the paper.

下面你会发现源代码和交互式可视化的例子，这些例子旨在补充Eugene W. Myers[1]的论文 "An O(ND) Difference Algorithm and Its Variations"。 本文介绍了Myers论文中讨论的算法的多种变体，以及论文中提出的伪代码的工作源代码版本。

     Two refinements to the linear-space Myers algorithm are also discussed.  These refinements reduce the memory requirements of the classical algorithm from O(len(a) + len(b)) to O(min(len(a),len(b))), and the worst-case execution-time requirements from O((len(a) + len(b)) * D) to O(min(len(a),len(b)) * D).  Finally, a proof-of-concept patch for GNU diffutils is included that produces slower execution for many typical use cases, but is asymptotically superior as the size difference between the files grows arbitrarily large when calculating the minimum edit difference.

我们还讨论了对线性空间迈尔斯算法的两个改进。 这些改进将经典算法的内存需求从O(len(a) + len(b))减少到O(min(len(a),len(b)))，将最坏情况下的执行时间需求从O((len(a) + len(b))* D）到O(min(len(a),len(b))* D). 最后，包括一个GNU diffutils的概念证明补丁，在许多典型的使用情况下会产生较慢的执行速度，但在计算最小编辑差异时，随着文件之间的大小差异的任意增长，会有渐进式的优势。

Linear Space Myers Diff Algorithm Python Code

线性空间迈尔斯差分算法 Python代码

def diff(e, f, i=0, j=0): N,M,L,Z = len(e),len(f),len(e)+len(f),2*min(len(e),len(f))+2 if N > 0 and M > 0: w,g,p = N-M,[0]*Z,[0]*Z for h in range(0, (L//2+(L%2!=0))+1): for r in range(0, 2): c,d,o,m = (g,p,1,1) if r==0 else (p,g,0,-1) for k in range(-(h-2*max(0,h-M)), h-2*max(0,h-N)+1, 2): a = c[(k+1)%Z] if (k==-h or k!=h and c[(k-1)%Z]<c[(k+1)%Z]) else c[(k-1)%Z]+1 b = a-k s,t = a,b while a<N and b<M and e[(1-o)*N+m*a+(o-1)]==f[(1-o)*M+m*b+(o-1)]: a,b = a+1,b+1 c[k%Z],z=a,-(k-w) if L%2==o and z>=-(h-o) and z<=h-o and c[k%Z]+d[z%Z] >= N: D,x,y,u,v = (2*h-1,s,t,a,b) if o==1 else (2*h,N-a,M-b,N-s,M-t) if D > 1 or (x != u and y != v): r...