Mere-parsing with boundary and semantic driven scoping

• US 7,908,552 B2
• Filed: 04/13/2007
• Issued: 03/15/2011
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: Optum360, LLC (UnitedHealth Group Incorporated)
• Original Assignee: A-Life Hospital Coding LLC (UnitedHealth Group Incorporated), A-Life Medical, Inc. (UnitedHealth Group Incorporated)
• Inventors: Morsch, Mark L., Heinze, Daniel T.
• Primary Examiner(s): HUYNH, CONG LAC T
• Application Number:
  US11/735,278
• Publication Number:
  US 20080256108A1
• Time in Patent Office: 1,432 Days
• Field of Search: 715/256, 715/272, 715/200, 704/9
• US Class Current: 715/256
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Methods, systems and computer program products for implementing a mere-parser are disclosed. Text data is processed to generate one or more parse items. A boundary based attribute associated with one of the parse items is identified, and the identified mere attribute is associated with one or more of the remaining parse items that is not blocked from being associated with the boundary based attribute.

Claims

1. A method comprising:

processing text data to generate a plurality of parse items;

determining that one or more of the generated parse items is associated with a boundary based attribute;

when determined that at least one of the generated parse items is associated with a boundary based attribute, associating the boundary based attribute with one or more of the other generated parse items that are not blocked from being associated with the boundary based attribute.

2. The method of claim 1 wherein processing the text data comprises:

identifying one or more boundary markers associated with the text data; and

generating the parse items based on the identified boundary markers.

3. The method of claim 2, wherein identifying one or more boundary markers comprises identifying at least one from a group including a punctuation mark, a word, and a phrase.

4. The method of claim 1, wherein processing the text data comprises:

normalizing the text data to obtain a predetermined text format;

morphologically processing the normalized text data to obtain a standardized format;

and

identifying one or more phrases in the morphologically processed text data to convert to another standardized format.

5. The method of claim 1, further comprising arranging the generated parse items in an ordered data structure.

6. The method of claim 5, wherein associating the boundary based attribute with one or more of the other generated parse items comprises:

determining a direction to propagate the boundary based attribute across the ordered data structure, the determined direction including one from a group including

a linear direction to the left of the generated parse item associated with the boundary based attribute,

a linear direction to the right of the generated parse item associated with the boundary based attribute, and

a linear direction to the left and a linear direction to the right of the generated parse item associated with the boundary based attribute; and

propagating the boundary based attribute to associate with one or more of the other generated parse items located along the determined direction.

7. A method of claim 6, further comprising blocking the boundary based attribute from associating with one or more of the other generated parse items when detected one from a group including

a competing boundary based attribute already associated with one or more of the other generated parse items along the determined direction, the competing boundary based attribute being a type same as the boundary based attribute;

and

a predetermined boundary marker.

8. A method of claim 6, further comprising transforming the boundary based attribute to an alternate boundary based attribute when detected one from a group including a predetermined boundary marker, and

a competing boundary based attribute of a type different than the boundary based attribute already associated with one or more of the other generated parse items;

and

propagating the transformed alternated boundary based attribute along the determined direction.

9. A method of claim 6, further comprising continuing the propagation of the boundary based attribute along the determined direction when detected one from a group including the propagation has not ended;

and

the boundary based attribute has not been transformed.

10. The method of claim 5, wherein arranging the generated one or more parse items in an ordered data structure comprises arranging the generated parse items in at least one from a group including a linked list, an array, a tree, a graph, a stack, and a heap.

11. The method of claim 1, further comprising merging two or more of the generated parse items including:

selecting at least two of the generated parse items;

comparing each of the selected parse items separately against a set of semantic definitions to obtain a first semantic match;

comparing a combination of the selected parse items together against the set of semantic definitions to obtain a second semantic match;

determining whether the second semantic match provides a better semantic match than the first semantic match;

merging the selected parse items when determined that the second semantic match provides the better semantic match; and

preserving the selected parse items when determined that the second semantic match does not provide the better semantic match.

12. A method of claim 11, wherein merging two or more of the parse items further comprises forming a level in a tree structure so that the generated parse items are children of a merged parse item.

13. The method of claim 1, further comprising:

determining whether one or more of the generated parse items is associated with a semantic based attribute;

selecting one of the other generated parse items and comparing the selected one of the other parse items against a predetermined set of semantic definitions to obtain a first semantic match;

comparing a combination of the semantic based attribute and the selected one of the other parse items together against the predetermined set of semantic definitions to obtain a second semantic match;

determining whether the second semantic match provides a better semantic match than the first semantic match;

merging the semantic based attribute with the selected one of the other parse items when determined that the second semantic match is better that the first semantic match; and

preserving the semantic based attribute and the selected one of the other parse items when determined that the second semantic match is not better than the first semantic match.

14. A method of claim 4, further comprising:

determining that one or more of the other generated parse items is already associated with another semantic based attribute;

