This should’ve been the first of the series “Fantastic Failures”, b/c it feels this way. But the only failure is me unable to Google and filter for the Hunt-McIlroy algorithm, before I got frustrated and tried to free-lance write the algorithm from a short description I read about years ago. Only after I was done, did I discover the Hunt-McIlroy algorithm, in a dusty corner of Internet. And it is so much simpler, than my concoction.

This was 3 days later. I thought it would take 3 hours. I did not use the above algorithms (b/c I’m a man and my mansplain is I refuse to read instructions that I can’t cut and paste). I did find a cut and paste solution but until days later. However, my loss in time, I will pass on, of my understanding of the diff algorithm.

TLDR

If you ever want to know how Unix GNU diff, or Windows Windiff works, I think I have a demo, based on a article I read a few years ago. I free-lanced wrote the demo, based on my understanding of the idea. Because I wanted a Javascript version.

But the version I found on internet is simpler and better. You can download my copy of the Hunt-McIlroy Algorithm here. Then use this code snippet, to use it.

<script src="hunt-mcilroy.js"></script>
<script>
function rediff(){
  const a = document.all['a'].value.split("\n");
  const b = document.all['b'].value.split("\n");
  const out = diff(a, b);
  console.log(a);
  console.log(b);
  console.log(out);
  var texta=null;
  var textb=null;
  var textd=null;
  var len=null;
  const re = document.all['result'];
  re.innerHTML="";
  for(var i=0; i<out.length; i++){
          const data=out[i];
          if(data.common) {
              len=data.common.length;
              texta=data.common;
              textb=data.common;
              textd="Same";
          } else if(data.file1) {
              len=data.file1.length;
              texta=data.file1;
              textb=[];
              textd="Del";
          }
          for(var j=0; j<len; j++){
              const row = re.insertRow(-1);
              const lineA = row.insertCell(0);
              const lineD = row.insertCell(1);
              const lineB = row.insertCell(2);
              lineA.innerHTML = texta[j] ? texta[j] : "";
              lineB.innerHTML = textb[j] ? textb[j] : "";
              lineD.innerHTML = textd;
              lineD.noWrap = true;
              lineD.style.paddingRight = "10px";
          }
          if(data.file2) {
              len=data.file2.length;
              texta=[];
              textb=data.file2;
              textd="Add";
          } else
              len=0;
          for(var j=0; j<len; j++){
              const row = re.insertRow(-1);
              const lineA = row.insertCell(0);
              const lineD = row.insertCell(1);
              const lineB = row.insertCell(2);
              lineA.innerHTML = texta[j] ? texta[j] : "";
              lineB.innerHTML = textb[j] ? textb[j] : "";
              lineD.innerHTML = textd;
              lineD.noWrap = true;
              lineD.style.paddingRight = "10px";
          }
  }
}
</script>
<table width="100%" cellpadding=0 style="font-size:8pt">
<tr><td><textarea id="a" 
            placeholder="Enter text for A" 
            rows="15" style="width:100%" 
            onchange="rediff()"></textarea></td>
<td><textarea id="b" 
            placeholder="Enter text for B" 
            rows="15" style="width:100%" 
            onchange="rediff()"></textarea>
</table>
<table id="result">
</table>

Failure, just made me understand what Hunt-McIlroy does

Hunt-McIlroy's simplicity, just hides a lot of meaning, that you don't get the taste of, by just copying the recipe. And not varying it, or trying to recreate it.

1. You just need to keep track of matches between the two files. This limits data we have to hold.
2. Matches between the two files, must be grouped into pairs, as they occur, and matches are not re-used. This further prunes the above data we have to search for.
3. Only the path to next match pair matters, from the current match location. You do not need to worry about other paths to other matches being more optimal. There is no such thing. So only one path is considered.

Those 3 assumptions, make the algorithm much faster than searching algorithm, like mine all are.

Basic Idea, of how to display differences between 2 files

First, if 2 files are different, you can show the files side by side and say "They are different". A bad algorithm, will do exactly what I said, and put the 2 files next to each other and say "Different". But we want an algorithm, that picks out the specific details that are different.

I will dub my algorithm the Tictawf Diff Algorithm. It was inspired by description of diff, I read a long time ago, which was - (summarized) diff is to find the shortest path, in a MxN grid whose dimensions represent the lines in files M and N, and whose cells are marked which lines 2 files is the same.

Visually, we need to find the shortest path from beginning of both files, to end of both files, gobbling up matching lines. This depicted metaphorically in the demo grid below, where you need to find a path from upper-left corner(beginning of both files), to lower-right corner(end of both files).

The clearest result, clusters the same matching text together, and clusters the changed texts together, and doesn't reflect matching text as changed text.

Once you understand how to produce a report of differences between 2 text files, using the metaphor in live demo above, you will start to realize that organizing certain paths, are clearer and has fewer lines. This is what diff algorithms try to accomplish. Below, I will explain my path to understanding how a heuristic group of rules, tries to recreate above. And then you realize that Hut-McIlroy algorithm has the simplest set of rules, and the fewest to produce the best result.

