JP2007241908A - Example sentence search method based on dependency structure, program, recording medium storing example sentence search program, and example sentence search apparatus - Google Patents

Abstract

An example sentence search method, apparatus, and program for searching an example sentence syntactically including a word included in a search condition from a plurality of stored example sentences without requiring a search condition based on a special expression.
A language material storage step for storing a plurality of example sentences stored in advance and dependency structure information obtained by analyzing in advance dependency relations between words constituting each example sentence, and searching A search condition setting step for setting a search condition based on a plurality of words included in the sentence and the order of the words, a dependency structure pattern generation step for generating a dependency structure pattern expressing a dependency structure of the plurality of words, In the dependency structure pattern generation step, a plurality of example sentences in which the dependency structures between all the words included in the search condition can be generated with one dependency structure pattern are selected as corresponding to the search condition. A sentence selection step.
[Selection] Figure 9

Description

  The present invention relates to an example sentence search method for searching an example sentence corresponding to a search condition from a plurality of example sentences in accumulated language material.

  In order to create correct English sentences, it is effective to refer to examples and imitate them, and it is important for English creators to easily find English sentences worthy of reference from a large number of example sentences. Therefore, in order to find an appropriate English example, the English creator needs an environment for searching English examples in which “phrase as a clue” is input and English including the input is output.

  Under these demands, the importance of large-scale corpora (corpus), which contains a large amount of sentences, has been increasing in recent years. It is used as a language resource in various situations such as development. And in order to utilize a corpus effectively, various corpus search systems which search the sentence applicable to arbitrary search conditions from a corpus are proposed.

  However, many systems only implement keyword-based example searches, and while this keyword-based search has the advantage of being simple and intuitive, simple matching, ie, each in the corpus The search is performed based on whether or not a word set as a search condition is simply included in a sentence, and a search utilizing a linguistic structure such as a syntax structure cannot be performed. For this reason, even if you want to search for example sentences that contain a syntax consisting of multiple words, the search results also include sentences that simply contain the multiple words but not the intended syntax. Will end up.

JP-A-9-265476 Corley, S.M. Corley, M .; , Keller, F,. Crocker, M.M. , And Trewin, S .; , “Finding Syntactic Structure in Unlimited Corpora: The Gsearch Corpus Query System, Vol., Computers and the Humanities, Spring, 200, Netherlands. 81-94 Resnik, P.M. and Elkiss, A.M. "The Linguist's Search Engine: An Overview" the ACL Interactive Poster and Demonstration Sessions, (USA), Association for Computational 200. 33-36

  On the other hand, systems such as Gsearch (Non-Patent Document 1) and Linguist's Search Engine (LSE) (Non-Patent Document 2) have been proposed as corpus search systems using syntax structure information. In these systems, a phrase structure pattern that is information on a part of speech and a phrase structure type constituting the phrase structure described later, that is, from a plurality of words set in a search condition or obtained by analysis The corpus is searched in consideration of the coincidence of the phrase structure, which is a structure indicating a group of word strings, and the phrase structure in the sentence constituting the corpus attached to the corpus. In Gsearch, the user enters phrase structure patterns and grammar into the system. The system parses sentences in the corpus using the input grammar and presents sentences having a given phrase structure pattern as search results. In LSE, a user first inputs an example of a sentence to be searched. The system analyzes the input example sentence by statistical syntax analysis and presents the analysis result to the user. The user edits the parsing result and creates a structural query. Finally, the system returns a sentence having a phrase structure that matches the query as a search result. In these systems, corpus search using syntactic information can be realized. However, since it is necessary to input a predetermined pattern or input an example sentence for the search, it is said that a simple and intuitive search like a keyword-based search system is realized. I want. Moreover, in these systems, the dependency relationship which is the modification between the words in the query and the corpus and the modified relationship is not considered.

  The present invention has been made against the background of the above circumstances, and the object of the present invention is to search from a plurality of example sentences in accumulated language materials without requiring a search condition by a special expression. An example sentence search method for searching for example sentences syntactically including words included in conditions, an example sentence search program executable by a computer, a recording medium storing the example sentence search program, and an example sentence search apparatus are provided.

  In order to achieve such an object, the gist of the method invention according to claim 1 is a dependency which is information on a plurality of example sentences in the accumulated language material and dependency relations between words constituting the example sentence. An example sentence search method for searching example sentences corresponding to a search condition from structure information, wherein (a) a search condition for setting a search condition based on a plurality of words included in a sentence to be searched and the order of the words A setting step; (b) a dependency structure pattern generation step for generating a dependency structure pattern expressing a dependency structure of a plurality of words; and (c) the plurality of example sentences of the plurality of example sentences by the dependency structure pattern generation step. For each example sentence, a sentence selection step of selecting, as a condition corresponding to the search condition, a structure in which a dependency structure between all words included in the search condition can be generated with a single dependency structure pattern; Characterized in that it.

  In this way, the search condition is set based on a plurality of words included in the sentence to be searched and the order of the words, and an attempt is made to generate a dependency structure pattern expressing the dependency structure of the plurality of words. Of the plurality of example sentences, for each of the plurality of example sentences, the one that can generate the dependency structure between all the words included in the search condition with one dependency structure pattern is selected as the one that satisfies the search condition. Therefore, the search can be performed syntactically.

  Further, according to the invention according to claim 2, preferably, a plurality of example sentences in the accumulated language material, dependency structure information that is information about a dependency relationship between words constituting the example sentence, and the example sentence The example sentence retrieval method retrieves an example sentence corresponding to a retrieval condition from the part of speech of the word constituting the word, wherein (d) the retrieval condition setting step selects the part of speech of the plurality of words in the sentence to be retrieved. (E) The dependency structure pattern generation step also considers the part-of-speech coincidence of the words in the example sentence, in addition to the plurality of words or in place of the plurality of words It is characterized by being. In this way, the part-of-speech matching is also taken into account in the example sentence search, so that more accurate example sentence search is possible.

  The gist of the invention according to claim 3 is an example sentence search program for causing a computer to execute the method invention according to claim 1 or 2.

  The gist of the invention according to claim 4 is a recording medium storing an example sentence search program for causing a computer to execute the method invention according to claim 1 or 2.

  Further, the gist of the invention according to claim 5 is that a search condition is obtained from a plurality of example sentences in the accumulated language material and dependency structure information which is information about a dependency relation between words constituting the example sentence. (A) search condition setting means for setting search conditions based on a plurality of words included in a sentence to be searched and the order of the words; and (b) Dependency structure pattern generation means for generating a dependency structure pattern expressing the dependency structure of a plurality of words; and (c) the dependency structure pattern generation means for each of the example sentences of the plurality of example sentences. Sentence selection means for selecting, as a condition that satisfies the search condition, a structure in which a dependency structure between all words included in the search condition can be generated with a single dependency structure pattern. In this way, the search condition is set based on a plurality of words included in the sentence to be searched and the order of the words, and an attempt is made to generate a dependency structure pattern expressing the dependency structure of the plurality of words. Of the plurality of example sentences, for each of the plurality of example sentences, the one that can generate the dependency structure between all the words included in the search condition with one dependency structure pattern is selected as the one that satisfies the search condition. Therefore, the search can be performed syntactically.

  Further, according to the invention of claim 6, preferably, a plurality of example sentences in the accumulated language material, dependency structure information that is information about a dependency relationship between words constituting the example sentence, and the example sentence The example sentence search device searches for an example sentence corresponding to a search condition from the part of speech of a word constituting the word, and (d) the search condition setting means determines the part of speech of a plurality of words in the sentence to be searched. And (e) the dependency structure pattern generating means also considers part-of-speech coincidence of the words in the example sentence. It is characterized by being. In this way, the part-of-speech matching is also taken into account in the example sentence search, so that more accurate example sentence search is possible.

  DESCRIPTION OF EXEMPLARY EMBODIMENTS Hereinafter, preferred embodiments of the invention will be described in detail with reference to the drawings.

  FIG. 1 shows an example sentence search apparatus 10 mainly composed of a so-called computer according to an embodiment of the present invention. This example sentence search device 10 is a computer equipped with a well-known computer body 12 having a CPU, ROM, RAM, HDD, input / output interface, an input operation device 14 such as a keyboard, an image display device 16 such as a CRT, and the like. Yes, the CPU executes a program stored in advance in response to the operation of the input operation device 14 and displays the calculation result on the screen of the image display device 16.

  The input operation device 14 is composed of a keyboard, a mouse, or the like, and is used by the user to input a plurality of word strings that are set and input as search conditions in the search condition setting means 30 described later. The output device 16 is an image display device, for example, and appropriately displays example sentences stored as search results in the search result storage means 36 described later.

  FIG. 3 schematically shows a functional block diagram showing the main part of the control function obtained by enabling the example sentence search apparatus 10 to read and execute the example sentence search program stored in the medium 20 in advance. Show.

