Patent ID: 12254267

DESCRIPTION OF THE EMBODIMENTS

Embodiments of the present invention will be described hereinafter with reference to the drawings. The embodiments described hereinafter, however, are merely illustrative and there is no intention to exclude various modifications and applications of techniques that are not explicitly described hereinafter. Various modifications (such as combinations of the respective embodiments) of the present invention may be implemented within the scope not departing from the spirit of the present invention. In the description of the drawings hereinafter, identical or similar parts are denoted by identical or similar reference numerals. The drawings are schematic and do not necessarily correspond to the actual dimensions, ratios or the like. Dimensional relations or ratios between parts may differ with respect to each other among the drawings.

FIG.1is a block diagram showing a schematic configuration of an information search system according to an embodiment of the present invention. As shown inFIG.1, the information search system1of the present embodiment is configured to include at least one search engine20and at least one client30, which are communicably connected to each other via a computer network10.

The computer network10typically includes an IP-based computer network, but the configuration is not limited thereto. For example, a network of any protocol that allows communication between nodes may be applied for the computer network10.

The search engine20is a computer system that provides the client30with an information search service and may be implemented by, for example, one or more general-purpose computing devices. Specifically, the search engine20is a virtual machine that is embodied, together with other hardware elements, by one or more CPUs (processors) on a computing device executing, for example, a search engine program of the present embodiment on a predetermined operating system (OS). The search engine20may be implemented with a virtual technique. The hardware configuration of a computing device that implements the search engine20is shown inFIG.18; however, since such configuration is known, a detailed description thereof will be omitted here. The search engine20in the present embodiment is an index-type search engine and has, for example, a function of creating/updating an index and a function of database searching based on such index. As shown inFIG.1, the search engine20is configured to include, for example, a crawler21, a dictionary22, an indexer23, a database24and a query server25. It should be noted that, from the point of view of a user who intends to conduct an information search, the search engine20is a virtual machine (a search engine in a narrow sense or a search apparatus) that implements the index-based database search function.

The crawler21is an automatic crawling agent program for automatically collecting a wide variety of resources on the web (e.g., webpages, documents, images, programs, etc.). In particular, the crawler21periodically visits websites while following links in webpages and collects resources in the websites. For example, the crawler21may collect resources in the websites pertaining to specific domains of expertise. The crawler21may temporarily store the collected resources in, for example, a storage device (not shown). In the information search system1of the present embodiment, a known crawler21may be applied and thus, a detailed description thereof will be omitted here.

The dictionary22includes one or more files or tables in which a plurality of phrases associated with each other regarding a specific concept are stored, but the configuration is not limited thereto. For example, the dictionary22may be configured as a static file or table, and may not be memory-resident and may be dynamically configured as a dictionary model (e.g., a neural network model) in which the relationship between the phrase families is built in accordance with a predetermined algorithm. The term “phrase” used in the present disclosure refers to a term or an expression made up of a single word or a sequence of two or more words. The plurality of phrases associated with each other is referred to as a related-phrase family. As an example, the related-phrase family may include synonyms, equivalent terms, related words, abbreviations and corresponding foreign words, and even derivative words and the like derived from the foregoing words. The dictionary22may be constructed based on available information sources in a manual, semi-automatic or full-automatic manner. In the case of the medical field, various dictionaries provided by the National Cancer Institute (NCI) are used for constructing the dictionary22. The dictionary22is referred to when the below-described indexer23creates an index241.

The indexer23registers the resources (e.g., information related to the resources) collected by the crawler21in the database24, analyzes the content (typically, text sentences) of such resources, and creates and updates the index241in accordance with the analysis result. In general, the indexer23of the present embodiment: divides the text sentence contained in the resources down into several tokens; creates a directed graph (a lattice) based on the tokens; conducts a search on the directed graph in accordance with a predetermined phrase with reference to the dictionary22; and expands and updates the directed graph under a predetermined condition. The updated directed graph becomes a new directed graph to be searched. The indexer23then extracts headwords using a predetermined approach (e.g., the N-gram approach) based on the expanded directed graph and associates the headwords with the collected resources (i.e., indexes the collected resources with the headwords) to create and/or update the index241. Further, the indexer23associates the created directed graph with the collected resources and registers them in the database24.

The database24stores therein information related to the resources collected by the crawler21and is configured to include the index241of such information. Further, the database24stores therein the directed graph used to create the index241.FIGS.2A and2Bshow an example of a database in a search engine according to an embodiment of the present invention.FIG.2Ashows an example of information related to the resources. The information related to the resources is a structure file that contains, for example, a resource ID for identifying a resource, a resource name, a URL, a directed graph ID for identifying a directed graph, and the like. The structure file having the information related to the resources stored therein is herein referred to as the resource information file. The index241is a structure file that is created by the indexer23and contains index information to be updated.FIG.2Bshows an example of the index241. The index241typically has a data structure referred to as an inverted index. The index information is, for example, a headword extracted from a word sequence in a directed graph by the N-gram approach. The headword in the index241is associated with a resource (more specifically, a resource ID) so that the headword is associated with an individual dataset of the resource information file of the database24. It should be noted that the index241is configured herein as part of the database24, but the configuration is not limited thereto and thus both the index241and the database24may be configured as separate entities.

