Inferring a sequence of editing operations to facilitate merging versions of a shared document
First Claim
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;
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;
wherein if the document is a string s1 of length N and the updated version of the document is a string s2 of length M, determining the minimum edit distance involves using a dynamic-programming technique that maintains an N×
M array of costs, wherein a given entry costs[n][m] stores minimum edit distances between a prefix of s1 of length n and a prefix of s2 of length m;
wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s1 and s2 until the minimum edit distance between s1 and s2 is ultimately computed; and
wherein each entry in costs[n][m] is computed by taking a minimum of;
costs[n][m−
1] plus a character insertion cost that possibly includes a block cost, costs[n−
1,m] plus a character deletion cost that possibly includes a block cost, and costs[n−
1][m−
1] plus a character matching cost which can be zero.
4 Assignments
0 Petitions
Accused Products
Abstract
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.
14 Citations
27 Claims
-
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; 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; wherein if the document is a string s1 of length N and the updated version of the document is a string s2 of length M, determining the minimum edit distance involves using a dynamic-programming technique that maintains an N×
M array of costs, wherein a given entry costs[n][m] stores minimum edit distances between a prefix of s1 of length n and a prefix of s2 of length m;wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s1 and s2 until the minimum edit distance between s1 and s2 is ultimately computed; and wherein each entry in costs[n][m] is computed by taking a minimum of; costs[n][m−
1] plus a character insertion cost that possibly includes a block cost, costs[n−
1,m] plus a character deletion cost that possibly includes a block cost, and costs[n−
1][m−
1] plus a character matching cost which can be zero. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for applying editing operations associated with a remote version of a document to a local version of the document, comprising:
-
receiving a sequence of editing operations associated with the remote version of the document, wherein the sequence of editing operations was generated while computing a minimum edit distance between the remote version of the document and an updated remote version of the document, wherein during the minimum edit distance computation a block cost is associated with each contiguous block of characters that is changed by an editing operation and a character cost with each character that is changed by an editing operation; using an operational transformation technique to transform the received sequence of editing operations; and applying the transformed sequence of editing operations to the local version of the document; wherein if the remote version of the document is a string s1 of length N and the updated remote version of the document is a string s2 of length M, computing the minimum edit distance involves using a dynamic-programming technique that maintains an N×
M array of costs, wherein a given entry costs[n][m] stores minimum edit distances between a prefix of s1 of length n and a prefix of s2 of length m;wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s1 and s2 until the minimum edit distance between s1 and s2 is ultimately computed; and wherein each entry in costs[n][m] is computed by taking a minimum of; costs[n][m−
1] plus a character insertion cost that possibly includes a block cost,costs[n−
1,m] plus a character deletion cost that possibly includes a block cost, andcosts[n][m−
1] plus a character matching cost which can be zero. - View Dependent Claims (8, 9)
-
-
10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for inferring a sequence of editing operations that were applied to a document to produce an updated version of the document, the method 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; 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; wherein if the document is a string s1 of length N and the updated version of the document is a string s2 of length M, determining the minimum edit distance involves using a dynamic-programming technique that maintains an N×
M array of costs, wherein a given entry costs[n][m] stores minimum edit distances between a prefix of s1 of length n and a prefix of s2 of length m;wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s1 and s2 until the minimum edit distance between s1 and s2 is ultimately computed; and wherein each entry in costs[n][m] is computed by taking a minimum of; costs[n][m−
1] plus a character insertion cost that possibly includes a block cost, costs[n−
1,m] plus a character deletion cost that possibly includes a block cost, and costs[n−
1][m−
1] plus a character matching cost which can be zero. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for applying editing operations associated with a remote version of a document to a local version of the document, the method comprising:
-
receiving a sequence of editing operations associated with the remote version of the document, wherein the sequence of editing operations was generated while computing a minimum edit distance between the remote version of the document and an updated remote version of the document, wherein during the minimum edit distance computation a block cost is associated with each contiguous block of characters that is changed by an editing operation and a character cost with each character that is changed by an editing operation; using an operational transformation technique to transform the received sequence of editing operations; and applying the transformed sequence of editing operations to the local version of the document; wherein if the remote version of the document is a string s1 of length N and the updated remote version of the document is a string s2 of length M, computing the minimum edit distance involves using a dynamic-programming technique that maintains an N×
M array of costs, wherein a given entry costs[n][m] stores minimum edit distances between a prefix of s1 of length n and a prefix of s2 of length m;wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s1 and s2 until the minimum edit distance between s1 and s2 is ultimately computed; and wherein each entry in costs[n][m] is computed by taking a minimum of; costs[n][m−
1] plus a character insertion cost that possibly includes a block cost, costs[n−
1,m] plus a character deletion cost that possibly includes a block cost, and costs[n−
1][m−
1] plus a character matching cost which can be zero. - View Dependent Claims (17, 18)
-
-
19. A system that infers a sequence of editing operations that were applied to a document to produce an updated version of the document, comprising:
-
at least one processor; a memory coupled to the at least one processor; and an application stored in the memory and configured to, determine 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; use 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; wherein if the document is a string s1 of length N and the updated version of the document is a string s2 of length M, determining the minimum edit distance involves using a dynamic-programming technique that maintains an N×
M array of costs, wherein a given entry costs[n][m] stores minimum edit distances between a prefix of s1 of length n and a prefix of s2 of length m;wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s1 and s2 until the minimum edit distance between s1 and s2 is ultimately computed; and wherein each entry in costs[n][m] is computed by taking a minimum of;
costs[n][m−
1] plus a character insertion cost that possibly includes a block cost, costs[n−
1,m] plus a character deletion cost that possibly includes a block cost, and costs[n−
1][m−
1] plus a character matching cost which can be zero. - View Dependent Claims (20, 21, 22, 23, 24)
-
-
25. A system that applies editing operations associated with a remote version of a document to a local version of the document, comprising:
-
at least one processor; a memory coupled to the at least one processor; and an application stored in the memory and configured to, receive a sequence of editing operations associated with the remote version of the document, wherein the sequence of editing operations was generated while computing a minimum edit distance between the remote version of the document and an updated remote version of the document, wherein during the minimum edit distance computation a block cost is associated with each contiguous block of characters that is changed by an editing operation and a character cost with each character that is changed by an editing operation; use an operational transformation technique to transform the received sequence of editing operations; and apply the transformed sequence of editing operations to the local version of the document; wherein if the remote version of the document is a string s1 of length N and the updated remote version of the document is a string s2 of length M, computing the minimum edit distance involves using a dynamic-programming technique that maintains an N×
M array of costs, wherein a given entry costs[n][m] stores minimum edit distances between a prefix of s1 of length n and a prefix of s2 of length m;wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s1 and s2 until the minimum edit distance between s1 and s2 is ultimately computed; and wherein each entry in costs[n][m] is computed by taking a minimum of;
costs[n−
n][m−
1] plus a character insertion cost that possibly includes a block cost, costs[n−
1,m] plus a character deletion cost that possibly includes a block cost, and costs[n−
1][m−
1] plus a character matching cost which can be zero. - View Dependent Claims (26, 27)
-
Specification