Navigation system for text

• US 7,774,198 B2
• Filed: 10/06/2006
• Issued: 08/10/2010
• Est. Priority Date: 10/06/2006
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Roulland, Frederic, Grasso, Antonietta, O'Neill, Jacki, Pettersson, Karin, Castellani, Stefania, Kaplan, Aaron N., Roux, Claude
• Primary Examiner(s): Smits; Talivaldis Ivars
• Assistant Examiner(s): ROBERTS, SHAUN A
• Application Number:
  US11/544,200
• Publication Number:
  US 20080091408A1
• Time in Patent Office: 1,404 Days
• Field of Search: 704/9, 707/3, 707/5, 707/765, 707/778, 715/853
• US Class Current: 704/9
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A computer retrieval system includes memory which stores instructions for (1) receiving a user query in a natural language, (2) identifying text strings from an associated knowledge base, each containing at least one expression (word or multi-word expression) which is matched with at least one expression of the user query, (3) refining the user query by representing at least a group of the text strings as a navigation tree in which each of a plurality of selectable nodes comprises an expression representative of at least one syntactic unit in at least one of the identified text strings and wherein relationships between syntactic units are used in structuring the nodes of the navigation tree, and (4) retrieving text from the knowledge base related to the refined query. A processor executes the instructions.

Claims

1. A computer retrieval system comprising:

memory which stores instructions comprising;

instructions for receiving a user query in a natural language;

instructions for identifying text strings from an associated knowledge base stored in associated memory, each identified text string in the knowledge base containing at least one expression which is matched with at least one expression of the user query, each text string comprising a sequence of words forming a sentence of a document;

instructions for refining the user query comprising instructions for representing at least a group of the text strings identified from different text documents as a navigation tree in which each of a plurality of selectable nodes comprises a linguistically coherent expression representative of at least one syntactic unit in at least one of the identified text strings and wherein parent-child relationships between syntactic units in text strings in the group of text strings are determined and used in structuring links between the respective nodes of the navigation tree, whereby in navigating the tree, a user is able to select nodes which refine the query by selecting a first node and selecting a second node which is linked to the first node in the tree, the first and second linguistically coherent expressions of the first and second nodes being representative of syntactic units in a same one of the identified text strings; and

instructions for retrieving text documents from the knowledge base related to the refined query; and

a processor which executes the instructions.

2. The system of claim 1, further comprising a user interface, in communication with the processor, which enables a user to input a user query and navigate the navigation tree.

3. The system of claim 1, wherein the instructions for identifying text strings comprise instructions for identifying a normalized form of at least one expression of the user query.

4. The system of claim 1, wherein the text strings are indexed in the associated knowledge base according to:

normalized forms of words in the text strings,

synonyms of at least some of the expressions in the text strings,

syntactic units in each of the text strings, and

relationships between the syntactic units in each of the text strings.

5. The system of claim 1, wherein the at least one expression which is matched in the knowledge base comprises at least one of:

the same expression as the at least one expression of the user query;

at least one expression whose words'"'"' lemma forms are the same as those of the at least one expression of the user query; and

a synonym of the at least one expression of the user query.

6. The system of claim 1, wherein the user query describes a problem experienced with a machine, each of the identified text strings comprising at least one of a problem statement and an associated solution sequence for addressing the problem with the machine.

7. The system of claim 1, wherein the instructions for refining the user'"'"'s query further comprise instructions for presenting subparts of the user'"'"'s query as alternate queries and for generating a navigation tree based on a user-selected one of the alternate queries.

8. The system of claim 1, wherein the syntactic units are selected from the group consisting of noun phrase chunks, prepositional phrase chunks, adverbial phrase chunks, adjectival phrase chunks, and verbal syntactic units.

9. The system of claim 8, wherein a verbal syntactic unit comprises a finite verb plus any associated auxiliary verbs, infinitive verbs, and adverbs, plus the verb'"'"'s direct object if any, plus the predicate if the verb is the verb “

be.”

10. The system of claim 1, wherein a node which would otherwise be a parent node having only one child node branching therefrom comprises an expression which represents syntactic units of the parent node and the child node.

11. The system of claim 1, wherein the relationships comprise syntactic dependency relationships between the syntactic units.

12. The system of claim 1, further comprising memory which stores the knowledge base.

