Patent Document ID: 9063949
Application ID: 13801303
Patent Status: 1

Claim One:
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.