前言

之前咱们三个同学做了个Simple-SCM,我负责那个Merge模块,也就是对两个不同分支的代码进行合并。当时为了简便起见,遇到文件冲突的时候,就直接按照文件的更改日期来存储,直接把更改日期较新的那个文件认为是我们要保留的文件版本。但是这样子做是存在很多问题的,因为这样做就无法对不同分支的代码他们各自的特性进行整合,最终保留的只是其中一个分支的代码。因此,加入按行进行比较的diff算法是非常必要的。

然后,本着自力更生的理念,我希望能够自己写出这个代码,然后把它应用到Simple-SCM之中。今年五月份的时候就看到了Google开源的diff-match-patch库,这里面提供了完善的diff功能。一看代码量,三千多行,就把这事往后推了。这个开源库里面讲到了,用的就是Myers的论文,我就想,我能不能自己阅读论文,把它复现出来呢?但是由于时间的缘故,就没去搞。毕竟当时是实训大作业要赶ddl嘛,先把软件做出来再说。

到了最近,我又找到了这个库,然后想起了还没有完成的Merge模块,就想着去把它做出来。于是,我说干就干,还深夜发了一条朋友圈,来立一个Flag。

然后我就,真的,抽空把这个论文给看了。并且把它的基础版本给复现了出来!(论文原文请转到文末)

什么是diff?

diff在软件开发过程中非常常见,最直观的就是在git里面,可以查看两个不同版本的代码的区别。得出的数据包括了:新增的、删除的、修改的、没有改变的。

在Github上查看代码版本之间的差异

上面这张图展现的就是在Github上看到的,展现了两个版本的代码之间的差异。红色的表示这段代码在新版中已经被删除了,绿色的表示是新增的,其中,颜色加深部分则是发生改变的。

并且,左边的旧版本代码有很多种方式来变成右边的新版代码。找到一个最符合人类直观反应的diff,也是一个复杂的问题。

Myers的Diff算法的原理

我们如何判断两份代码文件的差异呢?首先我们要认识到它是字符串,换行只是加了换行符而已。因此,从本质上来说,我们要能够判断两个字符串的差异。

这就回归到了我们熟知的最长公共子序列(LCS)问题了,对于LCS问题,在之前我也学过LCS的算法。之前学的基于DP的算法的时间复杂度是O(MN),也就是我们所说的N平方复杂度。对于大量的数据而言,之前的算法速度是很慢的。

编辑图

因此,Myers在论文中引入了编辑图(Edit Graph)的概念。也就是将旧字符串放在x轴,新字符串放在y轴。起点是(0,0),终点是(M,N)。

编辑图

编辑图具有横向边、纵向边以及对角边。这些边都是有向的,只能向右、向下和向右下角。

这三种边有其特定的含义:

  • 横向边:代表删除对应的旧字符串的字符
  • 纵向边:代表从新字符串中插入一个字符到旧串的当前位置中。
  • 对角边:新旧字符串中相同的部分。

然后,我们的目标就是,把旧字符串经过最少、最直观的变换,使其变成新字符串。转换到编辑图上,就是经过最短的、最多连续的一条路径,从(0,0)点走到(M,N)点。也就是SES问题(最短编辑图问题)

由于横向边和纵向边的出现意味着我们对字符串进行了编辑,而对角边则意味着没有编辑这个字符串。因此我们将横向边和纵向边的权值设置为1,对角边的权值设置为0. 那么,这个diff的问题就进一步转化为单源最短路径的问题了。

当时我看到这里,就想着用狄克斯特拉算法来求这个单源最短路径问题了。

但是!千万不要这么做!

(不然这篇文章就结束了)

狄克斯特拉算法确实可以求解SES问题,但是它却不能求解出“最直观”的变换。它求出来的编辑图虽然满足最短路,但是不一定满足“边的最连续”。而且,狄克斯特拉算法哪怕经过了优先级队列的优化,时间复杂度达到了O(ElogE),但是这个仍然比Myers的算法的时间复杂度高。原因在于狄克斯特拉算法在应用到diff问题上时,没有利用到两个字符串的diff的性质。

