A Corpus Search System Utilizing Lexical Dependency Structure
Yoshihide Kato∗ , Shigeki Matsubara† , Yasuyoshi Inagaki‡∗Graduate School of International Development, Nagoya University†Information Technology Center, Nagoya University
Furo-cho, Chikusa-ku, Nagoya, 464-8601 Japan‡
Faculty of Information Science and Technology, Aichi Prefectural University
1522-3 Ibaragabasama, Kumabari, Nagakute-cho, Aichi-gun, 480-1198 Japanyosihide@gsid.nagoya-u.ac.jp
Abstract
This paper presents a corpus search system utilizing lexical dependency structure. The user’s query consists of a sequence of keywords.
For a given query, the system automatically generates the dependency structure patterns which consist of keywords in the query, andreturns the sentences whose dependency structures match the generated patterns. The dependency structure patterns are generated byusing two operations: combining and interpolation, which utilize dependency structures in the searched corpus. The operations enable
the system to generate only the dependency structure patterns that occur in the corpus. The system achieves simple and intuitive corpus
search and it is enough linguistically sophisticated to utilize structural information.

1. Introduction
Large text corpora increasingly become important resources for linguistic research, development of natural language processing systems, language teaching, etc. Corpus
search systems are necessary to utilize text corpora effectively.
Several corpus search systems have been presented. Most
systems provide keyword-based search functionality. The
search is simple and intuitive, but not enough linguisticallysophisticated to utilize structural information.
On the other hand, (Corley et al., 2001) and (Resnik andElkiss, 2005) have presented corpus search systems utilizing syntactic structure, Gsearch and Linguist’s Search Engine (LSE), respectively. These systems can search corpora by using phrase structure patterns. In the Gsearch,
the user gives a phrase structure pattern and a grammar tothe system. The system constructs parse trees of the sentences in the corpus by using the given grammar, and returns the sentences whose parse trees match the given pattern. In the LSE, the user first gives an example of sentences which he/she needs. The system parses the exampleby using a statistical parser and returns the parsing result.
The user edits the resulting parse tree to specify a structuralquery. The system finally returns the sentences whose parsetrees match the structural query. The Gsearch and LSE cansearch corpora by utilizing syntactic information. However,they do not achieve simple search like keyword-based systems.
This paper presents a corpus search system which automatically generates structural queries from keyword-basedqueries. The system searches corpora based on lexical dependency information. The user’s query is a sequence ofkeywords. For a given query, it generates dependency structure patterns by using two operations: combining and interpolation. The user need neither to build a grammar like theGsearch nor to edit structural query like the LSE, becauseof the automatic pattern generation. The system achieves
simple and intuitive corpus search and it is enough to linguistically sophisticated to utilize structural information.

2. Corpus Search based on Dependency
Structure
This section presents a corpus search system based on dependency structure.
We assume that corpus sentences are annotated with dependency structures. The user’s query consists of a sequence ofkeywords (words or POSs). For a given query, the systemtries to generate dependency structure patterns and returns
the sentences whose dependency structures match one of
the generated patterns.
2.1. An Algorithm of Generating Dependency
Structure Patterns
This section proposes an algorithm of generating dependency structure patterns. The inputs are as follows:
query: q1 · · · qm (q1 , . . . , qm are keywords)
sentence: s = w1 · · · wn (w1 . . . , wn are pairs of wordsand POSs)
dependency structure (a set of dependencies): D
where D is a set of dependencies between words in s. If wi
depends on wj , the pair of the positions (i, j) is a elementof D. We write i → j for (i, j).
We define the dependency structure pattern as a 3-tuple d =(h, L, R), where h is a word position and L and R are listsof dependency structure patterns. h is called the head ofd. The dependency structure patterns d represents that theheads of dependency structure patterns in L depend on hfrom left. Similarly for R, from right.
Our proposed algorithm generates dependency structure
patterns by using the following two operations: combining
and interpolation.
combining: Let d = (h, L, R) and d0 = (h0 , L0 , R0 )be dependency structure patterns for qi · · · qj andqj+1 · · · qk , respectively. If h → h0 and R0 = ε, thengenerate a dependency structure pattern (h0 , d · L0 , R0 )(see Fig 1a)). If h0 → h, then generate a dependency
structure pattern (h, L, R · d0 ) (see Fig 1b)).

d=(h, L, R)

...

h'...

a) hh'h...

...

RL→h'...

input: query q1 · · · qm ,sentence w1 · · · wn ,dependency structure Dd'=(h', L', R')h...

→hb) h'

...

...

L'

L

hh'

...

R...

...

R'L'

R

L

initialization:for i = 1 to mfor each j s.t. wj = qi dopush (j, ε, ε) to D[i − 1, i, 0];

R'L'

