STRUCTURED SENTENCE RETRIEVAL BASED ON LEXICAL DEPENDENCIES
Shigeki Matsubara* and Yoshihide Kato***Information Technology Center, Nagoya University**Graduate School of International Development, Nagoya University
Furo-cho, Chikusa-ku, 464-8601, Japanmatubara@nagoya-u.jp

ABSTRACTThis paper presents a corpus search system utilizing lexical
dependency structure. The user’s query consists of a sequenceof keywords. For a given query, the system automaticallygenerates the dependency structure patterns which consist ofkeywords in the query, and returns the sentences whose dependency structures match the generated patterns. The dependency structure patterns are generated by using two operations: combining and interpolation, which utilize dependency
structures in the searched corpus. The operations enable thesystem 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 toutilize structural information.

search like keyword-based systems.
This paper presents a corpus search system which automatically generates structural queries from keyword-based queries.
The system searches corpora based on lexical dependency information. The user’s query is a sequence of keywords. Fora given query, it generates dependency structure patterns byusing two operations: combining and interpolation. The userneed neither to build a grammar like the Gsearch nor to edit
structural query like the LSE, because of the automatic patterngeneration. The system achieves simple and intuitive corpus
search and it is enough to linguistically sophisticated to utilize
structural information.
2. CORPUS SEARCH BASED ON DEPENDENCYSTRUCTURE

1. INTRODUCTION

This section presents a corpus search system based on dependency structure.
Large text corpora increasingly become important resources
We assume that corpus sentences are annotated with defor linguistic research, development of natural language propendency
structures. The user’s query consists of a sequence
cessing systems, language teaching, etc. Corpus search sysof
keywords(words or POSs). For a given query, the systemtems are necessary to utilize text corpora effectively.
tries
togenerate
dependency structure patterns and returns theSeveral corpus search systems have been presented. Mostsentences
whosedependency structures match one of the gensystems provide keyword-based search functionality. The searcheratedpatterns.
is simple and intuitive, but not enough linguistically sophisticated to utilize structural information.
On the other hand, [2] and [4] have presented corpus searchsystems utilizing syntactic structure, Gsearch and Linguist’sSearch Engine (LSE), respectively. These systems can searchcorpora by using phrase structure patterns. In the Gsearch, theuser gives a phrase structure pattern and a grammar to the system. The system constructs parse trees of the sentences in thecorpus by using the given grammar, and returns the sentences
whose parse trees match the given pattern. In the LSE, theuser first gives an example of sentences which he/she needs.
The system parses the example by using a statistical parser
and returns the parsing result. The user edits the resulting
parse tree to specify a structural query. The system finally
returns the sentences whose parse trees match the structuralquery. The Gsearch and LSE can search corpora by utilizing
syntactic information. However, they do not achieve simple

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 words andPOSs)
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 element ofD. We write i → j for (i, j).

d=(h,L,R)d'=(h',...

→a) h...

L...

R'→b) h'h'...

L'hhh'...

R')

...

RL

hL',h'h...

...

L'Lh'...

R

...

L'R

...

R'Fig. 1. Combining

We define the dependency structure pattern as a 3-tupled = (h, L, R), where h is a word position and L and R arelists of dependency structure patterns. h is called the headof d. The dependency structure patterns d represents that theheads of dependency structure patterns in L depend on h fromleft. 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 d = (h , L , R ) be dependency structure patterns for qi · · · qj and qj+1 · · · qk ,respectively. If h → h and R = ε, then generate a dependency structure pattern (h , d · L , R ) (see Fig 1a)).
If h → h, then generate a dependency structure pattern(h, L, R · d ) (see Fig 1b)).
interpolation: Let d be a dependency structure pattern forqi · · · qj whose head is h. For h such that h → h , if
h < h , then generate a dependency structure pattern(h∗ , d, ε) (see Fig. 2a)). If h > h , then generate a dependency structure pattern (h∗ , ε, d) (see Fig. 2b)). A
symbol ∗ means that h 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 thesystem 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 the query.
To avoid useless application of the operation, we introduce a cost defined as the number of occurrence of * in thedependency structure pattern. The algorithm does not generate the dependency structure patterns whose costs are greaterthan a threshold.
Figure 3 illustrates the algorithm of generating dependency
structure patterns. θ is the threshold of cost. D[i, j, c] is used
for recording the dependency structure patterns with cost cfor qi+1 · · · qj . rm(d) and lm(d ) are the rightmost word position in d and the leftmost word position in d , respectively.
These positions are used for checking the order of keywords
in dependency structures patterns generated.
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)
Similarly, the following dependency structure patterns are generated for keywords “is”, “for” and “to”, respectively:(2, ε, ε)(4)(4, ε, ε)(5)(6, ε, ε)(6)

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)a) h<h'b) h>h'h'h'hh

