User interface and other enhancements for natural language information retrieval system and method

Abstract

Techniques for generating sophisticated representations of the contents of both queries and documents in a retrieval system by using natural language processing (NLP) techniques to represent, index, and retrieve texts at the multiple levels (e.g., the morphological, lexical, syntactic, semantic, discourse, and pragmatic levels) at which humans construe meaning in writing. The user enters a query and the system processes the query to generate an alternative representation, which includes conceptual-level abstraction and representations based on complex nominals (CNs), proper nouns (PNs), single terms, text structure, and logical make-up of the query, including mandatory terms. After processing the query, the system displays query information to the user, indicating the system's interpretation and representation of the content of the query. The user is then given an opportunity to provide input, in response to which the system modifies the alternative representation of the query. Once the user has provided desired input, the possibly modified representation of the query is matched to the relevant document database, and measures of relevance generated for the documents. A set of documents is presented to the user, who is given an opportunity to select some or all of the documents, typically on the basis of such documents being of particular relevance. The user then initiates the generation of a query representation based on the alternative representations of the selected document(s).

Claims

What is claimed:

1. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a natural language query specifying information to be retrieved;

processing the query to generate an alternative representation of the query, the alternative representation including generating a logical representation incorporating terms and phrases found in the query and assigning weighted Boolean scores to the query terms;

displaying query information to the user indicating the result of said step of processing the query;

receiving user input responsive to the display of query information;

in response to such user input, if any, modifying the alternative representation of the query to reflect such user input; and

matching the alternative representation of the query, modified in accordance with such user input, if any, against the database.

2. The method of claim 1 wherein:

the alternative representation of the query includes a conceptual level defined by subset of a finite set of subject codes, the subset corresponding to subject codes interpreted by the system to characterize the subject contents of the query.

3. The method of claim 1 wherein

the user input specifies increasing or decreasing the set of terms and phrases.

4. The method of claim 1 wherein:

the alternative representation of the query includes a set of terms and phrases found in the query that are interpreted by the system to be mandatory requirements for relevance; and

the user input specifies increasing or decreasing the set of terms and phrases.

5. The method of claim 1 wherein:

the database contains documents that have been processed to generate corresponding alternative representations of the documents.

6. The method of claim 5, and further comprising the steps, performed after said step of matching the alternative representation of the query, of:

for at least some documents in the database, generating a measure of relevance of the document to the query using the alternative representation of the document and the alternative representation of the of the query; and

displaying a list of documents whose measures of relevance are deemed sufficiently high.

7. The method of claim 6, and further comprising the steps, performed after said step of displaying a list of documents, of:

receiving user input specifying selection of at least some of the list of documents;

using the alternative representations of the documents, so selected, to generate a new query representation; and

matching the new query representation against the database.

8. The method of claim 7 wherein the new query representation is a combination of the alternative representation of the query and the alternative representations of the documents, so selected.

9. The method of claim 7 wherein the new query representation does not depend on the alternative representation of the query.

10. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a natural language query specifying information to be retrieved;

processing the query to abstract the query to an alternative representation suitable for input to a database of documents, each document of which is abstracted to a corresponding alterative representation;

displaying query information to the user indicating the result of said step of processing the query, the query information including a number of items characterizing the query including a subset of a finite set of subjects, the subset corresponding to subjects interpreted by the system to characterize the subject contents of the query;

entering a mode that permits user modification of the items of query information;

remaining in the mode pending user input that specifies exiting the mode, user input that specifies exiting the mode including a request to execute the query;

while in the mode, receiving user modifications, if any, of the items of query information; and

in response to a request to execute the query, executing the query, modified in accordance with any user modifications of the items of query information, against the database.

11. The method of claim 10 wherein user input specifying exiting the mode further includes:

a request to modify the query; and

a request to input a new query.

12. The method of claim 10 wherein:

the query includes a proper noun;

the query information includes a plurality of variations representing an expansion of the proper noun.

13. The method of claim 10 wherein:

the query includes a particular term; and

the query information includes a plurality of variations representing an expansion of the particular term.

14. The method of claim 10 wherein

the user modifications include increasing or decreasing the subset of subjects.

15. The method of claim 10 wherein:

the query information is a set of terms and phrases found in the query that are interpreted by the system to be mandatory requirements for relevance; and

the user modifications include increasing or decreasing the set of terms and phrases.

16. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

processing a natural language query specifying information to be retrieved to generate an alternative representation of the query, the alternative representation including generating a logical representation incorporating terms and phrases found in the query and assigning weighted Boolean scores to the query terms;

matching the alternative representation of the query, against the database;

for at least some documents in the database, generating a measure of relevance of the document to the query using a common alternative representation of the document and the alternative representation of the query; and

displaying a list of documents whose measures of relevance are determined by the system to be sufficiently high;

