Operational Transformation Part 2: Operations

April 5th, 2011

This is the second post in a series I am doing on the real-time collaboration algorithm Operational Transformation (OT). The first post was an introduction to OT and this series. There are two repositiories on GitHub to follow along with:

  1. operational-transformation - This is an Operational Transformation library for plain text which assumes nothing about how the storage backend for your documents works, what kind of frontend you will be using, etc. This is where most of the ideas discussed in this series will be implemented.

  2. operational-transformation-example - This repository contains an example application which takes advantage of the OT library.

However, before we can start transforming operations and providing a real-time experience for our users, we have to decide how to represent and generate operations. That is the topic for this post.

Representing Operations

We will be representing operations as a stream of simple edits. As Daniel Spiewak notes in Understanding and Applying Operational Transformation, this is perfect for the type of automated processing we will be doing inside the xform function. Our operations will be made up of the following three types of edits:

  1. retain(n) - Copy n characters from the old version to the new one.

  2. insert(subsequence) - Insert subsequence in to the new document, without changing where we are indexed in the old document.

  3. delete(subsequence) - Advance the position we are indexed in the old document by the length of subsequence, without copying subsequence in to the new document. The reason we pass a subsequence instead of a number is soley so that we can assert we are deleting the proper subsequence and throw an error if we are not.

To create the document "Hello, World!" from the document "hello world", you would apply the following operation:

[ delete('h'),
  insert('H'),
  retain(4),
  insert(','),
  retain(1),
  delete('w'),
  insert('W'),
  retain(4),
  insert('!') ]

Note that the edits start at the beginning of the old document and finish at the end of it. If an operation doesn't affect the whole document, the last edit in the operation should be retain(length of remaining document).

Calculating Operations

First off: you don't want to add listeners to keyboard and mouse events! Imagine all of the edge cases and browser incompatibilities: would you successfully handle Ctrl-a or Shift-up-arrow followed by backspace? Yikes, I don't even want to think about all of the common key combinations (not to mention the differences between key combinations across OSs).

No, instead you want to take two versions of the document and programmatically generate a list of operations which transform one version to the other. Fortunately, comparing sequences and determining their similarity or difference is pretty much a solved problem in computer science.

Levenshtein Distance

Levenshtein distance (sometimes also referred to as edit distance) is defined as the number of edits required to transform one sequence in to another sequence. Classicly, these edits are either an insertion, deletion, or substitution of a single item in the sequence. Comparing sequences of characters (or, as we know them, plain text documents) is a classic use case for Levenshtein distance. Variations of Levenshtein distance are also often used in bioinformatics to compare sequences of DNA.

The Levenshtein distance between "WUTANG" and "MUTATION" is five, because it would take three substitutions and two insertions to transform "WUTANG" in to "MUTATION":

The algorithm for calculating Levenshtein distance runs in O(m * n). Here it is presented in psuedo code:

LevenshteinDistance( s[1..m], t[1..n] ):
  d = matrix[0..m, 0..n]

  # The distance between the empty string and another
  # string is equal to the length of the other string.
  for i = 0 to m:
    d[i, 0] = i
  for j = 0 to n:
    d[0, j] = j

  for j = 1 to n:
    for i = 1 to m:
      if s[i] is equal to t[j]:
        d[i, j] = d[i-1, j-1]              # No edit
      else:
        d[i. j] = minimum( d[i-1, j] + 1,  # Deletion
                           d[i, j-1] + 1,  # Insertion
                           d[i-1, j-1] + 1 # Substitution
                         )

  return d[m, n]

However, the number of edits is immaterial in our application; we care about what the edits are. Modifying the algorithm to return a list of edits instead of the number of edits is trivial: just store lists of edits in the d matrix rather than numbers.

Here is my JavaScript implementation of calculating an operation on GitHub.

Possible Improvements in Calculating Operations

Applying Operations To a Document

Applying operations to a document is straight forward. See the apply.js file in the operational-transformation GitHub repo.

Next Up

In the next part of this series, I will describe the xform function, and how it transforms a pair of operations so that two documents can be kept in sync.

References

« Previous Entry

Next Entry »


Recent Entries

Come work with me on Firefox Developer Tools on July 8th, 2014

Debugging Web Performance with Firefox DevTools - Velocity 2014 on June 26th, 2014

Beyond Source Maps on March 12th, 2014

Memory Tooling in Firefox Developer Tools in 2014 on March 4th, 2014

Hiding Implementation Details with ECMAScript 6 WeakMaps on January 13th, 2014

Re-evaluate Individual Functions in Firefox Developer Tools' Scratchpad on November 22nd, 2013

Testing Source Maps on October 2nd, 2013

Destructuring Assignment in ECMAScript 6 on August 15th, 2013

My Talk from Front Trends 2013 on June 21st, 2013

"Compiling to JavaScript, and Debugging with Source Maps" on Mozilla Hacks on May 22nd, 2013

Creative Commons License

Fork me on GitHub