定义:D-path指的是,横向边纵向边之和为D的路径

因此,0-path指的就是,全为对角边的路径。

如何标记对角边?

由于对角边是与x、y轴都成45°的,因此,我们只要知道其截距k,就能表示任意一条对角边。故有:

x-y=k

我们用k来给对角边编号,那么对角边的编号范围就是[-M,N]

两项引理

引理1:一条D-path的终点必须在对角边k∈[-D, -D+2,…,D-2, D]上

这其实很好理解,经过D次编辑,那么最远就只能到达第±D条对角边。并且由于折返的原因,从最远处,每次缩短一节,对应的对角边的编号就减2.这个画个图可以很好理解。

引理2:这个有点长,我就不翻译了,大家自己看看。

引理2

A furthest reaching 0-path ends at (x,x), where x is min( z−1 || a z ≠bz or z>M or z>N). A furthest reaching D-path on diagonal k can without loss of generality be decomposed into a furthest reaching (D − 1)-path on diagonal k − 1, followed by a horizontal edge, followed by the longest possible snake or it may be decomposed into a furthest reaching (D − 1)-path on diagonal k+1, followed by a vertical edge, followed by the longest possible snake

大概意思就是,d-path可以由(D-1)-path转移而来。这也为我们后面的计算提供了依据。

关于上面两项引理的证明,有兴趣的读者可以查阅论文原文的第五页,即可看到证明。

算法思路

Myers的diff算法是贪心的、使用了动态规划的思想的。我们既然要得到到达点(M,N)的最短路径,设到达点(M,N)的路径长度为D,那就是要先得到众多(D-1)-path,然后从这些备选路径的结束点为起点,计算出到达点(M,N)最直观最短的一条路径,这就是我们要连上去的路径。

因此,我们只需要从0-path开始,迭代的计算1-path,2-path,3-path,…,D-path。这样,我们求到的第一条能到达点(M,N)的路径,就是答案了。也就是我们的编辑路径。我们的diff就找到了。

上面两段讲了一个总体的思路,现在就放论文里面的伪代码上来,让读者更加直观地了解到这个算法的工作流程。

The Greddy LCS/SES Algorithm

上述伪代码中,数组V存储的是D-path在不同的对角边上能到达的最远的顶点的x值。

由于其下标可以是负数,因此我们可以把负下标映射到数组的高地址端,从高地址端向下生长,来实现负下标的功能。

自己的一些感悟

这次借着这个机会,看了英文原版的论文,把算法给复现了出来。算法本身不是特别的难,我觉得在这个过程中,我最大的收获在于,学会了看论文。这个只能说是刚刚会看,真正的对论文的深入思考和批判,我还做不到,这也是我需要提高的。在阅读的过程中,也深刻体会到了,英文的重要性。语言的问题是很大的阅读障碍,这个问题确实得重视。就像我逛GitHub和StackOverflow的时候的感觉一模一样,全英的,机器翻译也超不通顺,看着好辛苦。这个阅读能力真的得不断的提升。

然后,这个算法我目前只是把它复现出了基础版本,后面的线性空间优化还有一些变种,我还没有时间去看,这个也会继续去看,继续更新下去。

然后最初我说,要自己做一个difflib出来,现在想了想,确实不那么容易。因为要按行为单位来计算diff,要得到“原来存在,只是更改了一些”这类信息,还涉及到了相似度的计算的问题。确实不是那么的简单。于是,我决定,还是用Google的开源库来实现Simple-SCM的Merge吧。确实人家造的轮子还是很不错的。我这算是打脸了,我承认我的技术还不行,也没有这么多时间去钻研这个diff,把它做成difflib。这个我以后还要加油,说不定哪天真的能自己写一个了呢?

附件:基础版代码

#include <bits/stdc++.h>

using namespace std;


