Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#
Article

A word-wise HTML text compare and merge engine

Rate me:
Please Sign up or sign in to vote.
4.98/5 (31 votes)
27 Aug 20053 min read 113.3K   1.6K   40   33
A C# .NET implemntation of HTML text compare and merge engine based on a similar algorithm as the Unix diff.

Introduction

The initial motivation for writing this code was to compare the staging version with the current production version of the HTML document inside RainbowPortal when workflow is turned on, in order to provide a way for editor and/or approver to visually compare what is modified. The code is not published in RainbowPortal.

After some research, I chose to use the algorithm proposed by Eugene W. Myers in his paper "An O(ND) Difference Algorithm and its Variation" which is also the algorithm used by Unix Diff. A copy of the file can be found here.

The Unix Diff implementation found here is referenced during the implementation.

Design

The overall requirement can be summarized briefly as:

  1. The to-be-compared is HTML text which may contain HTML tags, HTML comments, whitespaces, and special characters such as " " "&#123" etc.
  2. The documents should be compared as a whole instead of line by line.
  3. Only the differences of content of the document is of importance because the formatting is already visually displayed.
  4. The differences should be highlighted.

Since it is going to be document-wise comparison, for the sake of performance and also convenience for only comparing the content of the documents, I decided to compare the document word by word instead of character by character. Thus, the process can be split into two parts. The first one is to parse the document to find out the tags, natural words, punctuations, special characters and whitespaces etc. The second part is to compare the words, punctuations and some of the special characters to find out the differences. Since the ignored things during the comparison are still needed for reconstructing the document, they must be retained by associating them with the words they are adjacent to.

A class Word is defined to represent the parsed word as well as the tags, whitespaces, and special characters before and after it. The definition of class Word is like:

C#
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){...}
}

The parsing follows the following rules:

  1. Anything starting with '<' and ending with '>' is treated as an HTML tag.
  2. HTML tags and whitespaces are treated as prefix or suffix to adjacent words and are put in the prefix or suffix fields of the Word object.
  3. English words separated by space(s), "&nbsp;", "&#xxx", tailing punctuation are treated as words and are put in the word field of the Word class.
  4. Whitespaces == {' ', '\t', '\n'}.

A strong typed collection WordsCollection is also defined to hold the parsed words.

The class HtmlTextParser is defined with one static method to do the parsing.

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

Finally, class Merger is defined to do the dirty work of comparing and merging:

C#
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(){...}
}

The constructor of Merger class will take in the HTML text strings and call HtmlTextParser.parse() to parse them into two word collections. When the public method merge() is called, it constructs Sequence objects from the collections and call the private method doMerge(), and doMerge will recursively compare and merge the whole collections.

The engine and the test code are separated into two projects. In the test/bin/release directory, there are old.html and new.html files, running the test program will generate a file called merged.html. Use the browser to test them.

Conclusion

When the HTML document has about 170 pages with about 50% modifications, the engine takes about 15 seconds to parse, compare and merge the two files. If the document's length is less than 10 pages, it takes less than 1-2 seconds. The compared result is tested to be very accurate.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
Canada Canada
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralDownload still not available Pin
Gareth Brown28-Aug-05 2:37
Gareth Brown28-Aug-05 2:37 
GeneralRe: Download still not available Pin
Hongwei Shen28-Aug-05 8:35
Hongwei Shen28-Aug-05 8:35 
GeneralRe: Download still not available Pin
Bimmelibimmbimmbimm31-Aug-05 1:17
Bimmelibimmbimmbimm31-Aug-05 1:17 
GeneralRe: Download still not available Pin
Anonymous31-Aug-05 3:12
Anonymous31-Aug-05 3:12 
GeneralRe: Download still not available Pin
Hongwei Shen31-Aug-05 3:32
Hongwei Shen31-Aug-05 3:32 
GeneralRe: Download still not available Pin
Bimmelibimmbimmbimm31-Aug-05 4:01
Bimmelibimmbimmbimm31-Aug-05 4:01 
Generaldownload failed. Pin
Huisheng Chen27-Aug-05 5:55
Huisheng Chen27-Aug-05 5:55 
General[Message Deleted] Pin
Hongwei Shen28-Aug-05 8:37
Hongwei Shen28-Aug-05 8:37 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.