Method and apparatus for semantic pattern matching for text retrieval

• US 5,331,554 A
• Filed: 12/10/1992
• Issued: 07/19/1994
• Est. Priority Date: 12/10/1992
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Graham, James M.
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): CHUNG TRANS, XUONG MY
• Application Number:
  US07/988,729
• Time in Patent Office: 586 Days
• Field of Search: 364/419.08, 364/419.13, 364/419.07, 364/419.19
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/3323 using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and apparatus utilizing automated semantic pattern recognition whereby a user of a manual enters a query regarding information in the text of the manual and the invention displays the locations in which information responsive to the query is located. The present invention includes a computer that stores a data structure representing the natural language text of a manual, the structure being a tree structure having nodes, wherein each node represents information from associated locations of the text. The nodes at higher levels of the tree represent general categories of information. Nodes at succeedingly lower levels of the tree represent succeedingly more specific categorical subsets of the general categories of information represented at the higher levels by ancestors of the lower level nodes. The query is formatted into a query data structure that is similar in format to the node structure representing the text. The query data structure is compared to each node in the tree. If the degree of similarity between the query and the node exceeds a predetermined threshold value after taking into account the degree of similarity between the ancestors of the node and the query, then the locations associated with the node are displayed on a video monitor as locations containing information responsive to the query.

Claims

1. A method for locating information in a natural language text using a computer including a video monitor and a memory device for storing a data structure representing the natural language text,

wherein said data structure has a tree structure having nodes and levels, each node representing information from associated locations in said text, each of said locations having a corresponding location identifier, the information in a node being a categorical subset of information represented by a parent node of that node, each node being one level below its parent node in the tree structure and containing node constituents, said parent node and the nodes at higher levels of the tree structure that represent more general categories of information than the information represented by a node being ancestors of that node,

the method comprising the steps of:

formatting a query regarding information in the text into a query data structure;

comparing the query data structure to a node to produce a comparison value representative of the degree of similarity between the query and the information represented by the node;

enhancing the comparison value by an amount representative of the degree of similarity between the query and the information represented by ancestors of the node to produce an enhanced comparison value; and

storing the location identifiers associated with the node if the enhanced comparison value exceeds a predetermined lower bound and the node contributes information responsive to the query.

2. The method of claim 1, further comprising the steps of:

performing said comparing, enhancing, and storing steps at each node in the tree structure; and

displaying the stored location identifiers on the video monitor.

3. A method for locating information in a natural language text using a computer including a video monitor and a memory device for storing a data structure representing said natural language text,

wherein said data structure has a tree structure having nodes and levels, each said node representing information from associated locations in said text, each said location having a corresponding location identifier, the information in a node being a categorical subset of information represented by a parent node of that node, each said node being one level below its parent node in said tree structure and containing node constituents,

said method comprising the steps of:

formatting a query regarding information in said text into a query data structure containing constituents of said query, each said query constituent representing a word or a phrase contained in said query;

producing a match vector having a plurality of match elements, said match vector being representative of a degree of similarity between said query data structure and one of said nodes, and each said match element corresponding in position to a predetermined query constituent and to a predetermined parent element of a parent vector;

merging said match vector with said parent vector to produce a merge vector having a plurality of merge elements, wherein each said merge element corresponds in position to a predetermined parent element by setting each said merge element to be equal to the greater of its corresponding parent element and the match element corresponding to the corresponding parent element;

setting a contribution flag to true if any of said match elements is greater than zero and, at the same time, greater than or equal to said parent element corresponding to said match element;

if said contribution flag is set to true;

averaging said merge elements to produce a merge vector average;

storing the location identifiers associated with said node if said merge vector average equals or exceeds a predetermined threshold value, whereby said stored location identifiers represent locations in said natural language text containing information responsive to said query;

whether said contribution flag is true or not;

performing, at each node in said data structure, said steps of producing a match vector, merging, setting a contribution flag, and, if said contribution flag is set to true, averaging and storing, wherein all said steps are performed at each said node after substituting for said parent vector said merge vector that resulted from performing said merging step on said parent node of said node; and

displaying on said video monitor said stored location identifiers.

4. The method of claim 3, wherein

said storing step further comprises the step of storing said merge vector average as a confidence score associated with said stored location identifiers, and

said displaying step further comprises the step of displaying on said video monitor said confidence scores associated with said stored location identifiers.

5. The method of claim 3, further comprising the steps of:

after producing the match vector;

averaging said match elements to produce a match vector average;

adding a constant value to said match vector average to produce an enhanced match vector average if said match vector average equals or exceeds said predetermined threshold;

