Systems and methods for extracting phases from text

• US 8,812,508 B2
• Filed: 12/14/2007
• Issued: 08/19/2014
• Est. Priority Date: 12/14/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company), Shanghai Hewlett-Packard Co., Ltd. (Hewlett-Packard Enterprise Company), Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Zhang, Li, Xiong, Yuhong, Wang, Wei-Chun
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Rayyan, Susan F
• Application Number:
  US12/738,844
• Publication Number:
  US 20100293159A1
• Time in Patent Office: 2,440 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

Systems and methods for extracting phrases from text are disclosed. In an exemplary embodiment, a method may include preprocessing desired phrases into at least one phrase indexing data structure for efficient matching. The method may also include scanning text to construct a hash table including keys and corresponding entries. The method may also include locating suffix trie trees for each word in the hash table. The method may also include matching each position in the hash table against the suffix trie trees, and outputting phrases matched in the scanned text.

Claims

1. A method for extracting phrases from text, comprising,

preprocessing desired phrases into at least one phrase indexing data structure for efficient matching;

during preprocessing building suffix trie trees, wherein one of the suffix trite trees is built at a word level, and then an order of words is reversed to build another one of the suffix tile trees;

after preprocessing, scanning text to construct a hash table including keys and corresponding entries;

locating suffix trie trees in the at least one phrase indexing data structure for each word in the hash table;

matching each position in the hash table against the suffix trie trees; and

outputting phrases matched in the scanned text.

2. The method of claim 1 wherein preprocessing further includes identifying a keyword for each of the desired phrases.

3. The method of claim 2 wherein the keyword is a word appearing least frequent in a typical text.

4. The method of claim 2 wherein preprocessing further includes grouping the desired phrases by keyword.

5. The method of claim 2 wherein preprocessing further includes breaking each phrase at a first encountered keyword.

6. The method of claim 1 wherein preprocessing further includes building the suffix trie trees and storing the suffix trie trees in the at least one phrase indexing data structure.

7. The method of claim 1 wherein preprocessing further comprises reducing false positives using related phrases.

8. The method of claim 7 further comprising determining relevance of the related phrases to the desired phrases.

9. The method of claim 1 further comprising selecting top related phrases for each desired phrase based on relevance.

10. The method of claim 1 further comprising during preprocessing:

grouping all the desired phrases by keyword;

breaking each phrase at a first encountered keyword obtaining p_i and s_i;

building suffix trie trees st(w) and pt(w), wherein the suffix trie tree st(w) is built at a word level and then order of words in p_i is reversed to obtain q_i, wherein the suffix trie tree pt(w) is but on q_i;

indexing the suffix trie trees st(w) and pt(w) by keyword.

11. The method of claim 1 wherein the at least one phrase indexing data structure is an overall index of a document.

12. A system for extracting phrases from text, comprising:

at least one phrase indexing data structure residing in non-transitory computer readable media, the at least one phrase indexing data structure including desired phrases;

program code stored on non-transitory computer readable media and executable by a processor for improving accuracy of matches in scanned text by reducing false positives using phrases related to the scanned text, the preprocessing program code building suffix trie trees, wherein one of the suffix trie trees is built at a word level, and then an order of words is reversed to build another one of the suffix trie trees;

a hash table constructed in non-transitory computer readable media, the hash table including keys and corresponding entries; and

program code stored on non-transitory computer readable media and executable by a processor for locating suffix trie trees for each word in the hash table and matching each position in the hash table against the suffix trie trees to match phrases in the scanned text.

13. The system of claim 12 wherein the keyword for each of the desired phrases is identified.

14. The system of claim 12 wherein the keyword is a word appearing least frequent in a typical text.

15. The system of claim 14 wherein the desired phrases are grouped by keyword.

16. The system of claim 14 wherein each phrase is broken at a first encountered keyword.

17. The system of claim 12 wherein the hash table includes keys and corresponding entries, the keys being words contained in the text and the corresponding entries being the list of positions of the words in the text.

18. The system of claim 12 wherein the program code executes a preprocessing operation to improve accuracy of matches by reducing false positives using related phrases.

19. The system of claim 12 wherein phrases extracted from text are movie titles, book titles, album names, or sport team names.

20. The system of claim 12 wherein a desired phrase is extracted from a large database.

21. A system for extracting movie titles from web-based text, comprising:

memory means for storing at least one phrase indexing data structure including desired movie titles;

preprocessing means for improving accuracy of matches of movie titles in the web-based text by reducing false positives using phrases related to the movie titles, the preprocessing means building suffix trie trees, wherein one of the suffix trie trees is built at a word level, and then an order of words is reversed to build another one of the suffix trie trees;

table means for storing keys and corresponding entries, the keys representing words in the web-based text, and the entries representing a list of positions of the words in the web-based text; and

means for locating suffix trie trees for each word in the table means and matching each position in the table means against the suffix trie trees to match movie titles in a scanned web-based text.