逐字 HTML 文本比较和合并引擎

• 下载源代码文件 - 38.4 Kb

引言

编写此代码的最初动机是为了比较RainbowPortal内部HTML文档的暂存版本和当前生产版本，当工作流开启时，以便为编辑者和/或审批者提供一种可视化比较修改内容的方式。该代码未在RainbowPortal中发布。

经过一些研究，我选择使用Eugene W. Myers在他的论文“An O(ND) Difference Algorithm and its Variation”中提出的算法，这也是Unix Diff使用的算法。该文件的副本可以在这里找到。

在实现过程中参考了这里找到的Unix Diff实现。

设计

总体要求可以简要概括为：

1. 要比较的是HTML文本，它可能包含HTML标签、HTML注释、空格和特殊字符，例如“ ”“&#123”等。
2. 应该将文档作为一个整体进行比较，而不是逐行比较。
3. 只有文档内容的差异才重要，因为格式已经以可视方式显示。
4. 应该突出显示差异。

由于这将是文档级别的比较，为了性能以及仅比较文档内容的方便性，我决定逐字而不是逐字符地比较文档。因此，该过程可以分为两个部分。第一部分是解析文档以找出标签、自然词、标点符号、特殊字符和空格等。第二部分是比较单词、标点符号和一些特殊字符以找出差异。由于比较过程中忽略的内容仍然需要用于重建文档，因此必须通过将它们与相邻的单词相关联来保留它们。

定义一个类Word来表示解析后的单词以及它之前和之后的标签、空格和特殊字符。类Word的定义如下：

internal class Word : IComparable
{
    private string _word = string.Empty;
    private string _prefix = string.Empty;
    private string _suffix = string.Empty;
    public Word() {...}
    public Word(string word, string prefix, string suffix) {...}
    ...
    // for reconstructing the word with no change  
public string reconstruct(){...} 
    // for reconstructing the word that is changed
public string reconstruct(string beginTag, string endTag){...}
    public int CompareTo(object obj){...}
}

解析遵循以下规则：

1. 任何以“<”开头并以“>”结尾的内容都被视为HTML标签。
2. HTML标签和空格被视为相邻单词的前缀或后缀，并放置在Word对象的前缀或后缀字段中。
3. 以空格、“&nbsp;”、“&#xxx”、尾随标点符号分隔的英文单词被视为单词，并放置在Word类的word字段中。
4. 空格 == {' ', '\t', '\n'}。

还定义了一个强类型集合WordsCollection来保存解析后的单词。

定义了类HtmlTextParser，其中包含一个静态方法来执行解析。

internal class HtmlTextParser
{
  static public WordsCollection parse(string s) {...}
}

最后，定义了类Merger来完成比较和合并的繁重工作。

class Merger
{
  private WordsCollection _original;
  private WordsCollection _modified;
  private IntVector fwdVector;
  private IntVector bwdVector;
  public Merger(string original, string modified){ ..}
  ...
  private MiddleSnake findMiddleSnake(Sequence src, Sequence des){...} 

  private string doMerge(Sequence src, Sequence des){...}
  ...
  public string merge(){...}
}

Merger类的构造函数将接收HTML文本字符串，并调用HtmlTextParser.parse()将它们解析为两个单词集合。当公共方法merge()被调用时，它会从集合中构造Sequence对象，并调用私有方法doMerge()，而doMerge将递归地比较和合并整个集合。

引擎和测试代码被分离为两个项目。在test/bin/release目录下，有old.html和new.html文件，运行测试程序将生成一个名为merged.html的文件。使用浏览器测试它们。

结论

当HTML文档大约有170页，修改比例约为50%时，引擎大约需要15秒来解析、比较和合并这两个文件。如果文档长度小于10页，则需要不到1-2秒。比较结果经过测试非常准确。