Annotation mapping

• US 9,275,368 B1
• Filed: 09/25/2012
• Issued: 03/01/2016
• Est. Priority Date: 09/25/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Harpalani, Manoj Suresh, Bacus, Michael Patrick, Deyell, Shawn C., Yacoub, Sherif M., Shafer, Daniel W., Datar, Ameya B.
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): Sheffield, Hope C
• Application Number:
  US13/626,814
• Time in Patent Office: 1,253 Days
• Field of Search: 715/289, 715/22
• US Class Current: 1/1
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A method for annotation mapping includes identifying a set of differences between a first version of a document and a second version of the document, the first version comprising annotations. The method further includes generating a position map that maps differences between the first version and the second version, where the position map facilitates the migration of the annotations from the first version to the second version.

Claims

1. A method comprising:

receiving, via a processing device, a new document version corresponding to an old document version, wherein the old document version is associated with a plurality of user-generated annotations, each user-generated annotation being mapped to a particular portion of the old document version;

aligning, via the processing device, words in the new document version with words in the old document version;

determining, via the processing device, differences between the new document version and the old document version using the aligned words, the differences comprising a word having an original position in the old document version and the word having a new position in the new document version, where the original position is different than new position;

generating, via the processing device, an entry in a position map, wherein the entry maps a first byte offset of the original position of the word in the old document version to a second byte offset of the new position of the word in the new document version, the entry comprising the word, the first byte offset, and the second byte offset; and

causing, via the processing device, the user-generated annotations to be transferred to the new document version based on the position map.

2. The method of claim 1, wherein each of the differences has an associated difference type comprising at least one of insertion, deletion, change, transposition, typographical error, split word, merged word, formatting change or style change.

3. The method of claim 1, wherein causing the user-generated annotations to be transferred to the new document version based on the position map comprises:

determining, for each user-generated annotation, a position within the old document version that corresponds with the particular portion of the old document version to which the user-generated annotation is mapped;

identifying, based on the position map, a position within the new document version that maps to the position within the old document version; and

associating the user-generated annotation with the identified position within the new document version.

4. The method of claim 1, wherein causing the user-generated annotations to be transferred to the new document version based on the position map comprises:

sending the position map to a user device, wherein the user device uses the position map to transfer the user-generated annotations to the new document.

5. The method of claim 1, wherein the position map is at least one of a forward position map that maps differences from the old document version to the new document version, or a reverse position map that maps differences from the new document version to the old document version.

6. A method comprising:

receiving a new document version corresponding to an old document version, wherein the old document version is associated with a plurality of user-generated annotations, each user-generated annotation being mapped to a particular position within the old document version;

identifying, by a processing device, a position map that maps differences between the old document version and the new document version, the differences comprising a word having an original position in the old document version and the word having a new position in the new document version, where the original position is different than new position, wherein the position map comprises an entry, the entry comprising the word, a first byte offset of the original position of the word in the old document version, and a second byte offset of the new position of the word in the new document version;

determining, based on the position map, a position of a user-generated annotation of the plurality of user-generated annotations within the new document version that maps to a position within the old document version that corresponds with the user-generated annotation; and

associating, by the processing device, the user-generated annotation with the determined position within the new document version to transfer the user-generated annotation to the new document version.

7. The method of claim 6, wherein each of the differences has an associated difference type comprising at least one of insertion, deletion, change, transposition, typographical error, split word, merged word, formatting change or style change.

8. The method of claim 6, wherein identifying the position map that maps differences between the old document version and the new document version comprises:

receiving the position map from a server.

9. The method of claim 6, wherein identifying the position map that maps differences between the old document version and the new document version comprises:

aligning words in the new document version to words in the old document version;

determining the differences between the new document version and the old document version using the aligned words; and

generating the position map that maps the original position of the word in the old document version to the new position of the word in the new document version.

10. The method of claim 6, wherein the position map is at least one of a forward position map that maps differences from the old document version to the new document version, or a reverse position map that maps differences from the new document version to the old document version.

11. A system comprising:

a processing device;

a memory having stored therein instructions which, when executed by the processing device, cause the processing device to;

receive, from a client device, a request for annotations associated with a first version of a document, wherein the client device has a second version of the document that is different from the first version;

select a difference position map that indicates differences between the first version and the second version, the differences comprising a word having an original position in the first version of the document and the word having a new position in the second version of the document, where the original position is different than new position, wherein the difference position map comprises an entry, the entry comprising the word, a first byte offset of the original position of the word in the first version of the document, and a second byte offset of the new position of the word in the second version of the document;

transfer the annotations from the first version of the document to the second version of the document based on the difference position map; and

transmit the transferred annotations to the client device in response to the request.

12. The system of claim 11, wherein the difference position map is generated using a difference algorithm that computes differences between words using a longest common sequence of words and a fuzzy string match algorithm that computes differences between words using fuzzy word similarity matrix.

13. The system of claim 12, wherein the instructions, when executed by the processing device, further cause the processing device to:

when the difference algorithm is unable to compute a difference between a sequence of words, applying the fuzzy string match algorithm to the sequence of words.

14. The system of claim 13, wherein the difference position map is generated by iterating over the first version and the second version based on a size of the sequence of words.

15. The system of claim 13, wherein the instructions, when executed by the processing device, further cause the processing device to:

expand or shrink a size of the sequence of words when a first sequence in the first version and a corresponding second sequence in the second version are below a similarity threshold.

16. The system of claim 11, wherein the difference position map further indicates at least one of a position for each difference, a difference type for each difference, or a length of each difference.

17. The system of claim 11, wherein the difference position map comprises positions of words in the first version and positions of corresponding words in the second version.

18. The system of claim 11, wherein the difference position map is selected from a set of difference position maps for a plurality of document versions.

19. A non-transitory computer-readable storage medium having stored therein instructions which, when executed by a processing device, cause the processing device to perform operations comprising:

aligning, by the processing device, words in a first version of a document with words in a second version of the document, the first version comprising annotations;

identifying differences between the first version of the document and the second version of the document, the differences comprising a word having an original position in the first version of the document and a new position in the second version of the document; and

generating, by the processing device, an entry in a position map, wherein the entry that maps a first byte offset of the original position of the word in the first version of the document to a second byte offset of the new position of the word in the second version of the document, the entry comprising the word, the first byte offset, and the second byte offset, the position map facilitating a transfer of the annotations from the first version to the second version.

20. The non-transitory computer-readable storage medium of claim 19, wherein generating the position map comprises:

determining a type for each of the differences;

determining that a difference comprises a split word; and

aligning an old word in the first version with new words in the second version.

21. The non-transitory computer-readable storage medium of claim 19, wherein generating alignments further comprises:

determining that a difference is not an insert or a delete, a small replacement, a split word, or a merge word; and

applying a word sequence alignment algorithm to generate an alignment for the difference.

22. The non-transitory computer-readable storage medium of claim 21, wherein the word sequence alignment algorithm is customized for aligning word sequences, wherein the word sequence alignment algorithm outputs a word similarity matrix.

23. The non-transitory computer-readable storage medium of claim 19, wherein the instructions, when executed by a processing device, further cause the processing device to perform operations comprising:

cleaning the differences.

24. The non-transitory computer-readable storage medium of claim 23, wherein cleaning the set of differences comprises at least one of:

merging differences that are less than a distance threshold apart; and

identifying and removing false positive matches.