when determined that the another semantic attribute is associated with at least one of the other generated parse items, determining that the another semantic attribute is of a type same as the semantic based attribute; and

blocking the semantic based attribute from being merged with the at least one of the other generated parse items that is already associated with the another semantic based attribute when determined that the another semantic based attribute is of a type same as the semantic based attribute.

15. A computer program product, embodied on a computer-readable medium, operable to cause a data processing apparatus to perform operations comprising:

processing text data to generate a plurality of parse items;

determining that one or more of the generated parse items is associated with a boundary based attribute;

when determined that at least one of the generated parse items is associated with a boundary based attribute, associating the boundary based attribute with one or more of the other generated parse items that are not blocked from being associated with the boundary based attribute.

16. The computer program product of claim 15 further operable to cause a data processing apparatus to process the text data comprising:

identifying one or more boundary markers of the text data; and

generating the parse items based on the identified boundary markers.

17. The computer program product of claim 16, further operable to cause a data processing apparatus to identify the boundary markers comprising identifying at least one from a group including a punctuation mark, a word, and a phrase.

18. The computer program product of claim 15, further operable to cause a data processing apparatus to process the text data comprising:

normalizing the text data to obtain a predetermined text format;

morphologically processing the normalized text data to obtain a standardized format; and

identifying one or more phrases in the morphologically processed text data to convert to another standardized format.

19. The computer program product of claim 15, further operable to cause a data processing apparatus to arrange the generated parse items in an ordered data structure.

20. The computer program product of claim 15, further operable to cause a data processing apparatus to associate the boundary based attribute with one or more of the other generated parse items comprising:

determining a direction to propagate the boundary based attribute across the ordered data structure, the determined direction including one from a group including

a linear direction to the left of the generated parse item associated with the boundary based attribute,

a linear direction to the right of the generated parse item associated with the boundary based attribute, and

a linear direction to the left and a linear direction to the right of the generated parse item associated with the boundary based attribute; and

propagating the boundary based attribute to associate with one or more of the other generated parse items located along the determined direction.

21. The computer program product of claim 20, further operable to cause a data processing apparatus to perform operations comprising blocking the boundary based attribute from associating with one or more of the other generated parse items when detected one from a group including:

a competing boundary based attribute is already associated with one or more of the other generated parse items along the determined direction, the detected competing boundary based attribute being a type same as the boundary based attribute; and

a predetermined boundary marker.

22. The computer program product of claim 20, further operable to cause a data processing apparatus to perform operations comprising:

transforming the boundary based attribute to an alternate boundary based attribute when detected one from a group including a predetermined boundary marker, and

a competing boundary based attribute of a type different than the boundary based attribute already associated with one or more of the other generated parse items; and

propagating the transformed alternated boundary based attribute along the determined direction.

23. A computer program product of claim 20, further operable to cause a data processing apparatus to continue the propagation of the identified boundary attribute along the determined direction when detected one from a group including the propagation has not ended;

and

the boundary based attribute has not been transformed.

24. The computer program product of claim 19, further operable to cause a data processing apparatus to generate parse items arranged in an ordered data structure comprising arranging the parse items in at least one from a group including a linked list, an array, a tree, a graph, a stack, and a heap.

25. The computer program product of claim 15, further operable to cause a data processing apparatus to merge the parse items comprising:

selecting at least two of the generated parse items;

comparing each of the selected parse items separately against a set of semantic definitions to obtain a first semantic match;

comparing a combination of the selected parse items together against the set of semantic definitions to obtain a second semantic match;

determining whether the second semantic match provides a better semantic match than the first semantic match;

merging the selected parse items when determined that the second semantic match provides the better semantic match; and

preserving the selected parse items when determined that the second semantic match does not provide the better semantic match.

26. the computer program product of claim 25, further operable to cause a data processing apparatus to merge two or more of the generated parse items to form a level in a tree structure so that the generated parse items are children of a merged parse item.

27. The computer program product of claim 15, further operable to cause a data processing apparatus to merge the identified semantic attribute with one or more of the remaining generated parse items comprising:

determining whether one or more of the generated parse items is associated with a semantic based attribute;

selecting one of the other generated parse items and comparing the selected one of the other parse items against a predetermined set of semantic definitions to obtain a first semantic match;

comparing a combination of the semantic based attribute and the selected one of the other parse items together against the predetermined set of semantic definitions to obtain a second semantic match;

determining whether the second semantic match provides a better semantic match than the first semantic match;

merging the semantic based attribute with the selected one of the other parse items when determined that the second semantic match is better than the first semantic match; and

preserving the semantic based attribute and the selected one of the other parse items when determined that the second semantic match is not better than the first semantic match.

28. A computer program product of claim 27, further operable to cause a data processing apparatus to perform operations comprising:

determining that one or more of the other generated parse items is already associated with another semantic based attribute;

