Patent Description:
It is known to provide searching algorithms for retrieving information contained in documents stored on a computer system or in a database. Typically, the searching algorithm performs two separate tasks: indexing and searching. During indexing, the text of all the documents is scanned and a list of search terms is built. Then, during a search in response to a specific query, only the index is referenced, rather than the actual text.

The most commonly used indexing system is an inverted index. The text is scanned, and the words within the text are parsed. Each unique word becomes an entry in the inverted index, and the 'inverse' of this index is a list of documents within which the word occurs. The index has a single level in that the words are linked only to their parent documents. Other data may also be captured within an index entry, such as the position of the word within the document.

However, it is known that conventional searches frequently produce many false positives (documents that include the search term(s) used but which are not relevant to the intended search query). This is particularly the case when the query involves compound terms (two or more separate search terms). For example, a search using the terms "high, blood, pressure" would return a document with the following text: "The patient had low blood pressure. The patient's temperature was high. Clearly, this is unlikely to be relevant. Performing an exact search would avoid this but could miss relevant results (such as "the patient's blood pressure was high"). The greater the size of the document, or the more common the search term(s), the greater the likelihood of a false positive. The search may return results in which the individual search terms are remote from each other in the document and, in reality, are unrelated to each other.

One known solution to this is to use proximity searching. A proximity search only returns documents in which the multiple search terms used are within a specified distance from each other in the document, this distance being the number of intervening words or characters. However, such a search offers limited improvement over non-proximity searches. In the above example concerning blood pressure, a search using a maximum proximity of only five words would still return the erroneous result. Also, the possibility of a false negative (a relevant document not being found) is substantially increased. This is even more likely in certain types of documents such as legal texts. For example, a search of the UK Patents Act <NUM> using the terms "state of the art, oral" and a long, specified proximity of <NUM> words would still not return the following section:
"S2(<NUM>): The state of the art in the case of an invention shall be taken to comprise all matter (whether a product, a process, information about either, or anything else) which has at any time before the priority date of that invention been made available to the public (whether in the United Kingdom or elsewhere) by written or oral description, by use or in any other way.

It is desirable to provide an improved method of searching which produces more relevant results with fewer false positives and/or false negatives.

The text that is indexed/searched is commonly referred to in the art as unstructured data. A conventional search engine has no recognition of any structure of the text, not even as a collection of individual words. Rather, the text is effectively one long string of characters, which includes a number of 'whitespace' and punctuation characters (used to create the index). However, in reality, most document text is highly structured. This is partly due to conventions used by authors when creating documents (physical structure) and partly due to the structure of language itself (logical structure).

Regarding physical structure, the text is contained in documents, and each document typically comprises a number of sections, which comprise a number of paragraphs, which comprise a number of sentences, which comprise a number of words. In other words, the text typically has a tree structure.

Regarding logical structure, when an author of a text wishes to relate a concept (such as the property of high blood pressure), there are a number of ways of expressing this, some of which use a different ordering of the individual words. Nevertheless, it is highly likely that the full expression of the concept will occur in one sentence.

At a more abstract level, authors tend to segregate individual remarks, arguments etc. into separate paragraphs. Individual topics are discussed in separate sections, chapters etc..

It is desirable to provide an improved method of searching which accounts for or utilises the underlying structure of existing texts.

A conventional search will produce a number of results which ideally should be ranked before being provided to the user. However, in the absence of some other ranking criterion, each result is of equal merit. Consequently, it is common to apply a subjective or commercially motivated ranking algorithm to the results.

It is desirable to provide an improved method of searching which utilises an objective ranking procedure.

Other searching methods can be found in <CIT> and <CIT>.

According to various aspects of the present invention there is provided a method of performing a search of a corpus of documents, a computer program product which is executable to perform a search of a corpus of documents and a system for performing a search of a corpus of documents as set out in the accompanying claims.

The invention will be described below, by way of example only, with reference to the accompanying drawings, in which:.

<FIG> shows steps of a method <NUM> for performing a search of a corpus of documents. The search can be performed by the processor of a computer on documents stored in the memory of the computer. The method may be implemented using a computer program product.

The computer program product may be stored on or transmitted as one or more instructions or code on a computer-readable medium. A storage media may be any available media that can be accessed by a computer. By way of example such computer-readable media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer. For example, if the software is transmitted from a website, server, or other remote source using a coaxial cable, fibre optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infra-red, radio, and microwave, then the coaxial cable, fibre optic cable, twisted pair, DSL, or wireless technologies such as infra-red, radio, and microwave are included in the definition of medium. The instructions or code associated with a computer-readable medium of the computer program product may be executed by a computer, e.g., by one or more processors, such as one or more digital signal processors (DSPs), general purpose microprocessors, ASICs, FPGAs, or other equivalent integrated or discrete logic circuitry.

At step <NUM>, the contents of each document is scanned and indexed to produce an index <NUM>. The index <NUM> may not include stop words. Unlike conventional searches, the index <NUM> produced has a tree structure <NUM>.

At step <NUM>, in response to a user query, the index is searched for the search terms specified by the user. From this, a result list is generated which corresponds to the documents that include the search terms.

At step <NUM>, the results are ranked. Details of the ranking procedure used are given below.

At step <NUM>, the ranked result list is provided to the user.

<FIG> shows the tree structure index <NUM> used in the method. The index <NUM> comprises various nodes at different node levels. Nodes at a particular level are associated with other nodes at the levels immediately above and/or below and this is represented by the shown branches <NUM>. In <FIG>, only a portion of the nodes and branches <NUM> are shown to aid clarity.