13. The system of claim 1, further comprising instructions for identifying query matches and for ranking the identified query matches according to at least one predetermined ranking criterion, each of the query matches grouping a plurality of the identified text strings which have at least one underlying concept in common.

14. The system of claim 13, wherein the instructions for ranking the query matches include:

instructions for ranking the identified text strings according to at least one of;

the number of words in the user query for which a match is found in the identified text strings; and

the number of syntactic units in the identified text strings which match the user query.

15. The system of claim 2, wherein the system is a web-based system and the processor is located on a server and wherein the user interface is remote from the server.

16. The system of claim 2, wherein the user interface comprises a graphical user interface and a web browser.

17. The system of claim 1, wherein the expressions representative of syntactic units serve to group together syntactic units having the same normalized form.

18. A method for retrieving text strings responsive to a user'"'"'s query comprising:

inputting a query in a natural language;

identifying text strings from a knowledge base, each of the identified text strings comprising at least one expression which is matched with at least one expression of the user query;

for each of at least a group of the identified text strings, determining relationships between syntactic units of the text string;

representing the at least a group of the text strings as a navigation tree in which each of a plurality of user-selectable nodes comprises a linguistically coherent expression representative of at least one syntactic unit in at least one of the identified text strings and wherein the determined relationships between syntactic units are used in structuring links between the nodes of the navigation tree, the linguistically coherent expressions that are representative of syntactic units grouping together syntactic units from different text strings having the same normalized form, and wherein the navigation tree includes nodes as query refinement choices, each refinement choice node comprising a linguistically coherent expression representative of at least one syntactic unit in at least one of the identified text strings which does not match any expressions of the input user query; and

retrieving text from the knowledge base related to the nodes selected by a user during navigation of the tree.

19. The method of claim 18, wherein the representing at least a group of the text strings as a navigation tree comprises executing instructions for:

generating a node as the root of the tree that enables selection of all text strings in the group via a pathway linking the root node to a terminal node;

appending child nodes to the root node, each of the child nodes including at least one syntactic unit of at least one query response;

appending further child nodes to the child nodes to represent those syntactic units which, in one of the text strings, are in a parent-child relationship with the syntactic unit of the child node;

recursively appending nodes to previously appended child nodes or further child nodes to represent normalized forms of those remaining syntactic units of the text string; and

optionally, thereafter appending a distinguishing node to distinguish two text strings whose pathways are otherwise indistinguishable.

20. The method of claim 18, wherein when a text string includes a plurality of syntactic units, each of which contains an expression which matches an expression of the query, the appending of child nodes to the root node comprises selecting one of the plurality of syntactic units and generating the child node therefrom.

21. The method of claim 18, further comprising presenting subparts of the user'"'"'s query as alternate refinements and presenting a navigation tree for a selected one of the alternate refinements.

22. The method of claim 21, wherein the presenting of subparts of the user'"'"'s query as alternate query refinements is presented where none of the retrieved text strings includes normalized forms of all the query words.

23. The method of claim 18, further comprising displaying text related to a retrieved text string which is represented by a pathway navigated by a user through the navigation tree.

24. A computer program product comprising a tangible computer-readable recording medium encoding instructions, which when executed by a processor, performs the method of claim 18.

25. A system for retrieving text responsive to a query comprising:

a knowledge base which stores indexed text strings;

a graphical user interface for inputting a user query and displaying a navigation tree for user navigation of a group of text strings, each of the text strings being retrieved from the knowledge base as responsive to the user query;

a processor in communication with the user interface and the knowledge base which processes the user query and retrieves the text strings from the knowledge base, the processor executing instructions for;

identifying text strings in the knowledge base, wherein each of the identified strings includes at least one expression which matches at least one expression of the user query, the at least one matching expression having the same lemma form as the expression in the user query or being indexed in the knowledge base as being a synonym of the at least one expression in the user query;

identifying syntactic units in each of the retrieved text strings;

representing the identified syntactic units of a plurality of the retrieved text strings in the form of a navigation tree in which a plurality of nodes are connected to a root node, whereby a pathway from a root node to a terminal node of the connected nodes represents one of the retrieved text strings, the nodes of the pathway each representing at least one of the identified syntactic units; and

when a user navigates from a root node to a selected one of the connected nodes, displaying text retrieved from the knowledge base which is associated with the pathway.