Abstract generating search method and system

• US 9,367,605 B2
• Filed: 08/27/2010
• Issued: 06/14/2016
• Est. Priority Date: 09/23/2009
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Alibaba Group Holding Ltd.
• Inventors: Luo, Yi
• Primary Examiner(s): Ahn, Sangwoo
• Application Number:
  US12/937,562
• Publication Number:
  US 20110218989A1
• Time in Patent Office: 2,118 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/345 Summarisation for human users

Abstract

The present disclosure provides an information search method and system applicable in an information search system wherein each document has corresponding forward index data to address the issue of low search efficiency suffered by existing information search techniques. In one aspect, the method may include: receiving an inquiry word and obtaining one or more keywords contained in the inquiry word by segmentation; searching one or more documents matching the one or more keywords and forward index data corresponding to the one or more documents through the information search system'"'"'s inverted index data; and determining an abstract of each of the one or more documents according to a corresponding document'"'"'s forward index data, and outputting the abstract and information of the one or more documents as a search result. The proposed techniques can increase efficiency of information search and, at the meantime, guarantee accuracy of the search to a certain extent.

Claims

1. A method comprising:

receiving, by a computing device, an inquiry word;

segmenting, by the computing device, the inquiry word into one or more keywords;

searching, by the computing device, an inverted index of a group of documents to determine in the group one or more documents in which one or more of the keywords are matched; and

searching, by the computing device, a forward index of a respective document of the determined one or more documents to generate an abstract for the respective document, the searching including;

determining a length limit of the abstract;

identifying a plurality of portions within the respective document, each portion of the plurality of portions including a respective beginning position in the respective document and a respective ending position in the respective document, the identifying including identifying, within the respective document, every portion that is within the length limit by traversing the forward index character-by-character or word-by-word;

finding a portion among the plurality of portions, the portion including a highest number of the one or more keywords between a beginning position and an ending position compared with any other portion of the plurality of portions; and

selecting the found portion to be the abstract of the respective document.

2. The method of claim 1, wherein each portion has a length that does not exceed the length limit.

3. The method of claim 2, wherein, when multiple portions in the plurality of portions each include the highest number of the one or more keywords, the abstract is one of the multiple portions that has a greatest total number of the keywords, including keywords that are repeated.

4. The method of claim 1, wherein the identifying the plurality of portions within the respective document comprises:

traversing, by the computing device, at least one word in the forward index of the respective document;

recording, by the computing device, the at least one traversed word and a location of the at least one traversed word in a first data structure by using the location of the traversed word as an index of the first data structure; and

when the at least one traversed word matches one of the keywords, recording, by the computing device, the at least one traversed word and the location of the at least one traversed word in a second data structure by using the at least one traversed word as an index of the second data structure.

11. The method of claim 1, further comprising outputting, by the computing device, the abstract as a search result.

12. The method of claim 11, further comprising:

ranking, by the computing device, abstracts of multiple determined documents based on a number of the keywords from the inquiry word that are matched in each of the documents; and

outputting, by the computing device, the ranked abstracts according to a predetermined data format.

19. The method of claim 4, wherein the finding the portion among the plurality of portions comprises:

determining, by the computing device, the beginning position of the portion and the ending position of the portion according to the first data structure, the second data structure, and the length limit, the determining including;

in response to determining that a total length of traversed words in the first data structure is less than the length limit, setting the beginning position to a location of a first traversed word in the first data structure and setting the ending position to a location of a last traversed word in the first data structure;

or

in response to determining that the total length of traversed words in the first data structure is not less than the length limit, utilizing the second data structure to determine one or more portions of the respective document that have lengths less than the length limit, to determine the portion of the one or more portions that has the highest number of the one or more keywords, and to set the beginning position and ending position of the portion based on the locations of a first traversed word and a last traversed word, respectively, in the portion.

5. A system comprising:

one or more data processing devices; and

one or more tangible computer-readable storage media having stored thereon computer executable components comprising;

a storage module configured to store an inverted index of documents in the system and forward indices corresponding to each of the documents;

an input module configured to receive an inquiry word; and

a search module configured to segment the inquiry word into one or more keywords, search the inverted index to determine one or more documents in which one or more of the keywords are matched, search a forward index of a respective document of the determined one or more documents to generate an abstract for the respective document, the search including;

determining a length limit of the abstract;

identifying a plurality of portions within the respective document, each portion of the plurality of portions including a respective beginning position in the respective document and a respective ending position in the respective document, the identifying including identifying, within the respective document, every portion that is within the length limit by traversing the forward index character-by-character or word-by-word;

finding a portion among the plurality of portions, the portion including a highest number of the one or more keywords between a beginning position and an ending position compared with any other portion of the plurality of portions; and

selecting the found portion to be the abstract of the respective document.

