System and method for phrase matching with arbitrary text

• US 9,619,458 B2
• Filed: 06/11/2013
• Issued: 04/11/2017
• Est. Priority Date: 07/20/2012
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Fuchs, Matthew, Gonzalez, Zandro Luis, Howland, Craig
• Primary Examiner(s): He, Jialong
• Assistant Examiner(s): WANG, YI SHENG
• Application Number:
  US13/915,356
• Publication Number:
  US 20140025369A1
• Time in Patent Office: 1,400 Days
• Field of Search: None
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A system and method for matching phrases having arbitrary text. A first data structure stores a list of common phrases having multiple words. Each unique word is indexed in a hash table and mapped to one or more values that describe attributes of using the word in one or more of the common phrases. Using the hash table and the list of common phrases, a temporary array is defined to keep track of possible matches between words in an input string and the list of common phrases.

Claims

1. A method for phrase matching in database operations, comprising:

storing, by a database system, a plurality of expressions in a first data structure, each expression having a plurality of words;

storing, by the database system, for each word of the plurality of expressions a corresponding key with at least one associated value into a second data structure, each associated value representing a first plurality of attributes relating to use of the corresponding word in one of the expressions in the first data structure, the first plurality of attributes including at least two of;

(i) an identification of the expression in the first data structure;

(ii) a position of the word in the expression;

(iii) a branch expression number;

(iv) whether the word is a terminal word in the expression; and

(v) whether the word follows arbitrary text;

receiving, by the database system, an input sentence having a string of words;

comparing, by the database system, a word from the input sentence with each key of the second data structure;

evaluating, in the input sentence, for each word that matches a key, the first plurality of attributes associated with the matched key and storing a second plurality of attributes in a third data structure, the second plurality of attributes indicating how use of the matching word in the input sentence compares with use of the word in one of the expressions in the first data structure, the second plurality of attributes including at least one of;

(i) a number of the input sentence;

(ii) a position of the word in the corresponding expression; and

(iii) a position of the word in the input sentence;

repeating, by the database system, the comparing step for each word from the input sentence; and

determining, by the database system, based on the first plurality of attributes and the second plurality of attributes if one or more expressions from the first data structure are present in the input sentence.

2. The method of claim 1, further comprising:

updating, by the database system, the second plurality of attributes when use of the word from the input sentence is consistent with use of the word in an expression of the first data structure.

3. The method of claim 1, the third data structure comprising an array having a length equal to a total of the plurality of expressions in the first data structure, and an index corresponding to the total of the plurality of expressions in the first data structure, the method further comprising:

retrieving, by the database system, the second plurality of attributes from the array at the index corresponding to the matched key.

4. The method of claim 1, the third data structure comprising an array having a length equal to a total of the plurality of expressions in the first data structure, and an index corresponding to the total of the plurality of expressions in the first data structure, the method further comprising:

updating, by the database system, the second plurality of attributes in the array at the index corresponding to the matched key.

5. The method of claim 1, the third data structure comprising an array having a length equal to a total of the plurality of expressions in the first data structure, and an index corresponding to the total of the plurality of expressions in the first data structure, the method further comprising:

retrieving, by the database system, the second plurality of attributes from the array at the index corresponding to the position of the word in the input sentence; and

evaluating, by the database system, the retrieved second plurality of attributes for consistency with the first plurality of attributes.

6. The method of claim 1, wherein at least one expression in the first data structure includes arbitrary text between words of the expression.

7. The method of claim 1, the determining step further comprising:

evaluating, by the database system, the second plurality of attributes for consistency with the first plurality of attributes for a word from the input sentence matching a key from the second data structure;

repeating, by the database system, the step of evaluating the second plurality of attributes for each word from the input sentence that matches a key from the second data structure; and

designating, by the database system, one or collections of words from the input sentence as matching expressions stored in the first data structure.

8. The method of claim 7, further comprising:

initializing, by the database system, the second plurality of attributes; and

updating, by the database system, the second plurality of attributes when the step of evaluating the second plurality of attributes is consistent with the first plurality of attributes.

9. A non-transitory computer-readable storage medium encoded with executable instructions for phrase matching in database operations, the instructions comprising:

storing a plurality of expressions in a first data structure, each expression having a plurality of words;

storing, by the database system, for each word of the plurality of expressions a corresponding key with at least one associated value into a second data structure, each associated value representing a first plurality of attributes relating to use of the corresponding word in one of the expressions in the first data structure, the first plurality of attributes including at least two of;

(i) an identification of the expression in the first data structure;

(ii) a position of the word in the expression;