receiving user input specifying selection of at least a portion of at least some of the list of documents;

using the alternative representations of the documents, or portions of documents, so selected, to generate a new query representation; and

matching the new query representation against the database.

17. The method of claim 16 wherein the new query representation is a combination of the alternative representation of the query and the alternative representations of the documents or portions of documents, so selected.

18. The method of claim 16 wherein the new query representation does not depend on the alternative representation of the query.

19. The method of claim 16 wherein:

the alternative representation of the query includes a conceptual level defined by subset of a finite set of subject codes, the subset corresponding to subject codes interpreted by the system to characterize the subject contents of the query; and

the user input specifies increasing or decreasing the subset of subject codes.

20. The method of claim 16 wherein

the user input specifies increasing or decreasing the set of terms and phrases.

21. The method of claim 16 wherein:

the alternative representation of the query is a set of terms and phrases found in the query that are interpreted by the system to be mandatory requirements for relevance; and

the user input specifies increasing or decreasing the set of terms and phrases.

22. The method of claim 16 wherein:

the database contains documents that have been processed to generate corresponding alternative representations of the items in the database.

23. In a computerized information retrieval system where documents in a database are retrieved in response to user queries, with each document being processed to produce a respective alternative representation and each query being processed to provide a corresponding alternative representation, the alternative representation of the query including generating a logical representation incorporating terms and phrases found in the query and assigning weighted Boolean scores to the query terms, a method comprising:

presenting the user with a list of documents, each document having a respective alternative representation;

receiving user input specifying selection of at least a portion of at least some of the list of documents;

using the alternative representations of the documents, or portions of documents, so selected, to generate a query representation; and

matching the query representation against the database.

24. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a natural language query specifying information to be retrieved;

extracting terms that appear in the query;

detecting words that indicate negation of interest in certain information;

if a word that indicates negation is detected, determining which of the terms belong to a negative portion of the query and which of the terms belong to a positive portion of the query;

generating an alternative representation of the query that includes the terms in both the positive and negative portions of the query;

matching the alternative representation of the query against the database by determining a measure of relevance for each document;

providing a set of documents that satisfy a retrieval criterion; and

within the set of documents, so provided, segregating those documents that satisfy only the positive portion of the query from those documents that satisfy both the positive and negative portions of the query.

25. The method of claim 24 wherein:

the alternative representation of the query includes a plurality of individual representations;

said step of determining a measure of relevance for each document includes, for each document, determining a score for each of the individual representations, and combining the scores; and

at least one of the individual representations does not include the terms in the negative portion of the query.

26. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a natural language query specifying information to be retrieved;

extracting terms that appear in the query;

detecting words that indicate that a given term is required to be in a retrieved document;

if a word that indicates a mandatory term is detected, determining which of the terms are indicated to be mandatory;

generating an alternative representation of the query that includes both the terms that are indicated to be mandatory and the terms that are not indicated to be mandatory, the alternative representation including a logical representation wherein the mandatory terms are logically connected to the query terms using an AND fuzzy Boolean operator;

matching the alternative representation of the query against the database by determining a measure of relevance for each document;

providing a set of documents that satisfy a retrieval criterion; and

within the set of documents, so provided, segregating those documents that satisfy the mandatory portion of the query from those documents that do not satisfy the mandatory portion of the query.

27. The method of claim 26, and further comprising the steps, performed before said matching step, of:

displaying query information to the user indicating the terms that are interpreted by the system to be mandatory;

receiving user input responsive to the display of such query information; and

in response to such user input, if any, modifying the alternative representation of the query to reflect such user input.

28. The method of claim 26 wherein:

said matching step includes increasing a document's measure of relevance if the document satisfies the mandatory portion of the query.

29. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a natural language query specifying information to be retrieved;

detecting linguistic clues, such as function words and punctuation, signifying logical relations among terms in the query;

generating a logical representation of the query, incorporating the terms, linked on the basis of the linguistic clues signifying logical relations among the terms;

assigning a respective weighted Boolean score to each term in the logical representation, the weighted Boolean scores based on the logical relations among the query terms;

comparing the logical representation of the query with a document to be scored;

for each term in the logical representation, (a) if that term is found in the document, assigning a possible weight corresponding to the weighted Boolean score to that term, and (b) otherwise assigning a zero weight to that term;

combining the weights, so assigned; and

computing a score based on the weights, so combined.

30. The method of claim 29 wherein:

the weighted Boolean scores have maximum values such that the score is 1 if all the terms in the logical representation are present in the document.

31. The method of claim 29 wherein:

a weight for ANDed terms is determined as the sum of weighted scores for the ANDed terms; and

a weight for ORed terms is determined as the maximum of the weighted scores for the ORed terms.

32. A method of operating a computerized information retrieval system where information is retrieved from a database containing documents in response to user queries, the method comprising:

receiving a natural language query specifying information to be retrieved;

processing the query to generate an alternative representation of the query;

processing the documents to generate respective alternative representations of the documents, the alternative representation of a given document including a conceptual level defined by subject areas interpreted by the system to characterize the subject contents of the document;

matching the alternative representation of the query against the database by determining a measure of relevance for each document;

providing of documents meeting a retrieval criterion;

determining a set of subject areas that are present in the conceptual level representations of the documents, so provided;

for at least some subject areas in the set, providing groups of documents having that subject area as part of their conceptual level representations.

33. The method of claim 32, and further comprising displaying a representation of folders having subject area labels.

34. The method of claim 32 wherein:

the retrieval criterion requires a document to be in the group having the highest measures of relevance.

Description

BACKGROUND OF THE INVENTION

The present invention relates generally to the field of computer-based information retrieval, and more specifically to the application of natural language processing (NLP) techniques to the interpretation and representation of computer text files, and to the matching of natural language queries to documents with the aid of user interactions.

Computer-based information retrieval is now an established industry serving many professional communities. Retrieval technologies used in this industry share many common features. For example, a user of these systems is typically required to either (1) state an information need, or query, in a circumscribed manner, usually by demarcing the logical requirements of the query as a sequence of terms linked by various operators, or (2) write the query as free-form text, which is then parsed automatically into a sequence of words or phrases, without regard for the logical form of the query or the underlying meaning of the query. In either event the query is represented only by the collection of words that are overtly stated in the query text (or limited stemmed forms of some words, such as plurals). The matching of documents to a query is based on the co-occurrence of these words or phrases.

A second commonality among retrieval systems is that a query representation derived from a user's query statement is automatically formed by the computer system, with limited or no interaction with the user. In most retrieval systems, once an initial query statement has been made in full, the computer system interprets the contents of the query without allowing the user to verify, clarify or expand upon query representations created by the computerized retrieval system. In the same fashion, the subsequent display of retrieved documents is largely under computer control, with little user interaction.

In view of these common characteristics of computer-based retrieval systems, their inability to capture both the preciseness and richness of meaning in queries and documents, and their inability to interact with the user to help formulate a query statement and present retrieved documents, retrieval is often an inexact process.

SUMMARY OF THE INVENTION

The present invention provides techniques for generating sophisticated representations of the contents of both queries and documents in a retrieval system by using natural language processing (NLP) techniques to represent, index, and retrieve texts at the multiple levels (e.g., the morphological, lexical, syntactic, semantic, discourse, and pragmatic levels) at which humans construe meaning in writing. The invention also offers the user the ability to interact with the system to confirm and refine the system's interpretation of the query content, both at an initial query processing step and after query matching has occurred.

According to one aspect of the invention, the user enters a query, possibly a natural language query, and the system processes the query to generate an alternative representation. This alternative representation may include conceptual-level abstraction and enrichment of the query, and may include other representations. In a specific embodiment, the conceptual-level representation is a subject field code vector, while the other representations include one or more of representations based on complex nominals (CNs), proper nouns (PNs), single terms, text structure, and logical make-up of the query, including mandatory terms. After processing the query, the system displays query information to the user, indicating the system's interpretation and representation of the content of the query. The user is then given an opportunity to provide input, in response to which the system modifies the alternative representation of the query. Once the user has provided desired input, the possibly modified representation of the query is matched to the relevant document database, and measures of relevance generated for the documents. The documents in the database have preferably been processed to provide corresponding alternative representations for matching to queries.

According to a further aspect of the invention, a set of documents is presented to the user, who is given an opportunity to select some or all of the documents, typically on the basis of such documents being of particular relevance. The user then initiates the generation of a query representation based on the alternative representations of the selected document(s). To the extent that the set of documents were retrieved in response to a previous query, the alternative representations of the selected documents may be combined with the alternative representation of the previous query. Thus the user is able to improve on an initial query representation by re-expressing the query as a composite of the representations derived from documents deemed highly relevant by the user, possibly combined with the representation of the original query.

According to a further aspect of the invention, a natural language query is processed to generate a logical representation of terms in the query. The system recognizes words that indicate negation, and divides the terms in the query as to whether such terms belong to the positive or negative portion of the query. In recognition of the fact that a document dealing with the negative portion of the query may contain information relevant to the positive portion, the system is designed to incorporate the terms in the negative portion of the query into the alternative representation of the query. However, in further recognition that the user explicitly specified certain types of subject matter as not being of interest, documents satisfying both the positive and negative portions of the query are segregated from documents meeting only the positive portion of the query.

According to a further aspect of the invention, a natural language query is processed to generate a logical representation of terms in the query. The system recognizes words that indicate a mandatory requirement of the query, and the presence of mandatory terms in a document can be given greater weight in matching. Whether or not the presence of mandatory terms enters into the score, documents containing the mandatory terms are identified and preferably segregated from documents that do not contain all the mandatory terms.

