Make the world a better place, one bug at a time.

Javascript Diff Algorithm
Friday, 29 April 2016




The Algorithm

The algorithm is based on an adaptation of google's diff-match-patch by jhchen. The output is modified to make it compact and JSON friendly. It is also fast enough to be called as you type.

ide.diff(src, dest, size)

This function takes a source string src, and a destination string dest. It returns a patch object that can be later used by ide.patch to reconstruct the destination string.

The size parameter determines the minimum length of a single patch string, the algorithm will optimize the result based on this number.

A patch object consists of an array of triplets, where the first item is the string to be inserted, the second, the characters to be skipped from the original string and the third the characters removed after inserting.

ide.patch(src, patch)

This function takes the original source string str and the result of a previous diff patch. The result will be the destination string dest.

Source code is hosted in github as a gist.

javascript diff algorithm