My failures at recreating diff from scratch

There are 3 revisions Tictawf Diff Algorithm, based on what I thought was a pathing problem. They are below.

Revision 1 of TictAwf.Diff
http://100.24.142.145/teach-diff.html

I went with 2 passes, but you can do it, in 1 pass. But two passes makes it easy to understand.

Step 1. Compare both files, and index where the lines match and don't. I stored this in 2d array. One dimension was number of lines in 1 file. And 2nd dimension was the number of lines in the 2nd file. Build the entire grid, based on whether the line in the file, indicated by the index of the dimension, matches, and store true/false.

You can subdivide using any criteria you wish, such as by byte, or word, or by token. But most diff programs divide the files by line. It is also easier to visualize.

Line 1. We the People of the United States, 
Line 2. in Order to 
Line 3. form a more perfect Union, 
Line 4. establish 
Line 5. Justice, 
Line 6. insure domestic Tranquility, 
Line 7. provide for the common defence, 
Line 8. promote the general Welfare, 
Line 9. and secure the Blessings of Liberty to ourselves 
Line 10. and our Posterity, 
Line 11. do ordain and establish this Constitution for the United States of America.
  

Line 1. We the People of the United States, 
Line 2. in Order to 
Line 3. (to make a united country), 
Line 4. establish 
Line 5. (fairness for all), 
Line 6. (keep the peace at home), 
Line 7. (protect the nation from threats to it), 
Line 8. (make good lies for people, providing happiness),
Line 9. and secure the Blessings of Liberty to ourselves 
Line 10. and (keep freedom a part of the lives of future generations) , 
Line 11. do ordain and establish this Constitution for the United States of America
Line 12. in Order to 
Line 13. Amen
  

Step 2. Find the path of least cost from (0,0) to (end1,end2). Rules are simple. Moving diagonally (+1,+1) from true to true, is zero cost. Moving (+1,0) or (0,+1) is cost 1. Those are the only 3 movement allowed. Find the path of least cost.

Purpose of Step 2 is to arrange similarities between the two files, and establish relationships between them. What the program is doing, is thinking like a computer. It assumes you want to see the differences, but a computer program finds matches easier. So it is a game of mutual exclusion for the computer program, whatever isn't a match, is a difference. The question then becomes, how to represent this to a human, that he can understand. The metaphor the computer tries to recreate, is - what is the least changes need to be made to File A, to make it File B. This computer program does this by finding path using only the moves described at the begining of step2 section, from the top of the envelope, to the bottom of the envelope, including the most matches. The rules are there to prevent repeats, or representing the data in both files out of order.

Once, the rules are clear, this is the step, that leaves the most to interpretation - How to find the path. I will call this revision 1, the hunt and peck method of path searching. But since I am so clever, I noticed that most text that changed only a few lines, and decided to have the program hunt and peck diagonally, not knowing it makes no difference once you enhance the algorithm later.

Step 3: Each movement in the path of least cost has an interpretation: (+1,+1) means next 1 lines from both files are same, (+1,0) means next 1 line in first file is extra in first file that doesn't exist in 2nd file (or interpreted as they were deleted from first file, to result in the second file), and (0,+1) means next 1 line in second file is extra in second file that doesn't exist in the first file (or interpreted as they were added to first file, to result in the second file). There is no such thing as "changing" a line. If it was changed, the interpretation is that the line was removed, and a different version added.

Step 4. Show each file, and interpretation assigned to that line.

Now replace in the table above, the not-ignored lines, with the actual lines from the file, and you should get the below.

--------- Added 4/12/2014-----------

The version1 of program kept searching same paths again and again. So I added code, to save results from paths that had already been searched

Version2
http://100.24.142.145/teach-diff.dynamicprog.html

Step 1. Same...

Except there are many language structures, that create repetitions. And repetition make the pathing, very much unclear. As a result, it results in more searching. Plus length of the files makes a dramatic degradation in execution time. So to make it useful, some improvements have to be made.

Take for instance the lyrics below, which is both longer than the previous example, and has repetitive sections.

