Concept synonym matching engine

• US 7,599,930 B1
• Filed: 10/18/2005
• Issued: 10/06/2009
• Est. Priority Date: 10/19/2004
• Status: Active Grant

• Current Assignee: Monster Worldwide Incorporated (Randstad NV)
• Original Assignee: Trovix, Inc. (Randstad NV)
• Inventors: Burns, Derrick, Rennison, Earl
• Primary Examiner(s): Alam; Shahid A
• Assistant Examiner(s): Shmatov; Alexey
• Application Number:
  US11/253,974
• Time in Patent Office: 1,449 Days
• Field of Search: 707/102, 707/9, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A concept synonym matching engine identifies and extracts specific information referenced in a selection of text and matches the information to a set of defined concepts. The engine is able to perform this identification and matching in the presence of errors (e.g., misspellings, etc.) or variations in the description of those concepts (e.g., use of different terms to define the same idea). The engine performs these functions by tokenizing an input string of text and matching these tokens to tokens of a pattern that represents a concept to be matched. The engine matches the pattern to a sub-string of text, scores the match, and uses the score to determine whether the concept is present in the input string or to select the optimal match.

Claims

1. A computer program product having a computer-readable storage medium storing computer program instructions that identify a parent concept referenced in an input string of text by determining the presence of a child concept in the input string, the computer program instructions comprising instructions that when executed by a processor cause the processor to perform the steps of:

storing a plurality of concept hierarchies, each concept hierarchy comprising a plurality of concepts in a knowledge base, including parent concepts and child concepts, wherein each child concept inherits characteristics of a parent concept, wherein each concept is represented in the knowledge base by a pattern which comprises one or more pattern tokens, wherein at least some of the patterns representing concepts comprise multiple pattern tokens that are associated with each other by a set of constraints;

dividing the input string into input tokens that represent sub-strings of text within the input string;

identifying at least one token match between any of the input tokens and any of the pattern tokens representing a child concept in the concept hierarchies;

identifying at least one pattern match between sub-strings of the input string that are comprised of more than one of the matched input tokens and the pattern representing the child concept based on the token match and the set of constraints for the pattern;

scoring the at least one pattern match based on the corresponding token match to provide at least one match score; and

determining which of the child concepts are present in the input string based on the corresponding match score, wherein a plurality of child concepts, contained in a plurality of concept hierarchies, is present in the input string, the presence of the child concepts in the input string identifying that at least one parent concept is referenced in the input string of text.

2. The computer program product of claim 1, wherein determining which of the child concepts are present in the input string further comprises identifying a sub-string of text in the input string as naming the child concept present in the input string based on the token match.

3. The computer program product of claim 1, wherein the concept is represented by one or more patterns that are synonyms describing the concept, and wherein any of the one or more patterns can be used to identify the concept.

4. The computer program product of claim 1, wherein the pattern includes a modifier that modifies how the pattern is interpreted.

5. The computer program product of claim 1, further comprising:

applying a hash function to the pattern to obtain a first hash value for the pattern that is stored in a hash table;

applying the hash function to the input tokens to obtain a second hash value; and

finding a match between the first and second hash values in the hash table.

6. The computer program product of claim 1, wherein the pattern is a compound pattern composed of sub-patterns, each sub-pattern comprising input tokens, wherein the compound pattern selected from a group consisting of:

set compound pattern, sequence compound pattern, alternative compound pattern, concatenation pattern, required pattern, optional pattern, more important pattern, and less important pattern.

7. The computer program product of claim 6, wherein the compound pattern is a sequence compound pattern that is matched when order of appearance of the input tokens in the sub-strings matches order of appearance of the sub-patterns in the compound pattern.

8. The computer program product of claim 1, wherein the token match is identified when characters forming the input tokens are substantially similar to characters forming the pattern tokens.

9. The computer program product of claim 1, wherein the pattern is comprised of basic patterns, selected from a group consisting of a character, a symbol, a number, a stemmed word, and an exact word.

10. The computer program product of claim 9, wherein scoring the pattern match further comprises:

assigning each of the basic patterns a weight; and

calculating the match score that comprises an overall score for the pattern based on the weight.

11. The computer program product of claim 10, wherein assigning each of the basic patterns a weight further comprises assigning a lower weight to less important of the basic patterns.

12. The computer program product of claim 10, further comprising calculating an importance value for each of the basic patterns, wherein the pattern is scored only when the importance value exceeds a threshold value.

13. The computer program product of claim 1, wherein scoring the pattern match further comprises taking into consideration the input tokens in the input string that are unmatched and that lie between the input tokens that are matched.

14. The computer program product of claim 1, wherein determining which of the child concepts are present in the input string based on the match score further comprises:

comparing the match score for the pattern match to a threshold score; and

selecting a substantially plausible match, wherein the pattern match is considered substantially plausible when the match score exceeds the threshold score.

15. The computer program product of claim 1, wherein determining which of the child concepts are present in the input string based on the match score further comprises selecting the pattern match to apply based on the match score, wherein the pattern match selected is non-conflicting with other pattern matches in the input string.

