US10783326B2

US10783326B2 - System for tracking changes in a collaborative document editing environment

Info

Publication number: US10783326B2
Application number: US13/830,023
Authority: US
Inventors: Robin Glover
Original assignee: Workshare Ltd
Current assignee: Workshare Ltd
Priority date: 2013-03-14
Filing date: 2013-03-14
Publication date: 2020-09-22
Also published as: US20140281872A1

Abstract

This invention discloses a novel system and method for displaying electronic documents on remote devices and enabling collaborative editing where the system tracks revisions, comments and other content between versions of the document by maintaining hierarchical representation of the version and mapping locations between the hierarchies.

Description

FIELD OF INVENTION

The present invention generally relates to the field of digital document review. More particularly, the present invention relates to methods and systems for detecting changes and/or differences between an original document and a modified version of the document, especially where the two versions of the document are encoded in different formats of document representation.

BACKGROUND

In several scenarios, one or more users may go through multiple revisions of a document to improve the content and presentability of the document contents. As a result of their being more than one user authorized to access and modify a document, other users may become confused when requesting to see a document if they are not aware that the document has changed and how. In doing so, a user may wish to compare a latest version of the document with a prior version to determine the changes that have been made to the latest version. Other limitations of existing or prior systems will become apparent to those of skill in the art upon reading the following Detailed Description.

At least one embodiment of this invention pertains to a document management service that enables a user to request a document from the service to be delivered to a remote computer and have the service compare the last version of the document that the user accessed with the latest version and to deliver a display document showing those changes The document management service may run as a standalone service on a user's computing device or, in some instances, may run as a web service on a remote server. In either scenario, the document management service receives as input a request for particular document that a user wishes to see. The system also stores versions of the document as separate data files. These can be compared to show the revisions more plainly. These and other objects, features and characteristics of the present invention will become more apparent to those skilled in the art from a study of the following detailed description in conjunction with the appended claims and drawings, all of which form a part of this specification. It should be understood that the description and specific examples are intended for purposes of illustration only and not intended to limit the scope of the present disclosure.

DESCRIPTION OF THE FIGURES

The headings provided herein are for convenience only and do not necessarily affect the scope or meaning of the claimed invention. In the drawings, the same reference numbers and any acronyms identify elements or acts with the same or similar structure or functionality for ease of understanding and convenience. To easily identify the discussion of any particular element or act, the most significant digit or digits in a reference number refer to the Figure number in which that element is first introduced (e.g., element 204 is first introduced and discussed with respect to FIG. 2).

FIG. 1. Schematic showing comparisons of two versions.

FIG. 2. Flow chart depicting the basic architecture of the process.

FIG. 3. Example document revision history as a tree structure.

FIG. 4. Example document revision history schematic

FIG. 5. Example metadata storage.

FIG. 6. Example change report.

FIG. 7. Example structural change, the deleted table, and the hierarchical representation of the deletion.

DETAILED DESCRIPTION

Various examples of the invention will now be described. The following description provides specific details for a thorough understanding and enabling description of these examples. One skilled in the relevant art will understand, however, that the invention may be practiced without many of these details. Likewise, one skilled in the relevant art will also understand that the invention can include many other features not described in detail herein. Additionally, some well-known structures or functions may not be shown or described in detail below, so as to avoid unnecessarily obscuring the relevant description. The terminology used below is to be interpreted in its broadest reasonable manner, even though it is being used in conjunction with a detailed description of certain specific examples of the invention. Indeed, certain terms may even be emphasized below; however, any terminology intended to be interpreted in any restricted manner will be overtly and specifically defined as such in this Detailed Description section.

The method and system operates on one or more computers, typically using one or more servers and one or more remote user's computing devices. A customer's device can be a personal computer, mobile phone, mobile handheld device like a Blackberry™ or iPhone™ or a tablet device like the iPad™ or Galaxy™ or any other kind of computing device a user can use to view and edit an electronic document. The user devices are operatively connected to the remote server using a data network. The invention does not require that the data network be in continuous contact with the remote file server. The invention works in conjunction with a document collaborative editing system (CES) or document management systems, (DMS) or both. For brevity, references to the DMS in the disclosure may disclose processes that may be performed by the CES or the CES in combination with the DMS. The system can be embodied in a client/server architecture, whereby an executable code operates on the user's remote device and interacts with processes operating on a server. In other embodiments, the same system can be running on the user's remote device by means of scripts or apps that are downloaded and executed within an Internet web-browser.

The user's remote computer is operatively connected to a data communication network, typically the Internet. This may be directly or indirectly through another network, for example a telephone network or a private data network. The user operates a client software on their computing device that communicates with the server that operates the process as a service, or the server that delivers documents for editing or review, that is the DMS or CES.

When the client requests to view a document available on the DMS, the request is received and processed on the DMS. In this case, the user's device may select a document title from a graphical user interface displayed on the screen of the device. The DMS maintains all of the revisions of the document in its data storage repository. Each time the CES saves a new version, that is a new computer file. That new file typically has a different filename than the prior version. The system also keeps track of the date and time that the version was stored. The system maintains a separate database that keeps track of each user authorized to access the document on the CES and their access of the document. Once the compared document is presented to the user, the user can make changes to the document and save it as yet a newer version When a new version of the document is created, it's a distinct document data file.

Document management and collaborative systems tend to only allow serial editing of documents—that is to say that only a single user may be actively editing a particular document at one time.

Some systems such as document management systems (DMS) tend to enforce this workflow by providing locking operations—in order to edit a document a user must check out or lock the document, which prevents other users from accessing it except in ‘read-only’ mode. In this embodiment, the system works with a document where for any version of the document, there is one parent version and one child version, except for the first version and the last version. See FIG. 3.

Other systems do not enforce locking but use a ‘first writer wins’ approach which allows two users to begin editing the document at once, but only the first to save will be allowed to save their changes as a new version. The second user to try to save will be informed that they are unable to do so. Here the serial editing requirement is still enforced, but at the point of saving rather than opening the document. This requires less overhead for the user and is a more natural flow in most cases where there is no conflict. However in the case where there is a conflict, the user who tries to save second has already expended time and effort on editing the document and may be frustrated by their inability to save their work as a new version.