Work, work, work, work, work, work
He said me haffi work, work, work, work, work, work
He see me do mi dirt, dirt, dirt, dirt, dirt, dirt
So me put in work, work, work, work, work, work
When you ah gon' learn, learn, learn, learn, learn?
Me nuh care if him hurt, hurt, hurt, hurt, hurting
Dry, me ah desert him
No time to have you lurking
Him ah go act like he nuh like it
You know I dealt with you the nicest
Nuh body touch me you nuh righteous
Nuh badda, text me in a crisis
I believed all of your dreams, adoration
You took my heart and my keys and my patience
You took my heart on my sleeve for decoration
You mistaken my love I brought for you for foundation
All that I wanted from you was to give me
Something that I never had
Something that you've never seen
Something that you've never been, mm
But I wake up and act like nothing's wrong
Just get ready fi work, work, work, work, work, work
He said me haffi work, work, work, work, work, work
He see me do mi dirt, dirt, dirt, dirt, dirt, dirt
So me put in work, work, work, work, work, work
Na, na, na, na, na, na
When you ah gon' learn, learn, learn, learn, learn, learn?
Before the tables turn, turn, turn, turn, turn, turn
Beg you something, please
Baby don't you leave
Don't leave me stuck here in the streets, uh huh
If I get another chance to
I will never, no never neglect you
I mean who am I to hold your past against you?
I just hope that it gets to you
I hope that you see this through
I hope that you see this true
What can I say?
Please recognize I'm tryin', babe
I haffi work, work, work, work, work, work
He said me haffi work, work, work, work, work, work
He see me do mi dirt, dirt, dirt, dirt, dirt, dirt
So me put in work, work, work, work, work, work
When you ah gon' learn, learn, learn, learn, learn
Me nuh care if him hurt, hurt, hurt, hurt, hurting
Yeah, okay
You need to get done, done, done, done at work, come over
We just need to slow the motion
Don't give that away to no one
Long distance, I need you
When I see potential I just gotta see it through
If you had a twin, I would still choose you
I don't wanna rush into it, if it's too soon
But I know you need to get done, done, done, done
If you come over
Sorry if I'm way less friendly
I got niggas tryna end me, oh, yeah
I spilled all my emotions tonight, I'm sorry
Rollin', rollin', rollin', rollin', rollin'
How many more shots until you're rollin'?
We just need a face to face
You could pick the time and the place
You spent some time away
Now you need to forward
And give me all the work, work, work, work, work, work
He said me haffi work, work, work, work, work, work
He see me do mi dirt, dirt, dirt, dirt, dirt, dirt
So me put in work, work, work, work, work, work
When you ah gon' learn, learn, learn, learn, learn
Me nuh care if him hurt, hurt, hurt, hurt, hurting
Mm
Mm
Work, work, work, work, work, work
Mm

Compare that to itself, and you still get .

BUT since the files are identical, AND my first program searches the diagonals first, the first result indicates a cost of zero. And trying any other path, creates a cost, and it will terminate the search early.

HOWEVER, for the files that are not the same, and has many repeating lines within the same file, that is repeated in the other file, this will produce a lot of possible paths with similar costing. Unfortunately, along with the increased size of the file, this will result in many more evaluations. And if you look closely, the cells closer to lower right, get re-evaluated over and over again, when the algorithm returns to evaluating the unevaluated cells in upper-left.

Step 2. Same...

Except... for more than 1 solution, the first program tends to search for the same matching lines, in the same place. Optimizations can be added, assuming that from any matched lines, anywhere in the grid, to get to the bottom-right of envelope, is always the same. Code was added to save the results of any pathing requested from that matching line, to the bottom of envelope. So when pathing is done, starting from cells in upper-left, that will eventually reach the already evaluated match, it can respond with it's already saved pathing to the lower-right corner. This assumes that saving redundant steps, are more expensive than memory recall, which it is almost always, but not always. I believe this technique was referred to as "dynamic programming" (but I think it is a bad name for it).

Step 3: (Same as for revision 1)

Step 4. (Same as for revision 1)

--------- Added 4/14/2014-----------

The previous programs naively searched for paths (the red blocks), one cell at a time. BUT we actually already know all the possible paths, from pass 1. And since it is a 2d graph, we should be able to represent the line matches as vertices, using the match positions as coordinates, and using our already established rules to create a cost between those coordinates. Then use a spanning tree to construct the most relevant and shortest paths between the line matches. We are cutting out searching for red blocks, and replacing it with a spanning tree, and then searching it, for the path from top left of envelope, to bottom-right of envelope.

Revision 3

http://100.24.142.145/teach-diff.spantree.html

Step 1. Same...

Except when we build the grid, we are replacing it with building a graph. But everywhere we created a match in the grid, we now save in a table.

So where these 2 files...

{
"departureStopName":
    "Metrotown Station @ Bay 4",
"departureStopCoor":
    {
"latitude":
    49.225794,
"longitude":
    -123.002518
},
"departureTime":
    [
2102,
2107,
2119,
2139,
2159,
2227,
2257,
2330
],
"departureTime":
    [
"9:02 PM",
"9:07 PM",
"9:19 PM",
"9:39 PM",
"9:59 PM",
"10:27 PM",
"10:57 PM",
"11:30 PM"
],
"departureTZ":
    "America/Vancouver",
"transitID":
    "TransLink",
"transitLine":
    "130",
"transitType":
    "BUS"
}
  

{
"departureStopName":
    "Metrotown Station @ Bay 4",
"departureStopCoor":
    {
"latitude":
    49.225794,
"longitude":
    -123.002518
},
"departureTime":
    [
2119,
2257,
2330,
2429
],
"departureTime":
    [
"9:19 PM",
"10:57 PM",
"11:30 PM",
"12:29 AM"
],
"departureTZ":
    "America/Vancouver",
"transitID":
    "TransLink",
"transitLine":
    "130",
"transitType":
    "BUS"
}
  

...used to produce this grid (I even added lines, so you can visualize a graph).
it is now changed into a graph, represented by only saving the points. And the point positions, are where 2 lines match, where the position in the files are. Just like their position in the grid.