Figure 1: Combininga) h<h'h'b) h>h'h'h...

Lh...

...

RL...

R

Figure 2: Interpolationinterpolation: Let d be a dependency structure pattern forqi · · · qj whose head is h. For h0 such that h → h0 , if
h < h0 , then generate a dependency structure pattern(h0∗ , d, ε) (see Fig. 2a)). If h > h0 , then generate a dependency structure pattern (h0∗ , ε, d) (see Fig. 2b)). A
symbol ∗ means that h0 is introduced by interpolation.
By applying the combining operation to the given query,all dependency structure patterns that directly connect keywords in the query can be generated. The generated patterns are guaranteed to match the dependency structure D,
so the system returns the sentences for which some patterns
are generated.
In some cases, the user may not intend that some keywords
in the query directly depend on the other keywords. To
process such queries robustly, we introduce the interpolation operation. This operation can generate the dependency
structure patterns which include words not occurring in thequery.
To avoid useless application of the operation, we introduce a cost defined as the number of occurrence of * inthe dependency structure pattern. The algorithm does not
generate the dependency structure patterns whose costs are
greater than a threshold.
Figure 3 illustrates the algorithm of generating dependency
structure patterns. θ is the threshold of cost. D[i, j, c] isused for recording the dependency structure patterns withcost c for qi+1 · · · qj . rm(d) and lm(d0 ) are the rightmost
word position in d and the leftmost word position in d0 , respectively. These positions are used for checking the orderof keywords in dependency structures patterns generated.

for cost = 0 to θcombining:for k = 2 to m
for j = k − 1 down to 1
for i = j − 1 down to 0
for c = 0 to costfor each d = (h, L, R) ∈ D[i, j, c],d0 = (h0 , L0 , R0 ) ∈ D[j, k, cost − c]s.t. rm(d) < lm(d0 ) do
if h → h0 ∈ D ∧ R0 = ε thenpush (h0 , dL0 , R0 ) to D[i, k, cost];
if h0 → h thenpush (h, L, Rd0 ) to D[i, k, cost];
interpolation:for j = 1 to m
for i = j − 1 down to 0
if i 6= 0 ∨ j 6= q thenfor each d = (h, L, R) ∈ D[i, j, cost]for h0 s.t. h → h0 ∈ D
if h < h0 thenpush (h0∗ , d, ε) to D[i, j, cost + 1];
else
push (h0∗ , ε, d) to D[i, j, cost + 1];
return D[0, m, 0] ∪ · · · ∪ D[0, m, cost];

Figure 3: An algorithm of generating dependency structure
patterns

Itisimportantforustohave

such

12

3

45678technology
9Figure 4: Dependencies for “It is important for us to havesuch technology”

2.1.1. An example of combining operation
Let us consider an example of generating dependency structure patterns for the following query:
it is for to(1)

and the following sentence:
It is important for us to have such technology.

(2)

Assume that the dependencies are as illustrated in Figure
4.
The first keyword “it” matches the first word in sentence(2), so the following dependency structure pattern is generated:(1, ε, ε)(3)

Table 1: Precision and recall for a query “it is for to.”Opera combines music and drama
1234 5threshold θ0123baseline

Figure 5: Dependencies for “Opera combines music anddrama”

Similarly, the following dependency structure patterns are
generated for keywords “is”, “for” and “to”, respectively:

precision
100.0% (17/17)
90.5% (19/21)
70.0% (21/30)
60.0% (21/35)
27.3% (21/77)

recall
81.0% (17/21)
90.5% (19/21)
100.0% (21/21)
100.0% (21/21)
100.0% (21/21)

Since 3 → 2, the algorithm combines (12) and (14) to generate the dependency structure pattern:(2, ε, ε)(4)(2, ε, (3∗ , ε, (4, ε, ε)))(4, ε, ε)(5)(6, ε, ε)(6)This example demonstrates that the interpolation operation
allows the generation of the dependency structure pattern inwhich some keywords indirectly depend on the other keyword.

For the heads of dependency structure patterns (3) and (4),the dependency 1 → 2 holds. Therefore, the following
dependency structure pattern is generated:(2, (1, ε, ε), ε)(7)

Similarly, the following dependency structure pattern isgenerated for “for to”:(4, ε, (6, ε, ε))(8)Furthermore, since 4 → 2, dependency structure patterns(7) and (8) are combined and the following dependency
structure pattern is generated:(2, (1, ε, ε), (4, ε, (6, ε, ε)))(9)This means that “it is for to” occur in sentence (2) in theform of dependency structure pattern (9).
On the other hand, for sentences in which some keywords
do not depend directly on the others (for instance, “It isclear whether support for the proposal will be broad enoughto a serious challenge”), the algorithm generates no dependency structure pattern.
2.1.2. An example of interpolation operation
Let us consider another example of dependency structure
pattern generation. The query and the sentence are as follows:
combines and(10)Opera combines music and drama(11)

