Matching large sets of words

• US 9,659,059 B2
• Filed: 09/08/2015
• Issued: 05/23/2017
• Est. Priority Date: 07/20/2012
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Fuchs, Matthew
• Primary Examiner(s): Vo, Huyen
• Assistant Examiner(s): Wang, Yi-Sheng
• Application Number:
  US14/847,769
• Publication Number:
  US 20160019204A1
• Time in Patent Office: 623 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2219 Large Object storage; Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/279 Recognition of textual entities

Abstract

Word phrases are stored in a phrase structure. Each word is stored as a keyword in a keyword structure. Each keyword is associated with usage attributes identifying use of a word in a word phrase. Any preceding words associated with a keyword, and a mapping from any preceding words to a word phrase, is stored for each word. A word string is input. Match attributes are updated in a match structure if a word in the word string matches any keyword and if any preceding words associated with any matching keyword includes a preceding word which precedes the word in the word string. The match attributes indicate use of the matching word in the word string and in a word phrase. Whether a word phrase is present in the word string is determined based on the usage attributes and the match attributes associated with multiple matching words.

Claims

1. A system for matching large sets of words, the system comprising:

one or more processors; and

a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to;

store a plurality of word phrases in a phrase-based data structure;

store each word in the phrase-based data structure as a corresponding keyword in a keyword-based data structure, wherein each corresponding keyword is associated with corresponding usage attributes identifying use of a corresponding word in a corresponding word phrase in the phrase-based data structure;

store, for each word in the phrase-based data structure, any corresponding preceding words associated with a corresponding keyword, and a mapping from any corresponding preceding words to a corresponding word phrase;

determine whether a word from an inputted word string matches any keyword in the keyword-based data structure;

determine whether any corresponding preceding words associated with any matching keyword comprises a preceding word which precedes the matching word in the word string in response to a determination that the word in the word string matches any keyword in the keyword-based data structure;

update corresponding match attributes in a match-based data structure in response to a determination that any corresponding preceding words associated with any matching keyword comprises the preceding word which precedes the matching word in the word string, wherein the corresponding match attributes indicate use of the matching word in the word string and use of the matching word in a corresponding word phrase in the phrase-based data structure;

determine, based on the usage attributes and the match attributes associated with a plurality of matching words, whether at least one of the word phrases in the phrase-based data structure is present in the word string.

2. The system of claim 1, wherein at least one word phrase in the phrase-based data structure comprises a specified number of arbitrary words between words, and wherein any arbitrary words are ignored when identifying a preceding word.

3. The system of claim 1, wherein the usage attributes comprise a numerical identifier of a corresponding word phrase in the phrase-based data structure, a position of a corresponding word in the corresponding word phrase;

whether the corresponding word is a terminal word in the corresponding word phrase, and a number of arbitrary words which the corresponding word follows.

4. The system of claim 1, wherein the match attributes comprise:

a numerical identifier of the word string, a position of a corresponding word in a corresponding word phrase, and a position of the corresponding word in the word string.

5. The system of claim 1, wherein the match-based data structure comprises an array having a length equal to a total number of word phrases in the phrase-based data structure, and an index corresponding to the total number of word phrases in the phrase-based data structure.

6. The system of claim 1, comprising further instructions, which when executed, cause the one or more processors to determine whether corresponding usage attributes associated with any matching keyword identify the use of the word in the word string in response to a determination that any corresponding preceding words associated with any matching keyword comprises the preceding word which precedes the matching word in the word string.

7. The system of claim 1, comprising further instructions, which when executed, cause the one or more processors to determine whether corresponding match attributes in the match-based data structure are consistent with the use of the matching word in the word string in response to a determination that corresponding usage attributes associated with any matching keyword identify the use of the word in the word string.

8. A computer program product comprising computer-readable program code to be executed by one or more processors when retrieved from a non-transitory computer-readable medium, the program code including instructions to:

store a plurality of word phrases in a phrase-based data structure;

store each word in the phrase-based data structure as a corresponding keyword in a keyword-based data structure, wherein each corresponding keyword is associated with corresponding usage attributes identifying use of a corresponding word in a corresponding word phrase in the phrase-based data structure;

store, for each word in the phrase-based data structure, any corresponding preceding words associated with a corresponding keyword, and a mapping from any corresponding preceding words to a corresponding word phrase;

determine whether a word from an inputted word string matches any keyword in the keyword-based data structure;

