Patent Publication Number: US-7587389-B2

Title: Question answering system, data search method, and computer program

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   This invention relates to a question answering system, a data search method, and a computer program, and more particularly to a question answering system, a data search method, and a computer program, which can provide a more precise answer to a question in a system wherein the user enters a question sentence and an answer to the question is provided. 
   2. Description of the Related Art 
   Recently, network communications through the Internet, etc., have grown in use and various services have been conducted through the network. One of the services through the network is search service. In the search service, for example, a search server receives a search request from a user terminal such as a personal computer or a mobile terminal connected to the network and executes a process responsive to the search request and transmits the processing result to the user terminal. 
   For example, to execute search process through the Internet, the user accesses a Web site providing search service and enters search conditions of a keyword, category, etc., in accordance with a menu presented by the Web site and transmits the search conditions to a server. The server executes a process in accordance with the search conditions and displays the processing result on the user terminal. 
   Data search process involves various modes. For example, a keyword-based search system wherein the user enters a keyword and list information of the documents containing the entered keyword is presented to the user, a question answering system wherein the user enters a question sentence and an answer to the question is provided, and the like are available. The question answering system is a system wherein the user need not select a keyword and can receive only the answer to the question; it is widely used. 
   For example, JP 2002-132811 A discloses a typical question answering system. JP 2002-132811 A discloses a question answering system including a question analysis section. The question analysis section determines a search word (keyword), which is applied in searching, and the question type from a question sentence presented by the user. The question answering system executes procedures of making a search based on the search word (keyword), applying an answer extraction rule to a search result, which is a sentence containing the search word (keyword) to extract answer candidates, ranking the obtained answer candidates to output them. 
   The search result based on the search word (keyword) is an article of a document, for example, and generally is made up of a plurality of sentences. How the accuracy of processing of selecting appropriate words as answer candidates to the question from the search result is enhanced is one problem. 
   For example, “NTT&#39;s Question Answering System for NTCIR QAC2,” (Isozaki. H, Working Notes of NTCIR-4 Workshop, pp. 326-332 (2004); hereinafter referred to as non-patent document 1) discloses a configuration for setting one unit (passage) of text contained in a search result as a variable-length morpheme string (window), searching a range of the window containing a given search word as a search target passage, applying a preset answer extraction rule to a search target passage portion, and efficiently extracting answer candidates. Thus, searching of the portion containing a possible answer candidate in most of existing question answering systems is designed based on the philosophy of acquiring a close portion from the keyword contained in the question sentence. “Importance of Pronominal Anaphora Resolution in Question Answering System” (Jose Luis Vicedo and Antonio Ferrandez, ACL 2000; hereinafter referred to as non-patent document 2) points out the importance of anaphoric analysis in a question answering system, namely, the importance of determining as to whether representations of noun phrases and pronouns contained in the text as the search result are identical with each other, and describes that it is effective to extract answer candidates with applying anaphoric analysis. 
   As described above, several propositions have been made for how answer candidates to a question are extracted efficiently and with high accuracy from the text as the search result based on the search word (keyword) in the question answering system for providing an answer corresponding to a user&#39;s question. However, the technique of the non-patent document 1 attempts to extract an answer candidate with assuming that a portion containing the answer candidate is in the vicinity of a keyword of a sentence containing a search keyword. In this technique, the context of the search document is not considered and therefore if an appropriate answer candidate does not exist before or after the text portion that the keyword most matches, the system cannot provide a right answer; this is a problem. 
   The non-patent document 2 recommends applying the anaphoric analysis processing. However, in the case of applying the anaphoric analysis processing to a document, which is a search result, if the context of the document obtained as the search result is complicated, a right answer cannot be obtained in some cases; this is a problem. A specific example will be discussed below. 
   By way of example, it is assumed that an input question from a client (questioner user) is the following sentence: 
   Question Sentence
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”       

   Assume that this question is input to a question answering system. Since the question contains “Where is . . . ?” the question answering system determines that the question is a question about “place.” The question type determination processing is executed in most existing techniques. 
   Further, the question answering system extracts a search word (keyword) applied to searching from the question sentence. Here, it is assumed that the keywords of “Christmas tree, pine tree, popular, enthusiasts” are extracted and that documents are searched using the keywords and one article made up of the following sentences is found: 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.       

   This article is made up of sentences 1 to 5 and extracted as a result of searching databases and Web pages, which are search targets (knowledge sources), by using the keyword search of “Christmas tree, pine tree, popular, enthusiasts.” 
   In the article as the search result, a topic of a Christmas tree in Hata City Castle Ruin Park is mentioned in sentence 2 and then, a topic of general Christmas trees is mentioned in sentences 3 and 4 and again the topic of the Christmas tree in Hata City Castle Ruin Park is mentioned in sentence 5. 
   The match degree between each of sentences 1 to 5 and the keywords is analyzed. Sentence 2 contains two keywords and sentence 5 contains three keywords, and thus, it is determined that sentences 2 and 5 have high match degree with the keywords. In the existing answer candidate extraction method, “New York” contained in sentence 5 or “Rockefeller Center” contained in sentence 4, which is “place” in the vicinity of the sentence most matching the keywords, is selected preferentially as an answer candidate to the question. 
   The true answer “Hata City Castle Ruin Park” is contained in sentence 1, but sentence 1 does not contain any keywords applied to the searching. Therefore, it is determined that sentence 1 is low in the match degree with the keywords. Answer candidate extraction from sentence 1 is executed after answer candidate extraction processing in the vicinity of a sentence having high match degree with the keywords. If a potent answer candidate is extracted in the sentence having high match degree with the keywords or in the vicinity of such a sentence, answer candidate extraction processing from sentence 1 may be unexecuted and consequently, the true answer “Hata City Castle Ruin Park” may not be presented to the user, because the noun phrase existing in the vicinity of the sentence having high match degree with the keywords is selected preferentially as an answer candidate in the existing answer candidate extraction method. 
   However, the right answer is “Hata City Castle Ruin Park” in sentence 1. Considering the structure of the article extracted as the search result, sentences 3 and 4 of general topics are inserted in midpoint of the context and the description relevant to the Christmas tree of the pine tree in Hata City Castle Ruin Park is distributed. Thus, it is made difficult to select “Hata City Castle Ruin Park” in sentence 1 as an answer to the question sentence. 
   Here, the case where anaphoric analysis recommended in the non-patent document 2, namely, it is determined as to whether representations of noun phrases, pronouns, and zero pronouns in the text as the search result are identical with each other is executed will be discussed. The case where anaphoric analysis is applied on the article obtained as the search result using an existing anaphoric analysis technique based on the non-patent document 2 and processing of grasping the anaphoric relation in sentences 1, 2, and 5 is performed will be discussed with reference to  FIG. 1 . 
   In the anaphoric analysis, identity determination between words in different representations is made. For example, in the anaphoric analysis, it is seen in  FIG. 1  that 
   (a-1) “Hata City Castle Ruin Park” in sentence 1 and (a2) “park” in sentence 2 are identical and indicate the same entity in different representations. 
   (b1) “Christmas tree” in sentence 2 and (b2) “this tree” in sentence 5 match. Also, in language such as Japanese language in which zero pronouns often appear, (b2) “this tree” is recognized as a zero pronoun with respect to “popular”, and this zero pronoun is a target of the anaphoric analysis. Furthermore, 
   (c1) “pine tree” in sentence 2, (c2) (pine tree), zero pronoun of the subjective case of “became” in sentence 2, and (c3) “the pine tree” in sentence 5 match. 
   Thus, in the anaphoric analysis, identity determination between representations of noun phrases, pronouns, and zero pronouns in the text is made. However, in the anaphoric analysis of the related art, the identity determination between representations is only made and processing of moving “Hata City Castle Ruin Park” in sentence 1 to sentence 5, for example, is not performed. Sentence 5 only tells popularity of “the Christmas tree of the pine tree” and such information containing “Hata City Castle Ruin Park” in sentence 5 does not exist. Thus, if only the existing anaphoric analysis processing is executed, it is difficult to arrange the search target of the complicated text or to execute extraction processing of the right answer candidate; this is a problem. 
   SUMMARY OF THE INVENTION 
   The invention provides a question answering system, a data search method, and a computer program, which can efficiently extract an appropriate search result for a question answer even from a document of a complicated context structure. 
   According to one embodiment of the invention, a question answering system includes a question input unit, a search unit, an anaphoric analysis unit, an information extraction unit and an answer candidate extraction unit. The question input unit is input to a question. The search unit executes search processing on a basis of the input question. The anaphoric analysis unit executes anaphoric analysis processing on a search result of the search unit. The information extraction unit extracts sentences, which include expressions having a reference relation therebetween, as reference relation sentences, the reference relation determined by finding relation in an expressions of at least one of a noun phrase, a pronoun, and a zero pronoun between sentences in the search result on a basis of a result of the anaphoric analysis executed by the anaphoric analysis unit. The information extraction unit selects a first candidate sentence from a passage obtained as the search result and selects a second candidate sentence, which is the reference relation sentence of the first candidate sentence. The answer candidate extraction unit extracts an answer candidate from the first and second candidate sentences selected by the information extraction unit. 
   According to one embodiment of the invention, a data search method includes inputting a question; executing search processing on a basis of the input question; executing anaphoric analysis processing on a search result of the search unit; arranging expressions including one of a noun phrase, a pronoun, and a zero pronoun at least contained in the search result on a basis of a result of the anaphoric analysis; extracting sentences, which include expressions having a reference relation therebetween, as reference relation sentences; selecting a first candidate sentence from a passage obtained as the search result; selecting a second candidate sentence, which is the reference relation sentence of the first candidate sentence; and extracting an answer candidate from the first and second candidate sentences selected. 
   According to one embodiment of the invention, a computer program is stored in a storage medium. The computer program causes a computer to execute data search processing. The data search processing includes inputting a question; executing search processing on a basis of the input question; executing anaphoric analysis processing on a search result of the search unit; extracting sentences, which include expressions having a reference relation therebetween, as reference relation sentences, the reference relation determined by finding relation in an expressions of at least one of a noun phrase, a pronoun, and a zero pronoun between sentences in the search result on a basis of a result of the anaphoric analysis; selecting a first candidate sentence from a passage obtained as the search result; selecting a second candidate sentence, which is the reference relation sentence of the first candidate sentence; and extracting an answer candidate from the first and second candidate sentences selected. 
   The computer program as set forth above may be a computer program that can be provided by a record medium or a communication medium for providing the computer program for a computer system that can execute various program codes in a computer-readable format, for example, a record medium such as a CD, an FD, or an MO or a communication medium such as a network. Such a program is provided in the computer-readable format, whereby processing responsive to the program is realized in a computer system. 
   In addition to extracting the reference relation of the representations of any of a noun phrase, a pronoun and a zero pronoun, a combination of the noun representations or all reference relations may be extracted. The sentence-level anaphoric relation may be obtained to thereby extract the reference relation with regard to an embed sentence or the whole sentence. (With regard to an example of the anaphoric analysis containing the whole sentence as a target, see “An Estimate of Referent of Nouns in Japanese Sentences with Referential Property of Nouns” (MURATA Masaki and NAGAO Makoto, Natural Language Processing, Vol. 3. No. 1, (1996)) 
   The above and other objects, features and advantages of the invention will be apparent from the following detailed description of the preferred embodiment of the invention in conjunction with the accompanying drawings. The system in the specification is a logical set made up of a plurality of units (apparatus) and is not limited to a set of units (apparatus) housed in a single cabinet. 
   According to the configuration set forth above, if a sentence is selected based on match degree with a search keyword in the processing of selecting a candidate sentence, it is made possible to reliably acquire a potent answer candidate at a position distant from a keyword as an answer candidate without missing the answer candidate and present the answer candidate to the client. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     In the accompanying drawings: 
       FIG. 1  is a drawing to describe an example of conducting anaphoric analysis on an article obtained as the search result using an existing anaphoric analysis technique; 
       FIG. 2  is a drawing of the network configuration to show an application example of a question answering system of the invention; 
       FIG. 3  is a block diagram to describe the configuration of the question answering system according to one embodiment of the invention; 
       FIG. 4  is a drawing to describe an example of anaphoric analysis processing executed by the question answering system according to the embodiment of the invention; 
       FIG. 5  is a drawing to describe score calculation processing in the question answering system according to the embodiment of the invention; 
       FIG. 6  is a flowchart to describe the processing sequence executed by the question answering system according to the embodiment of the invention; 
       FIG. 7  is a drawing to describe the result data of syntactic and semantic analysis processing on a sentence forming the search result, executed in the question answering system according to the embodiment of the invention; 
       FIG. 8  is a drawing to describe syntactic and semantic structure conversion processing of sentences forming the search result, executed in the question answering system according to the embodiment of the invention; 
       FIG. 9  is a drawing to describe syntactic and semantic structure conversion processing executed in the question answering system according to the embodiment of the invention; and 
       FIG. 10  is a block diagram to describe a hardware configuration example of the question answering system according to the embodiment of the invention. 
   

   DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION 
   A question answering system, a data search method, and a computer program according to an embodiment of the invention will be discussed in detail with reference to the accompanying drawings. 
   FIRST EXAMPLE 
   To begin with, an example of the question answering system of the invention will be discussed with reference to  FIG. 2 .  FIG. 2  is a drawing to show the network configuration wherein a question answering system  200  according to this example of the invention is connected to a network. A network  100  shown in  FIG. 2  is the Internet, an intranet, etc. Connected to the network  100  are clients  101 - 1  to  101 - n  as user terminals for transmitting a question to the question answering system  200  and various Web page providing servers  102 A to  102 N for providing Web pages as materials to acquire answers to the clients  101 - 1  to  101 - n  and databases  103   a  to  103   n.    
   The question answering system  200  inputs various question sentences generated by the users from the clients  101 - 1  to  101 - n  and provides the answers to the input questions for the clients  101 - 1  to  101 - n.  The answers to the questions are acquired from the Web pages provided by the Web page providing servers  102 A to  102 N, document data stored in the databases  103   a  to  103   n , and the like. The Web pages provided by the Web page providing servers  102 A to  102 N and the data stored in the databases  103   a  to  103   n  are the data to be searched and are called a corpus or information sources, knowledge sources, etc. 
   The Web page providing servers  102 A to  102 N provide Web pages as pages opened to the public by a WWW (World Wide Web) system. The Web page is a data set displayed on a Web browser and includes text data, HTML layout information, an image, audio, a moving image, etc., embedded in a document. A set of Web pages is a Web site, which includes a top page (home page) and other Web pages linked from the top page. 
   The configuration and processing of the question answering system  200  will be discussed with reference to  FIG. 3 . The question answering system  200  is connected to the network  100  and executes processing of receiving an answer from a client connected to the network  100 , searching the Web pages provided by the Web page providing servers and other databases connected to the network  100  as the information sources for an answer, generating a list of answer candidates, for example, and providing the list for the client. 
   The question answering system  200  according to this example of the invention executes anaphoric analysis processing on a search document, which is a search result obtained by making a search in response to a question from a client to consider the context thereof. The processing is similar processing to that described in the non-patent document 2; this processing differs from the processing described in the non-patent document 2 in that it expands a search range for the answer candidate later on the basis of the anaphoric analysis processing. 
   The question answering system according to this example of the invention arranges a search area for the answer candidate in the search document so as to easily search based on the result of the anaphoric analysis processing on the search document. The configuration and processing of the question answering system according to this example of the invention will be discussed in detail with reference to  FIG. 3 . 
   To begin with, the configuration of the question answering system  200  according to this example of the invention will be discussed with reference to  FIG. 3 . As shown in  FIG. 3 , the question answering system  200  has a question input unit  201 , a question analysis unit  202 , an information search unit  203 , an anaphoric analysis unit  204 , an information extraction unit  205 , an answer candidate extraction unit  206 , an answer candidate selection unit  207 , and an answer output unit  208 . The processing executed by each unit of the question answering system  200  will be discussed below. 
   [Question Input Unit] 
   The question input unit  201  is input to a question sentence (input question) from a client through the network  100 . In the description to follow, as a specific question example, it is assumed that the input question from a client (questioner user) is the following sentence: 
   (Input Sentence)
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”       

   It is assumed that this question is input to the question answering system  200 . 
   [Question Analysis Unit] 
   The question analysis unit  202  executes analysis processing of the input sentence. For example, a question type as to whether an answer required by the question is a person or a place is determined and a feature word used as a search word (search keyword) is detected from a sentence of the question. 
   (Input Sentence)
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”       

   Since the question contains “Where is . . . ?”, it is determined that the question is a question about “place.” The question type determination processing is similar to processing executed in most existing techniques. 
   Further, the question analysis unit  202  extracts a search word (keyword) applied to searching, from the question sentence. Here, it is assumed that keywords of “Christmas tree, pine tree, popular, enthusiasts” are extracted. 
   The information search unit  203  executes a search based on the search word (search keyword) extracted by analysis of the question analysis unit  202 . That is, for example, the information search unit  203  executes search processing using the Web pages provided by the Web page providing servers  102 A to  102 N connected to the network  100  and the databases  103   a  to  103   n  connected to the network  100  as documents to be searched (knowledge sources) and acquires text determined to contain an answer to the question. 
   Here, it is assumed that documents are searched using the keywords of “Christmas tree, pine tree, popular, enthusiasts” described above and one article made up of the following sentences is found: 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.       

   The search result is made up of sentences 1 to 5 and is extracted as a result of searching databases, Web pages, etc., which are the search targets (knowledge sources), by executing keyword search of “Christmas tree, pine tree, popular, enthusiasts.” 
   [Anaphoric Analysis Unit] 
   The anaphoric analysis unit  204  executes anaphoric analysis processing on a search document obtained as the search result of the information search unit  203 . The anaphoric analysis processing is executed as processing of analyzing a text obtained as the search result to make an identity determination of representation of any of a noun phrase, a pronoun, and a zero pronoun in the text. The anaphoric analysis technique is described in detail, for example, in “Analyze omission using automatically developed case dictionary and position preference order of antecedent” (KAWAHARA daisuke and KUROHASHI sadao, Natural Language Processing, Vol. 11, No. 3 (2004)), “One technique of anaphoric analysis of Japanese-language noun phrase by machine learning” (IIDA Ryuu, INUI Kentarou, MATSUMOTO Hiroharu and SEKINE sou, Language Processing Society 10th annual conference (2004)) and “A Machine Learning Approach to Coreference Resolution of Noun Phrases” (W. M. Soon, H. T. Ng, and D. C. Y. Lim, Computational Linguistics, Vol. 27, No. 4, pp. 521-544, (2001). 
   In the example, it is assumed that the search result made up of the following sentences 1 to 5 are already obtained: 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.       

   It is assumed that anaphoric analysis is conducted on the search result and the following anaphoric analysis result is obtained: 
   (a-1) “Hata City Castle Ruin Park” in sentence 1 and (a2) “park” in sentence 2 are identical and indicate the same entity in different representations. 
   (b1) “Christmas tree” in sentence 2, (b2) “This tree” in sentence 5 match. 
   and further 
   (c1) “pine tree” in sentence 2 and (c3) “the pine tree” in sentence 5 match. 
   In the case of the anaphoric analysis in Japanese language, (b3) (Christmas tree of the pine tree) in sentence 5 is recognized as a zero pronoun of the subjective case of “popular” in sentence 5, and (c2) (pine tree) in sentence 2 is recognized as a zero pronoun of the subjective case of “became” in sentence 2. Results of the anaphoric analysis in Japanese language show that the zero pronoun in sentence 5 matches (b1) “Christmas tree” in sentence 2 and (b2) “This tree” in sentence 5, and also the zero pronoun in sentence 2 matches (c1) “pine tree” in sentence 2 and (c3) “the pine tree” in sentence 5. 
   The analysis result is similar to the result previously described with reference to  FIG. 1 . 
   [Information Extraction Unit] 
   As described above, in the existing technique, in a case of selecting a plurality of sentences (a passage) from which each answer candidate is extracted, processing of preferentially selecting a sentence (passage) having high match degree with the keyword is performed. 
   In sentences 1 to 5, sentence 2 contains two keywords and sentence 5 contains three keywords and it is determined that sentences 2 and 5 have high match degree with the keywords. In the existing method, sentence 5 is the most effective sentence in answer candidate selection and sentence 2 is the second most effective sentence, and a noun phrase in the vicinity of sentence 5 is selected preferentially as an answer candidate. 
   In the actual processing of selecting an answer candidate, for example, the following processing is executed. First, an answer candidate is extracted from sentences (candidate sentences) including the sentence 5 and sentences preceding and following the sentence 5. Then, an answer candidate is extracted from sentences (candidate sentences) including the sentence 2 and sentences preceding and following the sentence 2. In the processing, the sentences preceding and following the sentences 2 and 5 are handled as sentences in the vicinity of the sentences 2 and 5, respectively. 
   In the question answering system according to this example of the invention, the information extraction unit  205  executes selection processing of each passage, that is, selects a candidate sentence, from which an answer candidate will be extracted, from a passage contained in the search result (in this example, the five sentences from sentence 1 to sentence 5). The information extraction unit  205  executes answer extraction processing from the candidate sentence. The selection processing and the answer extraction processing executed by the answer extraction unit  205  are different from conventional processing to which the anaphoric analysis processing is applied. Specifically, the information extraction unit  205  expands candidate sentences from which answer candidate will be extracted, on a basis of the result of the anaphoric analysis and extracts the answer candidates from the expanded candidate sentence. 
   Specific processing will be discussed. 
   The information extraction unit  205  arranges the representations of any of a noun phrase, a pronoun, and a zero pronoun based on the result of the anaphoric analysis for each sentence obtained as the search result (in this example, sentences 1 to 5), and extracts sentences sharing representations having reference relation therebetween. This processing will be discussed with reference to  FIG. 4 . 
   The following anaphoric analysis results (1) to (3) are obtained: 
   (1) (a-1) “Hata City Castle Ruin Park” in sentence 1 and (a2) “park” in sentence 2 match; 
   (2) (b1) “Christmas tree” in sentence 2 and (b2) “This tree” in sentence 5 match and 
   (3) (c1) “pine tree” in sentence 2 and (c3) “the pine tree” in sentence 5 match, 
   as shown in  FIG. 4 . 
   In the case of the anaphoric analysis in Japanese language, (b3) (Christmas tree of the pine tree) in sentence 5 is recognized as a zero pronoun of the subjective case of “popular” in sentence 5, and (c2) (pine tree) in sentence 2 is recognized as a zero pronoun of the subjective case of “became” in sentence 2. Results of the anaphoric analysis in Japanese language show that the zero pronoun in sentence 5 matches (b1) “Christmas tree” in sentence 2 and (b2) “This tree” in sentence 5, and also the zero pronoun in sentence 2 matches (c1) “pine tree” in sentence 2 and (c3) “the pine tree” in sentence 5. 
   The information extraction unit  205  arranges the representation of any of a noun phrase, a pronoun, and a zero pronoun based on the result of the anaphoric analysis and extracts sentences sharing the representation having the reference relation therebetween (reference relation sentences). The reference relation sentences sharing the representation having reference relation therebetween are sentences having the representation referencing the same entity in the anaphoric analysis results (1) to (3) described above. It is determined: 
   that sentences 1 and 2 share the representation having reference relation therebetween from the anaphoric analysis result (1); 
   that sentences 2 and 5 share the representation having reference relation therebetween from the anaphoric analysis result (2); and 
   that sentences 2 and 5 share the representation having reference relation therebetween from the anaphoric analysis result (3). 
   The information extraction unit  205  thus arranges the representations in the text based on the results of the anaphoric analysis and selects reference relation sentences. 
   In the example, the reference relation sentences are [sentences 1 and 2] and [sentences 2 and 5]. 
   As described above, in the processing of selecting a candidate sentence from which an answer candidate will be extracted, for example, match degree of each sentence (passage) with the keywords is calculated. In sentences 1 to 5, sentence 2 contains two keywords and sentence 5 contains three keywords. Therefore, it is determined that sentences 2 and 5 have high match degree with the keywords. In the existing method, sentence 5 is regarded as the most effective sentence in selecting answer candidate and sentence 2 is regarded as the second most effective sentence, and a noun phrase in the vicinity of sentence 5 is selected preferentially as an answer candidate. Then, the existing method selects preferentially a noun phrase in the vicinity of sentence 2 as an answer candidate. 
   In the question answering system  200  according to this example of the invention, when a candidate sentence is selected based on match degree with the keywords, the information extraction unit  205  determines whether or not a reference relation sentence is set for the selected candidate sentence (serving as a first candidate sentence). If yes, the information extraction unit  205  further selects the reference relation sentence as the candidate sentence (serving as a second candidate sentence). 
   In this example, when selecting a candidate sentence from which an answer candidate will be extracted, based on sentence 5 having the highest match degree with the keywords, the information extraction unit  205  determines as to whether or not a reference relation sentence corresponding to sentence 5 is set. In this example, sentence 2 is set as the reference relation sentence corresponding to sentence 5, as previously described with reference to  FIG. 4 . Therefore, the information extraction unit  205  selects sentence 5+sentence 2 and a sentence area including the vicinity of sentences 5 and 2 as a primary preference sentence area for answer candidate extraction. 
   Next, when selecting a candidate sentence from which an answer candidate will be extracted, based on sentence 2 having the second highest match degree with the keywords only to sentence 5, the information extraction unit  205  determines as to whether or not a reference relation sentence corresponding to sentence 2 is set. In this example, sentence 1 is set as the reference relation sentence corresponding to sentence 2, as previously described with reference to  FIG. 4 . Therefore, the information extraction unit  205  selects sentence 2+sentence 1 and a sentence area including the vicinity of sentences 2 and 1 as a secondary preference sentence area for answer candidate extraction. 
   For example, in the case where the information extraction unit  205  selects as the sentence area for answer candidate extraction, a sentence area including sentences preceding and following a sentence (first candidate sentence), which is selected on the basis of match degree with the keywords, firstly the following sentences are selected as the candidate sentence on the basis of sentence 5 having the highest match degree with the keywords.
         (a) sentence 5 and sentence 4 preceding sentence 5; and   (b) sentence 2, which is the reference relation sentence corresponding to sentence 5, and sentences 1 and 3 preceding and following sentence 2.       

   Secondly, the following sentences are selected as the candidate sentences on the basis of sentence 2 having the second highest match degree with the keywords only to sentence 5.
         (c) sentence 2 and sentences 1 and 3 preceding and following sentence 2; and   (d) sentence 1, which is the reference relation sentence corresponding to sentence 2, and sentence 2 following sentence 1       

   In fact, the sentences selected in (c) and (d) are already selected in (a) and (b) and therefore may be omitted. In the example, duplicate selected sentences occur because the passage is made of small number of sentences (i.e., sentences 1 to 5); however, if a long article is obtained as the search result, candidate sentences may be selected in order without selecting sentences redundantly. 
   [Answer Candidate Extraction Unit] 
   The answer candidate extraction unit  206  executes answer candidate extraction processing using the sentences, which the information extraction unit  205  selects as the candidate sentence by executing the candidate sentence extraction processing while considering the reference relation sentences as described above. 
   The answer candidate extraction unit  206  selects each noun phrase corresponding to “place”, which is of the question type obtained by the question analysis unit  202  described above, out of the candidate sentences selected by the information extraction unit  205 . When selecting each noun phrase corresponding to “place,” the answer candidate extraction unit  206  may use an existing NE technique so as to acquire each noun to which a “place” tag of an NE (named entity) tag indicating lexis is assigned from the candidate sentences. 
   In the processing of this example, the information extraction section  205  selects the candidate sentences from which an answer candidate will be extracted, while considering a reference relation sentence as described above. In this example, it is assumed that all of sentences 1 to 5 are selected as the candidate sentence. The following noun phrases are selected as noun phrases corresponding to “place” from sentences 1 to 5:
         “Hata City Castle Ruin Park”   “New York”   “Rockefeller Center”
 
[Answer Selection Unit]
       

   The answer selection unit  207  sets score indicating a suitability degree as an answer, for each answer candidate extracted by the answer candidate extraction unit  206 . Then, the answer selection unit  207  ranks the answer candidates, and generates an answer candidate list in which the answer candidates are arranged in the descending order of the score. The answer selection unit  207  sets the scores for the answer candidates in accordance with the following score addition criteria (a) and (b):
         (a) Add to each answer candidate, score obtained on the basis of a keyword match degree of a sentence containing each answer candidate.   (b) If the sentence containing each answer candidate has a reference relation sentence, add to each answer candidate, score obtained on the basis of a keyword match degree of the reference relation sentence.       

   That is, the answer selection unit  207  sets for each answer candidate as a score of each answer candidate, a total sum of the score obtained on the basis of the keyword match degree of a sentence containing each answer candidate and the score obtained on the basis of the keyword match degree of the reference relation sentence corresponding to the sentence containing each answer candidate. 
   Specific score calculation processing of this example will be described with reference to  FIG. 5 .  FIG. 5A  shows keywords, which are applied to searching and extracted by the question analysis unit  202  on the basis of 
   (input sentence)
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”.       

   The keywords are “Christmas tree, pine tree, popular, enthusiasts.” 
     FIG. 5B  shows the search result, which the information search unit  203  obtains by searching the knowledge source based on the keywords. The search result is made up of the following sentences 1 to 5: 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.       

   It is assumed that the search result made up of the sentences 1 to 5 has already obtained. 
   The anaphoric analysis unit  204  executes anaphoric analysis on the search result as previously described with reference to  FIG. 4 , and determines: 
   that sentences 1 and 2 are reference relation sentences sharing representations having a reference relation therebetween; and 
   that sentences 2 and 5 are also reference relation sentences sharing representations having a reference relation therebetween. 
     FIG. 5B  shows the keywords contained in sentences 1 to 5 by rectangular regions. 
   Sentence 2 contains the two keywords [pine tree] and [Christmas tree] and 
   sentence 5 contains three keywords [pine tree], [popular], and [enthusiasts]. 
   As described above, the answer candidate extraction unit  206  selects the following answer candidates:
         “Hata City Castle Ruin Park”   “New York”   “Rockefeller Center”       

   The answer selection unit  207  sets score for each answer candidate. It is confirmed from the result of the anaphoric analysis executed by the anaphoric analysis unit  204  that “Hata City Castle Ruin Park” is a representation indicating the same entity as “park” in sentence 2. Therefore, the answer selection unit  207  calculates scores while considering “park” as a similar answer candidate to “Hata City Castle Ruin Park.” 
   A simple scoring example is shown. Sentence 4 does not contain any keywords in the question sentence “Christmas tree, pine tree, popular, enthusiasts,” but sentence 5 following sentence 4 contains the three keywords “pine tree, popular, and enthusiasts”. Also, sentence 2 contains the keyword [pine tree] contained in sentence 5 and new keyword “Christmas tree”, which is not contained in sentence 5. 
   Therefore, the scores of the answer candidates “New York” and “Rockefeller Center” contained in sentence 4 are calculated as follows. 
   A first score value [3] is calculated on the basis of the three keywords “pine tree, popular, and enthusiasts” contained in sentence 5 adjacent to sentence 4. 
   A second score value [1] is calculated on the basis of the new keyword “Christmas tree” contained in the reference relation sentence of the adjacent sentence 5, namely, in sentence 2. 
   Then, a final score value [4] is obtained by summing the first score value and the second score value. The answer selection unit  207  gives this final score value [4] to the answer candidates “New York” and “Rockefeller Center” as score of those answer candidates. 
   The score of the answer candidate “park” (“Hata City Castle Ruin Park”) contained in sentence 2 us calculated as follows. 
   A first score value [2] is calculated on the basis of the two keywords “pine tree and Christmas tree” contained in sentence 2. 
   A second score value [2] is calculated on the basis of the new keywords “popular and enthusiasts”, which are contained in the reference relation sentence of sentence 2, namely, in sentence 5 but is not contained in sentence 2. 
   Then, the answer selection unit  207  gives a final score value [4] to the answer candidate “park” (“Hata City Castle Ruin Park”) as its score. 
   Accordingly, the answer selection unit  207  sets the scores of the answer candidates as follows:
         “park” (“Hata City Castle Ruin Park”)=score 4   “New York”=score 4   “Rockefeller Center”=score 4       

   Consequently, the scores of the answer candidates are set to the same value [4]. In such a case, an answer candidate existing in a location nearest to a keyword has precedence over the other answer candidates. Sentence 2 containing “park” contains a plurality of keywords, and sentence 4 containing “New York” and “Rockefeller Center” does not contain any keyword. Therefore, “park” (“Hata City Castle Ruin Park”) is output as the answer candidate closest to the right answer. Since it is seen from the anaphoric analysis result that “park” and “Hata City Castle Ruin Park” refer to the same entity, the question answering system  200  of the example can provide the right answer “Hata City Castle Ruin Park” for the client (questioner user). 
   The answer selection unit  207  may select a sole answer candidate thus obtained as the answer presented to the client. Alternatively, the answer selection unit  207  may generate and present an answer candidate list as a ranking list based on the score values, for example. 
   [Answer Output Unit] 
   The answer output unit  208  outputs the answer candidate finally determined by the answer selection unit  207  to the client. 
   According to the processing described above, as the answer to the input question 
   (Input Sentence)
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”
 
only
   “Hata City Castle Ruin Park”
 
can be selected or an answer candidate list in which “Hata City Castle Ruin Park” is set in the highest place can be presented to the user.
       

   Next, the processing sequence executed by the question answering system  200  according to this example of the invention will be described with reference to a flowchart of  FIG. 6 . 
   At step S 101 , when a question from a client is input to the question input unit  201 , analysis processing of the input question sentence is executed at step S 102 . The question analysis unit  202  shown in  FIG. 3  executes this analysis processing. For example, the keywords “Christmas tree, pine tree, popular, enthusiasts” are extracted from 
   (Input Sentence)
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”,
 
and the question type is determined as “place” from this input sentence.
       

   Next, at step S 103 , search processing corresponding to the question is executed on the basis the search keywords. This search processing searches the knowledge sources of Web pages and databases. The information search unit  203  shown in  FIG. 3  executes this search processing. The information search unit  203  executes search processing using queries generated on the basis of the keywords selected out of the question sentence. 
   Specifically, for example, the information search unit  203  searches on the basis of queries including the keywords “Christmas tree, pine tree, popular, enthusiasts” extracted from 
   (Input Sentence)
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”.
 
Then, the information search unit  203  obtains the search result made up of the following sentences 1 to 5:
       

   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.       

   Next, at step S 104 , anaphoric analysis processing of the search result acquired by executing the search processing is executed the anaphoric analysis unit  204  in  FIG. 3  executes this anaphoric analysis processing. 
   The anaphoric analysis processing analyzes a text obtained as the search result to make an identity determination of representations of any of a noun phrase, a pronoun, and a zero pronoun in the text. 
   If anaphoric analysis is executed on the search result made up of sentences 1 to 5, the following anaphoric analysis result is obtained: 
   (a-1) “Hata City Castle Ruin Park” in sentence 1 and (a2) “park” in sentence 5 are identical and indicate the same entity in different representations; 
   (b1) “Christmas tree” in sentence 2 and (b2) “this tree” in sentence 5 match; and further 
   (c1) “pine tree” in sentence 2 and (c3) “the pine tree” in sentence 5 match. 
   In the case of the anaphoric analysis in Japanese language, (b3) (Christmas tree of the pine tree) in sentence 5 is recognized as a zero pronoun of the subjective case of “popular” in sentence 5, and (c2) (pine tree) in sentence 2 is recognized as a zero pronoun of the subjective case of “became” in sentence 2. Results of the anaphoric analysis in Japanese language show that the zero pronoun in sentence 5 matches (b1) “Christmas tree” in sentence 2 and (b2) “This tree” in sentence 5, and also the zero pronoun in sentence 2 matches (c1) “pine tree” in sentence 2 and (c3) “the pine tree” in sentence 5. 
   The analysis result is similar to the result previously described with reference to  FIG. 1 . 
   Next, at step S 105 , a reference relation sentence is extracted from the text obtained as the search result with using the result of the anaphoric analysis and a candidate sentence from which an answer candidate will be extracted is determined. The information extraction unit  205  shown in  FIG. 3  executes this processing. 
   The information extraction unit  205  arranges the representations of any of a noun phrase, a pronoun, and a zero pronoun in the text on the basis of the result of the anaphoric analysis, for each of the sentences obtained as the search result (in the example, sentences 1 to 5). Also, the information extraction unit  205  extracts sentences (reference relation sentences) sharing representations having a reference relation therebetween. This processing is as previously described with reference to  FIG. 4 . 
   In the processing example described with reference to  FIG. 4 , sentences 1 and 2 and sentences 2 and 5 are determined as the reference relation sentences. Further, the information extraction unit  205  calculates the keyword match degree of each sentence, and determines a sentence having the high keyword match degree as a candidate sentence (a first candidate sentence). Also, the information extraction unit  205  checks whether or not a reference relation sentence corresponding to the sentence having the high keyword match degree. If a reference relation sentence exists, the information extraction unit  205  determines that the reference relation sentence as the candidate sentence (a second candidate sentence). Incidentally, the candidate sentence may further include a sentence adjacent to the sentence having the high keyword match degree and/or a sentence adjacent to the reference relation sentence of the sentence having the high keyword match degree. 
   Next, at step S 106 , answer candidate extraction processing from the candidate sentences is executed. The answer candidate extraction unit  206  shown in  FIG. 3  executes this processing. The answer candidate extraction unit  206  selects respective noun phrase corresponding to “place”, which is of the question type obtained by the question analysis unit  202  described above, from the candidate sentences selected by the information extraction unit  205 . To select each noun phrase corresponding to “place,” an existing NE technique may be used so as to acquire each noun to which a “place” tag of an NE (named entity) tag indicating lexis is assigned from the candidate sentences. 
   In the processing example described above,
         “Hata City Castle Ruin Park”   “New York”   “Rockefeller Center”
 
are selected as the answer candidates.
       

   Next, at step S 107 , score calculation processing for each answer candidate is executed with considering the result of the anaphoric analysis and the reference relation sentences. The answer selection unit  207  shown in  FIG. 3  executes this processing. The answer selection unit  207  sets score for each answer candidate extracted by the answer candidate extraction unit  206 , ranks the answer candidates and generates an answer candidate list in which the answer candidates are arranged in the descending order of the score. The score is set for each answer candidate according to the processing previously described with reference to  FIG. 5 . 
   That is, the answer selection unit  207  calculates summation data of score, which is obtained on the basis of keyword match degree of a passage (sentence x) to which an answer candidate belongs and/or its adjacent passage (sentence x±1 or the like), and score, which is obtained on the basis of keyword match degree of a reference relation sentence corresponding to each passage. Then, the answer selection unit  207  outputs the summation data as score for the answer candidate. 
   Next, at step S 108 , the answer selection unit  207  selects a sole answer candidate having the highest score as the answer to be presented to the client from among the answer candidates whose scores are calculated or generates an answer candidate list as a ranking list based on the score values. 
   Next, at step S 109 , the answer output unit  208  outputs the output answer candidate determined at step S 108  or the answer candidate list as the ranking list based on the score values to the client. 
   According to the processing described above, as the answer to the input question 
   (Input Sentence)
         “Where is a Christmas tree of a pine tree popular among enthusiasts?”
 
only
   “Hata City Castle Ruin Park”
 
can be selected or an answer candidate list in which “Hata City Castle Ruin Park” is set in the highest place can be presented to the user.
       

   OTHER MODIFIED EXAMPLES 
   Next, other examples in the question answering system according to the invention will be described. 
   In the example described above, in the processing of determining candidate sentences, the information extraction unit  205  operates as follows. That is, the information extraction unit  205  calculates keyword match degree of each sentence, determines the sentence having high keyword match degree and/or the sentences adjacent thereto as the candidate sentence (first candidate sentence), and checks whether or not a reference relation sentence corresponding to the sentence having the high keyword match degree exists. If a reference relation sentence exists, the information extraction unit  205  determines the reference relation sentence and/or sentences adjacent to the reference relation sentence as the candidate sentence (second candidate sentence). 
   In the processing of determining the candidate sentence, the information extraction unit  205  may combines the sentences containing the anaphoric representations on the basis of the result of the anaphoric analysis to generate a single sentence, and set a passage range based on the generated sentence. This processing will be discussed based on the following example sentences: 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.       

   In this example, an article is made up of sentences 1 to 5 obtained as the search result. In the article, sentences 2 and 5 and sentences 1 and 2 involve the anaphoric relation between the representations contained in those sentences, as described above. 
   It is assumed that the question answering system has already obtained the analysis result that sentences 2 and 5 contain search keywords and that sentences 2 and 5 have high keyword match degree. 
   In such a case, processing of combining all of sentences 2 and 5 and sentences 1 and 2 having reference relation therebetween, namely, combines sentences 1, 2, and 5 into a single sentence is executed. A processing described in “Estimate Instruction Target of Noun in Japanese-Language Sentence Using Referentiality of Noun” (MURATA Masaki, KUROHASHI Sadao, NAGAO Makoto, Natural Language Processing, Vol. 3. No. 1, (1996)), which is cited in the description of the processing executed by the anaphoric analysis unit  204 , may be used as the integration processing of a plurality of sentences into one sentence. 
   The sentence obtained by executing the sentence integration processing is adopted as a candidate sentence. The sentence integration processing is executed for sentences, which have the anaphoric relation between representations contained in the sentences and are determined as the reference relation sentences. To combine a plurality of sentences into one sentence, for example, a policy of “creating a relative clause concerning one noun phrase according to a sentence generation technique and combining two sentences into one sentence through the relative clause” is adopted. A procedure example of the sentence integration processing of inputting a plurality of sentences and combining the plurality of sentences into one sentence is shown below. 
   A target sentence is analyzed using, for example, a syntactic and semantic analysis system described in “Constructing a practical Japanese Parser based on Lexical Functional Grammar” (Masuichi and Ohkuma, natural language processing, Vol. 10. No. 2, pp. 79-109 (2003)), “Japanese Parser on the basis of the Lexical-Functional Grammar Formalism and its Evaluation” (Hiroshi Masuichi, et al., In Proceedings of The 17th Pacific Asia Conference on Language, Information and Computation (PACLIC17), pp. 298-309 (2003)), “The Parallel Grammar Project” (Miriam Butt, Helge Dyvik, Tracy Holloway King, Hiroshi Masuichi, and Christian Rohrer, In Proceedings of COLING-2002 Workshop on Grammar Engineering and Evaluation, pp. 1-7, (2002)), “Lexical-Functional Grammar: A formal system for grammatical representation” (Ronald M. Kaplan and Joan Bresnan, In Joan Bresnan, editor, The Mental Representation of Grammatical Relations, The MIT Press, Cambridge, Mass., pages 173-281, (1982), Reprinted in Dalrymple, Kaplan, Maxwell, and Zaenen, editors, Formal Issues in Lexical-Functional Grammar, 29-130. Stanford: Center for the Study of Language and Information, (1995)), and US 2003/0158723 A, entire contents of which are incorporated herein by reference in its entirety. Information about the syntactic structure of each sentence and the tense of each verb is obtained through this processing. 
   With regard to generation of sentences 1 and 2, which are integration targets, it is determined according to a generation processing order rule prepared manually in advance that which sentence a relative clause is embedded in the noun phrase of. The verbs of the main clauses of sentences 1 and 2 are both past. In such a case, the preceding sentence is embedded in the following sentence in the sentence appearance order. Such rules describe about the tense of the verb of the main clause, the sentence appearance order and the like. The rule takes precedence in the order of the verb tense and the sentence appearance order. 
   For example, in sentence generation for the two sentences
         “Tarou is fatigued.”   “Tarou worked too hard.”
 
the verb of the main clause of the first sentence is present and the verb of the main clause of the second sentence is past. In this case, the rule concerning the tense takes precedence and the second sentence is embedded in the first sentence to form a sentence of “Tarou who worked too hard is fatigued.” If the embedding order is opposite like a sentence of “Tarou who is fatigued worked too hard,” the original meaning changes.
       

   The above-described example will be discussed. That is, processing of combining sentences 1 and 2 of the following sentences into one sentence is performed 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.       

   Since “Hata City Castle Ruin Park” in sentence 1 and “park” in sentence 2 have the anaphoric relation therebetween, a relative clause sentence concerning “Hata City Castle Ruin Park” in sentence 1 is created. It is seen that the syntactic and semantic structure of sentence 1 has a structure as shown in  FIG. 7 . 
     FIG. 7  shows “f-structure (functional structure)” generated by executing syntactic and semantic analysis processing for 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.
 
The syntactic and semantic analysis processing may be performed using the syntactic and semantic analysis system described in “Constructing a practical Japanese Parser based on Lexical Functional Grammar” (Masuichi and Ohkuma, natural language. processing, Vol. 10. No. 2, pp. 79-109 (2003)) or US 2003/0158723 A.
       

   The syntactic and semantic analysis processing applies a grammar rule and a valence dictionary, analyzes the phrase structure based on the grammar rule and the like and analyzes a semantic structure representing a meaning of a sentence based on meaning of words contained in the sentence, semantic relation between the words and the like (the valence dictionary describes the relation with any other component in the sentence such as a verb and a subject, and the semantic relation between a predicate and its dependent word can be extracted). The syntactic and semantic analysis processing outputs “c-structure (constituent structure)” as a result of the syntactic analysis and outputs “f-structure (functional structure)”. “c-structure (constituent structure)” representing the phrase structure of the sentence made up of words, morphemes, etc., as a tree structure. “f-structure (functional structure)” is obtained as the result of semantically and functionally analyzing the input sentence as an interrogative sentence, past form, a polite sentence, etc., based on the case structure of a subject, an object, etc. 
   That is, c-structure represents the structure of a natural language sentence as a tree structure by collecting the morphemes of the sentence into an upper phrase. f-structure represents semantic information of the case structure, sentence tense, aspect, narration, etc., of a sentence as an attribute-attribute value matrix structure based on the notion of the grammar function. 
     FIG. 7  shows “f-structure (functional structure)” generated by executing syntactic and semantic analysis processing for 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.
 
f-structure represents the grammar function clearly and includes grammar function name, semantic format, and feature symbol. By referring f-structure, semantic understanding of subject, object, complement, adjunct, etc., can be obtained. f-structure is a set of features attached to respective nodes of c-structure shown as a tree structure, and is represented in the form of a matrix of attribute-value as shown in  FIG. 7 . That is, the left of the entries enclosed in [ ] is the names of the features (attributes) and the right is the values of the features (attribute values).
       

   The syntactic and semantic structure is used to execute the sentence integration processing. For example, the sentence integration processing based on the result of the syntactic and semantic analysis may use processing described in detail in “Chart Generation” (Kay, In Proceedings o the 34th Annual Meeting of the ACL). 
   As the processing result, the syntactic and semantic structure corresponding to
         “Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December”
 
is obtained based on
       

   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

     FIG. 8  shows the conversion processing of the syntactic and semantic structure. 
     FIG. 8  shows f-structure ( FIG. 8A ) obtained as the result of the syntactic and semantic analysis based on 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.
 
Also,  FIG. 8  shows f-structure ( FIG. 8B ) obtained as the result of the syntactic and semantic analysis based on
       

   generated sentence (A)
         “Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December”       

   Next, the relative clause sentence based on sentence 1 having the result of the syntactic and semantic analysis shown in  FIG. 8B  is embedded in 
   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.
 
When the embedding processing is performed, sentence 2 is changed to
   “In Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December, a pine tree was decorated and became a Christmas tree.”
 
and the changed sentence 2 is set as an integration sentence into which sentences 1 and 2 are combined.
       

   Subsequently, integrating processing of sentences 2 and 5 generated by executing the above-described processing is executed like the above-described processing. The generation order rule is also applied to sentences 2 and 5 and the embedding order of sentence 2 in sentence 5 is obtained. The sentence embedding processing can also be executed on the syntactic and semantic structure. 
   If a plurality of entities having an anaphoric relation therebetween exist, the syntactic and semantic structure for each representation referencing the entity must be grasped and an appropriate relative clause sentence must be cut out. In the following sentences 2 and 5: 
   Sentence 2:
         In Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December, a pine tree was decorated and became a Christmas tree.       

   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.
 
the anaphoric relations concerning the two representations of “pine tree” and “Christmas tree” appear. At this time, the verb to which “pine tree” relates is “decorated” and the verb to which “Christmas tree” relates is “became.” The sentences are changed so that a verb modifies the expressions between which the anaphoric relation appears.
       

   As shown in  FIG. 9A , “a pine tree which was decorated” is generated from 
   verb “decorated”, and 
   subjective case “pine tree”. 
   Furthermore, “a Christmas tree which (a pine tree) became” is obtained from 
   verb “became”, 
   subject case “pine tree” and 
   adjunct phrase “a Christmas tree”. 
   Based on these results, a relative clause sentence “In Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December, the pine tree which was decorated and a Christmas tree which (the pine tree) became” is generated from the sentence 2. 
   In the syntactic and semantic structure, the portion between parentheses indicates a portion “pine tree”, which appears previously. Also, the above-described sentence is obtained from the syntactic and semantic structure to which an operation is applied, and grammatical matters are not required here. 
   This relative clause sentence is generated based on sentence 2 generated by integrating sentences 1 and 2 described above, namely, 
   sentence 2:
         In Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December, a pine tree was decorated and became a Christmas tree.       

   As shown in  FIG. 9B , this relative clause sentence is embedded into: 
   Sentence 5:
         However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts.
 
As a result of the embedding processing, the syntactic and semantic structure shown in  FIG. 9C  is obtained and
       

   integrated sentence:
         “However, in Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December, a Christmas tree of the pine tree which was decorated, which (the pine tree) became, also has wonderful appeal and is popular among enthusiasts”.
 
is obtained. Also, although “pine tree” appears in “which the pine tree became” and “the pine tree which was decorated” both included in the integrated sentence derive from the single portion “pine tree” in the sentence 2, the single portion “pine tree” is changed into the two modification clauses, which overlap. When these portions are further integrated, finally the following single integrated sentence can be obtained as shown in  FIG. 9D .
   “However, in Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December, a Christmas tree which the pine tree, which was decorated became, also has wonderful appeal and is popular among enthusiasts”.       

   This sentence is generated by integrating and collecting the three sentences: 
   Sentence 1:
         Preparations for the year change period started at the 20th of December in Hata City Castle Ruin Park.       

   Sentence 2:
         In the park, a pine tree was decorated and became a Christmas tree.       

   Sentence 5: 
   However, this tree of the pine tree also has a wonderful appeal and is popular among enthusiasts. 
   The new sentence 5 (integrated sentence) thus generated based on sentences 1, 2, and 5 and the sentences preceding and following sentences 1, 2, and 5 are set as a candidate sentence and answer candidates are provided. Considering that sentences preceding and following the places where the sentences used to generate the integrated sentence exist are contained as the candidate sentence, the candidate sentences become as follows: 
   Sentence 3:
         Generally, a fir tree is used as a Christmas tree.       

   Sentence 4:
         A giant Christmas tree of Rockefeller Center in New York is world-famous.       

   Sentence 5:
         However, a Christmas tree that a decorated pine tree became in Hata City Castle Ruin Park in which preparations for the year change period started at the 20th of December also has a wonderful appeal and is popular among enthusiasts.       

   Answer candidate extraction processing applied to these candidate sentences is executed in a similar manner to that in the example described above, and answer candidates “New York,” “Rockefeller Center,” and “Hata City Castle Ruin Park” are obtained as the noun phrases each indicating a place. As the subsequent processing, score calculation similar to that described above in the example is executed and consequently “Hata City Castle Ruin Park” is obtained as the answer having the highest priority. 
   According to the processing example, a right answer can be obtained from a complicated context article. In addition, when a ground sentence from which the answer to the question is obtained is output, one sentence generated based on the result of the anaphoric analysis can be presented to the user, thereby enabling the user to save time and trouble for reading complicated text. 
   Last, a hardware configuration example of an information processing apparatus implementing the question answering system for executing the processing described above will be discussed with reference to  FIG. 10 . A CPU (Central Processing Unit)  501  executes processing corresponding to an OS (Operating System) and executes the search word (keyword) extraction, the search processing, the anaphoric analysis processing, the reference relation sentence extraction processing, the answer candidate extraction passage determination processing, the answer candidate extraction processing, the score calculation processing of the answer candidates, etc., based on the input question described above in the example. The CPU  501  executes the processing in accordance with a computer program stored in a data storage section of ROM, a hard disk, etc., of each information processing apparatus. 
   ROM (Read-Only Memory)  502  stores the program, operation parameters, etc., used by the CPU  501 . RAM (Random Access Memory)  503  stores a program used in execution of the CPU  501 , parameters, etc., changed whenever necessary in the execution of the CPU  501 . They are connected by a host bus  504  implemented as a CPU bus, etc. 
   The host bus  504  is connected to an external bus  506  of a PCI (Peripheral Component Interconnect/Interface) bus, etc., via a bridge  505 . 
   A keyboard  508  and a pointing device  509  are input devices operated by the user. A display  510  is implemented as a liquid crystal display, a CRT (cathode ray tube), or the like for displaying various pieces of information as text or an image. 
   An HDD (Hard Disk Drive)  511  contains a hard disk and drives the hard disk for recording or reproducing (playing back) a program executed by the CPU  501  and information. The hard disk is used as answer candidate, search result, and passage storage means, etc., for example, and further stores various computer programs such as a data processing program. 
   A drive  512  reads data or a program recorded on a removable record medium  521  such as a magnetic disk, an optical disk, a magneto-optical disk, or semiconductor memory mounted, and supplies the data or the program to the RAM  503  connected via the interface  507 , the external bus  506 , the bridge  505 , and the host bus  504 . 
   A connection port  514  is a port for connecting an external connection machine  522  and has a connection section of USB, IEEE 1394, etc. The connection port  514  is connected to the CPU  501 , etc., via the interface  507 , the external bus  506 , the bridge  505 , the host bus  504 , etc. A communication section  515  is connected to a network for executing communications with a client and a network connection server. 
   The hardware configuration example of the information processing apparatus applied as the question answering system shown in  FIG. 10  is an example of an apparatus incorporating a PC and the question answering system of the invention is not limited to the configuration shown in  FIG. 10  and may have any configuration if the configuration has the capability of executing the processing described above in the examples. 
   While the invention has been described in detail in its preferred embodiment (examples), it is to be understood that modifications will be apparent to those skilled in the art without departing from the spirit and the scope of the invention. That is, the invention is disclosed for illustrative purposes only and it is to be understood that the invention is not limited to the specific embodiment (examples) thereof except as defined in the claims. 
   The processing sequence described in the specification can be executed by both or either of hardware and software. To execute software processing, the program recording the processing sequence can be installed in memory in a computer incorporated in dedicated hardware for execution or can be installed in a general-purpose computer that can execute various types of processing for execution. 
   For example, the program can be previously recorded on a hard disk or in ROM (Read-Only Memory) as a record medium or can be stored (recorded) temporarily or permanently on a removable record medium such as a flexible disk, a CD-ROM (Compact Disk Read-Only Memory), an MO (Magneto Optical) disk, a DVD (Digital Versatile Disk), a magnetic disk, or semiconductor memory. Such a removable record medium can be provided as a package software product. 
   The program not only can be installed in a computer from a removable record medium as described above, but also can be transferred by radio waves from a download site to a computer or can be transferred to a computer in a wired manner through a network such as the Internet for the computer to receive the program thus transferred and install the program on a record medium such as a hard disk incorporated. 
   The various types of processing described in the specification may be executed not only in time sequence according to the description, but also in parallel or individually in response to the processing capability of the apparatus for executing the processing or as required. The system in the specification is a logical set made up of a plurality of units (apparatus) and is not limited to a set of units (apparatus) housed in a single cabinet. 
   According to the configuration described in each example, for example, even if a candidate sentence is selected from among a search result on the basis of a match degree with a search keyword, it is possible to reliably acquire a potent answer candidate located at a position distant from the keyword without overlooking it and to present the potent answer candidate to a user.