The dependencies are as illustrated in Figure 5.
For “combines” and “and”, the following dependency
structure patterns are generated:(2, ε, ε)(12)(4, ε, ε)(13)

Since neither 2 → 4 nor 4 → 2, no dependency structure
pattern is generated by the combining operation.
By applying the interpolation operation to dependency
structure pattern (13), the following pattern is generated:(3∗ , ε, (4, ε, ε))

(14)

(15)

3. Implementation and Evaluation
The system is implemented in CMUCL 1 . The system provides a simple KWIC display of the result. The returned
sentences are classified according to the dependency structure patterns matched. Figure 6 shows a screen shot of thesystem.
To evaluate the performance of our proposed system, weperformed an experiment. We searched Penn Treebank(Marcus et al., 1993), which is annotated with phrase structures. The phrase structures in the corpus are converted todependency structures by using the method in the literature(Collins, 1999).
We built several queries and assigned relevant sentences toeach query manually. We measured the precision and recallof the search system for the cost threshold of 0 to 3. The
precision and recall are defined as follows:
the number of relevant sentences returned
the number of sentences returned
the number of relevant sentences returned
Recall =the number of relevant sentences
Moreover, we measured the precision of the search which
returns the sentences including all keywords in the query inthe order. The recall of the search is always 100%. We callit the search baseline.
Precision =3.1. The result for a query “it is for to”
Let us consider the result for a query “it is for to.” Theprecision and recall are shown in Table 1. When θ = 0,
the system achieves high precision and recall, and all thedependency structure patterns that the system generated are
the same as the example of Section 2.1.1. The relevant sentences for which the system does not generate the dependency structure pattern with cost 0 have the dependency
structures where “for” depends not on “is” but on a complement. However, these relevant sentences were able to befound by using the interpolation operation.
3.2. The result for a query “combine and”
Let us consider the result of a query “combine and.” Theprecision and recall are shown in Table 2. No relevant sen1

http://www.cons.org/cmucl/

Figure 6: A screen shot of the system

Table 2: Precision and recall for a query “combine and.”threshold θ01
2
3
baselineprecision
0.0% ( 0/ 2)
55.0% (11/20)
42.3% (11/26)
32.4% (11/24)
24.5% (11/45)

recall
0.0% ( 0/11)
100.0% (11/11)
100.0% (11/11)
100.0% (11/11)
100.0% (11/11)

Table 3: Precision and recall for a query “havepreposition mind.”threshold θ0123
baselineprecision
100.0% (10/10)
73.3% (11/15)
61.1% (11/18)
61.1% (11/18)
50.0% (11/22)

recall
90.9% (10/11)
100.0% (11/11)
100.0% (11/11)
100.0% (11/11)
100.0% (11/11)

know the instance of preposition from the result (inthis example, most words matching preposition were“in”).

4.

Conclusion

This paper presents a corpus search system based on dependency structure. The system automatically generates
dependency structure patterns by utilizing corpus annotated with dependency structures so the user needs not
to construct a structural query. The experimental results
demonstrated that the system achieves high precision corpus search.
We would like to evaluate the system performance from theviewpoint of not only the precision and recall but also theusability.
Acknowledgments
This work is partially supported by the Grant-in-Aid forYoung Scientists (B)(No. 17700145) of JSPS.

5. References
tence was found by using the dependency structure patterns
with cost 0. However, all the relevant sentences are foundby using the dependency structure patterns with cost 1. The
result demonstrates that the interpolation operation is necessary for the system to process such queries robustly. The
precision is not good, but we expect that the user can seek
relevant sentences easily because the returned sentences areclassified according to the patterns and relevant sentences
are expected to belong to a few classes. In this example,
the relevant sentences belonged to 2 classes.
3.3. The result for query “have preposition mind”
Let us consider the result for a query “have prepositionmind”. preposition is not a word but a part of speech.
Table 3 shows the precision and recall. The system achieves
high precision and recall for the query. Moreover, we canM. Collins. 1999. Head-Driven Statistical Models for
Natural Language Parsing. Ph.D. thesis, University ofPennsylvania.
S. Corley, M. Corley, F. Keller, M. Crocker, and S. Trewin.
2001. Finding syntactic structure in unparsed corpora:
The gsearch corpus query system. Computers and theHumanities, 35:2:81–94.
M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz.
1993. Building a large annotated corpus of English: thepenn treebank. Computational Linguistics, 19(2):310–330.
P. Resnik and A. Elkiss. 2005. The linguist’s search engine: An overview. In Proceedings of the 43rd ACL
Interacrive Poseter and Demonstration Sessions, pages
33–36.