According to a further aspect of the invention, texts (documents and queries) are processed to determine discourse aspects of the text beyond the subject matter of the text. This text structure includes temporal information (past, present, and future), and intention information (e.g., analysis, prediction, cause/effect). Thus the invention is able to detect the higher order abstractions that exist in human communications that are above the word level, such as the difference between a statement describing an expected outcome, the consequence of a particular event (prediction), or a statement that described a past event. Since the system is able to recognize the manifold intentions in a query, it can operate on a greater scope of documents and data without the user having to pre-specify where one suspects the answers (documents) might be.

The sophistication of the text representation used in the invention means that certain discourse that exophorically references tables, graphs, photographs or other images can also be used to search with great efficiency for such images. For example, the captions used to label photographs has a certain discourse structure, and this structure can be used to help effectively search for graphic items.

According to a further aspect of the invention, the system automatically sorts, ranks and displays documents judged relevant to the content of the query, using a multi-tier system of folders containing ranked lists of documents. The inclusion of a document and its position within a folder are typically determined by a relevance score based on the various elements of the alternative representation. However, the user can modify both the viewing order and the sorting order based on one or more of the following: conceptual level subject content codes; the presence or absence of various proper nouns, including personal names, company names, countries, cities, titles, etc.; the presence or absence of various terms or phrases; the text structure of the document, such as the time frame, or the presence of various requirements such as analytic information, cause/effect dimension, predictions, etc.; the presence or absence of negated expressions; the document date or range of dates; the document source; the document author; the document language; and a similarity score criterion for the document.

A further understanding of the nature and advantages of the present invention may be realized by reference to the remaining portions of the specification and the drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of an information retrieval system embodying the present invention;

FIG. 2 is a more detailed block diagram of the interactions between the user and the system during text processing portion for information retrieval;

FIG. 3 is a block diagram of the document processing portion of the system;

FIG. 4 shows the document indexing structure for terms;

FIG. 5 a block diagram of the query processing portion of the system;

FIG. 6 is a tree-form logical representation of a query statement;

FIG. 7 shows an example of clustering;

FIG. 8 is a screen shot showing the general features common to most screens used in the graphic user interface (GUI);

FIGS. 9A and 9B, taken together, form a flow diagram showing the GUI-based interactive process of text retrieval;

FIG. 10 is the sign-on screen;

FIG. 11 is the query screen;

FIG. 12 is the database selection screen;

FIG. 13 is the date and/or time selection screen;

FIG. 14A is the full query processing (QP) review screen;

FIG. 14B is a detail of FIG. 14A, showing the arrangement of terms in the QP review screen;

FIG. 15 is the retrieved documents view screen (document headlines in folders);

FIG. 16 is the retrieved documents view screen (foldered by subject field code);

FIG. 17 is a retrieved document view screen (summary representation of a document);

FIG. 18 is a retrieved document view screen (full text of a document);

FIG. 19 is the More Like Marked (MLM) screen showing marked documents in folders; and

FIG. 20 is the More Liked Marked (MLM) screen showing results of a MLM-based query.

DESCRIPTION OF SPECIFIC EMBODIMENTS

1.0 Introduction

This application describes a computer system used for information retrieval that, through a sequence of computer and user interactions, allows the expression and clarification of complex query statements and the retrieval and display of relevant documents using natural language processing (NLP) techniques. The system incorporates aspects described in a paper by Liddy et al. [Liddy94a]. The system is referred to in the paper as DR-LINK (Document Retrieval using Linguistic Knowledge), and will also sometimes be referred to as DR-LINK in this application.

This application is divided into two parts. In the first part, a detailed description is given of the underlying software processing that facilitates NLP-based text retrieval. In the second part, a description is given of the graphic user interface (GUI) and the sequence of interactions that occur between the software processing system and the user.

Unless otherwise stated, the term "document" should be taken to mean text, a unit of which is selected for analysis, and to include an entire document, or any portion thereof, such as a title, an abstract, or one or more clauses, sentences, or paragraphs. A document will typically be a member of a document database, referred to as a corpus, containing a large number of documents. Such a corpus can contain documents in any or all of the plurality of supported languages.

Unless otherwise stated, the term "query" should be taken to mean text that is input for the purpose of selecting a subset of documents from a document database. While most queries entered by a user tend to be short compared to most documents stored in the database, this should not be assumed. The present invention is designed to allow natural language queries.

Unless otherwise stated, the term "word" should be taken to include single words, compound words, phrases, and other multi-word constructs. Furthermore, the terms "word" and "term" are often used interchangeably. Terms and words include, for example, nouns, proper nouns, complex nominals, noun phrases, verbs, adverbs, numeric expressions, and adjectives. This includes stemmed and non-stemmed forms.

