Google diff-match-patch源代码解析：听说比GNU diff-patch更厉害？（一）

文章目录

前言

GUN diff 与 Google diff-match-patch的区别

最近研究了google工程师开发的计算文本之间差异值的diff算法。该算法可以计算出不同文本之间的差异值并且生成patch文件来体现文本之间的差异。
GNU diff对于diff的计算是基于行的，也就是说如果使用GUN diff来计算两段文本之间的差异，两段文本的某一行绝大多数内容都相同，但是行内的某些字符有轻微的不同之处，那么GUN diff就会直接将其判定为冲突。比如：

第一行：
Google diff-match-patch源代码解析

第二行：
Google diff-patch源代码解析

那么使用GUN diff计算的结果就是：
< Google diff-match-patch源代码解析
---
> Google diff-patch源代码解析

而且使用GUN diff，如果两个文本同时修改了同一行，那么很容易引起冲突；冲突之后会将冲突结果存放入一个文件之中。如果使用基于GUN diff的merge方法，那么会将冲突结果直接写入合并后的文本之中。形如：

<<<<<<< 1.txt
Google diff-match-patch源代码解析=======
Google diff-patch源代码解析>>>>>>> 2.txt

而Google diff-match-patch的优势之处在于，它没有GUN diff这么死板。 Google diff-match-patch的算法是基于字符的，也就是说尽管一行之内有不同，但是Google的算法还是能找到行内的不同之处和相同之处。
还是上面那个例子，如果使用Google diff算法就会出现下面的结果：
在这里插入图片描述
最奇妙的是，Google diff算法还可以根据用户不同的需要进行定制化的diff操作，包括但不限于：

语义化优先的diff计算
效率优先的diff计算（可以设置diff单元的最小粒度）
设置ddl时间的diff计算（在n秒内完成diff计算操作）

如果想体验google diff-match-patch算法，这里提供了一个基于JS实现的在线demo。
另外该算法是开源的，具有多种语言的实现版本（包括但不限于：Java、JS、Python），git仓库在这里。

注释

这篇文章准备分几个部分来写，根据目前的构思，想分为三个部分完成这一篇博文：

diff_match_patch的diff算法是如何实现的？
diff_match_patch如何对生成的diff进行语义上的优化？
如何进一步优化diff_match_patch，以支持对富文本（标签文本）的diff计算？

这是第一篇博文，分析diff_match_patch的diff算法。

diff算法实现——如何定义一系列操作，来将字符串A转换为字符串B？

操作的定义

或许有人记得动态规划算法的教学题——编辑距离。如果想把字符串A转换为字符串B，那么最少需要多少步的操作？
很遗憾这里使用的似乎并不是动态规划算法；但是这两个问题之间有一个很重要的共同点：对于操作的定义。字符串的修改，无非“插入字符”、“删除字符”、“修改字符”。而为了简化操作的种类，“修改字符”可以用“删除字符”和“修改字符”的组合来完成。比如A字符串为aaa，B字符串为aab，从A到B的转换可以是：

