Context snippet generation for book search system

• US 7,739,220 B2
• Filed: 02/27/2007
• Issued: 06/15/2010
• 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
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Fan; Shiow-Jy
• Application Number:
  US11/679,499
• Publication Number:
  US 20080208833A1
• Time in Patent Office: 1,204 Days
• Field of Search: 707 3- 4, 707/5, 707/8, 707/10, 707/104.1, 707/E17.05, 705/26
• US Class Current: 707/771
• 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 storage 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, wherein accessing a book index comprises locating a hash corresponding to each word and loading an offset associated with the hash to obtain the list of locations;

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

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; and

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

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

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

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

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

6. 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.

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

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

9. A book search system having one or more computer-readable storage 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;

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

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

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

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

12. One or more computer-readable storage 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 that includes unstructured books, which lack markup language tags, to obtain a list of locations for each word in the one or more phrases, wherein accessing a book index comprises locating a hash corresponding to each word and loading an offset associated with the hash to obtain the list of locations;

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

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; and

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