The disclosures of all articles and references, including patent documents, mentioned in this application are incorporated herein by reference as if set out in full.

1.1 System Hardware Overview

FIG. 1 is a simplified block diagram of a computer system 10 embodying the text retrieval system of the present invention. The invention is typically implemented in a client-server configuration including a server 20 and numerous clients, one of which is shown at 25. The use of the term "server" is used in the context of the invention, where the server receives queries from (typically remote) clients, does substantially all the processing necessary to formulate responses to the queries, and provides these responses to the clients. However, server 20 may itself act in the capacity of a client when it accesses remote databases located on a database server. Furthermore, while a client-server configuration is known, the invention may be implemented as a standalone facility, in which case client 25 would be absent from the figure.

The hardware configurations are in general standard, and will be described only briefly. In accordance with known practice, server 20 includes one or more processors 30 that communicate with a number of peripheral devices via a bus subsystem 32. These peripheral devices typically include a storage subsystem 35 (memory subsystem and file storage subsystem), a set of user interface input and output devices 37, and an interface to outside networks, including the public switched telephone network. This interface is shown schematically as a "Modems and Network Interface" block 40, and is coupled to corresponding interface devices in client computers via a network connection 45.

Client 25 has the same general configuration, although typically with less storage and processing capability. Thus, while the client computer could be a terminal or a low-end personal computer, the server computer would generally need to be a high-end workstation or mainframe. Corresponding elements and subsystems in the client computer are shown with corresponding, but primed, reference numerals.

The user interface input devices typically includes a keyboard and may further include a pointing device and a scanner. The pointing device may be an indirect pointing device such as a mouse, trackball, touchpad, or graphics tablet, or a direct pointing device such as a touchscreen incorporated into the display. Other types of user interface input devices, such as voice recognition systems, are also possible.

The user interface output devices typically include a printer and a display subsystem, which includes a display controller and a display device coupled to the controller. The display device may be a cathode ray tube (CRT), a flat-panel device such as a liquid crystal display (LCD), or a projection device. Display controller provides control signals to the display device and normally includes a display memory for storing the pixels that appear on the display device. The display subsystem may also provide non-visual display such as audio output.

The memory subsystem typically includes a number of memories including a main random access memory (RAM) for storage of instructions and data during program execution and a read only memory (ROM) in which fixed instructions are stored. In the case of Macintosh-compatible personal computers the ROM would include portions of the operating system; in the case of IBM-compatible personal computers, this would include the BIOS (basic input/output system).

The file storage subsystem provides persistent (non-volatile) storage for program and data files, and typically includes at least one hard disk drive and at least one floppy disk drive (with associated removable media). There may also be other devices such as a CD-ROM drive and optical drives (all with their associate removable media). Additionally, the system may include drives of the type with removable media cartridges. The removable media cartridges may, for example be hard disk cartridges, such as those marketed by Syquest and others, and flexible disk cartridges, such as those marketed by Iomega. One or more of the drives may be located at a remote location, such as in a server on a local area network or at a site on the Internet's World Wide Web.

In this context, the term "bus subsystem" is used generically so as to include any mechanism for letting the various components and subsystems communicate with each other as intended. With the exception of the input devices and the display, the other components need not be at the same physical location. Thus, for example, portions of the file storage system could be connected via various local-area or wide-area network media, including telephone lines. Similarly, the input devices and display need not be at the same location as the processor, although it is anticipated that the present invention will most often be implemented in the context of PCs and workstations.

Bus subsystem 32 is shown schematically as a single bus, but a typical system has a number of buses such as a local bus and one or more expansion buses (e.g., ADB, SCSI, ISA, EISA, MCA, NuBus, or PCI), as well as serial and parallel ports. Network connections are usually established through a device such as a network adapter on one of these expansion buses or a modem on a serial port. The client computer may be a desktop system or a portable system.

The user interacts with the system using user interface devices 37' (or devices 37 in a standalone system). For example, client queries are entered via a keyboard, communicated to client processor 30', and thence to modem or network interface 40' over bus subsystem 32'. The query is then communicated to server 20 via network connection 45. Similarly, results of the query are communicated from the server to the client via network connection 45 for output on one of devices 37' (say a display or a printer), or may be stored on storage subsystem 35'.

1.2 Text Processing (Software) Overview

The server's storage subsystem 35, as shown in FIG. 1, maintains the basic programming and data constructs that provide the functionality of the DR-LINK system. DR-LINK software is designed to (1) process text stored in digital form (documents) or entered in digital form on a computer terminal (queries) to create a database file recording the manifold contents of the text, and (2) match discrete texts (documents) to the requirements of a user's query text. DR-LINK provides rich, deep processing of text by representing and matching documents and queries at the lexical, syntactic, semantic and discourse levels, not simply by detecting the co-occurrence of words or phrases. Users of the system are able to enter queries as fully-formed sentences, with no requirement for special coding, annotation or the use of logical operators.