Another approach is to use a ‘last writer wins’ approach—in this case parallel editing is allowed but ignored by the system. Multiple users are allowed to open and edit the document at once and all saves are accepted, but the system only tracks versions as a single, linear list. If two editors are changing the document at once, the changes of the editor who saves first will be overwritten by those of the editor who saves later. Providing the system maintains a history of content of versions of the document, the changes made by the first editor are not lost irretrievably, but the fact that they have been overwritten may not be noticed and even if it is noticed, integrating these changes into the newer versions of the document may require considerable time and effort.

Parallel review, where two or more editors can simultaneously make changes to documents, or editors can make changes to older versions of the document, is usually disabled because of the difficulties of merging these changes back into a definitive latest version of the document. In this embodiment, the system may have versions of the document where a document may have one parent, but more than one child version. This occurs when a version of the document is opened by two different users who then save their versions of the document as distinct versions. See FIG. 4. While automated techniques for merging changes from different versions of text documents have existed for some time (and are widely used for managing changes to computer source code files), there have been fewer options available for performing the same process on word-processing documents.

Microsoft Word provides a different approach to merging two versions of a document—a comparison technique labeled ‘Combine Documents’. This can compare two versions of a document from different branches of the version tree and label changes made in each with the author who made the changes. The changes can then be applied selectively as they are presented as track changes within word. Normally when comparing documents from two different branches of the version tree there is a problem with identifying in which branch a change was made—for instance if the text ‘Once upon a time there were three bears’ is present in the version from branch A, but not in the version from branch B, there is no way to tell if the text was inserted by the editor of branch A or was originally in an older version of the document but was deleted by the editor of branch B. Word gets around this problem by attaching identifiers termed ‘Revision Sequence IDs’ or ‘RSIDs’ to each block of text in the document. A new, random, RSID is used for each editing session of the document and a list is stored in the document. If a block of text such as the ‘three bears’ example above is found to have a RSID that is listed in both documents RSID history, then the block must have existed in a version of the document before the two branches diverged—this would mean that its absence from branch B indicates that it was deleted in that branch. Conversely, if the RSID for that block of text only exists in the list for branch A, then it must be an insertion in that branch. The technique used by Microsoft Word has limitations—for instance modifications of the document by another tool that does not insert RSIDs for new edits will confuse the system. Additionally, it is only possible to bring together changes from two versions at a time and the process must be performed on a computer running Microsoft Word, and so is not suitable for use in a server or cloud based offering.

The aim of this invention is to provide the ability to build a flexible, easy to use system for suggested merging changes from one or more versions of a word-processing document into another, target, version of the document. The invention is designed to be capable of being run either in a server environment—perhaps presented via a web interface, or running locally on a client computer.

Outline of Solution

For best results, the solution requires a content store which maintains the data describing past versions of the document. In addition to storing the content, the following metadata associated with each version is stored. See FIG. 5.

Parent Version—a link, by Id or otherwise indicating the earlier version of the document from which a particular version is derived

Author—the name of the person who created the version—the person who made the changes between that version and its parent version

A merged flag—indicating that changes in a particular version have already been merged into the master version of the document at some earlier point in time. This means that changes in an already merged version need not be included in future merging operations.

Creation date—the date and time at which the document version was created or added to the store

The main merging procedure may be carried out in the absence of this metadata, and in fact in the absence of a versioning content store by (for instance) the reviewer being requested to manually select files containing the different versions of the document to operate on and the relationships between those versions. It is assumed for purposes of explanation that all of the versions and associated metadata are available from some form of content store.

Determining the Versions to Show Changes from Contributions:

First the system fetches from the database a list of all available versions of the document to be worked on. One version is chosen as the ‘working version’. This version is the version to which changes from other versions will be applied. The reviewer may be allowed to select which version is to be used as the working version, or the working version may be chosen according to some rule—for instance the most recent version or the most recent version created by the reviewer who initiated the merge process.

Once the working version is selected, the remaining versions are divided into two categories—already merged versions and possible contributions. The Already Merged versions category consists of all versions which are either a) direct ancestors of the working version or b) marked as already merged by the merged flag being set. The Possible Contributions category consists of all other versions. This category consists of all the versions that may contain changes that need to be merged into the working version. Typically, this will be versions of the document that are related to a common ancestor but are not ancestors of the working document.

The possible contributions category is now narrowed further to obtain the set of actual contributions. In order to do this any version created by an author that has a child version in the set of possible contributions created by the same author is all merged into one possible contribution. Rather than presenting as two or more different sets of changes created by same author, the single author's changes are presented to the reviewer as one set of revisions presented by the author. Referring to FIG. 4, the system is adapted to present the revisions between the original version 1 and version 3 combined with version 6. We combine the changes of the same author, if they have not been flagged merged. We would not show changes between 3 and 1 again. This step ensures that if an author saves multiple versions to the system while working, his changes appear as a single set of changes in the system rather than two or more sets. For each version in the set of actual contributions, a reference version is chosen—this is the version that the contribution version will be compared against to determine the changes made by the author of the contribution. The reference version is the closest ancestor version of the contribution that is either authored by a different author to the contribution or a member of the ‘already merged versions’ category. An alternative approach can be taken where no versions are discarded from the possible contributions category—i.e. the set of actual contribution versions is identical to the set of possible contribution versions. In this case the reference version for each contribution should be its parent version, and multiple versions created by the same author will appear as separate sets of changes.

The process will be explained in the context of FIG. 4. Version #4 by Charles is already flagged as having been merged. Alice begins the merge/review process and version #8 is selected as the working version by the system. The already merged contributions category is determined to be #1, #2, #5 and #4. The first three because they form the direct ancestry of the working version (and therefore changes made in them are already in the working version) and the last because it is marked as already merged in its metadata (presumably as the result of a previous merge/review operation).