16. A computer-implemented method of identifying a parent concept referenced in an input string of text by determining the presence of a child concept in the input string, the method comprising:

storing a plurality of concept hierarchies, each concept hierarchy comprising a plurality of concepts in a knowledge base, including parent concepts and child concepts, wherein each child concept inherits characteristics of a parent concept, wherein each concept is represented in the knowledge base by a pattern which comprises one or more pattern tokens, wherein at least some of the patterns representing concepts comprise multiple pattern tokens that are associated with each other by a set of constraints;

dividing the input string into input tokens that represent sub-strings of text within the input string;

identifying at least one token match between any of the input tokens and any of the pattern tokens representing a child concept in the concept hierarchies;

identifying at least one pattern match between sub-strings of the input string that are comprised of more than one of the matched input tokens and the pattern representing the child concept based on the token match and the set of constraints for the pattern;

scoring the at least one pattern match based on the corresponding token match to provide at least one match score; and

determining which of the child concepts are present in the input string based on the corresponding match score, wherein a plurality of child concepts, contained in a plurality of concept hierarchies, is present in the input string, the presence of the child concepts in the input string identifying that at least one parent concept is referenced in the input string of text.

17. The method of claim 16, wherein the concept is represented by patterns that are synonyms describing the concept, and wherein any of the patterns can be used to identify the concept.

18. The method of claim 16, wherein the pattern tokens include a stem modifier modifying a word so that an input word in the input string matches the word when the input word contains a same stem.

19. The method of claim 16, further comprising:

applying a hash function to the pattern to obtain a first hash value for the pattern that is stored in a hash table;

applying the hash function to the input tokens to obtain a second hash value; and

finding a match between the first and second hash values in the hash table.

20. The method of claim 19, further comprising using a metaphone when applying the hash function.

21. The method of claim 16, wherein the pattern is a compound pattern composed of sub-patterns, each sub-pattern comprising input tokens, wherein the compound pattern selected from a group consisting of:

set compound pattern, sequence compound pattern, alternative compound pattern, concatenation pattern, required pattern, optional pattern, more important pattern, and less important pattern.

22. The method of claim 21, wherein the compound pattern is matched when at least one of its sub-patterns is matched.

23. The method of claim 16, wherein the token match is identified when words forming the input tokens are spelled substantially similarly to words forming the pattern tokens.

24. The method of claim 16, wherein the pattern is comprised of basic patterns, selected from a group consisting of a character, a symbol, a number, a stemmed word, and an exact word.

25. The method of claim 24, further comprising calculating an importance value for each of the basic patterns, wherein the importance value must exceed a threshold value for the pattern to be scored, wherein scoring the pattern match further comprises:

assigning each of the basic patterns a weight; and

calculating the match score that comprises an overall score for the pattern based on the weight.

26. The method of claim 24, wherein scoring the pattern match further comprises:

assigning each of the basic patterns a weight; and

calculating the match score that comprises an overall score for the pattern based on the weight.

27. The method of claim 26, wherein assigning each of the basic patterns a weight further comprises assigning a lower weight to more frequently used of the basic patterns.

28. The method of claim 16, wherein scoring the pattern match further comprises calculating the match score to take into account the input tokens in the input string that are unmatched and that lie between the input tokens that are matched.

29. The method of claim 28, wherein a distance constraint is applied that limits number of the unmatched input tokens that can lie between the input tokens that are matched.

30. The method of claim 16, wherein determining which of the child concepts are present in the input string based on the score further comprises:

comparing the match score for the pattern match to a threshold score;

selecting a substantially plausible match, wherein the pattern match is considered substantially plausible when the match score exceeds the threshold score; and

using dynamic programming techniques to select the pattern match that is non-conflicting with other pattern matches in the input string.

31. The method of claim 16, wherein determining which of the child concepts are present in the input string further comprises identifying a sub-string of text in the input string as naming the concept present in the input string based on the token match.

32. A computer system for identifying a parent concept referenced in an input string of text by determining the presence of a child concept in the input string, the system comprising:

a computer-readable storage medium configured to store a plurality of concept hierarchies, each concept hierarchy comprising a plurality of concepts in a knowledge base, including parent concepts and child concepts, wherein each child concept inherits characteristics of a parent concept, wherein each concept is represented in the knowledge base by a pattern which comprises one or more pattern tokens, wherein at least some of the patterns representing concepts comprise multiple pattern tokens that are associated with each other by a set of constraints;

a tokenization module, stored on the computer-readable storage medium, configured to divide the input string into input tokens that represent sub-strings of text within the input string;

a token matching module, stored on the computer-readable storage medium, configured to

identify at least one token match between any of the input tokens and any of the pattern tokens representing a child concept in the concept hierarchies;

a pattern matching module, stored on the computer-readable storage medium, configured to identify at least one pattern match between sub-strings of the input string that are comprised of more than one of the matched input tokens and the pattern representing the child concept based on the token match and the set of constraints for the pattern;