The search condition setting means 30 arranges the word string and its part of speech input by the input operation device 14 in a predetermined format, and passes them to the dependency structure pattern generation means 34 described later as a search condition. Here, only a part of speech of a word may be given to a part of a word input as a search condition without specifying the word. That is, the search condition q set by the search condition setting means 30 is:
q = (q1, q2,..., qm)
Here, q1, q2,..., Qm indicate a set of m words and their parts of speech, respectively. When only the part of speech is specified without specifying a word, data indicating that is written in the word portion.

The language material storage means 32 corresponds to a storage device such as a hard disk in which language material, a so-called corpus is stored, in which a plurality of example sentences are stored. Here, in each of the plurality of example sentences, the dependency relationship between words constituting the example sentence is analyzed in advance, and is accumulated together with the example sentence as dependency structure information. Also, the part of speech of the words constituting the example sentence is analyzed in advance and accumulated together with the example sentence. Examples of the above examples include, for example, Marcus, MP and Santorini, B. and Marcinkiewicz, M. Building a Large Annotated Corpus of English: the Penn Treebank, (Computational Linguistics, Vol. 19, No. 2, pp. 310-330, 1993), and the dependency structure information includes, for example, Collins, M., Head-Driven Statistical Models for Natural Language Parsing, Ph.D Dissertation. , University of Pennsylvania, 1999, the result of analyzing the dependency between words constituting each sentence in the corpus according to the proposed method. In this manner, the language material C stored in the language material storage means 32 stores a plurality of example sentences s and corresponding dependency structure information D. That is, when p example sentences are accumulated in the language material C,
C = (s1, D1, s2, D2,..., Sp, Dp)
It is written like this. Here, the example sentence s is composed of n words,
s = (w1, w2, ..., wn)
Where w1,..., Wn are a set of a word and its part of speech.

  FIG. 3 shows an example of an example sentence s included in the language material C, an example sentence s, dependency structure information D, and a part-of-speech set w of words constituting the example sentence. As shown in FIG. 3, for one example sentence, dependency relationships between a plurality of words constituting the example sentence are indicated by arrows as dependency structures. For convenience, a number starting from 1 is added to each word constituting the example sentence from the beginning of the sentence. At this time, when one of the dependency structures is such that, for example, the i-th word from the left depends on the j-th word from the left, this number is used to indicate i → j. In this way, the dependency structure information D represented by the arrows in FIG. 3 is 1 → 2, 3 → 2, 4 → 2, 5 → 6, 6 → 4, 7 → 6, 8 → 9, 9 →. 7 is expressed.

  The dependency structure pattern generation unit 34 sets the search condition set in the search condition setting unit 30 based on each of the plurality of example sentences stored in the language material storage unit 32 and the dependency structure information corresponding to each example sentence. For a plurality of constituent words, an attempt is made to determine whether or not the dependency relation between the plurality of words can be finally described by one dependency structure pattern by a dependency structure pattern described later.

  The dependency structure pattern refers to a plurality of words q1,..., Qm included in the search condition q set in the search condition setting means 30, and each example sentence s1,. Each of the sps indicates what kind of dependency is used, and is expressed as d = (h, L, R). Here, h is an integer value indicating the position of the word, that is, the number of the word from the head (left) in each example sentence, and L and R are lists of dependency structure patterns. If there is a dependency structure pattern written in L, it means that the main word depends on h from the left. If there is a dependency structure pattern written in R, the main word depends on h from the right. Means. At this time, the dependency structure patterns can be described in a superimposed manner in L and R, respectively, so that the superimposed dependency relationships of a plurality of words can be described. Further, when there is no word depending on the left or right with respect to h, L or R describes ε indicating that.

  The dependency structure pattern generation unit 34 includes an initialization operation unit, a combination operation unit, and a complement operation unit that perform the following three operations: initialization operation, combination operation, and complement operation. Attempt to generate a structure pattern. The initialization operation means prepares an initial dependency structure pattern corresponding to each word and part-of-speech pair as preparation for describing a dependency relationship between a plurality of words and part-of-speech pairs included in the search condition in each example sentence in the language material. Generated for each sentence (initialization operation). Specifically, for an example sentence s in the language material C, whether there is a match between the word and part-of-speech pairs qi (1 ≦ i ≦ m) included in the search condition q. As a result, if it matches the set wj (1 ≦ j ≦ n) of the word in the example sentence s and its part of speech, (j, ε, ε) is generated as an initial dependency structure pattern for qi. This is performed for a set qi of all words included in the search condition q and their part of speech. As a result, if the initial dependency structure pattern can be generated for the combination qi of all the words and the part of speech, the example sentence s includes at least the combination of the word and the part of speech included in the search condition q. A determination is made, and then a join operation and a complement operation are attempted. On the other hand, when the initial dependency structure pattern cannot be generated for the combination qi of all the words and their parts of speech, the example sentence s is all the combinations qi of the words included in the search condition q and the parts of speech. Therefore, it is determined that the example sentence does not match the search condition.

  When there are two dependency structure patterns and their main words have a dependency relationship, the combination operation means combines the two dependency structure patterns into one dependency structure pattern (a combination operation). FIG. 4 shows the state of this operation. In FIG. 4, a symbol 50 represented by a triangle represents a dependency structure pattern. Specifically, as dependency structure patterns for qi,..., Qj and qj + 1,..., Qk, which are part of the search conditions, d = (h, L, R) and d ′ = (h ′, L ′, respectively. , R ′) exist, and the rightmost branch of the dependent structure pattern d is traced as much as possible, and the position of the main word at the point where the destination is lost can be the leftmost branch of the structural pattern d ′. In the case where it follows to the left and is located to the left of the position of the main word where the destination is lost (FIG. 4 (a)), the relationship between these main words h and h 'is as follows. When the relationship is dependent, that is, when h → h ′ and R ′ = ε, these two dependency structure patterns are combined, and qi,. As a structural pattern for qk, d ″ = ( ', DL', to generate the R ') (Figure 4 (b)). Further, when h ′ is dependent on h, that is, h ′ → h, d ″ = (h, L, Rd ′) is generated as a structural pattern for qi,. (FIG. 4C). Here, the reason that R ′ = ε is required as a condition for performing the joining operation is to prevent the same dependency structure pattern from being generated repeatedly. By repeating this combining operation, a plurality of dependency structure patterns having dependency relationships are sequentially combined, and finally described by one dependency structure pattern.

  As described above, the initial dependency structure pattern for each pair of each word and its part of speech in the search condition q is sequentially combined with other dependency structure patterns by the combining operation, so that one dependency is finally obtained. When it is described as a structure pattern, it means that all words included in the search condition q and their parts of speech are included in the example sentence in the language material C in a form having a dependency. Yes. Therefore, when all initial dependency structure patterns are finally described as one dependency structure pattern, the sentence matches the search condition.

  Subsequently, the complementary operation means will be described. For example, let us consider a case where two sets of a word and its part of speech are used as search conditions and a sentence that does not have a direct dependency relationship between the two words is to be searched. In such a case, even if two initial dependency structure patterns can be created for a certain example sentence in the language material, since they do not have a direct dependency relationship, the above-described combining operation can be performed. They cannot be described by one dependency structure pattern. However, if the main words of these two dependency structure patterns depend on a word that is included in the example sentence but is not included in the search condition, generation of a dependency structure pattern with that word as the main word is performed. In some cases, a joining operation may be possible. It is the complementary operation means that performs such an operation. FIG. 5 shows the state of this complementing operation. Specifically, there is a dependency structure pattern d for qi,..., Qj that is a part of the search condition, and the main word is h. At this time, when h ′ in which the main character h of the dependency structure pattern d depends is present, that is, when h → h ′, h <h ′, that is, the word corresponding to h in the example sentence s is h ′. D * = (h ′ *, d, ε) is generated as a dependency structure pattern for qi,..., Qj (FIG. 5A). If h> h ′, that is, if the word corresponding to h in the example sentence s is to the right of the word corresponding to h ′, then d * = (h ′ *, ε) as the dependency structure pattern for qi,. , D) is generated (FIG. 5B). At this time, the subscript * indicates that the main word h 'is introduced by the complement operation. In this way, even if there is no direct dependency relationship between words in the search condition, the initial dependency structure can be obtained by performing the above combining operation using the dependency structure pattern generated by the complement operation. It can be expected that one dependency structure pattern can be finally generated from the pattern.

  However, even if a complement operation is performed, if there is no dependency between h ′, which is the main word of the dependency structure pattern generated by the complement operation, and the main word of another dependency structure pattern, the completion is performed. Even if the operation is performed once, the combining operation cannot be performed thereafter.

  On the other hand, if this complementing operation can be repeated indefinitely, it is possible to perform a combining operation on two words that indirectly depend through a plurality of words. In this way, when one dependency structure pattern is generated by a join operation that has been made possible through a plurality of complementary operations, even if one dependency structure pattern is finally generated, it is included in the search condition q. Even if a set of all words and their parts of speech are included in the example sentence in the language material C, they may be included in a form having a dependency relationship different from the dependency relationship intended in the search condition q. And this possibility becomes so high that many complementation operations are performed.

  Therefore, limiting the number of times of performing this complementary operation is performed. For example, only the maximum value may be given in advance, and the dependent structure pattern generation unit 34 may automatically perform a complementing operation within the range of the limitation while automatically performing a combining operation.

  FIG. 6 is a flowchart showing the main part of the control operation of the example sentence search apparatus 10. Hereinafter, the operation of the example sentence search apparatus 10 will be described with reference to this flowchart.

  In the search condition setting means 30 and the step corresponding to the search condition setting affirmation (hereinafter, “step” is omitted) SA1, a plurality of words serving as search conditions are input by the input operation device 14 or the like, and these are input as described above. The search condition q is a style. In the present embodiment, for example, a case is considered in which the search condition q input by the input operation device 14 or the like is “it (pronoun), is (be verb), for (preposition), to (preposition)”. This means that the language material C in the language material storage means 32 is searched for an example sentence included in the sentence in a state where the combination of these four words and the part of speech has a dependency.

  In SA2, the dependency structure pattern generation routine shown in FIG. 7 or FIG. 9 is executed. Here, FIG. 7 is a dependency structure pattern generation routine when the dependency structure pattern generation unit 34 performs only the initialization operation step and the combination operation step described above. FIG. 9 shows the dependency structure pattern generation unit 34 with the initialization operation step. This is a dependency structure pattern generation routine when a complementary operation process is performed in addition to the coupling operation process. First, an example in which the dependency structure pattern generation routine of FIG. 7 is employed will be described. In SB1 in FIG. 7, one example sentence s is extracted from a plurality of example sentences accumulated as the language material C in the storage device corresponding to the language material accumulation means 32. In addition, the dependency structure information of the example sentence and the information on the part of speech of the words constituting the example sentence, which are stored and accumulated together, are also extracted. For example, a sentence s “It is important for us to have technology” is extracted together with the dependency structure information D. This example sentence, dependency structure information, and information about the part of speech are shown in FIG.

  Subsequent SB2 to SB6 correspond to the dependency structure pattern generation unit 34. In SB2, it is determined whether the above-described initialization operation is possible. That is, it is determined whether or not all the combinations of the words constituting the search condition and the part of speech are included in the extracted example sentence. If the determination at SB2 is affirmed, an initialization operation is performed at SB3 corresponding to the initialization operation step. If the determination at SB2 is negative, the extracted example sentence has a dependency structure pattern. Since it cannot be generated, it is determined that the search condition is not satisfied, and the dependency structure pattern generation routine is terminated. In the present embodiment, since the set of four words included in the search condition q and its part of speech are all included in the sentence s, the determination of SB2 is affirmed and the process proceeds to SB3.

