Aligning content items to identify differences

• US 9,069,767 B1
• Filed: 03/17/2011
• Issued: 06/30/2015
• Est. Priority Date: 12/28/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Hamaker, Janna, Killalea, Tom, Weight, Christopher F., Rausch, Daniel B., Posokhow, Bruno A.
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US13/050,829
• Time in Patent Office: 1,566 Days
• Field of Search: 707/756
• US Class Current: 1/1
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

Techniques for aligning content items with one another are described herein. These techniques may align different versions of a same content item for the purpose of identifying differences between the versions, identifying commonalities between the versions, mapping annotations made in one version to the other version, aggregating annotations across the different versions, or for any other reason. The content items may include electronic books, songs, videos, documents, or the like.

Claims

1. One or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

determining an overall similarity between a first electronic book and a second electronic book;

determining that the overall similarity is less than a first overall similarity threshold and greater than a second overall similarity threshold;

selecting a first string of words of the first electronic book and a second string of words of the second electronic book;

comparing the first string of words to the second string of words;

determining that a similarity in alignment between the first string of words and the second string of words is greater than an alignment threshold based at least in part on the comparing;

selecting a third string of words of the first electronic book at a predetermined location relative to the first string of words;

identifying a fourth string of words of the second electronic book at the predetermined location relative to the second string of words;

determining a similarity metric between the third string of words and the fourth string of words; and

performing word-to-word matching between the third string of words and the fourth string of words, based at least in part on the similarity metric being greater than a predetermined threshold.

2. One or more non-transitory computer-readable media as recited in claim 1, the acts further comprising:

determining that no difference exists between a word at an end of the first string of words and a word at an end of the second string of words; and

wherein the performing of the word-to-word matching occurs at least partly in response to determining that no difference exists between the word at the end of the first string of words and the word at the end of the second string of words.

3. One or more non-transitory computer-readable media as recited in claim 1, the acts further comprising:

determining that a difference does exist between a word at the end of the first string of words and a word at the end of the second string of words;

selecting a different string of words of the first electronic book and a different string of words of the second electronic book, at least one of the different strings of words including the determined difference;

comparing the different string of words of the first electronic book to the different string of words of the second electronic book; and

determining a similarity in alignment between the different string of words of the first electronic book and the different string of words of the second electronic book based at least in part on the comparing.

4. One or more non-transitory computer-readable media as recited in claim 1, the acts further comprising:

at least partly in response to determining that the overall similarity is greater than the first overall similarity threshold, performing word-to-word matching between words of the first electronic book and words of the second electronic book.

5. One or more non-transitory computer-readable media as recited in claim 1, wherein a size of strings of words of the first and second electronic books is selected based at least in part on the overall similarity.

6. One or more non-transitory computer-readable media as recited in claim 1, the acts further comprising:

at least partly in response to determining that the overall similarity is less than the first and second overall similarity thresholds but greater than a third overall similarity threshold, partitioning the first and second electronic books into multiple discrete portions and repeating the determining of the overall similarity for each of the multiple discrete portions; and

at least partly in response to determining that the overall similarity is less than the first, second, and third overall similarity thresholds, indicating that the first and second electronic books are dissimilar.

7. One or more non-transitory computer-readable media as recited in claim 1, wherein the first electronic book comprises a first version of a particular book and the second electronic book comprises a second version of the particular book.

8. A method comprising:

under control of one or more computer systems configured with specific executable instructions,

associating a first string of words of a first version of an electronic book with a first position within the first version of the electronic book;

identifying a second string of words of a second version of the electronic book that correspond to the first string of words of the first version of the electronic book;

associating the second string of words of the second version of the electronic book with a second position within the second version of the electronic book, wherein the first version of the electronic book is in a same electronic book format as the second version of the electronic book;

aligning the first string of words of the first version of the electronic book with the second position of the second string of words of the second version of the electronic book; and

mapping the second string of words of the second version of the electronic book to the first position within the first version of the electronic book based at least in part on the aligning.

9. The method as recited in claim 8, further comprising:

identifying an object associated with a particular position within the first version of the electronic book;

identifying, based at least in part on the mapping, a particular position within the second version of the electronic book that corresponds to the particular position within the first version of the electronic book; and

associating the object to the particular position within the second version of the electronic book.

10. The method as recited in claim 8, wherein the aligning comprises:

selecting the first string of words of the first version and the second string of words of the second version for comparison;

determining an alignment of the first string of words of the first version and the second string of words of the second version; and

in response to the alignment being greater than a threshold, matching at least some words of the first version that are subsequent to the first string of words of the first version with respective words that are subsequent to the second string of words of the second version.

11. The method as recited in claim 10, wherein the determining of the alignment comprises comparing the first string of words of the first version and the second string of words of the second version using an algorithm that is based at least in part on the Needleman-Wunsch algorithm or the Smith-Waterman algorithm.

12. The method as recited in claim 10, wherein in response to the matching at least some of the words of the first version with respective words of the second version comprises:

determining that a word of the first version that is immediately subsequent to the string of words of the first version does not match a word of the second version that is immediately subsequent to the string of words of the second version;

selecting a different string of words of the first version and a different string of words of the second version for comparison; and

determining an alignment of the different string of words of the first version and the different string of words of the second version.

13. The method as recited in claim 8, further comprising:

identifying differences between the first string of words of the first version of the electronic book and the corresponding second string of words of the second version of the electronic book; and

mapping the differences to the first position within the first version of the electronic book.

14. The method as recited in claim 8, further comprising:

identifying an annotation associated with the corresponding second string of words of the second version of the electronic book; and

associating the annotation with the first position within the first version of the electronic book.

15. The method as recited in claim 8, further comprising:

determining that the second version of the electronic book is in a different language to the first version of the electronic book; and

wherein the aligning accounts for the different languages.

16. The method as recited in claim 8, further comprising:

identifying punctuation and white space differences in the corresponding second string of words of the second version of the electronic book relative to the first string of words of the first version of the electronic book; and

mapping the differences to the first position within the first version of the electronic book.

17. A method comprising:

under control of one or more computer systems configured with specific executable instructions,

calculating an overall similarity between a first content item and a second content item;

aligning the first content item with the second content item based at least in part on the overall similarity being greater than a predetermined threshold;

identifying an annotation that has been associated with a particular position within the first content item by a user that previously accessed the first content item;

determining a position in the second content item that corresponds to the particular position within the first content item at least partly based on the aligning; and

associating the annotation with the position in the second content item at least partly based on the determining.

18. The method as recited in claim 17, further comprising:

determining that the first content item is an audio eBook; and

wherein the corresponding particular position within the first content item is identified as a time index associated with the audio eBook.

19. The method as recited in claim 17, wherein the first content item comprises a first version of a particular book and the second content item comprises a second version of the particular book;

and

further comprising, determining that the second content item is in a different language to the first content item; and

wherein the aligning accounts for the different languages.

20. A system comprising:

one or more processors;

memory;

one or more modules, stored in the memory and executable on the one or more processors to;

determine an overall similarity between a first electronic book and a second electronic book;

select a string of words of the first electronic book and a string of words of the second electronic book based at least in part on the overall similarity being less than a first overall similarity threshold and greater than a second overall similarity threshold;

determine a similarity in alignment for the string of words of the first electronic book and the string of words of the second electronic book;

at least partly in response to the similarity in alignment being greater than an alignment threshold, determine a similarity metric for words subsequent to the string of words of the first electronic book and words subsequent to the string of words of the second electronic book; and

performing word-to-word matching between the words subsequent to the string of words of the first electronic book and the words subsequent to the string of words of the second electronic book, based at least in part on the similarity metric being greater than a predetermined threshold.

21. The system as recited in claim 20, wherein the one or more modules are further executable on the one or more processors to:

at least partly in response to the similarity in alignment being less than the threshold;

compare a different string of words of the first electronic book to a different string of words of the second electronic book; and

determine a similarity in alignment between the different string of words of the first electronic book and the different string of words of the second electronic book.

22. The system as recited in claim 20, wherein the one or more modules are further executable on the one or more processors to:

identify differences between the string of words of the first electronic book and the string of words of the second electronic book based at least in part on the comparing.

23. The system as recited in claim 20, wherein the one or more modules are further executable on the one or more processors to:

determine that the word subsequent to the string of words of the first electronic book matches the word subsequent to the string of words of the second electronic book;

expand the string of words of the first electronic book to include the word subsequent to the string of words of the first electronic book;

expand the string of words of the second electronic book to include the word subsequent to the string of words of the second electronic book; and

determine a similarity of a word subsequent to the expanded string of words of the first electronic book and a word subsequent to the expanded string of words of the second electronic book until a mismatch or an end of one of the electronic books is found.

24. The system as recited in claim 20, wherein the one or more modules are further executable on the one or more processors to:

at least partly in response to the word subsequent to the string of words of the first electronic book not matching the word subsequent to the string of words of the second electronic book;

compare a different string of words of the first electronic book to a different string of words of the second electronic book; and

determine a similarity in alignment between the different string of words of the first electronic book and the different string of words of the second electronic book.

25. The system as recited in claim 20, wherein the one or more modules are further executable on the one or more processors to:

determine an alignment between the first electronic book and the second electronic book based at least in part on matching the word subsequent to the string of words of the first electronic book with the word subsequent to the string of words of the second electronic book;

determine that the first electronic book has an annotation that has been associated by a user with a particular position in the first electronic book; and

associate the annotation with a corresponding position in the second electronic book based at least in part on the alignment between the first electronic book and the second electronic book.

26. The system as recited in claim 25, wherein the annotation comprises a comment, a highlight, or marking made by a user that previously accessed the first electronic book.

27. The system as recited in claim 25, wherein the particular position in the first electronic book and the corresponding position in the second electronic book comprise invariant reference locators.

28. The system as recited in claim 20, wherein the determining the similarity in alignment is performed with use of at least one of a global alignment algorithm or a local alignment algorithm.