Reverting toFIG.1, the query server25receives a search query provided from the client30, conducts a search on the index241, extracts information related to a relevant resource from the database24based on a result of the search, and provides the client30with such information as the search result. For example, the query server25may calculate a degree of matching between the search query and the extracted resources by way of a predetermined method and provide the search result in which the extracted resources are ranked in accordance with the calculated result. The query server25in the present embodiment directly returns to the client30the search result in response to the search query from the client30, but the configuration is not limited thereto. For example, the query server25may pass the search result to another application program via a predetermined application program interface (API), and then a result of predetermined information processing on the search result by such other application program may be returned to the client30. A known query server25may be applied in the information search system1of the present embodiment.

The client30is typically a computing device possessed by a user and may be, for example, a personal computer. The client30includes, for example, a viewer that functions as a user interface for accessing the search engine20via the computer network10. The viewer may be a web browser, but the configuration is not limited thereto. The client30may establish a communication session with the search engine20via the computer network10by utilizing a secure communication technique, such as SSL. The client30is configured to include one or more CPUs (processors), a memory and any other component; however, since the hardware configuration of the client is known, a detailed description thereof will be omitted here.

FIG.3is a diagram for illustrating an example of a dictionary in a search engine according to an embodiment of the present invention. As shown inFIG.3, the dictionary22is configured as a table in which a plurality of phrases, which are made up of one or more words, are stored. Each of the plurality of phrases is associated with each other for each specific concept. InFIG.3, for example, each of the phrases “parp,” “poly|adp|ribose|polymerase” and “PORI|adp|RIBOSU|PORIMERAZE” are associated with each other and registered in the dictionary. (The original texts in Japanese herein are denoted as “PORI,” “RIBOSU,” and “PORIMERAZE.” The same should apply hereinafter.) The symbol “|” (vertical line) represents a delimiter added for separating individual words in the phrase. As will be described hereinafter, the individual words configuring the phrase can be handled as individual tokens in a directed graph by separating the words configuring the phrase by a delimiter in this manner. It should be noted that the mutually-associated three phrases are herein shown as a single dataset, but the configuration is not limited thereto and thus the number of phrases is not limited.

FIG.4is a block diagram showing a schematic configuration of an indexer of a search engine according to an embodiment of the present invention. As shown inFIG.4, the indexer23of the present embodiment is configured to include, for example, an input interface unit231, a text processing unit232, a directed graph generation unit233, a directed graph search unit234and an index creation unit235.

The input interface unit231serves as an interface between, for example, the crawler21and the text processing unit232. The input interface unit231communicates with the crawler21and inputs, into the text processing unit232, a text sentence, such as that shown inFIG.5, that is contained in the resources collected by the crawler21.

The text processing unit232performs, for example, morphological analysis on the input text sentence to extract a plurality of tokens. The text processing unit232may typically include a language analysis engine (not shown) adapted to the respective languages such as Japanese and English. A known language analysis engine may be used for the language analysis engine.