将A字符串的最后一位替换为b
将A字符串的最后一位删除；在A字符串的最后一位添加字符`b``

那么Google diff-match-patch算法中是怎么定义操作的呢？

  /**
   * 将操作分为三种枚举类型：Delete，Insert，Equal
   */
  public enum Operation {
    DELETE, INSERT, EQUAL
  }

  public static class Diff {
    /**
     * INSERT, DELETE , EQUAL.这三种枚举操作类型中的一种
     */
    public Operation operation;
    /**
     * 操作的文本内容
     */
    public String text;

	... ...
}

这里定义的三种操作：INSERT， DELETE， EQUAL对应的三种Diff情形，举个例子：
比如，文本AHelloworld 到文本BGoodbyeworld的转换就可以定义为三个Diff：

Diff(Operation.DELETE, “Hello”): delete “Hello” //删除Hello文本
Diff(Operation.INSERT, “Goodbye”): add “Goodbye” //增添Goodbye文本
Diff(Operation.EQUAL, " world."): keep " world." //保持原有的world不变

定义完了操作，基于这个操作集，任意（String A，String B）的转换经过计算，都可以转换为一系列Diff的组合——LinkedList<Diff>：哪里删除了，哪里增加了，哪里没有变。

Diff的计算

其实整个Google diff-match-patch的源代码带上注释有大约2500行（Java实现版本）。但是真正“单纯”的计算Diff的代码只有不到300行。剩下的很多代码其实都是用于后续Diff类转化为文本服务的——为了应对客户对于导出Diff定制化的需求：有的想快速把Diff导出，有的想基于语义导出Diff等等。

这里的导出Diff指的是，将计算出LinkedList<Diff>的重新生成为用户易于理解的Diff文本。

首先，整个进行Diff计算的入口（一上来就利用多态进行两次跳转，如果不进行特殊的参数配置则默认使用下面代码框中的第三段代码）：

  public LinkedList<Diff> diff_main(String text1, String text2) {
    return diff_main(text1, text2, true); // 这里的true暂时可以忽略（跟本篇的关系不大），绝大多数情况下可以直接置为True。
  }


  public LinkedList<Diff> diff_main(String text1, String text2, boolean checklines) {
    ......
    return diff_main(text1, text2, checklines, deadline);
  }

  /**
   * 计算两个文本之间的Diff。 通过给相似的文本“掐头去尾”来简化问题。
   * @param text1 Old string.
   * @param text2 New string.
   * @param checklines Speedup flag.  ......
   * @param deadline Time when the diff should be complete by.  ......
   * @return Linked List of Diff objects.
   */
  private LinkedList<Diff> diff_main(String text1, String text2,
                                     boolean checklines, long deadline) {
    // 检查两个字符串是否为空。如果为空则直接报错，不进行计算。
    if (text1 == null || text2 == null) {
      throw new IllegalArgumentException("Null inputs. (diff_main)");
    }

    // 这里为了计算的效率，先检查两段文本是否相等。如果相等就可以直接返回Diff(EQUAL,...)
    LinkedList<Diff> diffs;
    if (text1.equals(text2)) {
      diffs = new LinkedList<Diff>();
      if (text1.length() != 0) {
        diffs.add(new Diff(Operation.EQUAL, text1));
      }
      return diffs;
    }

    // 找到这两段text的共同的开头部分（从该字符开始相似）掐掉相同的开头部分
    int commonlength = diff_commonPrefix(text1, text2);
    String commonprefix = text1.substring(0, commonlength);
    text1 = text1.substring(commonlength);
    text2 = text2.substring(commonlength);

    // 掐掉相同的结尾部分
    commonlength = diff_commonSuffix(text1, text2);
    String commonsuffix = text1.substring(text1.length() - commonlength);
    text1 = text1.substring(0, text1.length() - commonlength);
    text2 = text2.substring(0, text2.length() - commonlength);

    // 将两段字符串中间完全不同的部分拿去做Diff计算。这里是计算方法的跳转，请看下一段代码框。
    diffs = diff_compute(text1, text2, checklines, deadline);

    // 如果两段文本的开头有重复的部分，那么就将重复的开头转换为Diff(EQUAL, 重复的开头内容)操作留在DiffList的开头。
    if (commonprefix.length() != 0) {
      diffs.addFirst(new Diff(Operation.EQUAL, commonprefix));
    }
    // 如果两段文本的结尾有重复的部分，那么就将重复的开头转换为Diff(EQUAL, 重复的结尾内容)操作留在DiffList的结尾。
    if (commonsuffix.length() != 0) {
      diffs.addLast(new Diff(Operation.EQUAL, commonsuffix));
    }


    diff_cleanupMerge(diffs);
    return diffs;
  }

这一段代码主要目的是为了简化操作：如果两串字符串的像下面这种格式：

A123zxcvb，B123asdfghhjj 开头有相同的一小段
Azxcv123，Bzxcv987 结尾有相同的一小段
A123uuuuuuuuuzxc，B123vvvvvvvvvvvvccccccczxc 开头和结尾都各有相同的一小段

这种A和B字符串，开头或者结尾有重复的部分；那么经过这一步的递归处理，就可以把开头或者结尾的重复字符串筛除，将中间的完全不同的部分拿去做Diff计算。提高了效率也简化了后续Diff计算的操作。也就是把“掐头去尾”之后的两段文本再拿去diff_compute进行计算。

/**
   * 由于调用该方法的父方法对text1和text2进行了“掐头去尾”的处理，
   * 所以这个方法的实现可以假定为：text1和text2的头尾皆没有重复的字符串。
   * 这也就意味着，这个方法返回的Difflist不可能以Diff(EQUAL,...)作为开头或者结尾。
   * @param text1 Old string to be diffed.
   * @param text2 New string to be diffed.
   * @param checklines Speedup flag. ......
   * @param deadline ......
   * @return Linked List of Diff objects.
   */
  private LinkedList<Diff> diff_compute(String text1, String text2,
                                        boolean checklines, long deadline) {
    LinkedList<Diff> diffs = new LinkedList<Diff>();

	/**
	 *	如果其中一段文本经过掐头去尾的操作，已经成了空字符串；
	 *	那么则说明另一段字符串相对于这一串字符串只增不减；那么只需要对于原有的字符串
	 *	进行“添加”或者“删除”的操作就能使两端字符串保持一致。
	 *	比如，A为“asssddd”，B为“addd”；那么掐去重复的头和尾之后，
	 *	A字符串就只剩下“sss”，而B字符串只剩下“”；这时候，只需要把“sss”进行插入操作，
	 *	也就是将“sss”插入到“a”和“ddd”之间就能够完成变换。
	**/
    if (text1.length() == 0) {
      // Diff(INSERT,...)
      diffs.add(new Diff(Operation.INSERT, text2));
      return diffs;
    }
    if (text2.length() == 0) {
      // Diff(DELETE,...)
      diffs.add(new Diff(Operation.DELETE, text1));
      return diffs;
    }


    /** 
     * 上述情况毕竟为偶然；
     * 两段文本区分长短，长的文本记为longtext，短的文本记为shorttext
    **/
    String longtext = text1.length() > text2.length() ? text1 : text2;
    String shorttext = text1.length() > text2.length() ? text2 : text1;
    int i = longtext.indexOf(shorttext);
    /** 
     *  这一步假设，就算两段字符串开头和结尾没有相同的字符；但是长的字符串恰好包含了短的字符串。
     * 比如：
     * 字符串A：“aassssdddfffggg”，字符串B“aadddggg”
     * 掐去重复的头尾之后变成：
     * 字符串A1：“sssdddfff”，字符串B1“ddd”
     * A1恰好是包含B1的！
     * 那么只需要在B1的头和尾分别加上Diff(Insert,...)，中间的部分保持Diff(EQUAL,...)
     * 就可以成功的进行转换！
    **/
    if (i != -1) {
      // Shorter text is inside the longer text (speedup). 这里假设了长文本中包含短文本的场景
      Operation op = (text1.length() > text2.length()) ?
                     Operation.DELETE : Operation.INSERT;
      diffs.add(new Diff(op, longtext.substring(0, i)));
      diffs.add(new Diff(Operation.EQUAL, shorttext));
      diffs.add(new Diff(op, longtext.substring(i + shorttext.length())));
      return diffs;
    }

    /**
     *  这里列举了短字符串只剩下一个字符的情况。经过上面两个If的假设，
     * 该字符串不可能被包含在长字符串之中。那么要进行转换，就是将该字符串替换为该字符即可。
     * 替换对应的操作为一次Diff(INSERT,...)和一次Diff(DELETE,...)
    **/
    if (shorttext.length() == 1) {
      diffs.add(new Diff(Operation.DELETE, text1));
      diffs.add(new Diff(Operation.INSERT, text2));
      return diffs;
    }

	/**
	 * 还有最后一种情况：
	 * 两个字符串，虽然头尾没有共同的部分，但是它们包含着相同的子串。
	 * 
	 * 下面的diff_halfMatch()方法用来计算两段文本中是否存在相同的子串。
	 * 返回值为一个String[]数组，该数组长度为5:
	 * 1. the prefix of text1,  text1的相同段的前缀
     * 2. the suffix of text1,  text1的相同段的后缀
     * 3. the prefix of text2,  text2的相同段的前缀
     * 4. the suffix of text2,  text2的相同段的后缀
     * 5. the common middle.  text1和text2中间的相同段。如果text1和text2中根本就没有相同的字段，
     * 那么这个值为null。
	 **/
    String[] hm = diff_halfMatch(text1, text2);
    // 如果两个字符串含有相同的子串（一串或者多串）
    if (hm != null) {
      // A half-match was found, sort out the return data.
      // text1_a: text1的相同段的前缀
      String text1_a = hm[0];
      // text1_b: text1的相同段的后缀
      String text1_b = hm[1];
      // text2_a: text2的相同段的前缀
      String text2_a = hm[2];
      // text2_b: text2的相同段的后缀
      String text2_b = hm[3];
      // mid_common: text1和text2中间的相同段。如果text1和text2中根本就没有相同的字段，那么这个值为null。
      String mid_common = hm[4];
      
      // 对text1的相同段的前缀、text2的相同段的前缀进行Diff计算（递归）
      LinkedList<Diff> diffs_a = diff_main(text1_a, text2_a,
                                           checklines, deadline);
      // 对text1的相同段的后缀、text2的相同段的后缀进行Diff计算（递归）                                      
      LinkedList<Diff> diffs_b = diff_main(text1_b, text2_b,
                                           checklines, deadline);
      // 将Diff的结果进行合并
      diffs = diffs_a;
      diffs.add(new Diff(Operation.EQUAL, mid_common));
      diffs.addAll(diffs_b);
      return diffs;
    }

	// 下面这些是为了整合Diff，本篇范围内不用看这些。
    if (checklines && text1.length() > 100 && text2.length() > 100) {
      return diff_lineMode(text1, text2, deadline);
    }

    return diff_bisect(text1, text2, deadline);
  }

在这个函数内，列举了两个开头和结尾没有重复部分的字符串可能遇到的所有情形：

其中某个字符串长度为0
其中某个字符串只剩下最后一位（长度为1，可以直接进行替换）
两个字符串中，长的那个字符串恰好包含了短的那个字符串。
两个字符串恰好享有子字符串。（提取出相同的子字符串之后进行递归操作）

然后针对上述情况，分别进行分析和处理，得到最终的Difflist结果。这个算法本质上也是一种对于情形的穷举，不得不说Google工程师的逻辑是真的缜密……设计也非常的精巧。换成我写这段逻辑怕不是药丸。

最后，欢迎大家讨论、转发、交流。转载须注明出处。下一篇中会对Difflist的导出（文档化）部分的代码进行分析。

参考博客

实时协同编辑的实现 - FEX
google-diff-match-patch文本内容对比的使用

原文链接：https://blog.csdn.net/APPTITE/article/details/107691493