...

...

...

L

R

L...

R

Fig. 2. Interpolation

It is important for us to have such technology
1 234 5 6 789Fig. 4. Dependencies for “It is important for us to have such technology”

Similarly, the following dependency structure pattern is generated 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 the formof dependency structure pattern (9).
On the other hand, for sentences in which some keywords
do not depend directly on the others (for instance, “It is clear
whether support for the proposal will be broad enough to aserious challenge”), the algorithm generates no dependency
structure pattern.

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)

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

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)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 the system.
To evaluate the performance of our proposed system, weperformed an experiment. We searched Penn Treebank [3],which is annotated with phrase structures. The phrase structures in the corpus are converted to dependency structures byusing the method in the literature [1].
We built several queries and assigned relevant sentences
to each query manually. We measured the precision and recallof the search system for the cost threshold of 0 to 3. The
1 http://www.cons.org/cmucl/

Fig. 6. A screen shot of the system

Table 1. Precision and recall for a query “it is for to.”threshold θ01
23baselineprecision
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)

precision and recall are defined as follows:
Precision =the number of relevant sentences returned
the number of sentences returned

the number of relevant sentences returned
the number of relevant sentences
Moreover, we measured the precision of the search which returns the sentences including all keywords in the query in theorder. The recall of the search is always 100%. We call it thesearch baseline.
Recall =3.1. The result for a query “it is for to”
Let us consider the result for a query “it is for to.” The precision and recall are shown in Table 1. When θ = 0, the systemachieves high precision and recall, and all the dependency

Table 2. Precision and recall for a query “combine and.”threshold θ0123baseline

precision
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)

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 be found 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 sentence was found by using the dependency structure patterns
with cost 0. However, all the relevant sentences are found byusing the dependency structure patterns with cost 1. The result demonstrates that the interpolation operation is necessary

Table 3.
Precision and recall for a query “havepreposition mind.”input: query q1 · · · qm ,sentence w1 · · · wn ,dependency structure D
initialization:for i = 1 to mfor each j s.t. wj = qi dopush (j, ε, ε) to D[i − 1, i, 0];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],d = (h , L , R ) ∈ D[j, k, cost − c]s.t. rm(d) < lm(d ) doif h → h ∈ D ∧ R = ε thenpush (h , dL , R ) to D[i, k, cost];
if h → h thenpush (h, L, Rd ) to D[i, k, cost];
interpolation:for j = 1 to m
for i = j − 1 down to 0
if i = 0 ∨ j = q thenfor each d = (h, L, R) ∈ D[i, j, cost]for h s.t. h → h ∈ D
if h < h thenpush (h∗ , d, ε) to D[i, j, cost + 1];
else
push (h∗ , ε, d) to D[i, j, cost + 1];
return D[0, m, 0] ∪ · · · ∪ D[0, m, cost];

Fig. 3. An algorithm of generating dependency structure patterns

threshold θ01
2
3
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)

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 are classified
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 canknow the instance of preposition from the result (in thisexample, 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 withdependency structures so the user needs not to construct astructural query. The experimental results demonstrated thatthe system achieves high precision corpus search.
We would like to evaluate the system performance fromthe viewpoint of not only the precision and recall but also theusability.

Acknowledgments
This work is partially supported by the Grant-in-Aid for Scientific Research (A)(2)(No. 16200001) and for Young Scientists (B)(No. 17700145) of JSPS.

Opera combines music and drama
12345Fig. 5. Dependencies for “Opera combines music and drama”

5. REFERENCES[1] M. Collins: Head-Driven Statistical Models for Natural
Language Parsing, University of Pennsylvania (1999).
[2] S. Corley, M. Corley, F. Keller, M. Crocker and S. Trewin:
Finding Syntactic Structure in Unparsed Corpora: The
Gsearch Corpus Query System, Computers and the Humanities”, vol. 35, no. 2, pp. 81–94 (2001).

[3] M. P. Marcus, B. Santorini and M. A. Marcinkiewicz:
Building a Large Annotated Corpus of English: the Penn
Treebank, Computational Linguistics, vol. 19, no. 2, pp.
310–330 (1993).
[4] P. Resnik and A. Elkiss: The Linguist’s Search Engine:
An Overview, Proceedings of the 43rd ACL Interacrive
Poseter and Demonstration Sessions, pp. 33–36 (2005).