The directed graph generation unit233generates a directed graph that is based on the plurality of tokens extracted by the text processing unit232. More specifically, the directed graph generation unit233connects neighboring tokens by a node for each of the plurality of tokens extracted by the text processing unit232in order to generate a directed graph (see, for example,FIG.7Athat represents the connection relationship between the plurality of tokens. In other words, a directed graph is generally represented by edges and nodes, and in the directed graph of the present embodiment, it can be said that the individual tokens are defined as edge labels and that the directed graph is represented by such labelled edges and nodes. The directed graph thus directly generated from the text sentence by the directed graph generation unit233includes only a single path extending from a leading node to a final node. It should be noted that the directed graph illustrated in the present disclosure is drawn for ease of understanding and that, in effect, the directed graph is typically treated in a computing device as a type of data structure that can be interpreted by a processor. The directed graph generation unit233expands and updates the directed graph by dynamically changing the connection relationship in the directed graph in accordance with the search result from the below-described directed graph search unit234.

The directed graph search unit234sets a phrase to be searched (hereinafter referred to as the “search-target-phrase”) and conducts a search on the directed graph based on the search-target-phrase with reference to the dictionary22. The search-target-phrase is any one or more tokens in the directed graph and may be selected and set sequentially from the leading token. More specifically, the directed graph search unit234of the present embodiment conducts a search on the directed graph along the edges and nodes in a sequential order based on the set search-target-phrase in order to determine whether or not the search-target-phrase is registered in the dictionary22. If the directed graph search unit234determines that the search-target-phrase is registered in the dictionary22, i.e., if the search-target-phrase is found in the dictionary22, then the directed graph search unit234locates the location in the directed graph where the search-target-phrase appeared and notifies the directed graph generation unit233of the located location. In response to this, the directed graph generation unit233updates the directed graph by additionally connecting a phrase associated with the search-target-phrase in the dictionary22between a node in front of the located location and a node behind the located location in the directed graph. Therefore, in the updated directed graph to which a new phrase is added, a plurality of paths may be present between the leading node and the final node of the text sentence, as shown in, for example,FIG.9(b).

The index creation unit235creates an index indicating the association with the collected resources based on the final directed graph that can be obtained when the directed graph search unit234terminates the search. More specifically, the index creation unit235traces the updated final directed graph and extracts therefrom a word (token)-based N-gram (hereinafter referred to as the “word-N-gram”) (i.e., a sequence of words) in order to create the index241by associating the extracted word-N-gram with a resource. The extracted word-N-gram is treated as a headword. In the present embodiment, N is equal to or smaller than 3, i.e., N≤3 (where N is a positive number). Namely, a sequence of one to three words (i.e., a 1-gram, a 2-gram and a 3-gram) is used as a headword in the index241. The word-based N-gram is used in the present embodiment but the configuration is not limited thereto and thus there is no intention to exclude the use of a character-based sequence (i.e., a sequence of one character, two characters, . . . ) as in the conventional N-gram method.

FIG.6is a flowchart for illustrating index creation processing by a search engine according to an embodiment of the present invention. Such processing may be implemented by a processor in a computing device executing a predetermined search engine program according to the present embodiment.

As shown inFIG.6, the search engine20receives a text sentence contained in a resource collected by the crawler21(S601). For example, if the input interface unit231receives the resource collected by the crawler21, the input interface unit231inputs the text sentence contained in the resource to the text processing unit232. If the search engine20receives the text sentence, the search engine20performs morphological analysis on the text sentence and tokenizes the text sentence, i.e., extracts a plurality of tokens from the text sentence (S602). For example, the text processing unit232determines the language of the text sentence and extracts the plurality of tokens from the text sentence through the morphological analysis processing adapted to the determined language.

The search engine20then generates a directed graph based on the extracted plurality of tokens (S603). For example, the directed graph generation unit233connects neighboring edges by a node, with the tokens being used as edge labels, for each of the plurality of tokens extracted by the text processing unit232in order to generate a directed graph that represents the connection relationship between the plurality of tokens. Herein, the directed graph first generated from the text sentence will be referred to as the initial directed graph.FIGS.7A and7Bshows part of the initial directed graph generated from the input text sentence shown inFIG.5. Namely, as shown inFIG.7A, in the directed graph of the present embodiment, the individual tokens are defined as edge labels, and the directed graph is represented by such labelled edges and the nodes. As shown inFIG.7A, the initial directed graph has only one path leading from the leading node.

It should be noted that the present embodiment shows the directed graph in which the individual tokens are defined as the edge labels as described above; however, the configuration is not limited thereto. For example, as shown inFIG.7B, a token may also be defined as a node (i.e., there are two types of nodes) and these two types of nodes may be connected by a simple edge in the directed graph. It should also be noted that such graph may be referred to as a lattice in the field of natural language processing, and the terms “graph” and “lattice” will be used interchangeably in the present disclosure.

Reverting toFIG.6, the search engine20conducts a search on the directed graph with reference to the dictionary22, and expands and updates the directed graph in accordance with the search result (S604). More specifically, the search engine20sequentially sets a predetermined term from the directed graph as a search-target-phrase, which is the target for search, and conducts a search on the directed graph along the edges and nodes based on such search-target-phrase. Every time the search-target-phrase is found in the dictionary22, the search engine20expands and updates the directed graph based on a phrase associated with the found search-target-phrase. The details of the search/update processing of the directed graph will be described below withFIG.8.

After the above-described search/update processing of the directed graph, the search engine20creates an index241that indicates the association with the collected resource based on the updated directed graph (S605). For example, the index creation unit235traces the updated final directed graph, extracts therefrom a sequence of words, including a 1-gram, a 2-gram and/or a 3-gram, and associates the extracted sequence of words with the collected resource as a headword in order to create the index241, such as that shown inFIG.2B. The index creation unit235also registers the resource information file, such as that shown inFIG.2A, in the database24so as to correspond to the created index241. This allows, for a future search query, a search to be conducted on resources based on headwords that fall within the extended scope of phrases related to the search query. In addition, the index creation unit235in the present embodiment associates the updated final directed graph with the collected resources when creating the index241and stores the directed graph associated with such resources in the database24. In a case where a search is conducted based on a search query and such resources are obtained and extracted, the directed graph associated with such resources is used to present the grounds (e.g., the related phrases) for such resources obtained through the search.

FIG.8is a flowchart for illustrating index creation processing by a search engine according to an embodiment of the present invention. More specifically,FIG.8is a flowchart illustrating the details of the search/update processing of the directed graph shown inFIG.6.

Specifically, as shown inFIG.8, for example, the directed graph search unit234first sets the current directed graph to a directed graph to be searched (S801). Then, the directed graph search unit234sets a predetermined token at the current search location in the directed graph as a search-target-phrase (S802). At the beginning of the search, the initial directed graph is the directed graph to be searched and the token connected to the leading node of the initial directed graph is set as the search-target-phrase. Predetermined tokens in the directed graph are sequentially set through the search of the directed graph. The search-target-phrase corresponds to one or more tokens.

The directed graph search unit234then conducts a search on the directed graph based on the set search-target-phrase with reference to the dictionary22(S803). For example, the directed graph search unit234conducts a search on the directed graph along the edges and nodes in a sequential order based on the set search-target-phrase in order to determine whether or not the search-target-phrase is registered in the dictionary22(S804). The search within the directed graph may be performed in accordance with, for example, the Knuth-Morris-Pratt (KMP) algorithm, but the configuration is not limited thereto.

If the directed graph search unit234determines that the search-target-phrase is registered in the dictionary22(S804, Yes), i.e., if the search-target-phrase is found in the dictionary22, the directed graph search unit234locates the location in the directed graph where the search-target-phrase appeared and notifies the directed graph generation unit233of the located location (S805). In response to this, the directed graph generation unit233updates the directed graph by additionally connecting a phrase associated with the search-target-phrase in the dictionary22to between a node in front of and a node behind the located location in the directed graph (S806). Typically, such phrase is extracted as one or more tokens and connected to the directed graph. Thereafter, the directed graph search unit234returns to the processing in step S801to continue the search. More specifically, the directed graph search unit234sets the current directed graph as the directed graph to be searched (S801), moves to the next search location and sets the token at such search location as a new search-target-phrase in order to proceed with the search processing (S802).

If, on the other hand, the search-target-phrase is not found in the dictionary22(S804, No), the directed graph search unit234determines whether or not a terminal node of the directed graph has been reached (S807). If the directed graph search unit234determines that the terminal node of the directed graph has not yet been reached (S807, No), the directed graph search unit234returns to the processing in step S802in order to continue the search in the directed graph. If, on the other hand, the directed graph search unit234determines that the last node of the directed graph has been reached (S807, Yes), the directed graph search unit234terminates the search processing.

By way of the above-described processing, when creating an index for a search based on an entered text sentence, the search engine20is enabled to create the index based not only on a phrase in the original text sentence but also on individual phrases that fall under the extended related-phrase family by using the dictionary22in which a plurality of mutually-associated phrases are registered.

Next, an example of expansion processing of the directed graph by the search engine20will be described.FIG.9is a diagram for illustrating an example of a process in which a directed graph is expanded by a search engine according to an embodiment of the present invention. This example shows the expansion of the directed graph when the search engine20creates the index241for the resources including the text sentence shown inFIG.5based on the dictionary22shown inFIG.4.

The search engine20first generates an initial directed graph, such as that shown inFIG.7A, based on the entered text sentence as described above. The search engine20then starts conducting a search on the directed graph. If the set search-target-phrase “poly|adp|ribose|polymerase” is found in the dictionary22in such search process, the search engine20connects, in a parallel manner, each of the phrases “parp” and “PORI|adp|RIBOSU|PORIMERAZE” in the dictionary22, which are phrases associated with the search-target-phrase “poly|adp|ribose|polymerase,” between a beginning node and a terminal node, which are respectively in front of and behind the location of the search-target-phrase “poly|adp|ribose|polymerase” in the directed graph, in order to update the directed graph (FIG.9(a)).

The search engine20then proceeds with conducting of a search on the directed graph. If the phrase “adp|RIBOSU” in the directed graph is set as the search-target-phrase, the search engine20finds this phrase “adp|RIBOSU” in the dictionary22. The search-target-phrase “adp|RIBOSU” corresponds to a term has been added to the directed graph by the search engine20in the above-described search process. Analogously, the search engine20connects, in a parallel manner, the phrase “adenosine|diphosphate|ribose” in the dictionary22, which is a phrase associated with the search-target-phrase “adp|RIBOSU,” between a beginning node and a terminal node, which are respectively in front of and behind the location of the search-target-phrase “adp|RIBOSU” in the directed graph, in order to update the directed graph (FIG.9(b)). In this manner, a further paraphrase may be additionally added to the path including the added phrases.

The search engine20then further proceeds with conducting of a search on the directed graph. If the phrase “parp|inhibitor” in the directed graph is set as the search-target-phrase, the search engine20finds this phrase “parp|inhibitor” in the dictionary22. The search-target-phrase “parp|inhibitor” corresponds to a term that is obtained by combining the phrase “parp,” which has been added to the directed graph by the search engine20, with the neighboring word “inhibitor.” Analogously, the search engine20connects, in a parallel manner, the phrase “parp|SOGAI|ZAI” in the dictionary22, which is a phrase associated with the search-target-phrase “parp|inhibitor,” between a beginning node and a terminal node, which are respectively in front of and behind the location of the search-target-phrase “parp|inhibitor” in the directed graph, in order to update the directed graph (FIG.9(c)). In other words, the phrase “parp|SOGAI|ZAI” is connected, in a parallel manner, to the original path (i.e., poly→adp→ribose→polymerase→inhibitor) in the initial directed graph.

The search engine20expands and updates the directed graph by performing the search operation on the directed graph as described above. As a consequence, the updated directed graph has several parallel paths formed with respect to the original path in the initial directed graph. Accordingly, the extraction of headwords based on such directed graph enables an index to be created based not only on a phrase in the original text sentence but also on individual phrases (i.e., paraphrases) that fall under the extended related-phrase family.

FIG.10is a flowchart for illustrating search processing by a search engine according to an embodiment of the present invention. Such processing is implemented by, for example, a processor in a computing device executing a predetermined search engine program.

As shown inFIG.10, the search engine20receives a search query from the client30(S1001). For example, the client30transmits the search query to the search engine20when, for example, a user enters a search query to a search screen displayed on a web browser (not shown). The search engine performs predetermined analysis processing on the received search query (S1002). For example, the query server25creates an N-gram search formula for the search query received from the client30. In the present embodiment, the maximum number for N is 3 (i.e., N=3), but the number is not limited thereto. Accordingly, if the search query includes four or more words, the query server25extracts 3-gram words and performs an AND search of these words. For example, if the search query is “platinum and parp inhibitor,” then the search formula would be “(platinum and parp) AND (and part inhibitor).”

The search engine20then conducts a search on the index241based on the created search formula (S1003). For example, the query server25conducts a search on the index241based on the created search formula to check whether or not there is a matching headword in the index241. If there is a matching headword, the query server25refers to the database24in accordance with the matching headword to extract information, including names and positional information of the resource associated with the headword, and returns the extracted result to the client30. For example, the query server25conducts a search on the index241based on the search formula “(platinum and parp” AND (and parp inhibitor),” and thereby the resource containing the text sentence, such as that shown inFIG.5, would match and be extracted. If there are a plurality of extracted results, the query server25may rank these results in accordance with their scores based on a predetermined score calculation. In the present embodiment, in a case of extracting resources associated with the headword, the query server25also identifies related phrases that served as the grounds for the matching resources and phrases in text sentences in the resources based on the directed graph associated with the resources (S1004). The details of the processing for identifying the search grounds will be described below, with reference toFIG.11.

After the search engine20has identified the phrases that served as the search grounds, the search engine20transmits the search result including the phrases that served as the search grounds to the client (S1005). In response, the client30displays the search result on the search screen onto which the search query is entered.

A conventional search engine registers, in an index, a headword that is only based on a phrase contained in a text sentence in a collected resource and thus, in order for such resource to be extracted through a search, a search query needs to include the headword contained in such resource. For example, the conventional search engine would not create an index having a headword of the phrase “parp inhibitor” with respect to the text sentence shown inFIG.5. Accordingly, if the search query from the client30is “platinum and parp inhibitor,” a resource that does not include “parp inhibitor” would not be presented as a search result, or even if such resource is presented for other reasons, such resource would only be presented with a low rank. In contrast, the search engine20of the present embodiment is enabled to register, in the index241, headwords based not only on a phrase contained in the text sentence but also on individual phrases that fall under the extended related-phrase family. Accordingly, even if the search query from the client30is “platinum and parp inhibitor,” a resource that does not include “parp inhibitor” would still be presented as a search result.

FIG.11is a flowchart for illustrating search processing by a search engine according to an embodiment of the present invention. More specifically,FIG.11is a flowchart for illustrating the details of the processing for identifying the search grounds shown inFIG.10.

As shown inFIG.11, the search engine20first identifies a directed graph of a resource that is obtained through a search (S1101). For example, the query server25refers to a resource information file of the database24as shown inFIG.2, identifies a directed graph ID associated with a text sentence in the obtained resource, and reads a directed graph stored in the database24based on the identified directed graph ID. It should be noted that the search engine20in the present embodiment uses the directed graph IDs stored in association with the obtained resource but the configuration is not limited thereto and thus a directed graph may be re-generated for the obtained resource following the search/update processing shown inFIG.8.

The search engine20then conducts a search on the identified directed graph based on the search query (S1102) in order to locate the location within the directed graph where the search query appeared (S1103). For example, the query server25traces each path in the directed graph along edges and nodes in a sequential order to locate the location where there is a match with the search query. The located location is either the entirety or part of one path and may therefore include a plurality of edges and nodes. The search may be performed according to the KMP algorithm. Alternatively, the search may be performed using tries T.

The search engine20then identifies a branch node on the original path in the directed graph, to which the path including the located location is connected (S1104), and then the search engine20identifies a merge node on the original path in the directed graph, to which the path including the located location is connected (S1105). The original path refers to a path in the directed graph that is obtained directly from the text sentence in the resource and is equivalent to a path in the above-described initial directed graph (seeFIG.7A). For example, the query server25traces the path including the located location backward (i.e., in the direction opposite to the edge orientation) from a front-end node of the located location until a node in the text-sentence-based original path is reached, and the query server25identifies the reached node as the branch node. Further, the query server25traces the path including the located location forward (i.e., in the direction of the edge orientation) from a back-end node of the located location until a node of the original path is reached, and the query server25identifies the reached node as the merge node. It should be noted that the query server25in the present example identifies the merge node after identifying the branch node; however, the query server25may identify the branch node after identifying the merge node or the branch node and the merge node may be identified in a simultaneous and parallel manner.

After identifying the branch node and the merge node, the search engine20identifies any phrase that is present on the path including the located location between the branch node and the merge node (S1106). For example, the query server25may extract edge labels during the backward path tracing in step S1104and the forward path tracing in step S1105, store the extracted edge labels in a buffer, and identify a phrase based on the extracted edge labels stored in the buffer. The phrase identified in this step S1106corresponds to a related phrase that served as the grounds for a hit obtained through the search.

Subsequently, the search engine20extracts any phrase that is present on the original path between the branch node and the merge node in an analogous manner (S1107). For example, the query server25may extract edge labels from the branch node to the merge node in the direction of the edge orientation, store the extracted labels in a buffer, and identify a phrase based on the extracted labels stored in the buffer. The phrase identified in this step S1107corresponds to the phrase in the text sentence that served as a basis for related phrase generation.

It should be noted that the search engine20may perform the above-described processing for identifying the search grounds for each location where the search query appeared in the directed graph.

The above-described processing allows the search engine20to provide the user with related phrases that served as grounds for a hit obtained through a search, even if a resource obtained in response to a search query is not obtained directly based on a phrase in the search query but obtained based on phrases related to the phrase in the search query.

In addition, for example, even if a search is conducted on the index241of the present embodiment based on a search query involving an OR search on a plurality of phrases, the user is still enabled to easily discern the phrases, in the plurality of phrases, that contributed to the obtaining of a resource with the aid of the presentation of the search grounds to the user. Further, even if resources are obtained from the search query that are unexpected by the user, the user is enabled to recognize that the search engine20is functioning normally with the aid of the representation of the search grounds.

An example of processing for identifying the search grounds by the search engine20will be described below.FIGS.12A to12Dare diagrams for illustrating an example of a process in which search grounds are identified based on a directed graph of a resource searched by a search engine according to an embodiment of the present invention. This example shows the identification of the search grounds by the search engine20in the present example based on the directed graph shown inFIG.9.

The search engine20first identifies a directed graph ID of the obtained resource from the resource information file of the database24, as described above, to read a directed graph, such as that shown inFIG.12A, from the database24and starts conducting a search on the directed graph based on the phrase “diphosphate ribose” contained in a search query. During such search process, if a phrase that matches the phrase in the search query is found in a path in the directed graph, the search engine20locates the location in the directed graph where such phrase appeared (FIG.12B). Hereinafter, a front-end node of the located location will be referred to as the “front-end node A” and a back-end of the located location will be referred to as the “back-end node B.”

The search engine20then traces the path including the located location backward from the front-end node A until a node in the text-sentence-based original path is reached, and the reached node is identified as a branch node A′. The search engine20traces the path including the located location forward from the back-end node B until a node in the original path is reached, and the reached node is identified as a merge node B′ (FIG.12C).

The search engine20then traces the path from the branch node A′ to the merge node B′ via the path including the located location to identify the phrase “PORI|adenosine|diphosphate|ribose|PORIMERAZE.” The phrase in the located location is the phrase related to the search query, i.e., the related phrase that served as the grounds for the obtained resource. The search engine20then also traces the original path that is based on the text sentence in the resource from the branch node A′ to the merge node B′ to identify the phrase “poly|adp|ribose|polymerase” (FIG.12D). The identified phrase in the original path corresponds to the phrase in the text sentence that served as a basis for related phrase generation.

After the search engine20identifies the phrase that served as the search grounds as described above, the search engine20transmits the search result including such phrase that served as the search grounds to the client30. In response to this, the client30may display the search result on a web browser.

FIGS.13A to13Cshow examples of a search result screen displayed on a client in an information search system according to an embodiment of the present invention.

In the example shown inFIG.13A, the search result screen1300A shows, for example, a name1302of a resource and a link1303to the resource. Such resource is obtained through a search by the search engine20based on a search query entered into a search query input field1301. In the example shown inFIG.13A, the name “Cancer therapeutic drugs” of the resource that is obtained in response to the search query “‘diphosphate ribose’ OR ‘parp SOGAIZAI’” and the URL of such resource are shown. The search result screen of the present embodiment also includes: a body text display area1304and a search ground display area1305. For example, the body text display area1304and the search ground display area1305may be arranged side by side. The body text display area1304displays at least part of the text sentence in the resource obtained in response to the search query. The displayed text sentence may be, for example, at least part of the text sentence related to the phrase in the search query. The search ground display area1305displays the related phrase that served as grounds for the resource to be obtained in response to the search query. The related phrase is highlighted for better visibility for the user by techniques such as color coding, hatching, bold type, italic type or boxed type. The example inFIG.13Aindicates which related phrase the phrase in the resource obtained in response to the phrase in the search query, is associated with. In other words, the example indicates which phrase in the text sentence in the resource is replaced by which related phrase that led to the obtained resource.

FIG.13Bshows the search result screen1300B in which at least part of the text sentence in the resource that is obtained in response to the search query and the related phrase that served as grounds for the resource to be obtained in response to the search query are displayed in the body text display area1304′. The related phrase may be highlighted for better visibility for the user. The search result screen1300B in the present example also includes a checkbox1306for allowing the user to arbitrarily select whether or not to display the search grounds. If the checkbox1306is checked, the search grounds are displayed in the search result screen1300B. For example, when the user enters a search query and is presented with the search result, if the user wants to view the search grounds, the checkbox1306may be checked in order to display the search grounds. In this manner, after the search result screen1300B is displayed in an abbreviated form, the user is enabled to selectively display the search grounds of the relevant part.

FIG.13Cshows the search result screen1300C in which at least part of the text sentence in the resource that is obtained in response to the search query is displayed in the body text display area1304. When the user operates a pointer cursor1307to hover the pointer cursor1307over the related phrase, the search ground display area1305′ is displayed in a pop-up manner. The related phrase may be highlighted so that the user can know which phrase the related phrase is associated with.

As described above, the search result screen of the present embodiment displays, in a mutually-associated manner, the text sentence in the resource that is obtained in response to the search query and the related phrase that served as grounds for the resource to be obtained. This configuration enables the user to easily recognize the related phrase that served as the search grounds.

Another example of search/update processing of a directed graph illustrated inFIG.8will be described below. In this example, the search is conducted only on edges (tokens) in the directed graph that have not yet been searched. In other words, re-search on the tokens that have already been searched is avoided. For this purpose, a tree structure configured by an ordered node is used in the present example. Such tree structure is known as a trie or a prefix tree. Specifically, in the trie, all nodes subordinate to a node have a shared prefix in their corresponding character string (here, a token). In the present example, individual words that configure a phrase in the dictionary22are allocated to edges between nodes in the trie. For ease of understanding, descriptions will be provided hereinafter based on the premise that the phrases, such as those shown inFIG.14, are registered in part of the dictionary22.

The search engine20of the present example comprises a trie created based on the dictionary22.FIG.15is a diagram for illustrating an example of a trie created based on the phrases registered in the dictionary shown inFIG.14. The trie T is typically a type of data structure or data arrangement that can be interpreted by a processor in a computing device, and is configured, for example, as one or more files or tables, but the configuration is not limited thereto. For example, the trie T may be configured as a static file or table, and the entirety or part thereof may not be memory-resident and may be dynamically configured during execution of processing in accordance with a predetermined algorithm.

As shown in the trie T inFIG.15, the individual words in the phrase registered in the dictionary22are allocated in a sequential order to the edges between the nodes, with the node n0 being set as a root node. Each node is assigned with, for example, a unique number. The root node n0 is assigned with, for example, the number “0.” InFIG.15, each of the rest of the nodes is assigned with a number from 1 to 10 for the sake of convenience. A solid node inFIG.15represents a phrase terminal node and functions as a flag for recognizing a phrase registered in the dictionary22. In other words, a phrase indicated by the path from the root node n0 to the phrase terminal node corresponds to a phrase registered in the dictionary22. For example, as shown inFIG.14, both “EIYOU” and “EIYOU|RYOUHOU” are registered in the dictionary22and thus, the nodes n3 and n9 in the trie T shown inFIG.15are phrase terminal nodes.

FIGS.16A and16Bare flowcharts for illustrating another example of index creation processing by a search engine according to an embodiment of the present invention. More specifically,FIGS.16A and16Bare flowcharts of search/update processing of a directed graph.

As shown inFIG.16A, the directed graph generation unit233may first assign, for example, the number “0” representing a root node n0 (i.e., the root number) of a trie to each node of the initial directed graph (S1601). Alternatively, assignment of the root numbers to the respective nodes in the initial directed graph may be performed when the initial directed graph is generated (see S603inFIG.6).

Next, the directed graph search unit234sets the initial directed graph as the directed graph to be searched (S1602), and then selects one leading node in the directed graph and sets this leading node as the current search node (S1603). Then, the selected search node is stored as a searched node. At this point in time, the directed graph search unit234caches the position of the search node and a start position where a phrase is to be inserted (hereinafter referred to as the “phrase-insertion-start position”) in a cache region (not shown) (S1604). Accordingly, the directed graph search unit234is enabled to locate the positions of nodes that are not yet searched and the positions where the related phrase should be inserted based on the cached content.

The directed graph search unit234then determines whether or not a token (phrase) associated with the search node is to be searched (retrieved) in accordance with the corresponding node in the trie T (S1605). More specifically, the directed graph search unit234identifies a token of an edge connected to the search node and determines whether or not the identified token matches a token of an edge connected to the node of the trie T that corresponds to the number assigned to the search node. If the identified token is searched in the trie T (S1605, Yes), the directed graph search unit234additionally assigns the number assigned to a node downstream of the token in the trie T to a node downstream of the identified token in the directed graph (S1606inFIG.16B).

For example, if one considers the token connected to the search node in the directed graph to be “tpn,” in this case, the directed graph search unit234finds the token “tpn” of the edge connected to the root node n0 in the trie T, and additionally assigns the number “2” of the downstream node connected to such edge to the downstream node connected to the token “tpn” in the directed graph (seeFIG.17(b)).

The directed graph search unit234then determines whether or not the downstream node of the trie T is a phrase terminal node (S1607). If the downstream node is determined to be a phrase terminal node (S1607, Yes), the directed graph search unit234determines whether there is a node further downstream of such downstream node (S1608). If the directed graph search unit234determines that there is no further downstream node (S1608, No), the directed graph generation unit233extracts a related phrase of the token (phrase) with reference to the dictionary22(S1609) and additionally connects the extracted related phrase between the relevant nodes in the directed graph in order to update the directed graph (S1610). In other words, the directed graph generation unit233connects the path including the related phrase, in a parallel manner, between a node at the cached phrase-insertion-start position and the node (i.e. the node at the back-end position of the insertion) downstream of the token in the directed graph. After the directed graph has been updated by the directed graph generation unit233, the directed graph search unit234assigns the number “0” of the root node n0 to a node connected to the newly added related phrase in the directed graph (S1611) and returns to the processing in step S1603(FIG.16A).

If, on the other hand, the directed graph search unit234determines that the downstream node of the trie T is not a phrase terminal node (S1607, No), the directed graph search unit234returns to the processing in step S1603in order to set a next search node. In addition, if the directed graph search unit234determines that the downstream node of the trie T has a further downstream node (S1608, Yes), the directed graph search unit234also returns to the processing in step S1603in order to set a next search node.

In step S1605, if the directed graph search unit234fails to search the identified token in the trie T (S1605, No), the directed graph search unit234determines whether or not all of the nodes in the directed graph have been searched (S1612). If the directed graph search unit234determines that not all of the nodes in the directed graph have been searched (S1612, No), the directed graph search unit234returns to the processing in step S1603in order to continue the search in the directed graph. On the other hand, if the directed graph search unit234determines that all of the nodes in the directed graph have been searched (S1612, Yes), the directed graph search unit234terminates the search processing.

An example of directed graph expansion processing by a search engine20using the above-described trie T will now be described.FIG.17is a diagram for illustrating another example of a process in which a directed graph is expanded by a search engine according to an embodiment of the present invention. It should be noted that a blank node inFIG.17represents a node to be searched (i.e., a not-yet-searched node) and a solid node represents a node that has already been searched.

If one considers that an initial directed graph is generated based on the entered text sentence as described above,FIG.17(a)shows part of such initial directed graph. Each node in the initial directed graph is assigned with the root number “0.” In the process of conducting a search on the directed graph, the directed graph search unit234sets a node indicated by a blank arrow as a search node. The directed graph search unit234also caches the position of the search node and a start position where a phrase is to be inserted in a cache region.

The directed graph search unit234then determines whether or not the token “tpn” of an edge connected to the search node matches a token of an edge connected to the node in the trie T that corresponds to the number “0” of such search node. In the present example, one of the edges connected to the root node n0 in the trie T has the token “tpn” and thus the directed graph search unit234additionally assigns the number “2,” which is assigned to a node downstream of the token in the trie T, to a node downstream of the token in the directed graph (FIG.17(b)).

The directed graph search unit234then determines that the downstream node of the token in the trie T is a phrase terminal node. In response, the directed graph generation unit233adds, to the directed graph, the phrase “total|parenteral|nutrition” related to the token (phrase) with reference to the dictionary22(FIG.14) in accordance with the cached phrase-insertion-start position. The directed graph generation unit233also assigns the number “0” representing a root node n0 to a newly added node (FIG.17(c)).

Thereafter, the directed graph search unit234proceeds with the search processing in an analogous manner. If one considers that the filled-in nodes have already been searched and a node indicated by a blank arrow is set as a search node as shown inFIG.17(d), then, in accordance with the token “nutrition” of the edge from the node n6, the directed graph search unit234assigns the node number “9” of a node subordinate to the node n6 to a subordinate node in the directed graph in the search in the trie T. The node n6 is a phrase terminal node. Therefore, the directed graph search unit234would normally connect a path including the phrase (token) “tpn” related to the phrase “total|parenteral|nutrition” with reference to the dictionary22; however, the related phrase “tpn” is already present at the phrase insertion position and thus the directed graph search unit234does not connect this path. This configuration suppresses redundant path addition in the directed graph expanding processing.

Subsequently, the directed graph search unit234proceeds with the search processing in an analogous manner. The node n4 in the trie T is a phrase terminal node and thus a path including the token “EIYOU” is connected to a phrase insertion position in the directed graph with reference to the dictionary22(FIG.17(e)).

As a result of the directed graph search by the directed graph search unit234as described above, the directed graph generation unit233finally generates the directed graph shown inFIG.17(f).

It should be noted that, regarding the above-described processing, part of the processing performed by the directed graph generation unit233may be performed by the directed graph search unit234and/or part of the processing performed by the directed graph search unit234may be performed by the directed graph generation unit233.

As described above, according to the present embodiment, an index241is created that enables the collected resources to be efficiently searched in the index-type search engine. As such, a user is enabled to access the collected resources by phrases other than the phrases contained in the collected resources that served as the basis for creating the index241. Consequently, resources including a related-phrase family, such as synonyms, can be searched in an extensive and efficient manner based on a specific phrase in a specialized field such as the medical field.

In addition, even if a search is conducted on the index241of the present embodiment based on a search query involving, for example, an OR search, a user is still enabled to easily discern the phrases, in the plurality of phrases, that contributed to the obtained resources with the aid of the representation of the search grounds to the user. Further, even if resources are obtained from the search query that are unexpected by the user, the user is still enabled to recognize that the search engine20is functioning normally with the aid of the representation of the search grounds.

The above-described respective embodiments are illustrations for describing the present invention and are not intended to limit the invention only to these embodiments. The present invention may be implemented in various forms as long as they do not depart from the scope of the present invention.

For example, regarding the methods disclosed in the present specification, steps, operations or functions may be implemented in parallel or in a different order, as long as the results are not inconsistent. The described steps, operations and functions are only provided as examples, and some of the steps, operations and functions may be omitted, combined into a single step, operation or function, or other steps, operations and functions may be added within a scope not departing from the scope of the present invention.

Further, various embodiments are disclosed in the present specification; however, a specific feature (technical matter) in an embodiment may be added to a different embodiment, with an appropriate modification, or may be replaced with a specific feature in such different embodiment, and such form is also included in the scope of the present invention.

INDUSTRIAL APPLICABILITY

The present invention can be extensively used in the field of information search techniques.

REFERENCE NUMERALS

1information search system10computer network20search engine21crawler22dictionary23indexer231input interface unit232text processing unit233directed graph generation unit234directed graph search unit235index creation unit24database241index25query server30client