The system is modular and performs staged processing of documents, with each module adding a meaningful annotation to the text. For matching, a query undergoes analogous processing to determine the requirements for document matching. The system generates both conceptual and term-based representations of the documents and queries. It is convenient to refer to the collection of various representations which the system produces for each document or for each query as "the alternative representation" for that document or query. Put another way, a reference to "the alternative representation," should be taken to encompass a single representation, or any or all of the plurality of representations.

The processing modules include a set of processing engines, shown collectively in a processing engine block 50, and a query-document matcher 55. It should be understood, however, that by the time a user is entering queries into the system, the relevant document databases will have been processed and annotated, and various data files and data constructs will have been established. These are shown schematically as a "Document Database and Associated Data" block 60, referred to collectively below as the document database. An additional set of resources 65, possibly including some derived from the corpus at large, is used by the processing engines in connection with processing the documents and queries. Alternatively, documents can be processed and annotated on the fly as they arrive in real time.

User interface software 70 allows the user to interact with the system. The user interface software is responsible for accepting queries, which it provides to processing engine 50. The user interface software also provides feedback to the user regarding the system's interpretation of the query, and accepts responsive feedback from the user in order to reformulate the query. The user interface software also presents the retrieved documents as a result of the query to the user and reformats the output in response to user input. User interface software 70 is preferably implemented as a graphical user interface (GUI), and will often be referred to as the GUI.

1.3 GUI Interaction Overview

FIG. 2 is a more detailed block diagram of the text processing portion of the system, showing the nature of the interactions between the user and the system. In the figure, processing engine block 50 has been broken into document processing engines 50D, collectively referred to as the document processor, and query processing engines 50Q, collectively referred to as the query processor (QP). Each has its own resources, shown as document processor resources 65D and query processor resources 65Q. It should be understood that some of the resources can be shared resources.

GUI 70 is shown as a single block with inputs and outputs, as well as links to matcher 55, QP 50Q, and an additional module 77, called "More Like Marked" (MLM). As well as providing exceptionally rich and powerful document and query representations, user interface enhancements allow the user to interact with the retrieval process.

Documents are shown as being input to document processor 50D, which outputs a set of tagged documents 72 and a document index file 75, which stores alternative representations of the documents for use by matcher 55. Similarly, queries are shown as being input to GUI 70, and communicated to query processor 50Q, which generates an alternative representation of the query for use by the matcher. As noted above, and will be described in detail below, the alternative representation for a document or a query typically includes several different types of information that the system has generated based on the content of the document or query.

Matcher 55 executes the query by comparing the query representation to the document representations, and provides results to GUI 70 for display and other action. However, before the query representation is sent to the matcher, results of the query processing (indicating the query representation) are displayed for the user. This provides the user an opportunity to provide input specifying modification of the query representation. This user feedback is shown schematically as a semi-elliptical arrow in the figure. QP 50Q modifies the query representation accordingly before sending the query representation to matcher 55.

Once the query, possibly modified, is executed, the search results are displayed to the user. The user is then able to provide feedback to the system by marking documents that are considered particularly relevant. The representations of these documents are then used by MLM module 77 to create a further revised query for execution. This feedback based on document relevance is referred to as relevance feedback.

2.0 Document Processing

2.1 Document Processing Overview

FIG. 3 is a block diagram showing the document processing modules within document processor 50D, and some associated resources. The set of modules that perform the processing to generate the conceptual representation and the term-based representation of each document includes:

a preprocessor 80;

a part of speech (POS) tagger 90, with its associated POS, end of sentence detection, and lexical clue databases;

a subject field coder (SFC) 100, with its associated concept category database containing a hierarchy of concept categories for all words, domain knowledge concept category correlation matrix database used to disambiguate concept categories at the domain level, and global knowledge concept category sense-frequency database used to disambiguate concept categories at the global level;

a proper noun (PN) categorizer (PNC) 110, with its associated proper noun bracketer database used to bracket PNs with embedded conjunctions and/or prepositions, proper noun category databases used to categorize PNs, proper noun prefix/suffix database used to identify PN categories by reference to the suffix or prefix, and proper noun clarification database which presents alternative proper names based on what user has typed in the query;

a complex nominal (CN) detector 120,

single term detector 130, with its associated numeric information database used to identify and catalog numeric data types (currency, temperature, etc.);

a text structurer 140, with its associated text structure evidence phrase database used to gather evidence for a particular text structure; and

a term indexer 150.

In the course of operation, SFC 100 and term indexer 150 write document information into database index file 75, which as mentioned above, is used for query matching.

2.2 Document Preprocessor 80

