SYSTEMS AND METHODS FOR EXTRACTING PHASES FROM TEXT

• US 20100293159A1
• Filed: 12/14/2007
• Published: 11/18/2010
• 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: Wang, Wei-Chun, Zhang, Li, Xiong, Yuhong
• Granted Patent: US 8,812,508 B2
• Time in Patent Office: Days
• US Class Current: 707/728
• 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;

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

locating suffix trie trees 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 9 further comprising selecting top related phrases for each desired phrase based on relevance.

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

at least one phrase indexing data structure residing in memory, the at least one phrase indexing data structure including desired phrases;

a hash table constructed in memory, the hash table including keys and corresponding entries; and

program code 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 a scanned text.

11. The system of claim 10 wherein the keyword for each of the desired phrases is identified.

15. The system of claim 10 wherein the suffix trie trees are stored in the hash table.

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

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

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

19. The system of claim 10 wherein a desired phrase is extracted from a large database.

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

13. The system of claim 12 wherein the desired phrases are grouped by keyword.

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

20. 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;

table means for storing keys and corresponding entries; and

means 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 movie titles in a scanned web-based text.

21. The system of claim 20 further comprising 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.