In the initialization operation of SB3, initial dependency structure patterns are generated for all pairs of words constituting the search condition and their parts of speech. In the present embodiment, among the words included in the search condition q, “it (pronoun)” matches “It (pronoun)” that is the first word from the left constituting the sentence s. As an initial dependency structure pattern corresponding to this,
(1, ε, ε) (1)
Is generated. Similarly, initial dependency structure patterns (2, ε, ε) (2) for “is (be verb)”, “for (preposition)”, and “to (preposition)” in the search condition q, respectively. )
(4, ε, ε) (3)
(6, ε, ε) (4)
Is generated. At this time, when matching a word and its part of speech included in the search condition q with a word and its part of speech included in the sentence s, the change of the word, for example, the change of the verb by the third person singular or the tense. Considering the change of the verb by singular and the change of the noun by singular and plural, these differences are recognized as the same word.

  In SB4, it is determined whether or not a join operation is possible for the dependency structure pattern. That is, each main word of the existing dependency structure pattern is compared with the dependency structure information of the sentence s, and it is determined whether there is a pair of two main words having a dependency relationship. If it is determined in SB4 that there is a set of main words in a dependency relationship, the process moves to SB5 to combine the dependency structure patterns for the two main words in the dependency relationship. If there are multiple pairs of dependent headings, the join operation is performed from the dependency on which the main word corresponding to the word at the end of the dependency, that is, the word that does not depend on other words depends. Execute. On the other hand, if it is determined that there is no dependent main word, the process proceeds to SB6 on the assumption that all possible join operations have been completed.

  In this embodiment, referring to the dependency structure information D for the main letters 1, 2, 4, 6 of the four initial dependency structure patterns generated in SB3, three dependencies 1 → 2, 4 → 2, 6 → 4 You can see that there is a relationship. Here, among these three dependency relationships, 1 and 6 corresponding to the dependency source in the dependency relationship of 1 → 2 and 6 → 4 are not dependent on other dependency relationships, but 4 → 2 Is the dependency destination of the dependency relationship of 6 → 4, the operation of combining the dependency relationships of 1 → 2 and 6 → 4 is performed before the operation of combining the dependency relationship of 4 → 2. . In this case, any of the join operations corresponding to the dependency relationship of 1 → 2 and the dependency relationship of 6 → 4 may be performed first, but for example, it corresponds to the dependency relationship having the dependency source on the left side of the sentence s. It is sufficient to determine that the joining operation to be performed is performed first. As described above, in SB4, the initial dependent structure pattern corresponding to the dependency relationship of 1 → 2, that is, the initial dependent structure pattern having 1 and 2 as main characters can be combined, and the process proceeds to SB5.