This leaves the set of possible contributions as being #3, #6 and #7. From this set, #3 is dropped as it is authored by Bob and also has a child version that is also a possible contribution and also authored by Bob. Thus the set of actual contributions consists of versions #6 and #7. For each of these a reference version must be chosen. In the case of #7, the reference version is chosen as #3, since it is the nearest ancestor version authored by a different user. In the case of version #6, the reference version is #1 as it is the nearest ancestor that is either authored by a different user or part of the already merged category (in this case it's both).

So, for the version tree in FIG. 4, we have 2 possible sets of changes to allow the reviewer to apply, changes made by Bob (version #6 compared against version #1) and changes made by Charles (version #7 compared against version #3). The system may choose to automatically calculate both sets of changes and display them to the reviewer or prompt the reviewer with a list of possible contributions to include and allow them to select which ones to use. It's worth noting, once again, that it's possible for the contribution versions, reference versions and working version to be chosen in other ways to that outlined above—for instance the reviewer could select them manually.

It's also possible to use the system in a very simplified form where there are only two versions of interest in the version tree—the original (parent) version and the modified (child) version. In this case, if the original version is chosen as the working version, and the single contribution consists of the modified version against a reference version which is also the original version, the system then allows the reviewer to selectively choose which of the changes made to the document in the modified version to keep and which to discard.

Determining the Changes from Each Contribution

A document comparison engine can be used to determine the changes made in each contribution by comparing the contribution version against the reference version. Document comparison includes string matching algorithms, which can be further improved by ignoring certain characters, for example, spaces, carriage returns and line feeds, and certain other formatting characters. The outputs from this comparison process should include a machine readable representation of the full result of the comparison, including the text and structure of the redline document and annotations to indicate which parts are inserted, deleted etc. The content of the document is thereby more than simply text, but includes formatting data, insertion indications, deletion indications, document structure control data like tables, cells, footnotes and other data that an application can use to render the document as the author intended. In one embodiment, output is encoded in XML format. The output of the comparison may also include a redline document in a file format associated with word-processing documents, for example, .DOC, .DOCX, or .RTF, which can be displayed to the reviewer by means of the appropriate word processing or viewing software.

Displaying Changes to the Reviewer

At this point the system may optionally collect additional information about each change by determining the location where the change would be applied in the working version of the document. This location is determined as follows:

The location of the change in the reference version for the contribution is determined by mapping from the redline for the contribution to the content of the reference document in a hierarchical manner further described below.

This location in the reference version is then tracked to the equivalent version in the working version.

Determining the location of each change in the working version enables the additional information to be shown to the reviewer when they are presented with the changes. This information includes:

Changes that clash with each other by acting on the same area of the working version of the document—these are detected by finding changes where the ranges they would apply to in the working version overlap.

Changes that duplicate each other, because they would end up making the same change at the same location in the working version

Changes that cannot be applied (because for some reason the location in the working version cannot be determined, or has been removed—for instance a change to the wording of a footnote that has already been deleted in the working version).

Changes that need not be applied because they have already been effected in the working version—for instance a deletion where the range for the change location in the working version is reduced to a single point—this indicates that the text has already been deleted in the working version.

The changes may be ordered by their position in the working version when displayed, grouping changes that are applied to the same area of the working version together.

With or without this additional information, the changes need to be presented to the reviewer, so that he or she can select which changes to apply. This presentation could be in the form of a web page if the system is hosted on a server, or user interface within an application if the system is running on computer, or possibly within an app on a smart phone or tablet. See FIG. 6. In the case of display on a smart phone or tablet, it is possible that the calculations of all changes to be shown and the additional information associated with them would be performed on a server and the result of this calculation downloaded to the app in the form of XML, JSON or some other data format transmitted over the network.

The presentation of changes may take the form of a simple list, grouped by contribution, or a categorized arrangement as described in U.S. Pat. App. No. 2012/0136862, to Robin Glover, incorporated herein by reference, or alternatively, ordered according to their position in the working version if such information is made available. Additionally, the system may display the whole or fragments of the redline document along with the summary of changes to give the reviewer a better insight into the context in which the changes are being made.

It may be possible for one of several different views of the changes to be selected or switched between by the reviewer. Where additional information is attached to each change, this may be displayed to the reviewer in association with the display of the change itself or when the reviewer interacts with the change—for instance using a ‘tooltip’ to show associated information when the reviewer hovers the mouse cursor over the change. For each change that can be applied, the reviewer should have some method of indicating whether they want to apply the change—one example of this could be to place a checkbox next to each change which can be ticked by the reviewer to indicate that the change should be applied to the working version. The fact that a change cannot be applied for some reason may be indicated to the reviewer by disabling the action of this checkbox and showing a tooltip when the reviewer attempts to interact with it showing the reason that the change cannot be applied.

Where changes from different contributions have been detected to duplicate each other, the user interface may automatically change the check state of the checkbox against all duplicates of a change when the checkbox of any one of them is altered. Where changes conflict with each other the system may inform the reviewer by a tooltip, message box or other notification when they try to select two or more changes that are likely to conflict with each other.

The system may offer the reviewer the ability to save the selection state of the changes that they have already chosen to apply, close the app, application or web page and resume their work with the saved selections restored at a later time. In this case the system would have to not only save the selection information for all changes but the exact choices of versions for the working version, contributions and reference versions to allow an identical configuration to be recreated at the later time. Once the reviewer has finished selecting changes to be applied, they will have the option of carrying out the changes to the working version of the document by an appropriate interaction with the user interface—for instance pressing a button labeled ‘Apply Changes’. At this point the apply process (detailed below) will take place to create a new, updated version of the document by applying the selected changes to the working version.

The system may allow the reviewer to do any or all of the following with this new version:

View it on a device, computer or in a browser

Open it for editing in an appropriate application

Save it to storage on the computer or device

Save it to the versioned file storage which the other versions were retrieved from—as a new version which will be a child of the working version.

Applying the Changes to the Working Version

The apply process begins with a set of input data consisting of:

Details of the working version of the document which changes are to be applied to

Details of the contributions that have been selected and the reference versions which they have been compared to

A list of changes that have been selected to be applied by the reviewer—This list could consist of a list of pairs of numbers—(contribution number, change number), (contribution number, change number) etc, or could identify the changes selected in some other way. The first two pieces of information ensures that the apply process can exactly reproduce the set of changes that were generated to be shown to the client, avoiding problems if (for instance) extra versions of the document have been created while the reviewer was deciding which changes to apply.

If the system calculated the position of changes in the working document, the apply process may be able to re-use the mapping information calculated. If the mapping information was not stored or is not available, then it can be re-calculated from scratched based on the input data for the apply process—i.e. the identity of the working version, the list of contribution and reference versions. This calculation process will need to access the content of the various versions from their storage location.

Since the apply process will make changes to the content of the working copy, the representation used to access the content of this document for mapping (the in memory hierarchical object model described further below) must support modification to the content of the document and the ability to re-save the modified content of the document. Various software libraries (including the OpenXML SDK from Microsoft) are capable of performing these operations. The entire process is made simpler if all versions of the document that need to be loaded to perform the apply operation (working version, contributions and reference versions) are all loaded using the same software library.

As described earlier as an optional step when displaying the changes to the reviewer, the mappings between different versions can be used to calculate the position of changes made in one version to the correct location in a later version of the document. See FIG. 1. This calculation is now performed for all changes that have been selected to be applied, and the location for the change in the working document is stored alongside each change. This location will be called the target location for the change. The target location may be a point in the document (for insertions) or a range between two points (for deletions). Each point in the document will be of the form of a reference to an object in the hierarchical object model representing the document, with (optionally) an offset within the object. For instance consider that an object may represent the following block of text within the document:

The quick brown fox jumps over the lazy dogs.

A range that identifies the word ‘brown’ would have a start point which references this object with an offset of 10 and an end point referencing the object with an offset of 15.

In addition to storing the change location in the working version for each change, the mapping process also needs to store the change location in the contribution document for each insertion (or move destination) change. This information allows the apply process to gather the text to be inserted and any style or formatting information to be brought along with it when the change is applied. This location will be called the change source location. As an explanatory example, the document hierarchy may be represented as a list of nodes, each entry having its own list of elements:

[versionXnodenum, content, location, childnodenum (1) . . . childnodenum(n)]

The comparison mapping between versionX and the redline is another list of entries, each entry having its own list of elements:

[versionXnodenum, redlinenodenum, location reference].

The system maps the content in the original by searching on content, retrieving the nodenum for that content. It then can look up in the mapping tree for that nodenum in the first entry and retrieve the redlinenodenum. It then can go to the version 2 mapping to redline, search on the redlinenodenum, retrieve the location reference and display the content at that location, and/or insert the content into the version2 node.

In order to apply changes which are deletions (or move source changes) to the working copy, the text within the target range for the change must be removed from the working copy of the document. In order to apply changes which are insertions (or move destination changes) to the working copy, the text that lies within the change source range must be copied from the contribution document and inserted at the target location in the working version of the document. Formatting information may optionally be brought from the contribution version to the working version of the document for the inserted text.

Each time a change is applied to the working version of the document, care must be taken to update the target locations for other changes that are still to be applied to take account of the change that has been made and ensure that the locations remain correct. In the example given earlier with a range that identifies the word ‘brown’ by offset within a longer block of text, if the application of another change deletes the word ‘quick’, the offsets of each end of the target range for the word ‘brown’ must be adjusted to subtract the number of characters removed to ensure that the word ‘brown’ is still targeted. The adjustment to change target locations may not be simply limited to changing offsets within an existing element in the document object model. Application of changes could lead to insertion, deletion, splitting or combining of elements in the document object model and change target locations must be updated to account for each of these actions if they occur.

Applying Structure Changes to the Document

As well as changing text within a document, an author can also make changes to the structure of the document—for instance they can insert or delete tables, rows, cells, footnotes, endnotes, headers, footers etc. If these changes are detected in the comparison progress and included in the machine readable comparison summary, then they can be applied to the working version of the document in a manner similar to the application of textual changes. See FIG. 7.

One approach would be to show these structural changes in the summary of all changes presented to the reviewer and allow them to select which changes to apply. This is simple but puts an extra workload on the reviewer requiring them to consider and select these changes and potentially allows the reviewer to select a contradictory set of changes—for instance they could select to apply text that is inserted within a new table but not to insert the table itself. A more satisfactory approach is to link the structural changes to the textual changes they contain, so that, for instance a deleted table row containing 3 textual deletions would be removed from the working copy of the document if (and only if) the reviewer selected to apply all 3 textual deletions in the row. The logic being here that if all the textual content within a piece of document structure such as a table, table row, footnote etc. is deleted then it makes sense to delete the (now empty) structure too. A slightly different rule applies for inserted structure—a piece of structure should be inserted into the working version of the document if any (rather than all) of the textual insertions within it are selected to be applied.

Tracking and Mapping Changes.

This application incorporates by reference the co-pending application to Robin Glover, titled “A Method and System for Comparing Documents Encoded in a Hierarchical Representation,” filed on the same date as this application, docket number WS15.

The solution works by maintaining a pair of cursors, one recording the position that the algorithm has reached in the first representation of the data and the other recording the position that the algorithm has reached in the second representation of the data. In one embodiment, these cursors begin at the root node of each representation and are advanced by traversing the tree in depth first order. FIG. 2. By cursor, it is also meant to include a pointer or other data object that an algorithm can use as the reference to a node in a tree data structure. The details of how each decision is made is dependent on the type of data represented by the two trees and how the tree structures differ. Where the types of data differ, then one cursor advances to the next node in the search while the other cursor remains at the same position. See FIG. 2. For instance in the case of two representations of a document, tree 1 (103) may contain nodes that represent the position of bookmarks in the document, while tree 2 (104) may not contain bookmark information. In this case, the decision ‘can ignore item at tree1 cursor’ would be yes if the tree 1 cursor is pointing to a bookmark node. The tree1 cursor would then be advanced past the bookmark node (without moving the tree 2 cursor) to allow the matching process to proceed.

In the case of the decisions as to whether the items at the cursors match, the logic is domain dependent. To give another document related example, in tree 1 a paragraph may be represented as a paragraph node with the text of the paragraph contained in its child node(s). In tree 2, the end of paragraphs may be represented by ‘paragram marker’ nodes which have no children and are sibling nodes to the nodes containing text. In this case the end of a paragraph node from tree 1 is taken to be a match for a paragraph marker node from tree 2, while the start of a paragraph node from tree 1 may be ignored.

In the case where the two nodes do not match at all, the process re-synchronizes. The re-synchronization stage exists to deal with minor mismatches between the content of the two documents that cannot be handled by simply ignoring items from one tree or another or allowing more flexible matching between the two trees. It can deal with situations such like ‘sometimes we get an extra paragraph break from tree 2 which isn't in tree 1’. This situation cannot be dealt with by ignoring paragraph breaks from tree 2 (which would ignore all of them), or by allowing them to match to nothing in the matching stage, so it must be dealt with by the resynchronization stage.

Resynchronization is only attempted after normal ignoring and matching has failed. This ensures that items that can be matched will be in preference to them being skipped over by a resynchronization. That the ordering of the resynchronization stage after the ignoring and matching stages cannot move the cursors forward at a particular location is important. In practice, the resynchronization step consists of trying, in turn, each strategy in a list of resynchronization strategies that have been designed to deal with the differences between the two representations of the data. Each strategy is tested to see if it can deal with the current situation. If it can, the strategy takes steps to resynchronize the cursors, which may involve advancing one or both cursors and possibly recording a match. As soon as a strategy succeeds in advancing either cursor, the processing of the list of resynchronization strategies stops and the main algorithm returns to testing for ignores and matches. This ensures that possible matches are not missed due to unnecessary resynchronizations.

In general, resynchronization strategies will be attempted in order from the most simple and restrictive first to more complex and more generally applicable towards the end of the list. Some resynchronization strategies may just examine the nodes pointed to by the current cursor positions, others may ‘look ahead’ at nodes further on in the traversal of the tree or up the tree to the parent nodes of the current nodes to determine if they are applicable—for instance a strategy might only be applicable if the current location is within a table cell. Now the technique for hierarchical mapping can be applied twice—firstly between the original document hierarchy and the redline hierarchy and secondly between the modified document hierarchy and the redline hierarchy. The rules for what content is ignorable, how content should be matched and what resynchronizations to apply need to be based on the details of how the document and redline are represented in their respective object models, but the following basic rules need to be included:

When mapping the redline to the original (101), all elements in the redline marked as inserted (or move destination) should be treated as ignorable.

When mapping the redline to the modified (102), all elements in the redline marked as deleted (or move source) should be treated as ignorable.

By ignoring all inserted content from the redline, the structure and content of the remaining, un-ignored, redline elements should essentially match the structure and content of the original document, allowing for a successful mapping between the original and the redline content. Similarly ignoring deleted content when mapping the modified allows for a successful mapping between the redline and the modified document.

As a result of the two mapping procedures completing, there now exist correspondences between nodes in the redline hierarchy and the appropriate matching nodes in the original and modified versions of the document. A position or piece of content from the original document can be tracked to the equivalent location in the modified document by first following the correspondence from the node (or nodes) that represent the item in the original document to the equivalent nodes in the redline. (101) Then, it can be tracked from the node in the redline to the corresponding node in the modified version of the document. (102) The correspondence between the redline and the modified can then be followed to identify the nodes in the modified document that correspond to the starting content or position in the original document. For example, if an object needs to be positioned in the modified document, its location in the original can be mapped to the modified and then the object inserted into the modified with the appropriate position data so that it appears when rendered in the correct place. In cases of comments or other content, the content is not necessarily inserted, rather, its displayed or included with reference to the correct location in the modified document so that the second document is not changed, but rather displayed with an overlay, or reference.

Operating Environment:

Those skilled in the relevant art will appreciate that the invention can be practiced with other communications, data processing, or computer system configurations, including: wireless devices, Internet appliances, hand-held devices (including personal digital assistants (PDAs)), wearable computers, all manner of cellular or mobile phones, multi-processor systems, microprocessor-based or programmable consumer electronics, set-top boxes, network PCs, mini-computers, mainframe computers, and the like. Indeed, the terms “computer,” “server,” and the like are used interchangeably herein, and may refer to any of the above devices and systems. In some instances, especially where the mobile computing device is used to access web content through the network (e.g., when a 3G or an LTE service of the phone is used to connect to the network), the network may be any type of cellular, IP-based or converged telecommunications network, including but not limited to Global System for Mobile Communications (GSM), Time Division Multiple Access (TDMA), Code Division Multiple Access (CDMA), Orthogonal Frequency Division Multiple Access (OFDM), General Packet Radio Service (GPRS), Enhanced Data GSM Environment (EDGE), Advanced Mobile Phone System (AMPS), Worldwide Interoperability for Microwave Access (WiMAX), Universal Mobile Telecommunications System (UMTS), Evolution-Data Optimized (EVDO), Long Term Evolution (LTE), Ultra Mobile Broadband (UMB), Voice over Internet Protocol (VoIP), Unlicensed Mobile Access (UMA), etc.

The user's computer may be a laptop or desktop type of personal computer. It can also be a cell phone, smart phone or other handheld device, including a tablet. The precise form factor of the user's computer does not limit the claimed invention. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held, laptop or mobile computer or communications devices such as cell phones and PDA's, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

The system and method described herein can be executed using a computer system, generally comprised of a central processing unit (CPU) that is operatively connected to a memory device, data input and output circuitry (I/O) and computer data network communication circuitry. A video display device may be operatively connected through the I/O circuitry to the CPU. Components that are operatively connected to the CPU using the I/O circuitry include microphones, for digitally recording sound, and video camera, for digitally recording images or video. Audio and video may be recorded simultaneously as an audio visual recording. The I/O circuitry can also be operatively connected to an audio loudspeaker in order to render digital audio data into audible sound. Audio and video may be rendered through the loudspeaker and display device separately or in combination. Computer code executed by the CPU can take data received by the data communication circuitry and store it in the memory device. In addition, the CPU can take data from the I/O circuitry and store it in the memory device. Further, the CPU can take data from a memory device and output it through the I/O circuitry or the data communication circuitry. The data stored in memory may be further recalled from the memory device, further processed or modified by the CPU in the manner described herein and restored in the same memory device or a different memory device operatively connected to the CPU including by means of the data network circuitry. The memory device can be any kind of data storage circuit or magnetic storage or optical device, including a hard disk, optical disk or solid state memory.

The computer can display on the display screen operatively connected to the I/O circuitry the appearance of a user interface. Various shapes, text and other graphical forms are displayed on the screen as a result of the computer generating data that causes the pixels comprising the display screen to take on various colors and shades. The user interface also displays a graphical object referred to in the art as a cursor. The object's location on the display indicates to the user a selection of another object on the screen. The cursor may be moved by the user by means of another device connected by I/O circuitry to the computer. This device detects certain physical motions of the user, for example, the position of the hand on a flat surface or the position of a finger on a flat surface. Such devices may be referred to in the art as a mouse or a track pad. In some embodiments, the display screen itself can act as a trackpad by sensing the presence and position of one or more fingers on the surface of the display screen. When the cursor is located over a graphical object that appears to be a button or switch, the user can actuate the button or switch by engaging a physical switch on the mouse or trackpad or computer device or tapping the trackpad or touch sensitive display. When the computer detects that the physical switch has been engaged (or that the tapping of the track pad or touch sensitive screen has occurred), it takes the apparent location of the cursor (or in the case of a touch sensitive screen, the detected position of the finger) on the screen and executes the process associated with that location. As an example, not intended to limit the breadth of the disclosed invention, a graphical object that appears to be a 2 dimensional box with the word “enter” within it may be displayed on the screen. If the computer detects that the switch has been engaged while the cursor location (or finger location for a touch sensitive screen) was within the boundaries of a graphical object, for example, the displayed box, the computer will execute the process associated with the “enter” command. In this way, graphical objects on the screen create a user interface that permits the user to control the processes operating on the computer.

The system is typically comprised of a central server that is connected by a data network to a user's computer. The central server may be comprised of one or more computers connected to one or more mass storage devices. The precise architecture of the central server does not limit the claimed invention. In addition, the data network may operate with several levels, such that the user's computer is connected through a fire wall to one server, which routes communications to another server that executes the disclosed methods. The precise details of the data network architecture does not limit the claimed invention.

A server may be a computer comprised of a central processing unit with a mass storage device and a network connection. In addition a server can include multiple of such computers connected together with a data network or other data transfer connection, or, multiple computers on a network with network accessed storage, in a manner that provides such functionality as a group. Servers may be virtual servers, each an instance of software operating as an independent server but housed in the same computer hardware. Practitioners of ordinary skill will recognize that functions that are accomplished on one server may be partitioned and accomplished on multiple servers that are operatively connected by a computer network by means of appropriate inter process communication. In addition, the access of the website can be by means of an Internet browser accessing a secure or public page or by means of a client program running on a local computer that is connected over a computer network to the server. A data message and data upload or download can be delivered over the Internet using typical protocols, including TCP/IP, HTTP, SMTP, RPC, FTP or other kinds of data communication protocols that permit processes running on two remote computers to exchange information by means of digital network communication. As a result a data message can be a data packet transmitted from or received by a computer containing a destination network address, a destination process or application identifier, and data values that can be parsed at the destination computer located at the destination network address by the destination application in order that the relevant data values are extracted and used by the destination application.

The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices. Practitioners of ordinary skill will recognize that the invention may be executed on one or more computer processors that are linked using a data network, including, for example, the Internet. In another embodiment, different steps of the process can be executed by one or more computers and storage devices geographically separated by connected by a data network in a manner so that they operate together to execute the process steps. In one embodiment, a user's computer can run an application that causes the user's computer to transmit a stream of one or more data packets across a data network to a second computer, referred to here as a server. The server, in turn, may be connected to one or more mass data storage devices where the database is stored. The server can execute a program that receives the transmitted packet and interpret the transmitted data packets in order to extract database query information. The server can then execute the remaining steps of the invention by means of accessing the mass storage devices to derive the desired result of the query. Alternatively, the server can transmit the query information to another computer that is connected to the mass storage devices, and that computer can execute the invention to derive the desired result. The result can then be transmitted back to the user's computer by means of another stream of one or more data packets appropriately addressed to the user's computer.

Computer program logic implementing all or part of the functionality previously described herein may be embodied in various forms, including, but in no way limited to, a source code form, a computer executable form, and various intermediate forms (e.g., forms generated by an assembler, compiler, linker, or locator.) Source code may include a series of computer program instructions implemented in any of various programming languages (e.g., an object code, an assembly language, or a high-level language such as FORTRAN, C, C++, JAVA, or HTML or scripting languages that are executed by Internet web-broswers) for use with various operating systems or operating environments. The source code may define and use various data structures and communication messages. The source code may be in a computer executable form (e.g., via an interpreter), or the source code may be converted (e.g., via a translator, assembler, or compiler) into a computer executable form.

The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The computer program and data may be fixed in any form (e.g., source code form, computer executable form, or an intermediate form) either permanently or transitorily in a tangible storage medium, such as a semiconductor memory device (e.g., a RAM, ROM, PROM, EEPROM, or Flash-Programmable RAM), a magnetic memory device (e.g., a diskette or fixed hard disk), an optical memory device (e.g., a CD-ROM or DVD), a PC card (e.g., PCMCIA card), or other memory device. The computer program and data may be fixed in any form in a signal that is transmittable to a computer using any of various communication technologies, including, but in no way limited to, analog technologies, digital technologies, optical technologies, wireless technologies, networking technologies, and internetworking technologies. The computer program and data may be distributed in any form as a removable storage medium with accompanying printed or electronic documentation (e.g., shrink wrapped software or a magnetic tape), preloaded with a computer system (e.g., on system ROM or fixed disk), or distributed from a server or electronic bulletin board over the communication system (e.g., the Internet or World Wide Web.) It is appreciated that any of the software components of the present invention may, if desired, be implemented in ROM (read-only memory) form. The software components may, generally, be implemented in hardware, if desired, using conventional techniques.

The described embodiments of the invention are intended to be exemplary and numerous variations and modifications will be apparent to those skilled in the art. All such variations and modifications are intended to be within the scope of the present invention as defined in the appended claims. Although the present invention has been described and illustrated in detail, it is to be clearly understood that the same is by way of illustration and example only, and is not to be taken by way of limitation. It is appreciated that various features of the invention which are, for clarity, described in the context of separate embodiments may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment may also be provided separately or in any suitable combination. It is appreciated that the particular embodiment described in the specification is intended only to provide an extremely detailed disclosure of the present invention and is not intended to be limiting.

It should be noted that the flow diagrams are used herein to demonstrate various aspects of the invention, and should not be construed to limit the present invention to any particular logic flow or logic implementation. The described logic may be partitioned into different logic blocks (e.g., programs, modules, functions, or subroutines) without changing the overall results or otherwise departing from the true scope of the invention. Oftentimes, logic elements may be added, modified, omitted, performed in a different order, or implemented using different logic constructs (e.g., logic gates, looping primitives, conditional logic, and other logic constructs) without changing the overall results or otherwise departing from the true scope of the invention.

Also, while processes or blocks are at times shown as being performed in series, these processes or blocks may instead be performed or implemented in parallel, or may be performed at different times.

Claims

What is claimed:

1. A method for tracking locations of content in a document, said document comprised of content and said document being embodied by a first and second document version and data representing a first machine readable representation of the result of a comparison between the two versions, each of the first and second versions of the document being an individual data file, comprising:

generating for each of the first and second versions of the document, a corresponding first and second data structure embodying a corresponding first and second hierarchical representation of the content of the respective first and second versions of the document each comprising at least one node, said at least one node corresponding to a content data object comprising the respective version of the document and referring to a corresponding location in the respective version of the document and referring to at least one other node in the respective version of the document;

generating a third data structure representing a hierarchical representation of the the first machine readable representation of the result of a comparison, comprising at least one node, said at least one node corresponding to a content data object comprising the machine readable representation of the result of a comparison and referring to a corresponding location in the first machine readable representation of the result of a comparison;

for at least one piece of content comprising the first version of the document, generating a fourth data structure representing a mapping of data representing the location of the at least one piece of content in the first version of the document to data representing the location of the at least one piece of content in the second version of the document by determining a mapping from the data representing the location of the at least one piece of content in the first version of the document to data representing a location in the first machine readable representation of the result of a comparison and determining a mapping from the data representing the location in the first machine readable representation of the result of a comparison to data representing a location in the second version of the document.

2. The method of claim 1 where the determining a mapping step is comprised of sequentially comparing the content referenced by the nodes in the hierarchies of the first version and the first machine readable representation of the result of a comparison and sequentially comparing the content referenced by the nodes in the hierarchies of the first machine readable representation of the result of a comparison and the second version.

3. The method of claim 2 further comprising:

for each mapping, generating two cursors, each corresponding to a respective first and second hierarchies being mapped and each cursor referencing a first node from the first hierarchy and a second node from the second hierarchy;

making a first determination whether a data type associated with the first node may be ignored, and in dependence thereon, advancing the first cursor to the next node in a search sequence of the first hierarchy;

making a second determination whether a data type associated with the second node may be ignored, and in dependence thereon, advancing the second cursor to the next node in a search sequence of the second hierarchy;

in the case where the first and second determinations do not advance either the first or second cursors, making a third determination whether any of the contents of the first and second nodes match and in dependence thereon, storing in a data file data representing the matching contents.

4. The method of claim 1 further comprising:

using the determined mappings to cause content associated with a mapped location on the second version to be displayed as an overlay at the mapped location of the second version upon a condition that such location of the second version is displayed on the user's device.

5. The method of claim 3 further comprising:

modifying the second version by applying an edit represented by the mapped content at the location of the mapped content in the second version.

6. The method of claim 5 further comprising: creating a fifth data structure representing a merging of the four mappings.

7. The method of claim 1 further comprising:

generating a fifth data structure representing a hierarchical representation of the content in a third version of the document;

generating a second machine readable representation of the result of a comparison between the second version and the third version of the document;

generating a data structure representing a hierarchical representation of the content in the second machine readable representation of the result of a comparison; and

determining a mapping from the location of the content in the second version to the location of the content in the second machine readable representation of the result of a comparison and from the location of the content in the second machine readable representation of the result of a comparison to the location of the content in the third version of the document.

8. The method of claim 7 further comprising:

modifying the third version by applying the edit represented by the mapped content at the location of the mapped content in the third version.

9. The method of claim 1 further comprising: creating a fifth data structure representing a merging of the two mappings.

10. The method of claim 1 where the first and second versions of the document are data files of two different document encoding format types.

11. A method for tracking locations of content changes to a document, said document comprised of content and said document being embodied by a first and second version, each an individual data file, comprising:

generating a first and second data structure each embodying a corresponding hierarchical relationship among the content in each of the respective first and second versions of the document said first and second data structures comprising at least one node, said node corresponding to a data object comprising the respective version of the document and each node referring to a location in the respective version of the document and referring to at least one other node in the hierarchy of the respective version of the document;

generating a third version of the document comprising a first machine readable representation of the result of a comparison between the first and the second versions of the document;

generating a third data structure embodying a hierarchical relationship among the content comprising the first machine readable representation of the result of a comparison said third data structure comprising at least one node, said node corresponding to a data object comprising the first machine readable representation of the result of a comparison and referring to a location in the first machine readable representation of the result of a comparison; and

generating a mapping between node locations in the first and second versions of the document by using the third data structure to determine for locations of content in the first hierarchical representation of the first version of the document, the location of the content in the second hierarchical representation of the second version of the document.

12. The method of claim 11 further comprising:

determining the location of a content item in the second version of the document by means of using the location of the content item in the first version of the document as an input to a determination that uses the generated mapping in order to track the position of the content item to its modified location in the second version.

13. The method of claim 12 further comprising:

modifying the second version by applying the edit represented by the mapped content at the location of the mapped content in the second version.

14. The method of claim 11 where the generating a mapping step is further comprised of:

sequentially comparing the content referenced by the nodes in the hierarchies of the first version of the document and the first machine readable representation of the result of a comparison and sequentially comparing the content referenced by the nodes in the hierarchies of the first machine readable representation of the result of a comparison and the second version of the document.

15. The method of claim 14 where the sequential comparing step is comprised of selectively ignoring certain data comprising the content referenced by the nodes in the hierarchies.

16. A method for tracking changes to a document, said document comprised of content and said document being embodied by a first and second versions, each an individual data file, comprising:

generating a comparison output document of the first and second versions of the document;

creating three data structures representing three corresponding hierarchies of the content corresponding to the first and second versions of the document and the comparison output document, respectively, each data structure comprising at least one node, each said node corresponding to a data object comprising the respective first, second or third version of the document and referring to a location in the respective version of the document and referring to at least one other node in the hierarchy representing the respective version of the document;

generating a data structure embodying a mapping of locations of at least one nodes from the hierarchy of representing first version to locations of nodes in the hierarchy representing the comparison output document; and

generating a data structure embodying a mapping of locations of nodes from the hierarchy representing the comparison output document to the corresponding locations of nodes in the hierarchy representing the second version of the document, where each mapping is for content at a content location in the first document that corresponds to content at a location in the second document.

17. The method of claim 16 where the creating step is further comprised of ignoring at least one insertion present in the comparison output document.

18. The method of claim 16 where the creating step is further comprised of ignoring at least one deletions present in the comparison output document.

19. A method for tracking locations of content in a document, said document comprised of content and said document being embodied by a first and second version and data representing a first machine readable representation of the result of a comparison between the two first and second versions, each of the first and second versions of the document an individual data file, comprising:

the step of generating for each of the first and second versions of the document, a corresponding first and second data structure embodying a corresponding first and second hierarchical representation comprised of at least one node comprising a corresponding at least one portion of the content of the document, said node comprised of data referring to a location in the respective version of the document and referring to at least one other node in the respective hierarchy;

the step of generating a third data structure representing a hierarchical representation of the content comprising the first machine readable representation of the result of a comparison, comprising at least one node, said node comprised of data referring to a location in the first machine readable representation of the result of a comparison;

for at least one piece of content present in the first version of the document, the step of generating a fourth data structure representing a mapping of the location of a node comprised of the at least one content to the location of the node comprised of an at least one corresponding content in the second version of the document by means of determining a mapping from the location of the node comprised of the at least one content in the first version of the document to a location of the node comprised of the corresponding at last one content in the first machine readable representation of the result of a comparison and a determining of a mapping from the location of the node comprised of the at least one content in the first machine readable representation of the result of a comparison to the location of the at least one node comprised of the corresponding content in the second version.

20. A computer system comprised of computer memory adapted to track locations of content in a document, said document comprised of content and said document being embodied by a first and second version and a first machine readable representation of the result of a comparison between the two versions, each version of the document and the representation embodied by data stored in the computer memory, comprising:

a first component adapted to generate for each of the first and second versions of the document, corresponding first and second data structures embodying a corresponding first and second hierarchical representation comprised of at least one node corresponding to a data object comprising the content of the respective version of the document, said node comprised of data referring to a location in the respective version of the document and referring to at least one other node in the respective hierarchical representation;

a second component adapted to generate a third data structure representing a hierarchical representation of the content comprising the first machine readable representation of the result of a comparison, comprising at least one node, said node comprised of data referring to a location in the first machine readable representation of the result of a comparison;

a third component adapted to generate, for at least one piece of content present in the first version of the document, a fourth data structure representing a mapping of the location of a node comprised of the at least one piece of content to the location of the node comprised of the at least one piece of content in the second version of the document by means of determining a mapping from the location of the node comprised of the at least one content in the first version of the document to a location of the node comprised of the at least one first corresponding content in the first machine readable representation of the result of a comparison and a determining of a mapping from the location of the node comprised of the first corresponding content in the first machine readable representation of the result of a comparison to the location of the node comprised of a second corresponding at least one content in the second version.

21. The system of claim 20 where the third component is further adapted to sequentially compare the content referenced by the nodes in the hierarchies of the first version and the first machine readable representation of the result of a comparison and sequentially compare the content referenced by the nodes in the hierarchies of the first machine readable representation of the result of a comparison with the second version.

22. The system of claim 21 where the third component is further adapted to:

generate for each mapping, two cursors, each corresponding to a respective first and second hierarchies being mapped and each cursor referencing a first node from the first hierarchy and a second node from the second hierarchy;

make a first determination whether a data type associated with the first node may be ignored, and in dependence thereon, advance the first cursor to the next node in a search sequence of the first hierarchy;

make a second determination whether a data type associated with the second node may be ignored, and in dependence thereon, advance the second cursor to the next node in a search sequence of the second hierarchy;

in the case where the first and second determinations do not advance either the first or second cursors, make a third determination whether any of the contents of the first and second nodes match and in dependence thereon, store in a data file data representing the matching contents.

23. The system of claim 22 further comprised of a fourth component adapted to modify the second version by applying the edit represented by the mapped content at the location of the mapped content in the second version.

24. The system of claim 20 further comprising;

a component adapted to track the location of at least one comment from the first version to the second version by means of using the two determined mappings to identify the location of the comment in the second version.

25. The system of claim 20 where the first and second versions of the document are data files of two different document encoding format types.

26. The system of claim 20 further comprising:

a component adapted to use the determined mappings to cause content associated with a mapped location on the second version to be displayed as an overlay at the mapped location of the second version upon the condition that such location of the second version is displayed on the user's device.