Document preprocessor 80 transforms raw digital data files of text into a uniform format suitable for further processing by the DR-LINK system. Preprocessing involves some discourse-level manipulation of text, such as the explicit decomposition of composite documents into appropriate sub-texts. All text is annotated with pseudo-SGML tags. Preprocessing tags include, but are not limited to, fields such as <caption>, <date>, <headline>, <sub-text headline>, and <sub-text>, <Fig.> and <table>. The preprocessor further identifies various fields, clauses, parts-of-speech and punctuation in a text, and annotates a document with identifying tags for these units. The identification process occurs at the sentence, paragraph and discourse levels and is a fundamental precursor to later natural language processing and document-query matching.

2.3 Part-of-Speech (POS) Tagger 90

In a current implementation, documents are first processed using a custom End-of-Sentence detection program, followed by a commercial off-the-shelf (COTS) probabilistic part-of-speech (POS) tagger of the type provided by such companies as Inso Corporation, Boston, Mass. The POS tagger identifies over 47 grammatical forms and punctuation marks. In addition, hyphenated words are often given multiple tags--each constituent word is given a tag, and the whole hyphenated phrase is given a tag. The preferred implementation performs additional processing of text, numerals, and other markings and attributes beyond that of the commercial POS tagger (see discussion of additional modules below).

2.4 Subject Field Coder (SFC) 100

Using the text output from the POS tagger, the SFC 100 tags content-bearing words in a text with a disambiguated subject code using an online lexical resource of words whose senses are grouped in subject categories. This is described in detail in copending patent application Ser. No. 08/135,815, filed Oct. 12, 1993, entitled "Natural Language Processing System For Semantic Vector Representation Which Accounts For Lexical Ambiguity," to Elizabeth D. Liddy, Woojin Paik, and Edmund Szu-Li Yu. The application mentioned immediately above, hereinafter referred to as "Natural Language Processing," is hereby incorporated by reference for all purposes.

A subject field code indicates the conceptual-level sense or meaning of a word or phrase. The current implementation, with 680 hierarchically arranged sub-categories, offers sufficient resolution without too much diffusion of the codes. The present invention, however, is not limited to a specific hierarchical arrangement or a certain number of subject field codes.

Each information bearing word in a text is looked up in the online, lexical resource. If the word is in the lexicon, it is assigned a single, unambiguous subject code using, if necessary, a process of disambiguation. Once each content-bearing word in a text has been assigned a single SFC, the frequencies of the codes for all words in the document are combined to produce a fixed length, subject-based vector representation of the document's contents. This relatively high-level, conceptual representation of documents and queries is an important representation of texts used for later matching and ranking.

Polysemy (the ability of a word to have multiple meanings) is a significant problem in information retrieval. Since words in the English language have, on average, about 1.49 senses, with the most commonly occurring nouns having an average of 7.3 senses, and the most commonly occurring verbs having an average of 12.4 senses [Gentner81], a process of disambiguation is involved in assigning a single subject field code to a word.

Words with multiple meanings (and hence multiple possible subject field code assignments) are disambiguated to a single subject field code using three evidence sources (this method of disambiguation has general application in other text processing modules to help improve performance):

2.4.1 Local Context. If a word in a sentence has a single subject code tag, it is Unique. If there are any subject codes that have been assigned to more than a pre-determined number of words in a sentence, then the codes are Frequent Codes. These two types of codes are used as anchors to disambiguate the remaining words in a sentence that share the same codes.

2.4.2 Domain Knowledge. Certain subject codes are highly correlated with other codes within a given domain. This strong association is used to disambiguate polysemous words that cannot be disambiguated using local context.

2.4.3 Global Knowledge. If words cannot be disambiguated in steps 1 or 2, then the most frequently used sense of a word is invoked.

The fixed-length vector representation of the subject contents of a text is stored in database index file 75 along with other index representation of the text.

2.5 Proper Noun Detector and Categorizer (PNC) 110

Proper nouns, group proper nouns (e.g., the Far East) and group common nouns (e.g., anti-cancer drugs) are recognized as important sources of information for detecting relevant documents in information retrieval [Paik93a]. PNC 110 first locates the boundaries of proper noun phrases using the POS tags mentioned earlier, and other text analysis tools. Heuristics developed through corpus analysis are applied to bracket proper noun phrases which contain embedded conjunctions and prepositions (e.g., Department of Defense, Centers for Disease Control and Prevention).

PN categorization is the process whereby a proper noun is assigned to a single category rather like the concept categories used in SFC 100. Categories include city, state, country, company, person, etc. The current DR-LINK proper noun classification scheme is expanded and modified from earlier attempts, and over 40 concept categories, which in tests correctly account for over 89% of all proper nouns, with the remainder being classified as "miscellaneous." This invention is not dependent on a specific number of concept categories or a specific arrangement of categories.