int get_index(int maxn, int idx) {
    if (idx >= 0)
        return idx;
    else
        return (maxn << 1) + idx;

}

struct Snake {
    Snake() = default;

    Snake(int sx, int sy, int mx, int my, int ex, int ey) {
        start_x = sx;
        start_y = sy;
        mid_x = mx;
        mid_y = my;
        end_x = ex;
        end_y = ey;
    }

    int start_x, start_y, end_x, end_y;
    int mid_x, mid_y;
};

struct point {
    point(int xx, int yy) {
        x = xx, y = yy;
    }

    int x, y;

    bool operator==(const point &p) const {
        if (x == p.x && y == p.y)
            return true;
        else
            return false;
    }

    bool operator!=(const point &p) const {
        if (*this == p)
            return false;
        else
            return true;
    }
};

void MyersDiff(string a, string b) {
    vector<vector<Snake>> ans;

    const int MAXN = a.length() + b.length();
    int *V = new int[2 * MAXN + 1];
    memset(V, 0, sizeof(int) * (2 * MAXN + 1));
    V[1] = 0;
    for (int d = 0; d <= MAXN; ++d) {
        printf("D:%d\n", d);

        vector<Snake> tmp;
        bool flag = false;
        for (int k = -d; k <= d; k += 2) {
            int start_x, start_y;
            bool down = false;
            if (k == -d || (k != d && V[get_index(MAXN, k - 1)] < V[get_index(MAXN, k + 1)]))
                down = true;
                //start_x = V[get_index(MAXN,k+1)];
            else
                down = false;
            //start_x = V[get_index(MAXN,k-1)]+1;

            int kPrev = down ? (k + 1) : (k - 1);

            start_x = V[get_index(MAXN, kPrev)];
            start_y = start_x - kPrev;
            int mid_x = down ? start_x : (start_x + 1);
            int mid_y = mid_x - k;

            int end_x = mid_x, end_y = mid_y;

            int snake = 0;
            while (end_x < a.length() && end_y < b.length() && a[end_x] == b[end_y]) {
                ++end_x;
                ++end_y;
                ++snake;
            }

            V[get_index(MAXN, k)] = end_x;
            tmp.emplace_back(Snake(start_x, start_y, mid_x, mid_y, end_x, end_y));
            printf("start:(%d,%d),  mid:(%d,%d),  end:(%d,%d)\n", start_x, start_y, mid_x, mid_y, end_x, end_y);

            if (end_x >= a.length() && end_y >= b.length()) {
                //found
                printf("Found.\n");
                flag = true;
                break;
            }
        }
        ans.emplace_back(tmp);
        if (flag)
            break;
    }

    delete[] V;
    cout << ans.size() << endl;
    //处理得到路径
    int end_x = a.length(), end_y = b.length();
    stack<point> st;
    for (auto ptr = ans.end() - 1; ptr >= ans.begin(); --ptr) {
        auto tmp = *ptr;
        Snake tmps;
        for (auto p: tmp) {
            if (p.end_x == end_x && p.end_y == end_y) {
                tmps = p;
                auto tmpp = point(p.end_x, end_y);
                if (st.empty() || st.top() != tmpp)
                    st.push(tmpp);

                tmpp = point(p.mid_x, p.mid_y);
                if (st.empty() || st.top() != tmpp)
                    st.push(tmpp);
                end_x = p.start_x, end_y = p.start_y;
                break;
            }
        }
    }

    while (!st.empty()) {
        const auto tmpp = st.top();
        st.pop();
        printf("(%d,%d)==>", tmpp.x, tmpp.y);
    }


    printf("done\n");
}

int main() {

    string a = "XBCAC";
    string b = "ABBAC";
    MyersDiff(a, b);
}

References

EUGENE W. MYERS “An O(ND) Difference Algorithm and Its Variations” https://neil.fraser.name/writing/diff/myers.pdf

转载请注明来源:https://www.longjin666.cn/?p=1233

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论