In SB5 corresponding to the joining operation step, the two dependency structure patterns determined to perform the joining operation in SB4 are joined. In the present embodiment, the initial dependency structure pattern having 1 as the main character described in the above (1) and the initial dependency structure pattern having 2 as the main character described in the above (2) are combined, and the dependency structure pattern (2, (1, ε, ε), ε) (5)
Is generated.

  Subsequently, returning to SB4, it is determined whether there is a dependency structure pattern that can be combined again. In this embodiment, as a result of the combination of the initial dependency patterns (1) and (2) in SB5, the initial dependency patterns (3) and (4) and the dependency structure pattern (5) exist. That is, since the main words are 4, 6, and 2, there is a 6 → 4, 4 → 2 dependency based on the dependency structure information D in the sentence s, but as described above, the dependency is 4 → 2. The dependency structure pattern combining operation corresponding to the dependency relationship 6 → 4 is performed first. Therefore, the process proceeds to SB5 on the assumption that the initial dependency structure pattern corresponding to the dependency relationship 6 → 4, that is, the initial dependency structure pattern having 6 and 4 as main characters can be combined.

In SB5, the joining operation is performed in the same manner as in the previous case. That is, the initial dependency structure pattern described in (3) having 4 as a main character and the initial dependency pattern having 6 as a main character described in (4) are combined to form a dependency structure pattern (4, ε, (6, ε). , Ε)) (6)
Is generated.

  Then, the process returns to SB4 again to determine whether there is a dependency structure pattern that can be combined. At this stage, there are two dependency structure patterns described in (5) and (6), and their heads are 2 and 4. Here, according to the dependency structure information D of the sentence s, since there is a dependency relationship of 4 → 2, it is assumed that these two dependency structure patterns can be combined, and the process proceeds to SB5.