In this embodiment, the contents of the documents comprises text and so the tree structure <NUM> is a linguistic tree structure. The node levels of the tree structure <NUM> comprise words <NUM>, sentences <NUM>, paragraphs <NUM> and sections <NUM>. The top node level is the documents <NUM> themselves.

The words of the text are the leaf nodes of the tree structure <NUM>. Each word, excluding stop words, is stored in the index <NUM> and given a unique identifier.

The sentence node level <NUM> is a parent level to the word node level <NUM>. During scanning of the text of each document, punctuation is identified to determine individual sentences. These sentences are stored in the index <NUM> and given a unique identifier. Each word in the index is mapped to each sentence in which it appears in the text. A particular word may appear in many sentences and this explains the many different branches <NUM> between words and sentences in <FIG>.

The paragraph node level <NUM> is a parent level to the sentence node level <NUM>. Line breaks in the text of each document are used to identify individual paragraphs. These paragraphs are stored in the index <NUM> and given a unique identifier. Each sentence in the index <NUM> is mapped to each paragraph in which is appears in the text.

The section node level <NUM> is a parent level to the paragraph node level <NUM>. Sections can be identified by page breaks in the text or text following a heading. A heading can be identified by a change in font size or style (such as bold text). These sections are stored in the index <NUM> and given a unique identifier. Each paragraph in the index <NUM> is mapped to each section in which is appears in the text.

Each section in the index <NUM> is mapped to each document in which is appears in the text. Typically, within a document, each section, paragraph and sentence will tend to be unique and so there will be a one to one mapping of the parent and child. However, this need not be the case as there may be duplicate text within a number of documents for various reasons.

The sentences in the index are then examined for the existence of meaningful entities, such as people, places, medicines, treatments etc. Entity instances are then added to the index, linked to the sentences in which these occur through their parent identifiers. This makes it possible to search for instances of specified entity types.

A user can submit a search request including one or more search terms. When a single search term is used, the searching procedure is fairly conventional in that a result list is generated which includes every document that contains an instance of the search term. The following describes the procedure used when more than one search term is used in the query.

The user can specify a node level for the query. The result list generated will then correspond only to documents which include each search term within the same node level. So, for example, the user may specify two search terms and a sentence node level <NUM> for the query. In which case, the result list generated will comprise only documents which include both search terms within the same sentence.

During the search, the search term associated with the fewest parent level instances in the index is determined. Then, it is determined if another search term of the query has the same parent level instances in the index.

This search procedure was carried out in a corpus of <NUM> medical records using the search terms "high, blood, pressure". A conventional search had previously been carried out which produced a result list of over <NUM> documents. In the majority of these results, the terms 'blood' and 'pressure' were related but the term 'high' was not. But it met the search criterion because it appeared somewhere in the document in relation to something else. The search according to the invention produced only five results, each of which was highly relevant. It was found that, although a medical professional could express that a patient had high blood pressure in a number of different ways linguistically, they would always use the three search terms in the same sentence.

The search results can be displayed in context, allowing the user to easily navigate the results. The user can select a result sentence and view the context in which the sentence occurs. The system determines the genealogy of each of the sentences identified as including the search terms. Therefore, the parents of each sentence are obtained by iterating recursively upwards through the multi-level structured text index, gathering each current parent's parent. The genealogy for a given sentence may therefore include the identifier of the paragraph in which it occurs, the section in which it occurs, and the document in which it occurs. These genealogy lists are combined, so that for each commonly occurring parent such as a document, a single genealogy tree is built of all of the recursively occurring child structures (sections, paragraphs and sentences) within the document.

The method includes ranking of the documents in the result list. This is done in an objective manner.

The number of parent level instances is determined for each result. The results are then ranked in order of the determined number. So, in the case of the above example involving a search of medical records, perhaps two of the five found records both contain two sentences which include all the search terms (the other three records containing only one sentence). These two records would have the highest ranking in the ranked result list.

A further objective ranking step is then carried out for the two highest ranked records (and separately for the three lower ranked records). The ratio of the number of parent level instances to the total number of parents in the associated document is determined for each result. For example, one of records may have a total number of sentences of <NUM>, while the other record is considerably longer with a total number of <NUM> (as stated, both have two sentences in which all three search terms are used). This results in ratios of <NUM> and <NUM> respectively. It is assumed that shorter documents which still have the same high number of matching instances are likely to have an increased relevance. Therefore, the record with the higher ratio of <NUM> is ranked higher than the other record.

The method can include generating a second index. This index is of the meta data for the corpus of documents. The user can include meta data search terms in the query.

Particular users can be assigned different levels of access for performing a search. Also, the method can include redacting text which is designated as restricted. Restricted words and phrases will only be displayed to users having the appropriate authorisation.

Claim 1:
A method of performing a search of a corpus of documents (<NUM>), the method comprising:
indexing the contents of each document of the corpus to produce an index (<NUM>);
in response to a query comprising a plurality of search terms submitted by a user, searching the index (<NUM>) for each search term; and
providing to the user a result list corresponding to documents which include each search term,
wherein indexing the contents of each document (<NUM>) comprises generating a tree structure (<NUM>) for the contents, and wherein:
the submitted query includes a specified node level (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>) of said tree structure (<NUM>) such that the result list provided to the user includes the one or each search term found at the specified node level (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>);
the method includes determining for the specified node level (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>), its parent level and further the number of parent level instances for each result and displaying the results in a ranked order of the determined number; and (i) the result list corresponds only to documents which include each search term within the same node level (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>); or (ii) the method includes identifying the search term associated with the fewest parent level instances in the index (<NUM>).