(iii) a branch expression number;

(iv) whether the word is a terminal word in the expression; and

(v) whether the word follows arbitrary text;

receiving an input sentence having a string of words;

comparing a word from the input sentence with each key of the second data structure;

evaluating, in the input sentence, for each word that matches a key, the first plurality of attributes associated with the matched key and storing a second plurality of attributes in a third data structure, the second plurality of attributes indicating how use of the matching word in the input sentence compares with use of the word in one of the expressions in the first data structure, the second plurality of attributes including at least one of;

(i) a number of the input sentence;

(ii) a position of the word in the corresponding expression; and

(iii) a position of the word in the input sentence;

repeating the comparing step for each word from the input sentence; and

determining based on the first plurality of attributes and the second plurality of attributes if one or more expressions from the first data structure are present in the input sentence.

10. The computer-readable storage medium of claim 9, the instructions further comprising:

updating the second plurality of attributes when use of the word from the input sentence is consistent with use of the word in an expression of the first data structure.

11. The computer-readable storage medium of claim 9, the third data structure comprising an array having a length equal to a total of the plurality of expressions in the first data structure, and an index corresponding to the total of the plurality of expressions in the first data structure, the method further comprising:

updating the second plurality of attributes in the array at the index corresponding to the matched key.

12. The computer-readable storage medium of claim 9, the third data structure comprising an array having a length equal to a total of the plurality of expressions in the first data structure, and an index corresponding to the total of the plurality of expressions in the first data structure, the method further comprising:

retrieving the second plurality of attributes from the array at the index corresponding to the position of the word in the input sentence; and

evaluating the retrieved second plurality of attributes for consistency with the first plurality of attributes.

13. The computer-readable storage medium of claim 9, the determining step further comprising:

evaluating the second plurality of attributes for consistency with the first plurality of attributes for a word from the input sentence matching a key from the second data structure;

repeating the step of evaluating the second plurality of attributes for each word from the input sentence that matches a key from the second data structure; and

designating one or collections of words from the input sentence as matching expressions stored in the first data structure.

14. The computer-readable storage medium of claim 9, wherein at least one expression in the first data structure includes arbitrary text between words of the expression.

15. A system for phrase matching in database operations, comprising:

a processor; and

one or more stored sequences of instructions which, when executed by the processor, cause the processor to;

store a plurality of expressions in a first data structure, each expression having a plurality of words;

store, by the database system, for each word of the plurality of expressions a corresponding key with at least one associated value into a second data structure, each associated value representing a first plurality of attributes relating to use of the corresponding word in one of the expressions in the first data structure, the first plurality of attributes including at least two of;

(i) an identification of the expression in the first data structure;

(ii) a position of the word in the expression;

(iii) a branch expression number;

(iv) whether the word is a terminal word in the expression; and

(v) whether the word follows arbitrary text;

receive an input sentence having a string of words;

compare a word from the input sentence with each key of the second data structure;

evaluate, in the input sentence, for each word that matches a key, the first plurality of attributes associated with the matched key and storing a second plurality of attributes in a third data structure, the second plurality of attributes indicating how use of the matching word in the input sentence compares with use of the word in one of the expressions in the first data structure, the second plurality of attributes including at least one of;

(i) number of the input sentence;

(ii) a position of the word in the corresponding expression; and

(iii) a position of the word in the input sentence;

repeat the comparing step for each word from the input sentence; and

determine based on the first plurality of attributes and the second plurality of attributes if one or more expressions from the first data structure are present in the input sentence.

16. The system of claim 15, the third data structure comprising an array having a length equal to a total of the plurality of expressions in the first data structure, and an index corresponding to the number of the expression in the first data structure, the instructions, which when executed by the processor, further cause the processor to:

retrieve the second plurality of attributes from the array at the index corresponding to the matched key.

17. The system of claim 15, the third data structure comprising an array having a length equal to a total of the plurality of expressions in the first data structure, and an index corresponding to the total of the plurality of expressions in the first data structure, the instructions, which when executed by the processor, further cause the processor to:

retrieve the second plurality of attributes from the array at the index corresponding to the position of the word in the input sentence; and

evaluate the retrieved second plurality of attributes for consistency with the first plurality of attributes.

18. The system of claim 15, the instructions, which when executed by the processor, further cause the processor to:

evaluate the second plurality of attributes for consistency with the first plurality of attributes for a word from the input sentence matching a key from the second data structure;

repeat evaluating the second plurality of attributes for each word from the input sentence that matches a key from the second data structure; and

designate one or collections of words from the input sentence as matching expressions stored in the first data structure.