In SB5, the joining operation is performed in the same manner as in the previous case. That is, the dependency structure pattern described in (5) having 2 as the main character and the dependency pattern described in (6) having 4 as the main character are combined, and the dependency structure pattern (2, (1, ε, ε), (4, ε, (6, ε, ε))) (7)
Is generated.

  Returning to SB4, it is determined whether there is a dependency structure pattern that can be combined again. At this stage, only one dependency structure pattern described in (7) remains, and no further join operation can be performed. Therefore, the determination of SB4 is denied and the process proceeds to SB6.

  In SB6, it is determined whether or not the dependency structure pattern for the search condition q has been generated as a result of the join operation in SB4 to SB5. Specifically, the determination is made based on whether or not one dependency structure pattern is generated from the plurality of initial dependency structure patterns by the combining operation. If this determination is affirmed, the sentence s satisfies the search condition q, and the process proceeds to SB7. On the other hand, when this determination is denied, the sentence s does not satisfy the search condition q, and the dependency structure pattern generation routine is terminated. In this embodiment, since the initial dependency structure pattern generated as (1) to (4) is generated as one dependency structure pattern described in (7) as a result of the join operation, this determination is made. Is processed, and the process proceeds to SB7.

  In the SB 7 corresponding to the sentence selection means 36 and the sentence selection step, the sentence s for which the determination in SB 6 is affirmed satisfies the search condition q, and the sentence s is stored in the search result storage means 38.

  Returning to FIG. 6, in SA3, it is determined whether the dependency structure pattern generation routine of SA2 has been executed for all sentences in the language material C. If this determination is negative, the process returns to SA2. On the other hand, if this determination is affirmed, the process proceeds to SA4. Thereby, the generation of the dependency structure pattern is attempted for all sentences in the language material C.

  In SA4, the sentence stored in the search result storage means 38 as a sentence that matches the search condition q is output through the output device 16.

By operating the example sentence search device 10 in this way, not only a combination of a word and a part of speech included in the search condition q is included, but a sentence in which these words have a dependency in the search result is set as a search result. Can do. For example, let us consider a case where another sentence s ′ “It is clear where support for the proposal will be broadcast to a series of challenges.” Is extracted in SB1. FIG. 8 shows the dependency relationship between words constituting the sentence and the part of speech of the word. In this case, the determination of SB2 is affirmed because the set of four words and parts of speech of the search condition q are all included in the sentence s ′. Therefore, an initialization operation is performed in SB3,
(1, ε, ε) (8)
(2, ε, ε) (9)
(6, ε, ε) (10)
(13, ε, ε) (11)
The four initial dependency structure patterns are generated. In the subsequent SB4, when comparing the main structure and the dependency structure information D of the sentence s ′, it can be seen that there is a dependency structure of 1 → 2, so that the initial dependency structure patterns of (8) and (9) are combined in SB5. ,
(2, (1, ε, ε), ε) (12)
Is generated.

  Subsequently, returning to SA4 again, it is determined whether there are other dependency structure patterns that can be combined. At this time, the main words 6, 13, and 2 of (10), (11), and (12) are dependent. Therefore, it is determined that no more join operations can be performed. Accordingly, the process moves to SB6, where it is determined whether or not the dependency structure pattern corresponding to the search condition has been generated. At this time, there are three dependency structure patterns (10), (11), and (12). It cannot be described with two dependency structure patterns. Accordingly, the determination at SB6 is denied, and the dependency structure pattern generation routine is terminated without the sentence s' being included in the search result. That is, if all the words included in the search condition q are merely included and these words are present in a sentence without dependency, the sentence is not included in the search results. .

  Subsequently, another embodiment will be described. In the following description, portions common to the embodiments are denoted by the same reference numerals and description thereof is omitted.

  FIG. 9 is a flowchart showing another operation of the dependency structure pattern generation routine in FIG. 6, and is used instead of the flowchart in FIG. The flowchart of FIG. 7 is different from the flowchart of FIG. 7 in that the dependency structure pattern generation routine performs a complement operation in addition to the initialization operation and the join operation. As described above, when performing the complement operation, it is necessary to set in advance an upper limit of the number of times the operator performs the complement operation. In this embodiment, the upper limit is set, for example, twice.

  In SA1 corresponding to the search condition setting means 30 and the search condition setting step, a plurality of words as search conditions are input by the input operation device 14 or the like, and this is set as the search condition q in the above-described manner. In the present embodiment, for example, a case is considered where the search condition q ′ input by the input operation device 14 or the like is “combines (verb), and (conjunction)”. This means that the language material C in the language material storage means 32 is searched for an example sentence that includes the pair of these two words and parts of speech in a sentence having a dependency relationship.

  In the subsequent SA2, the flowchart of FIG. 9 is executed as a dependency structure pattern generation routine. SC1 in FIG. 9 corresponds to the language material accumulating means 32 as in SB1 described above, and one example sentence s ″ is extracted from a plurality of example sentences accumulated as the language material C. Also, the dependency structure information of the example sentence and the information about the part of speech of the words constituting the example sentence, which are stored and accumulated together, are extracted. For example, a sentence s ″ “Ora combines music and druma.” Is extracted together with the dependency structure information D. This example sentence, dependency structure information, and information on part of speech are shown in FIG.

  Subsequent SC2 to SC9 correspond to the dependency structure pattern generation unit 34. In SC2, as in SB2, it is determined whether an initialization operation is possible. If the determination in SC2 is affirmed, an initialization operation is executed in SC3. If the determination in SC2 is negative, it is determined that the sentence does not satisfy the search condition, and the dependency structure pattern generation routine is terminated. In this embodiment, since the two words and part-of-speech pairs included in the search condition q ′ are both included in the sentence s ″, the determination in SC2 is affirmed and the process proceeds to SC3.