when determined that the another semantic attribute is associated with at least one of the other generated parse items, determining that the another semantic attribute is of a type same as the semantic based attribute; and

blocking the semantic based attribute from being merged with the at least one of the other generated parse items that is already associated with the another semantic based attribute when determined that the another semantic based attribute is of a type same as the semantic based attribute.

29. A system comprising:

a storage device; and

a processor to control operations of systems including;

a bounding system configured to process text data to generate one or more parse items, and

determine that one or more of the generated parse items is associated with a boundary based attribute, and

a propagation system configured to when determined that at least one of the generated parse items is associated with a boundary based attribute, associate the boundary based attribute with one or more of the other generated parse items that are not blocked from being associated with the boundary based attribute.

30. The system of claim 29 wherein the bounding system is further configured to process the text data comprising:

identifying one or more boundary markers associated with the text data; and

generating the parse items based on the identified boundary markers.

31. The system of claim 30, wherein the bounding system is configured to identify the boundary markers comprising identifying at least one from a group including a punctuation mark, a word, and a phrase.

32. The system of claim 29, wherein the bounding system is further configured to process the text data by performing operations comprising:

normalizing the text data to a predetermined text format;

morphologically processing the normalized text data to a standardized format; and

identifying one or more phrases in the morphologically processed text data to convert to another standardized format.

33. The system of claim 29, wherein the bounding system is further configured to arranged the generated parse items in an ordered data structure.

34. The system of claim 33, wherein the propagation system is further configured to associate the boundary based attribute with one or more of the other generated parse items comprising:

determining a direction to propagate the boundary based attribute across the ordered data structure, the determined direction including one from a group including

a linear direction to the left of the generated parse item associated with the boundary based attribute,

a linear direction to the right of the generated parse item associated with the boundary based attribute, and

a linear direction to the left and a linear direction to the right of the generated parse item associated with the boundary based attribute; and

propagating the boundary based attribute to associate with one or more of the other generated parse items located along the determined direction.

35. A system of claim 34, wherein the propagation system is further configured to block the propagation of the identified boundary attribute along the determined direction when detected one from a group including

a competing boundary based attribute already associated with one or more of the other generated parse items along the determined direction, the competing boundary based attribute being a type same as the boundary based attribute;

and

a predetermined boundary marker.

36. A system of claim 34, wherein the propagation system is further configured to perform the operations comprising:

transforming the boundary based attribute to an alternate boundary based attribute when detected one from a group including

a predetermined boundary marker, and

a competing boundary based attribute of a type different than the boundary based attribute already associated with one or more of the other generated parse items; and

propagating the transformed alternate boundary based attribute along the determined direction.

37. A system of claim 34, wherein the propagation system is further configured to continue the propagation of the boundary based attribute along the determined direction when detected one from a group including

the propagation has not ended, and

the boundary based attribute has not been transformed.

38. The system of claim 33, wherein the bounding system if further configured to generate one or more parse items arranged in an ordered data structure by arranging the generated parse items in at least one from a group including a linked list, an array, a tree, a graph, a stack, and a heap.

39. The system of claim 29, further comprising a tree building system configured to merge two or more of the parse items by performing operations comprising:

selecting at least two of the generated parse items;

comparing each of the selected parse items separately against a set of semantic definitions to obtain a first semantic match;

comparing a combination of the selected parse items together against the set of semantic definitions to obtain a second semantic match;

determining whether the second semantic match provides a better semantic match than the first semantic match;

merging the selected parse items when determined that the second semantic match provides the better semantic match; and

preserving the selected parse items when determined that the second semantic match does not provide the better semantic match.

40. The system of claim 38, wherein the tree building system is further configured to merge two or more of the generated parse items by forming a level in a tree structure so that the generated parse items are children of a merged parse item.

41. The system of claim 39, wherein the tree building system is further configured to perform the operations comprising:

determining whether one or more of the generated parse items is associated with a semantic based attribute;

selecting one of the other generated parse items and comparing the selected one of the other parse items against a predetermined set of semantic definitions to obtain a first semantic match;

comparing a combination of the semantic based attribute and the selected one of the other parse items together against the predetermined set of semantic definitions to obtain a second semantic match;

determining whether the second semantic match provides a better semantic match than the first semantic match;

merging the semantic based attribute with the selected one of the other parse items when determined that the second semantic match is better than the first semantic match; and

preserving the semantic based attribute and the selected one of the other parse items when determined that the second semantic match is not better than the first semantic match.

42. The system of claim 41, wherein the bounding system is further configured to perform the operations comprising:

determining that one or more of the other generated parse items is already associated with another semantic based attribute, and

when determined that the another semantic attribute is associated with at least one of the other generated parse items, determining that the determined another semantic attribute is of a type same as the semantic based attribute; and

the propagation system is further configured to block the semantic based attribute from being merged with the at least one of the other generated parse items that is already associated with the another semantic based attribute when determined that the another semantic based attribute is of a type same as the semantic based attribute.