The proper noun classification scheme is based on algorithmic machine-aided corpus analysis. In a specific implementation, the classification is hierarchical, consisting of branch nodes and terminal nodes, but this particular hierarchical arrangement of codes is but one of many arrangements that would be suitable.

Table 1 shows a representative set of proper noun concept categories and subcategories.

                  TABLE 1
    ______________________________________
    Proper Noun Categories and Subcategories
    Geographic Entity:   Human:
    City                 Person
    Port                 Title
    Airport              Document:
    Island               Periodicals/Books
    County               Treaties/Laws/Acts
    Province             Equipment:
    Country              Software
    Continent            Hardware
    Region               Machines
    Water                Scientific:
    Geographic Miscellaneous
                         Disease
    Affiliation:         Drugs
    Religion             Chemicals
    Nationality          Organic Matter
    Organization:        Temporal:
    Company              Date
    Company Type         Time
    Sports Franchise     Holiday
    Government           Miscellaneous:
    U.S. Government      Miscellaneous
    Education/Arts Services
    Political Organization
    Religious Organization
    ______________________________________

                  TABLE 2
    ______________________________________
    Text Structure Tags
    Tag  Description      Examples of Evidence Phrases
    ______________________________________
    AN   Analysis or opinion of a
                          Advantages; Disadvantages; In
         person, action or event.
                          anticipation of; Pro; Con.
    CE   Cause and/or Effect Noted.
                          As a means of, Gives rise to;
                          Designed to; Affects, Impacts;
                          Repercussions.
    CR   Credential.      Officer; Chief; Credential; Duties;
                          Title.
    ED   Editorial.       Editorial.
    FA   Factual Information.
                          Number of; How many; The date
                          of the highest; The least.
    FU   An Action or Event that
                          Looking ahead to; Coming months;
         takes place in the Future.
                          Emerging; Expected; Trends.
    HL   Headline.        (From Text Preprocessing)
    IN   Instructions.    Instructions; Directions; Method
                          for; Ingredients; Steps in
                          the process.
    LP   Lead Paragraph.  First paragraph of a document.
    OB   Obituary.        Obituary; Death notice; Died
                          today.
    OG   An Action or Event is
                          Over the months; Continuing;
         Ongoing in the Present.
                          Daily; Trends.
    PA   An Action or Event that took
                          In the last few years; In the past;
         place in the Past (1 yr or
                          History; Ancient.
         more).
    PR   An Action or Event that took
                          Past few months; 1st. Quarter;
         place in the Recent Past
                          Prior month; Recently.
         (one week to 1 yr. ago).
    QU   A Direct or Indirect Quote.
                          Statements by; Announces;
                          Quoting; Testified.
    ST   A Reference to Stock, Bond
                          Dow opened; Nikkei closed; Stock
         or other Financial
                          reports; Dividends, NYSE.
         Information.
    RV   Reviews of a Product,
                          Standards and specifications;
         Service, or other entity.
                          Evaluate; Review; Test.
    ______________________________________

                  TABLE 3
    ______________________________________
    Structure for Aspects Probability Matrix (APM) database
    Evidence Phrase
                 AN Tag  EV Tag    CE Tag
                                         FA Tag
    ______________________________________
    Phrase #1    0.811   0.100     0.000 0.005
    Phrase #2    0.100   0.144     0.337 0.107
    Phrase #3    0.000   0.000     0.567 0.122
    ______________________________________

                  TABLE 4
    ______________________________________
    Term Record for Index
    1. Index Term
                2.    3.       4.  5.      6.  7.
    ______________________________________
    Document retrieval
                25    3425     2   FA/QU   1/9 525
    Information retrieval
                19    3425     1   FA      1   131
    ______________________________________

                  TABLE 5
    ______________________________________
    Operators Used for Boolean Representation
    Operator
           Operation    Fuzzy Weight/Score
    ______________________________________
    AND    Boolean AND  Addition of scores from ANDed terms
    OR     Boolean OR   Maximum score from all ORed terms
    !NOT   Negation     --
    #AND   Conditional AND
                        head term #AND tail term. If head term
                        present, revert to AND, else 0
    *AND   Mandatory marker
                        query *AND mandatory. Used to
                        separate mandatory elements for
                        later foldering. Scores as AND.
    =AND   Proximity AND
    ______________________________________

    ______________________________________
    <POSITIVE>
    document.sub.-- retrieval .vertline.AN, FU.vertline. 0.5
    &AND
    information.sub.-- extraction .vertline.AN, FU.vertline. 0.5
    }
    </POSITIVE>
    ______________________________________

    ______________________________________
    document.sub.-- retrieval
                 25     3425    1    AN    9    600
    information.sub.-- extraction
                 19     3425    1    CE    4    600
    ______________________________________