Granted Patent B2

US 9,063,949 · App. 13/801,303 · Granted Jun 23, 2015

Abstract

Claims (90)

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 s 1 of length N and the updated version of the document is a string s 2 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 s 1 of length n and a prefix of s 2 of length m;

wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s 1 and s 2 until the minimum edit distance between s 1 and s 2 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.

2. The method of claim 1 , wherein determining the minimum edit distance additionally involves associating a character cost with each character that is changed by an editing operation associated with the minimum edit distance.

3. The method of claim 1 , wherein the minimum edit distance is determined based on a set of editing operations comprising insertions, deletions and replacements of contiguous blocks of one or more characters.

4. The method of claim 1 , wherein each entry costs[n][m] includes:

a minimum cost for the case where the last operation was an insertion;

a minimum cost for the case where the last operation was a deletion; and

a minimum cost for the case where the last operation was a match.

5. The method of claim 1 ,

wherein the document is a shared document; and

wherein the method further comprises communicating the sequence of editing operations to a remote version of the document located on a remote computing device, so that the remote computing device can use an operational transformation technique to transform the sequence of editing operations before applying the transformed sequence of editing operations to the remote version of the document.

6. The method of claim 5 , wherein the shared document is maintained by an online content management system that uses the method to maintain consistency between different versions of the shared document located on different computing devices.

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 s 1 of length N and the updated remote version of the document is a string s 2 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 s 1 of length n and a prefix of s 2 of length m;

wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s 1 and s 2 until the minimum edit distance between s 1 and s 2 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][m−1] plus a character matching cost which can be zero.

8. The method of claim 7 , wherein the minimum edit distance is computed based on a set of editing operations comprising insertions, deletions and replacements of contiguous blocks of one or more characters.

9. The method of claim 7 , wherein the document is maintained by an online content management system that uses the method to maintain consistency between different versions of the document located on different computing devices.

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 s 1 of length N and the updated version of the document is a string s 2 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 s 1 of length n and a prefix of s 2 of length m;

wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s 1 and s 2 until the minimum edit distance between s 1 and s 2 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.

11. The non-transitory computer-readable storage medium of claim 10 , wherein determining the minimum edit distance additionally involves associating a character cost with each character that is changed by an editing operation associated with the minimum edit distance.

12. The non-transitory computer-readable storage medium of claim 10 , wherein the minimum edit distance is determined based on a set of editing operations comprising insertions, deletions and replacements of contiguous blocks of one or more characters.

13. The non-transitory computer-readable storage medium of claim 10 , wherein each entry costs[n][m] includes:

a minimum cost for the case where the last operation was an insertion;

a minimum cost for the case where the last operation was a deletion; and

a minimum cost for the case where the last operation was a match.

14. The non-transitory computer-readable storage medium of claim 10 ,

wherein the document is a shared document; and

wherein the method further comprises communicating the sequence of editing operations to a remote version of the document located on a remote computing device, so that the remote computing device can use an operational transformation technique to transform the sequence of editing operations before applying the transformed sequence of editing operations to the remote version of the document.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the shared document is maintained by an online content management system that uses the method to maintain consistency between different versions of the shared document located on different computing devices.

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 s 1 of length N and the updated remote version of the document is a string s 2 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 s 1 of length n and a prefix of s 2 of length m;

wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s 1 and s 2 until the minimum edit distance between s 1 and s 2 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.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the minimum edit distance is computed based on a set of editing operations comprising insertions, deletions and replacements of contiguous blocks of one or more characters.

18. The non-transitory computer-readable storage medium of claim 16 , wherein the document is maintained by an online content management system that uses the method to maintain consistency between different versions of the document located on different computing devices.

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 s 1 of length N and the updated version of the document is a string s 2 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 s 1 of length n and a prefix of s 2 of length m;

wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s 1 and s 2 until the minimum edit distance between s 1 and s 2 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.

20. The system of claim 19 , wherein determining the minimum edit distance additionally involves associating a character cost with each character that is changed by an editing operation associated with the minimum edit distance.

21. The system of claim 19 , wherein the minimum edit distance is determined based on a set of editing operations comprising insertions, deletions and replacements of contiguous blocks of one or more characters.

22. The system of claim 19 , wherein each entry costs[n][m] includes:

a minimum cost for the case where the last operation was an insertion;

a minimum cost for the case where the last operation was a deletion; and

a minimum cost for the case where the last operation was a match.

23. The system of claim 22 ,

wherein the document is a shared document; and

wherein the application is further configured to communicate the sequence of editing operations to a remote version of the document located on a remote computing device, so that the remote computing device can use an operational transformation technique to transform the sequence of editing operations before applying the transformed sequence of editing operations to the remote version of the document.

24. The system of claim 23 , further comprising an online content management system that interacts with the system to maintain consistency between different versions of the shared document located on different computing devices.

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 s 1 of length N and the updated remote version of the document is a string s 2 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 s 1 of length n and a prefix of s 2 of length m;

wherein the dynamic-programming technique computes minimum edit distances between progressively larger prefixes of s 1 and s 2 until the minimum edit distance between s 1 and s 2 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.

26. The system of claim 25 , wherein the minimum edit distance is computed based on a set of editing operations comprising insertions, deletions and replacements of contiguous blocks of one or more characters.

27. The system of claim 25 , wherein the document is maintained by an online content management system that uses the method to maintain consistency between different versions of the document located on different computing devices.

Assignments (8)