said storing step further comprising the steps of;

if said merge vector average equals or exceeds said predetermined threshold and said contribution flag is set to true;

if said enhanced match vector average is greater than said merge vector average, storing for display said enhanced match vector average as a confidence score associated with said stored location identifiers; and

if said enhanced match vector average is not greater than said merge vector average, storing for display said merge vector average as a confidence score associated with said stored location identifiers;

said performing step further comprising the step of performing the above steps at each node in said data structure; and

said displaying step further comprising the step of displaying on said video monitor said confidence scores associated with said stored location identifiers.

6. The method of claim 5, further comprising the steps of:

after said setting step;

if said contribution flag is not true;

successively replacing one element of the parent vector at a time with the corresponding match element to produce a semi-merge vector, wherein said semi-merge vector comprises all the elements of the parent vector except for the substituted match element, either until the average of the elements of said semi-merge vector equals or exceeds the predetermined threshold and the corresponding match element exceeds zero value, or until each element of the parent vector has been subject to replacement; and

thereafter setting said semi-merge vector equal to a nil value if the average of the elements of said semi-merge vector does not equal or exceed the threshold;

if said semi-merge vector is not nil;

averaging the elements of said semi-merge vector to produce a semi-merge vector average;

if said enhanced match vector average is greater than said semi-merge vector average, storing for display said enhanced match vector average as a confidence score associated with said stored location identifiers; and

if said enhanced match vector average is not greater than said semi-merge vector average, storing for display said semi-merge vector average as a confidence score associated with said stored location identifiers,

wherein said performing step further comprises the step of performing the above steps at each node in said data structure.

7. The method of claim 6, wherein said averaging step to produce the semi-merge vector average comprises the steps of adding together the elements of said semi-merge vector to produce a semi-merge vector total, and dividing the semi-merge vector total by the number of elements in said semi-merge vector to produce said semi-merge vector average.

8. The method of claim 5, wherein said averaging step to produce the match vector average comprises the steps of adding together said match elements to produce a total, and dividing the total by the number of match elements in said match vector to produce said match vector average.

9. The method of claim 3, wherein the step of producing the match vector comprises the steps of:

comparing each said query constituent with each said node constituent at a particular node to produce a constituent value representative of a degree of similarity between said query constituent and said node constituent; and

setting each said match element equal to the highest constituent value obtained as a result of comparing the query constituent corresponding to said match element to each said node constituent.

10. The method of claim 9, further comprising the steps of:

after said comparing step;

if the comparison of two or more query constituents to the same node constituent results in the highest constituent values obtained for said two or more query constituents;

selecting the greatest of said highest constituent values and setting the match element in the position corresponding to the query constituent associated with said greatest constituent value to the greatest constituent value;

setting the match elements corresponding in position to the remaining query constituents that resulted in the highest match to the same node to the next highest constituent value obtained as a result of comparing said remaining query constituents to the other node constituents; and

repeating said selecting and setting steps immediately above if two or more of the remaining query constituents again result in the highest match to the same node constituent.

11. The method of claim 3, wherein said averaging step to produce the merge vector comprises the steps of adding together said merge elements to produce a total, and dividing the total by the number of merge elements in said merge vector to produce said merge vector average.

12. The method of claim 3, further comprising the step of a user inputting the query.

13. The method of claim 3, further comprising the step of determining the threshold value according to a user input.

14. The method of claim 3, wherein said location identifiers are page numbers.

15. The method of claim 3, said displaying step further comprising the step of displaying on said video monitor the text of the locations containing information responsive to said query.

16. A system for locating information in a natural language text using a computer including a video monitor and a memory device for storing a data structure representing the natural language text,

wherein said data structure has a tree structure having nodes and levels, each node representing information from associated locations in said text, each of said locations having a corresponding location identifier, the information in each node being a categorical subset of information represented by a parent node of each node, each node being one level below its parent node in the tree structure and containing node constituents, said parent node and the nodes at higher levels of the tree structure that represent more general categories of information than the information represented by a node being ancestors of that node,

the system comprising:

query formatting means for formatting a query regarding information in the text into a query data structure;

comparison means for comparing the query data structure to a node to produce a comparison value representative of the degree of similarity between the query and the information represented by the node;

enhancing means for enhancing the comparison value by an amount representative of the degree of similarity between the query and the information represented by ancestors of the node to produce an enhanced comparison value;

storing means for storing the location identifiers associated with the node if the enhanced comparison value exceeds a predetermined lower bound and the node contributes information responsive to the query; and

display means for displaying the stored location identifiers on the video monitor.

