CONTEXT SNIPPET GENERATION FOR BOOK SEARCH SYSTEM

• US 20080208833A1
• Filed: 02/27/2007
• Published: 08/28/2008
• Est. Priority Date: 02/27/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: BASMOV, INNOKENTIY GENNADYEVICH
• Granted Patent: US 7,739,220 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/2452 Query translation

Abstract

A book search system and media for generating a book index corresponding to a collection of books and for providing context snippets related to a search string formulated by a user based on the book index are provided. The book index includes a word hash that represents unique words and an offset to a location list that stores locations for each instance of the unique word. The book search system receives the search string from the user, parses the search string to locate phrases and words, and traverses the book index to generate a list of locations for each word or phrase included in the search string. The book search system utilizes a variable-sized container having a maximum size to store subsets of each word or phrase included in the list of locations to generate the context snippets for the search string.

Claims

1. One or more computer-readable media having computer-executable instructions embodied thereon that perform a method for extracting a phrase related to a book in a collection of books, the method comprising:

receiving a search string having one or more phrases specified by a user, wherein the phrases include one or more words;

parsing the search string to extract each word and word sequence for the one or more phrases;

accessing a book index corresponding to a collection of books to obtain a list of locations for each word in the one or more phrases;

traversing the list of locations to find each word in the word sequence specified by the one or more phrases of the search string; and

generating a phrase list having the location of the one or more phrases of the search string based on the locations included in the list of locations for each word.

2. The media of claim 1, wherein accessing a book index further comprises locating a hash corresponding to each word and loading an offset associated with the hash to obtain the list of locations.

3. The media of claim 1, wherein the phrase list includes deltas to represent similar phrases.

4. The media of claim 1, wherein the location of each phrase is based on the location of at least one word in the phrase.

5. The media of claim 1, further comprising selecting a specific book in the collection of books based on the search string.

6. The media of claim 1, wherein the word sequence includes an enumeration for each phrase in the search string.

7. The media of claim 1, wherein generating a phrase list comprises for each phrase, checking each location corresponding to each word to determine whether the word sequence is satisfied.

8. The media of claim 7, further comprising adding the phrase to the phrase list when the word sequence is satisfied.

9. The media of claim 7, further comprising selecting and checking another phrase included in the search string, when the word sequence is not satisfied.

10. One or more computer-readable media having computer-executable instructions embodied thereon that perform a method for generating a context snippet from a collection of books, the method comprising:

generating a variable-sized container, associated with a maximum size, to store snippets corresponding to the collection of books based on a search string;

traversing a book index to search the collection of books and to generate a list of locations for words or phrases included in the search string;

checking the list of locations for words or phrases to determine that the list of locations for words or phrases is not empty;

generating an empty variable-sized container, when the list of locations for words or phrases is empty;

checking the variable-sized container to determine that a current size of the variable-sized container is less than the maximum size, when the list of locations for words or phrases is not empty;

moving one or more words or phrases from the list of locations for words or phrases to the variable-sized container and increasing a match count, when the current size of the variable-sized container is less than the maximum size;

removing one or more words from the variable-sized container and decreasing the match count, when the current size of the variable-sized container is greater than the maximum size; and

communicating the variable-sized container, in response to the search string.

11. The media of claim 10, further comprising counting a number of unique words in the variable-sized container that are included in the search string.

12. The media of claim 10, further comprising generating a rank for the variable-sized container based on the match count and the number of unique words in the variable-sized container that are included in the search string.

13. The media of claim 12, wherein communicating the variable-sized container, in response to the search string further comprises communicating the variable-sized container based on the rank.

14. The media of claim 10, wherein communicating the variable-sized container, in response to the search string further comprises checking the variable-sized container to determine that a current size of the container is less than the maximum size.

15. The media of claim 14, further comprising adding words that are within half of a difference between the maximum size and the current size to the beginning or end of the variable-sized container, when the current size is less than the maximum size.

16. The media of claim 10, wherein the list of locations for words or phrases is a stack.

17. The media of claim 10, wherein the variable-sized container is one of a queue or double-ended queue.

18. A book search system having one or more computer-readable media configured to provide a data structure for processing searches related to a collection of books, the data structure comprising:

one or more headers to store a hash for each unique word in the collection of books and an offset to a location list that provides the location of each instance of the unique word;

the location list is accessible via the offset and includes word location and character location pairs for each instance of each unique word in the collection of books, wherein word locations and character locations of each subsequent instance is represented as delta to a previous instance of the unique word; and

the location list is searchable to obtain all locations for each word included in a search string.

19. The book search system of claim 18, wherein the header is sorted based on the hash for each unique word.

20. The book search system of claim 18, wherein each book in the collection of books has a corresponding header.