In SC3 corresponding to the initialization operation process, the initialization operation is performed as in SB3. That is, the initial dependency structure pattern (2, ε, ε) (13) for each of the words “combines” and “and” included in the search condition q ′.
(4, ε, ε) (14)
Is generated.

  In SC4, as in SB4, it is determined whether there is a plurality of dependency structure patterns that can be combined. If this determination is affirmative, the process proceeds to SC5, and in SC5 corresponding to the coupling operation step, the coupling operation of the dependency structure pattern is performed as in SB5. If this determination is negative, the process proceeds to SC6. In this embodiment, referring to the dependency structure information D of the sentence s ″, there is no dependency of 2 → 4 or 4 → 2. That is, there is no direct dependency between 2 and 4 which are the main words of the initial dependency pattern. Therefore, the determination of SC4 is denied and the process proceeds to SC6.

  In SC6, whether or not the dependency structure pattern for the search condition q 'has been generated is determined based on whether or not one dependency structure pattern is generated from the plurality of initial dependency structure patterns by the combining operation. If this determination is affirmed, the sentence s "is assumed to satisfy the search condition q ', and the process proceeds to SC10. On the other hand, if this determination is negative, the process proceeds to the subsequent SC7. In this embodiment, since there are two dependency structure patterns described in (13) and (14) at this time, the determination in SC6 is denied and the process moves to SC7.

  In SC7, it is determined whether the number of complementary operations performed so far is smaller than the limit value of the number of operations. If this determination is affirmed, the process proceeds to SC8 because it is possible to perform a further complementary operation. On the other hand, when this determination is negative, no further complementing operation can be performed on the sentence s ″, and the dependency structure pattern generation routine is terminated. In the present embodiment, the complementary operation is not yet performed at this point, and the upper limit of the complementary operation is set to two, so the determination in SA7 is affirmed and the process proceeds to SC8.

  In SC8, it is determined whether a complementary operation is possible in the dependency structure pattern. This is because, based on the dependency structure information D of the sentence s ″, the main part of the dependency structure pattern indirectly takes a dependency relationship through one word of the sentence s ″ that is not the main part of the dependency structure pattern. Judgment is made based on whether or not the word is present in the sentence s ″. Specifically, in this embodiment, the main characters of the dependency structure pattern are 2 and 4, but there is neither 2 → 4 nor 4 → 2 in the dependency structure information D of the sentence s ″. However, since the dependency structure information D has a dependency relationship of 4 → 3, it is determined that a complementing operation is possible. As described above, in this embodiment, the determination of SC8 is affirmed and the process proceeds to SC9.

In SC9 corresponding to the complementary operation step, the above-described complementary operation is performed based on the dependency that is the basis for determining in SC8 that complementation is possible. In this embodiment, when the complementary operation is performed on the initial dependency structure pattern (14) based on the dependency relationship 4 → 3, the dependency structure pattern (3 *, ε, (4, ε, ε)). (15)
Is generated.

  Subsequently, the process returns to SC4 again, and it is determined whether or not the dependency operation can be performed on the dependency structure pattern. In this embodiment, there are dependency structure patterns (13) and (15), and the main characters are 2 and 3. Here, since 3 → 2 is included in the dependency structure information D of the sentence s ″, the determination of SC4 is affirmed that these dependency structure patterns can be combined.