6. The system of claim 5, wherein each portion has a length that does not exceed the length limit.

7. The system of claim 6, wherein, when multiple portions in the plurality of portions each include the highest number of the one or more keywords, the abstract is one of the multiple portions that has a greatest total number of the keywords, including keywords that are repeated.

8. The system of claim 5, wherein the search module further comprises:

a search sub-module configured to segment the inquiry word into the one or more keywords, and determine the one or more documents matching the one or more keywords based on the inverted index;

an abstract generation sub-module configured to

traverse at least one word in the forward index of the respective documents,

record the at least one traversed word and a location of the at least one traversed word in a first data structure by using the location of the traversed word as an index of the first data structure;

when the at least one traversed word matches one of the keywords, record the traversed word and the location of the at least one traversed word in a second data structure by using the at least one traversed word as an index of the second data structure;

determine the beginning position of the abstract and the ending position of the abstract according to the first data structure, the second data structure, and the length limit, wherein;

in response to determining that a total length of traversed words in the first data structure is less than the length limit, set the beginning position to a location of a first traversed word in the first data structure and set the ending position to a location of a last traversed word in the first data structure;

or

in response to determining that the total length of traversed words in the first data structure is not less than the length limit, utilize the second data structure to determine one or more portions of the respective document that have lengths less than the length limit, to determine the portion of the one or more portions that has the highest number of the one or more keywords, and to set the beginning position and ending position of the portion based on the locations of a first traversed word and a last traversed word, respectively, in the portion; and

generate the abstract according to the determined beginning position and the ending position; and

a submission sub-module configured to submit to an output module the generated abstracts.

13. The system of claim 5, further comprising an output module configured to output the abstract as a search result.

14. The system of claim 13, wherein the output module:

ranks abstracts of multiple determined documents based on a number of the keywords from the inquiry word that are matched in each of the documents; and

outputs the ranked abstracts according to a predetermined data format.

9. One or more tangible computer-readable storage media having computer-executable instructions stored thereon that are configured to program one or more computing devices to perform operations comprising:

receiving an inquiry word;

segmenting the inquiry word into one or more keywords;

searching an inverted index of a group of documents to determine in the group one or more documents in which one or more of the keywords are matched; and

searching a forward index of a respective document of the determined one or more documents to generate an abstract for the respective document, the searching including;

determining a length limit of the abstract;

identifying a plurality of portions within the respective document, each portion of the plurality of portions including a respective beginning position in the respective document and a respective ending position in the respective document, the identifying including identifying, within the respective document, every portion that is within the length limit by traversing the forward index character-by-character or word-by-word;

finding a portion among the plurality of portions, the portion including a highest number of the one or more keywords between a beginning position and an ending position compared with any other portion of the plurality of portions; and

selecting the found portion to be the abstract of the respective document.

10. The one or more tangible computer-readable storage media of claim 9, wherein the identifying the plurality of portions within the respective document comprises:

traversing, by the computing device, at least one word in the forward index of the respective document;

recording, by the computing device, the at least one traversed word and a location of the at least one traversed word in a first data structure by using the location of the traversed word as an index of the first data structure; and

when the at least one traversed word matches one of the keywords, recording, by the computing device, the at least one traversed word and the location of the at least one traversed word in a second data structure by using the at least one traversed word as an index of the second data structure.

15. The one or more tangible computer-readable storage media of claim 9, wherein the operations further comprise outputting the abstract as a search result.

16. The one or more tangible computer-readable storage media of claim 15, wherein the operations further comprise:

ranking, by the computing device, abstracts of multiple determined documents based on a number of the keywords from the inquiry word that are matched in each of the documents; and

outputting, by the computing device, the ranked abstracts according to a predetermined data format.

17. The one or more tangible computer-readable storage media of claim 9, wherein each portion has a length that does not exceed the length limit.

18. The one or more tangible computer-readable storage media of claim 17, wherein, when multiple portions in the plurality of portions each include the highest number of the one or more keywords, the abstract is the one of the multiple portions that has a greatest total number of the keywords, including keywords that are repeated.

20. The one or more tangible computer-readable storage media of claim 10, wherein the finding the portion among the plurality of portions comprises:

determining, by the computing device, the beginning position of the portion and the ending position of the portion according to the first data structure, the second data structure, and the length limit, the determining including;

in response to determining that a total length of traversed words in the first data structure is less than the length limit, setting the beginning position to a location of a first traversed word in the first data structure and setting the ending position to a location of a last traversed word in the first data structure;

or

in response to determining that the total length of traversed words in the first data structure is not less than the length limit, utilizing the second data structure to determine one or more portions of the respective document that have lengths less than the length limit, to determine the portion of the one or more portions that has the highest number of the one or more keywords, and to set the beginning position and ending position of the portion based on the locations of a first traversed word and a last traversed word, respectively, in the portion.