determine whether any corresponding preceding words associated with any matching keyword comprises a preceding word which precedes the matching word in the word string in response to a determination that the word in the word string matches any keyword in the keyword-based data structure;

update corresponding match attributes in a match-based data structure in response to a determination that any corresponding preceding words associated with any matching keyword comprises the preceding word which precedes the matching word in the word string, wherein the corresponding match attributes indicate use of the matching word in the word string and use of the matching word in a corresponding word phrase in the phrase-based data structure;

determine, based on the usage attributes and the match attributes associated with a plurality of matching words, whether at least one of the word phrases in the phrase-based data structure is present in the word string.

9. The computer program product of claim 8, wherein at least one word phrase in the phrase-based data structure comprises a specified number of arbitrary words between words, and wherein any arbitrary words are ignored when identifying a preceding word.

10. The computer program product of claim 8, wherein the usage attributes comprise a numerical identifier of a corresponding word phrase in the phrase-based data structure, a position of a corresponding word in the corresponding word phrase;

whether the corresponding word is a terminal word in the corresponding word phrase, and a number of arbitrary words which the corresponding word follows.

11. The computer program product of claim 8, wherein the match attributes comprise:

a numerical identifier of the word string, a position of a corresponding word in a corresponding word phrase, and a position of the corresponding word in the word string.

12. The computer program product of claim 8, wherein the match-based data structure comprises an array having a length equal to a total number of word phrases in the phrase-based data structure, and an index corresponding to the total number of word phrases in the phrase-based data structure.

13. The computer program product of claim 8, wherein the program code comprises further instructions to determine whether corresponding usage attributes associated with any matching keyword identify the use of the word in the word string in response to a determination that any corresponding preceding words associated with any matching keyword comprises the preceding word which precedes the matching word in the word string.

14. The computer program product of claim 8, wherein the program code comprises further instructions to determine whether corresponding match attributes in the match-based data structure are consistent with the use of the matching word in the word string in response to a determination that corresponding usage attributes associated with any matching keyword identify the use of the word in the word string.

15. A method for matching large sets of words, the method comprising:

storing a plurality of word phrases in a phrase-based data structure;

storing each word in the phrase-based data structure as a corresponding keyword in a keyword-based data structure, wherein each corresponding keyword is associated with corresponding usage attributes identifying use of a corresponding word in a corresponding word phrase in the phrase-based data structure;

storing, for each word in the phrase-based data structure, any corresponding preceding words associated with a corresponding keyword, and a mapping from any corresponding preceding words to a corresponding word phrase;

determining whether a word from an inputted word string matches any keyword in the keyword-based data structure;

determining whether any corresponding preceding words associated with any matching keyword comprises a preceding word which precedes the matching word in the word string in response to a determination that the word in the word string matches any keyword in the keyword-based data structure;

updating corresponding match attributes in a match-based data structure in response to a determination that any corresponding preceding words associated with any matching keyword comprises the preceding word which precedes the matching word in the word string, wherein the corresponding match attributes indicate use of the matching word in the word string and use of the matching word in a corresponding word phrase in the phrase-based data structure;

determining, based on the usage attributes and the match attributes associated with a plurality of matching words, whether at least one of the word phrases in the phrase-based data structure is present in the word string.

16. The method of claim 15, wherein at least one word phrase in the phrase-based data structure comprises a specified number of arbitrary words between words, and wherein any arbitrary words are ignored when identifying a preceding word.

17. The method of claim 15, wherein the usage attributes comprise a numerical identifier of a corresponding word phrase in the phrase-based data structure, a position of a corresponding word in the corresponding word phrase;

whether the corresponding word is a terminal word in the corresponding word phrase, and a number of arbitrary words which the corresponding word follows.

18. The method of claim 15, wherein the match attributes comprise:

a numerical identifier of the word string, a position of a corresponding word in a corresponding word phrase, and a position of the corresponding word in the word string.

19. The method of claim 15, wherein the match-based data structure comprises an array having a length equal to a total number of word phrases in the phrase-based data structure, and an index corresponding to the total number of word phrases in the phrase-based data structure.

20. The method of claim 15, wherein the method further comprises:

determining whether corresponding usage attributes associated with any matching keyword identify the use of the word in the word string in response to a determination that any corresponding preceding words associated with any matching keyword comprises the preceding word which precedes the matching word in the word string; and

determining whether corresponding match attributes in the match-based data structure are consistent with the use of the matching word in the word string in response to a determination that corresponding usage attributes associated with any matching keyword identify the use of the word in the word string.