In SC5, two dependency structure patterns determined to be connectable in SC4 are combined by a combining operation. In the present embodiment, the dependency structure pattern described in (13) having 2 as the main character and the dependency structure pattern described in (15) having 3 as the main character are combined, and the dependency structure pattern (2, ε, ( 3 *, ε, (4, ε, ε))) (16)
Is generated.

  Thereafter, the process returns to SC4 again, and it is determined whether there is a dependency structure pattern that can be further combined. At this stage, since only one dependency structure pattern described in (16) remains, it is determined that SC4 cannot be further combined, so the determination in SC4 is denied and the process proceeds to SC6.

  In SC6, whether or not the dependency structure pattern for the search condition q 'can be generated is determined again depending on whether or not one dependency structure pattern is generated from the plurality of initial dependency structure patterns by the combining operation. In this embodiment, at this point, one dependency structure pattern described in (16) is generated from the two initial dependency structure patterns described in (13) and (14) by the complement operation and the join operation. Therefore, this determination is affirmed, and the sentence s ″ is transferred to the SC 10 as satisfying the search condition q ′.

  The SC 10 corresponding to the sentence selection unit 36 stores the sentence s ″ in the search result storage unit 38, assuming that the sentence s ″ for which the determination in SC6 is affirmed satisfies the search condition q ′.

  Subsequently, the process proceeds to SC7, and whether or not a supplement operation can be performed is determined by the number of complements already performed and the size of the preset upper limit value. In the present embodiment, the number of complementary operations that have already been performed is one, while the upper limit number of complementary operations is set to two, so this determination is affirmed and the process proceeds to SC8.

  In SC8, as in the previous SC8, it is determined whether or not the complementary operation is possible in the dependency structure pattern. If this determination is affirmed, the process proceeds to SC9 and the complementary operation is performed again. On the other hand, if this determination is negative, no further complementing operation can be performed, and this routine is terminated. In the present embodiment, the main character of the dependency structure pattern is 2, but in the dependency structure information D of the sentence s ″, there is no word on which 2 depends, so the main character h ′ * that is the target of the complement operation. Does not exist and cannot be complemented. Therefore, the determination in SC8 is denied, and this routine is terminated on the assumption that no further complement operation can be performed.

  Returning to FIG. 6, in SA3, it is determined whether the dependency structure pattern generation routine of SA2 has been executed for all sentences in the language material C. If this determination is negative, the process returns to SA2. On the other hand, if this determination is affirmed, the process proceeds to SA4. Thereby, the generation of the dependency structure pattern is attempted for all sentences in the language material C.

  In SA4, the sentence stored in the search result storage means 38 as a sentence that matches the search condition q 'is output through the output device 16.

  Tables 1 and 2 show the accuracy of the search results for the example sentence search apparatus 10 of the present embodiment and the example sentence search apparatus according to a simple method for taking out a sentence including words included in the search condition q, which is a conventional technique. It compares the recall and their harmonic mean values. Here, as the language material C in this comparison, the Penn Treebank is used, and the dependency structure information of the sentence in the language material is the above-mentioned Collins, M., Head-Driven Statistical Models for Natural Language Parsing, The results of analysis according to the method proposed in Ph.D Dissertation, University of Pennsylvania, 1999 were used.

Table 1 calculates the accuracy, recall, and harmonic average of the search results when the search condition is “it (pronoun), is (be verb), for (preposition), to (preposition)”. Is a comparison. Where accuracy, recall and their harmonic averages are respectively
Accuracy = Number of correct answers detected / Number of detection results Recall rate = Number of correct answers detected / Number of true correct answers Harmonic average = (Number of detected correct answers x 2) / (Number of detection results + True Number of correct answers)
Is expressed as a percentage and is usually used as an index representing the accuracy of the search result of the search device. In particular, evaluation is performed using a harmonic average (also referred to as “F value”). Note that the case where the upper limit of the complement operation is set to 0 corresponds to the case where the flowchart of FIG. 7 is used as the dependency structure pattern generation routine.

  According to Table 1, even when the upper limit of the complementing operation is any of 0 to 3 times, a better F value is obtained than the example sentence search device according to the conventional method, and a highly accurate search is performed. It is confirmed that

  Table 2 compares the search results when the search conditions are “combines (verb), and (conjunction)” in the same manner as in Table 1. Also in this case, a better F value is obtained regardless of the upper limit of the supplementary operation than the conventional weekly sentence example sentence retrieval apparatus, and it is confirmed that the retrieval is performed with high accuracy.

  In this way, the search condition q set in the search condition setting means 30 and the search condition setting step SA1 is set on the basis of a plurality of words included in the sentence to be searched and the order of the words. An attempt is made to generate a dependency structure pattern d representing the dependency structure of a plurality of words by the pattern generation means 34 and the dependency structure pattern generation steps SB2 to SB6 or SC2 to SC9, and each of the plurality of example sentences among the plurality of example sentences. On the other hand, the one that can generate the dependency structure between all the words included in the search condition with one dependency structure pattern is selected by the sentence selection means 36 and the sentence selection step SB7 or SC10 as corresponding to the search condition q. Therefore, preferably, the dependency relationship between a plurality of example sentences in the language material C accumulated in advance and the words constituting the example sentence is set. And a dependency structure information D is information you are, syntactically can search for example sentences.

  Further, the language material storage means 32 analyzes in advance the part of speech of each word constituting the plurality of example sentences for each of the plurality of stored example sentences, and each of the plurality of example sentences and the part of speech of the words constituting the example sentence. The search condition setting means 30 and the search condition setting step SA1 set the part of speech of a plurality of words in the sentence to be searched as the search conditions. Furthermore, for some of the plurality of words, only the part of speech is given without specifying the word, the dependency structure pattern generation means 34 and the dependency structure pattern generation steps SB2 to SB6 or SC2 to SC9. Is also considered in terms of part-of-speech consistency in the example sentence search if it also considers the part-of-speech consistency of the words in the example sentence Since it is also taken into consideration, it is more accurate from the dependency structure information D, which is information about the dependency relationships between the plurality of example sentences in the language material C accumulated in advance and the words constituting the example sentences, and the part of speech of the words. Search for simple example sentences.

  As mentioned above, although the Example of this invention was described in detail based on drawing, this invention is applied also in another aspect.

  For example, in this embodiment, a word and its part of speech are given as a search condition, but a part of the word may not be required and only the part of speech may be designated. When only the part of speech is given as a part of the search condition, a word with a part of speech that is part of the search condition is present in the example sentence in the initialization operation unit in the dependency structure pattern generation unit 34 described above. In some cases, a search can be performed by generating an initial dependency structure pattern and performing subsequent operations in the same manner. In this way, it is possible to perform a search in which a part of the search condition is ambiguous by specifying only a part of speech match without specifying a word as a part of the search condition. If there are many example sentences extracted as search results in spite of having dependency structure information not intended by the operator, in addition to the search conditions in the search, only the part of speech is not specified. By adding a search condition to be specified and searching again, it is possible to search based on dependency relationships between words based on only part of speech without specifying a word, and narrow down the search results to only example sentences having a specific syntax structure. Can do. As a result, a desired search result can be obtained.

  Conversely, the search condition may be made up of only words without giving a part of speech. In this case, in the initialization operation means in the dependency structure pattern generation means 34 described above, if a word included in the search condition is included in the example sentence, the initialization operation is performed without requiring the matching of the part of speech as a requirement. You can search by doing the same. At this time, the linguistic material C stored in the linguistic material accumulating unit 32 includes information about the part of speech of each word constituting the plurality of sentences included in the linguistic material. The information may not be included.

  In performing the above-described complementing operation, the operator sets an upper limit of the number of complementing operations in advance, and the dependent structure pattern generation unit 34 appropriately performs the complementing operation within the range. The dependency structure pattern generation means 34 may determine the upper limit, or the example sentence search device 10 is executed under the condition of the upper limit once determined by the operator, and the upper limit value is appropriately set according to the result. It is also possible to increase or decrease.

  In the present embodiment, the language material storage means 32 is arranged inside the computer 12 as the example sentence search device 10, but is not limited to this. For example, the language material storage means 32 may be another place provided at another location via a network. It may be arranged in a computer. The input operation device 14 and the output device 16 are also those attached to the computer 12 as the example sentence search device 10, but the input operation device 14 and the output device 16 are not limited to this, and input operations of other computers connected via a network are used. A device or an output device may be used.

  In the present embodiment, the example sentence search device 10 searches for example sentences for English, but is not limited to this, and any language that can describe the dependency relationship between words as in the dependency structure information described above. It can be applied to other languages.

