INFERRING A SEQUENCE OF EDITING OPERATIONS TO FACILITATE MERGING VERSIONS OF A SHARED DOCUMENT

摘要

The disclosed embodiments relate to a system that infers a sequence of editing operations that were applied to a document to produce an updated version of the document. During operation, the system computes a minimum edit distance between the document and the updated version of the document. During this process, the system associates a block cost with each contiguous block of characters that is changed by an editing operation and also a character cost with each character that is changed. Next, the system uses information stored during the computation to determine the sequence of editing operations which were used to achieve the minimum edit distance. The system communicates the sequence of editing operations to a remote computing device, wherein the remote computing device uses an operational transformation technique to transform the sequence of editing operations before applying the transformed sequence of editing operations to a remote version of the document.

主权项

1. A method for inferring a sequence of editing operations that were applied to a document to produce an updated version of the document, comprising:
determining a minimum edit distance between the document and the updated version of the document; wherein determining the minimum edit distance involves associating a block cost with each contiguous block of characters that is changed by an editing operation associated with the minimum edit distance; and using information stored while determining the minimum edit distance to determine the sequence of editing operations, including changes to contiguous blocks of characters, which were used to achieve the minimum edit distance.