a pattern scoring module, stored on the computer-readable storage medium, configured to score the at least one pattern match based on the corresponding token match to provide at least one match score; and

a pattern selection module, stored on the computer-readable storage medium, configured to determine which of the child concepts are present in the input string based on the corresponding match score, wherein a plurality of child concepts, contained in a plurality of concept hierarchies, is present in the input string, the presence of the child concepts in the input string identifying that at least one parent concept is referenced in the input string of text.

33. The system of claim 32, wherein the concept is represented by patterns that are synonyms describing the concept, and wherein any of the patterns can be used to identify the concept.

34. The system of claim 32, wherein the pattern tokens include an exact modifier modifying a word so that an input word in the input string matches the word when spelling of the input word exactly matches spelling of the word.

35. The system of claim 32, further comprising:

a hash module for applying a hash function to the pattern to obtain a first hash value for the pattern that is stored in a hash table and for applying the hash function to the input tokens to obtain a second hash value; and

a matching module for finding a match between the first and second hash values in the hash table.

36. The system of claim 32, wherein the pattern is a compound pattern composed of sub-patterns, each sub-pattern comprising input tokens, wherein the compound pattern selected from a group consisting of:

set compound pattern, sequence compound pattern, alternative compound pattern, concatenation pattern, required pattern, optional pattern, more important pattern, and less important pattern.

37. The system of claim 32, wherein the system is configured to match the concept with a term in the input string where the term is spelled differently from the concept.

38. The system of claim 32, wherein the pattern is comprised of basic patterns and wherein the pattern scoring module is further configured to:

assign each of the basic patterns a weight, wherein the weight assigned is inversely related to frequency of the basic patterns; and

calculate the match score that comprises an overall score for the pattern based on the weight.

39. The system of claim 32, wherein the pattern is comprised of basic patterns and wherein the pattern selection module is further configured to retrieve from an importance index an importance value for each of the basic patterns to determine whether to score each of the basic patterns.

40. The system of claim 32, wherein the pattern scoring module is further configured to take into account the input tokens in the input string that are unmatched and that lie between the input tokens that are matched.

41. The system of claim 32, wherein the pattern determination module is further configured to:

compare the match score for the pattern match to a threshold score;

select a likely match, wherein the pattern match is considered likely when the match score exceeds the threshold score; and

selecting a non-conflicting pattern match.

42. The system of claim 32, wherein the pattern determination module is further configured to identify a sub-string of text in the input string as naming the concept present in the input string based on the token match.

43. The system of claim 32, wherein the pattern includes a constraint in which a term in the pattern must appear in the input string for the pattern match to be identified.

44. The system of claim 32, wherein the pattern includes a constraint in which a term in the pattern is optional in the input string for the pattern match to be identified.

45. The system of claim 32, wherein the pattern includes a constraint that allows a sequence of concatenated patterns to match adjacent input tokens in the input string.

46. A computer-implemented method of matching a parent concept to one or more sub-strings in an input string of text by determining the presence of a child concept in the input string, the method comprising:

storing a plurality of concept hierarchies, each concept hierarchy comprising a plurality of concepts in a knowledge base, including parent concepts and child concepts, where each child concept inherits characteristics of a parent concept, wherein each concept is represented in the knowledge base by a pattern formed of basic patterns, each of which comprises one or more pattern tokens, wherein at least some of the patterns representing concepts comprise multiple pattern tokens that are

dividing the input string into input tokens that represent sub-strings of text within the input string;

identifying at least one token match between any of the input tokens and any of the

pattern tokens representing a child concept in the concept hierarchies;

identifying at least one pattern match between sub-strings of the input string that are comprised of more than one of the matched input tokens and the pattern representing the child concept based on the token match and the set of constraints for the pattern;

scoring the at least one pattern match based on the corresponding token match to provide at least one match score by assigning each of the basic patterns a weight that together equals a total weight for the pattern; and

selecting the at least one pattern match with the total weight that is highest and where the at least one pattern match does not overlap any other pattern matches for the input string, the at least one pattern match indicating that the child concept is present in the input string, wherein a plurality of child concepts, contained in a plurality of concept hierarchies, is present in the input string, the presence of the child concepts in the input string identifying that at least one parent concept is referenced in the input string of text.

47. The method of claim 46, wherein the concept is represented by patterns that are synonyms describing the concept, and wherein any of the patterns can be used to identify the concept.

48. The method of claim 46, wherein the pattern matches a term in the concept that is misspelled.

49. The method of claim 46, wherein the basic patterns are selected from a group consisting of a character, a symbol, a number, a stemmed word, and an exact word.

50. The method of claim 46, wherein one or more of the basic patterns form sub-patterns of a compound pattern, the compound pattern selected from a group consisting of:

set compound pattern, sequence compound pattern, alternative compound pattern, concatenation pattern, required pattern, optional pattern, more important pattern, and less important pattern.