It is a figure which shows the outline of a structure of the example sentence search apparatus by the Example of this invention. It is a functional block diagram showing the outline | summary of the principal part of the control function of the example sentence search apparatus by the Example of this invention. It is a figure showing the example sentence accumulate | stored in a language material storage means, the dependency of the word which comprises the example sentence, and the part of speech of a word. It is a figure showing the outline | summary of joining operation. It is a figure showing the outline | summary of complement operation. It is a flowchart showing the action | operation of the example sentence search apparatus of this invention. 6 is a flowchart showing a dependency structure pattern generation routine in FIG. 5. It is a figure showing another example sentence accumulated in the language material accumulation means, the dependency of the words constituting the example sentence, and the part of speech of the word. It is a flowchart showing another dependence structure pattern generation routine used instead of the flowchart of FIG. It is a figure showing another example sentence accumulated in the language material accumulation means, the dependency of the words constituting the example sentence, and the part of speech of the word.

Explanation of symbols

10: Example sentence search device (computer)
20: Medium 30: Search condition setting means 34: Dependent structure pattern generating means 36: Sentence selecting means SA1: Search condition setting process SB2 to SB6, SC2 to S9: Dependent structure pattern generating process SB7, SC10: Sentence selecting process

Claims (6)

An example sentence search method for searching for an example sentence corresponding to a search condition from a plurality of example sentences in an accumulated language material and dependency structure information which is information about a dependency relation between words constituting the example sentence,
A search condition setting step for setting a search condition based on a plurality of words included in a sentence to be searched and the order of the words;
A dependency structure pattern generation step for generating a dependency structure pattern expressing a dependency structure of a plurality of words;
In the dependency structure pattern generation step, among the plurality of example sentences, the dependency structure between all the words included in the search condition can be generated with one dependency structure pattern for each of the plurality of example sentences. A sentence selection step of selecting a sentence that satisfies the search condition. Example sentences corresponding to a search condition from a plurality of example sentences in the accumulated language material, dependency structure information that is information about dependency relations between words constituting the example sentences, and parts of speech of the words constituting the example sentences An example sentence search method for searching for
In the search condition setting step, the part of speech of a plurality of words in the sentence to be searched is set as the search condition in addition to or in place of the plurality of words.
The example sentence search method according to claim 1, wherein the dependency structure pattern generation step also considers the coincidence of parts of speech of words in the example sentence.   An example sentence search program for causing a computer to execute the method according to claim 1.   A computer-readable recording medium recording an example sentence search program for causing a computer to execute the method according to claim 1. An example sentence search device that searches an example sentence corresponding to a search condition from a plurality of example sentences in accumulated language material and dependency structure information that is information about a dependency relation between words constituting the example sentence,
Search condition setting means for setting a search condition based on a plurality of words included in a sentence to be searched and the order of the words;
Dependency structure pattern generation means for generating a dependency structure pattern expressing the dependency structure of a plurality of words;
Of the plurality of example sentences, the dependency structure pattern generating unit can generate the dependency structure between all the words included in the search condition in one dependency structure pattern for each of the plurality of example sentences. An example sentence search device comprising: sentence selection means for selecting a sentence that satisfies a search condition. Example sentences corresponding to a search condition from a plurality of example sentences in the accumulated language material, dependency structure information that is information about dependency relations between words constituting the example sentences, and parts of speech of the words constituting the example sentences An example sentence search device for searching for
The search condition setting means sets the part of speech of a plurality of words in the sentence to be searched as the search condition in addition to or in place of the plurality of words.
6. The example sentence search apparatus according to claim 5, wherein the dependency structure pattern generation means also considers the coincidence of parts of speech of words in the example sentence.

Images