17. A system for locating information in a natural language text using a computer including a video monitor and a memory device for storing a data structure representing said natural language text,

wherein said data structure has a tree structure having nodes and levels, each said node representing information from associated locations in said text, each of said locations having a corresponding location identifier, the information in a node being a categorical subset of information represented by a parent node of that node, each said node being one level below its parent node in said tree structure and containing node constituents,

said system comprising:

query formatting means for formatting a query regarding information in said text into a query data structure containing constituents of said query, each said query constituent representing a word or a phrase contained in said query;

matching means for producing a match vector having a plurality of match elements, said match vector being representative of a degree of similarity between said query data structure and one of said nodes, and each said match element corresponding in position to a predetermined query constituent and to a predetermined parent element of a parent vector;

merging means for merging said match vector with said parent vector to produce a merge vector having a plurality of merge elements, wherein each said merge element corresponds in position to a predetermined parent element, by setting each said merge element to be equal to the greater of its corresponding parent element and the match element corresponding to the corresponding parent element;

contribution detecting means for setting a contribution flag to true if any of said match elements is greater than zero and, at the same time, greater than or equal to said parent element corresponding to said match element;

contribution testing means for determining whether said contribution flag is set to true;

merge averaging means responsive to said contribution testing means for averaging said merge elements to produce a merge vector average;

threshold testing means for determining whether said merge vector average equals or exceeds a predetermined threshold value;

storing means responsive to said threshold testing means for storing the location identifiers associated with said node if said merge vector average equals or exceeds said predetermined threshold value, whereby stored location identifiers represent locations in said natural language text containing information responsive to said query;

substitution means for substituting said merge vector for said parent vector; and

display means for displaying on said video monitor said stored location identifiers.

18. The system of claim 17, said storing means further comprising means for storing said merge vector average as a confidence score associated with said stored location identifiers, and

said display means further comprising means for displaying on said video monitor said confidence scores associated with said stored location identifiers.

19. The system of claim 17, further comprising:

match averaging means for averaging said match elements to produce a match vector average;

reward means for adding a constant value to said match vector average to produce an enhanced match vector average if said match vector average equals or exceeds said predetermined threshold;

comparison means for outputting the greater of said enhanced match vector average and said merge vector average;

said storing means coupled to said comparison means for storing for display the output of said comparison means as a confidence score associated with said stored location identifiers; and

said display means further comprising means for displaying on said video monitor said confidence scores associated with said stored location identifiers.

20. The system of claim 19, further comprising:

semi-merge means coupled to said contribution testing means for successively replacing one element of the parent vector at a time with the corresponding match element to produce a semi-merge vector if said contribution flag is not true, wherein said semi-merge vector comprises all the elements of the parent vector except for the substituted match element, either until the average of the elements of said semi-merge vector equals or exceeds the predetermined threshold and the corresponding match element exceeds zero value, or until each element of the parent vector has been subject to replacement, and for thereafter setting said semi-merge vector to a nil value if the average of the elements of said semi-merge vector does not equal or exceed the threshold;

semi-merge testing means for determining whether said semi-merge vector is nil;

semi-merge averaging means responsive to said semi-merge testing means for averaging the elements of said semi-merge vector to produce a semi-merge vector average if said semi-merge vector is not nil; and

said comparison means further comprising means for outputting the greater of the enhanced matched vector average and the semi-merge vector average.

21. The system of claim 17, wherein said matching means comprises means for comparing each said query constituent with each said node constituent at a particular node to produce a constituent value representative of a degree of similarity between said query constituent and said node constituent, and for setting each said match element equal to the highest constituent value obtained as a result of comparing the query constituent corresponding to said match element to each said node constituent.

22. The system of claim 21, further comprising:

check means for setting a check flag if the comparison of two or more query constituents to the same node constituent results in the highest constituent values obtained for said two or more query constituents;

means coupled to said check means for selecting the greatest of said highest constituent values and setting the match element in the position corresponding to the query constituent associated with said greatest constituent value to the greatest constituent value if said check flag is set;

means for setting the match elements corresponding in position to the remaining query constituents that resulted in the highest match to the same node to the next highest constituent value obtained as a result of comparing said remaining query constituents to the other node constituents if said check flag is set.

23. The system of claim 17, further comprising query input means for enabling a user to input the query.

24. The system of claim 17, further comprising a threshold input means for determining said threshold value in response to a user input.

25. The system of claim 17, wherein said location identifiers are page numbers.

26. The system of claim 17, wherein said display means further comprises means for displaying on said video monitor the text of the locations containing information responsive to said query.