Posts tagged "algorithms"

Diff Library for ActionScript

I was working on an interesting automation project here at Adobe recently. In short, we wanted to have a utility that shows a particular set of configurations and settings on our various servers and indicates to us if any of the servers are different from the rest, configuration-wise. Sounds simple, right? Sure! So, I thought it would be cool to enhance this a bit and instead of just indicating that yes, there is a difference, I would indicate exactly what that difference was.

Since I’m working predominately with text files, the first thing that came to mind was a diff algorithm. (D’uh!) The front-end for the tool that we use is built in Flex, and so I started looking for a diff algorithm implementation in ActionScript. No luck. Guess I’ll have to write my own :\ I started doing some research on the various approaches to diff algorithms and came to the consensus that the Myer’s diff algorithm[1] is widely accepted as the best general-purpose diff algorithm around. After about 6 pages into the research paper, though, I realized it would take too long to grok this all and implement it from scratch. So, instead, I found an implementation of the Myer’s diff algorithm and ported it to ActionScript. A few hours later, it was done!

As you can tell from the example above, text additions are green, and omissions are red. Any text that is the same remains black. And that’s it!

The usage is quite straightforward, too. There is really only one API, diff(), and it takes two parameters, the before-text and after-text. Done!

var diffs:Array = new Diff().diff(beforeText.text, afterText.text);

The result that you get back is an Array of the different operations that it took to go from the original string to the modified string. You can easily use this to display the differences in whatever way you want!

The code is too long to post here, but you can find it in my GitHub project ->



[1] “An O(ND) Difference Algorithm and Its Variations” by Eugene W. Myers