Barbara J. Grosz PROCEDURES FOR INTEGRATING KNOWLEDGE IN A SPEECH UNDERSTANDING SYSTEM
PROCEDURES FOR INTEGRATING KNOWLED GE IN A SPEECH UND ERSTAND ING SYSTEM
B a r b a r a J. Grosz
Donald E Walker and W i l l i a m H P a x t o n, w i t h
Gary G. H e n d r l x, Ann E R o b i n s o n, Jane J. Robinson and J o n a t h a n Slocum SRI I n t e r n a t i o n a l Menlo P a r k, C a l i f o r n i a 94025
T h i s paper d e s c r i b e s t h e p r o c e d u r e s f o r
i n t e g r a t i n g knowledge f r o m d i f f e r e n t s o u r c e s i n t h e SRI speech u n d e r s t a n d i n g s y s t e m. A l a n g u a g e
d e f i n i t i o n system c o o r d i n a t e s—a t t h e p h r a s e l e v e l
—i n f o r m a t i o n f r o m s y n t a x, s e m a n t i c s and d i s c o u r s e
i n t h e c o u r s e o f t h e i n t e r p r e t a t i o n o f a n
u t t e r a n c e. The system e x e c u t i v e uses t h e s e
c o n t e x t u a l c o n s t r a i n t s i n a s s i g n i n g p r i o r i t i e s t o
a l t e r n a t i v e i n t e r p r e t a t i o n s, c o m
b i n i n g t o p-d o w n,
b o t t o m-u p, and b i d i r e
c t i o n a l s t r a t e g i e s a s
r e q u i r e d E x p e r i m e n t a l r e s u l t s t h a t d e m o n s t r a t e
t h e e f f e c t i v e n e s s o f c o n t e x t c h e c k i n g a r e
d i s c u s s
e d.
D e s c r i p t i v e Terms: Language U n d e r s t a n d i n g> Speech
U n d e r s t a n d i n g, System C o n t r o l, Language D e f i n i t i o n,
S y n t a x, S e m a n t i c s, i s c o u r s e
1 INTRODUCTION
For t h e p a s t f i v e y e a r s, SRI I n t e r n a t i o n a l has p a r t i c i p a t e d i n a m a j o r program o f r e s e a r c h o n t h e
a n a l y s i s o f c o n t i n u o u s speech
b y
c o m p u t e r,
s p o n s o r e d by t h e Advanced Research P r o j e c t s Agency
o f t h e D epartment o f D e f e n s e. The g o a l o f t h e
p r o g r a m was t h e d e v e l o p m e n t of a speech
u n d e r s t a n d i n g system c a p a b l e of e n g a g i n g a human
o p e r a t o r i n a n a t u r a l c o n v e r s a t i o n a b o u t t h e
p e r f o r m a n c e o f a p a r t i c u l a r t a s k (see Newell e t
a l ., 1973). A r a t h e r complex s e t o f s p e c i f i c a t i o n s
d e f i n e d t h e p a r a m e t e r s more p r e c i s e l y. The program
c u l m i n a t e
d i n t h
e d e m o n s t r a t i o n o
f a s y s t e m t h a t
d i d meet t h
e t a r g e t s p e c i
f i c a t i o n s (see Reddy e t
a l., 1976; Medress e t a l., 1977),
b u t more
i m p o r t a n t f o r a r t i f i c i a l i n t e l l i g e n c e were
d e v e l o p m e n t s i n t h e v a r i o u s knowledge s o u r c e s—
p a r t i c u l a r l y s y n t a x, s e m a n t i c s, and d i s c o u r s e—a n d
i n t h e system a r c h i t e c t u r e n e c e s s a r y f o r
c o o r
d i n a t i n g them
e
f f i c i e n t l y and e f f e c t i v e l y.
At S R I, we have made s i g n i f i c a n t advances b o t h
i n b u i l d i n g components f o r knowledge s o u r c e s and i n d e v e l o p i n g a' f r a m e w o r k f o r c o o r d i n a t i n g and
c o n t r o l l i n g them. The s y n t a c t i c component i s a
p e r f o r m a n c e grammar; i t d e s c r i b e s t h e s y n t a x o f t h e E n g l i s h used i n s p o n t a n e o u s d i a l o g r a t h e r t h a n t h e
E n g l i s h o f e d i t e d t e x t. The s e m a n t i c s component
uses a p a r t i t i o n e d s e m a n t i c n e t w o r k t o e n a b l e t h e
r e p r e s e n t a t i o n o f m u l t i p l e a l t e r n a t i v e p a r s e s
w i t h o u t d u p l i c a t i o n, t h e a s s o c i a t i o n o f s y n t a c t i c
u n i t s w i t h t h e i r n e t w o r k images and t h e
e s t a b l i s h m e n t o
f scopes f o r h i
g
h e r o r d e r p r e d
i c a t e s (e s p e c i a l l y q u a n t i f i e r s). A d i s c o u r s e component
has been d e v e l o p e d t h a t uses t h e c o n t e x t o f t h e
p r e c e d i n g d i a l o g t o r e s o l v e d e f i n i t e noun p h r a s e
r e f e r e n c e s and expand e l l i p t i c a l u t t e r a n c e s; i t
works o n t h e p a r t i a l k n o w l e d g e a v a i l a b l e when
p a r s i n g a n u t t e r a n c e.
T h i s r e s e a r c h has been f u n d e d under t h e f o l l o w i n g ARPA c o n t r a c t s, a l l a d m i n i s t e r e d t h r o u g h t h e Army Research O f f i c e: D AHC04-72-C-0009, AHC04-75-C-
0006, and D AAG29-76-C-0011. , , ,
N a t u r a l L a n g
Our a p p r o a c h t o c o o r d i n a t i o n and c o n t r o l
s t r e s s e s i n t e g r a t i o n—t h e p r o c e s s o f f o r m i n g a
u n i f i e d system o u t o f t h e c o l l e c t i o n o f components --a n d c o n t r o l—t h e dynamic d i r e c t i o n o f t h e o v e r a l l a c t i v i t y o f t h e system d u r i n g t h e p r o c e s s i n g o f a n i n p u t u t t e r a n c e. Our a p p r o a c h t o i n t e g r a t i o n
p r o v i d e s f o r i n t e r a c t i o n s o f i n f o r m a t i o n f r o m
v a r i o u s s o u r c e s o f knowledge i n a p r o c e d u r a l
r e p r e s e n t a t i o n; a means f o r a d j u s t i n g t h e l a n g u a g e d e f i n i t i o n t o p a r t i c u l a r domains w i t h o u t l o s s o f
g e n e r a l i t y; and a v o i d s commitment t o a p a r t i c u l a r system c o n t r o l s t r a t e g y, t h u s a l l o w i n g f l e x i b i l i t y i n c o m b i n i n g words and p h r a s e s. Our a p p r o a c h t o
c o n t r o l p r o v i
d
e s s p e c i a l t e c h n i q u e s t o a s s i g n
p r i o r i t i e s b y u s i n g c o n t e x t u a l c o n s t r a i n t s; a l l o w s c o m b i n a t i o n s o f t o p-d o w n, b o t t o m u p, and
b i d i r e
c t i o n a l s t r a t e g i e s; o r g a n i z e s an
d c o n s t r u c t s d a t a s t r u c t u r
e s for h y p o t h e s e s i n a manner t h a t
g r e a t l y r e d u c e s d u p l i c a t i o n o f e f f o r t; and i s based o n e x t e n s i v e e x p e r i m e n t a l s t u d i e s t o e v a l u a t e
d e s i g n a l t e r n a t i v e s.
A r e v i e w o f t h e t o t a l p r o j e c t i s beyond t h e scope o f t h i s paper I n s t e a d w e w i l l c o n c e n t r a t e o n i n t e g r a t i o n. A f t e r p r e s e n t i n g a n o v e r v i e w o f
t h e o p e r a t i o n o f t h e system t o p r o v i d e c o n t e x t, w e w i l l p r e s e n t b r i e f d e s c r i p t i o n s o f t h e knowledge
s o u r c e components m e n t i o n e d above t o g e t h e r w i t h
more e x t e n s i v e d i s c u s s i o n s o f a f a c i l i t y f o r
l a n g u a g e d e f i n i t i o n t h a t p r o v i d e s t h e b a s i s f o r
c o o r
d i n a t i n g them and o f t h
e e x e c u t i v e r o u t i n e s
t h a t c o n t r o l them. We c o n c l u d e w i t h a
c o n s i
d
e r a t i o n o
f r e l e v a n t e x p e r i m e n t a l r e s u l t s.
A more c o m p l e t e s t a t e m e n t o f t h i s work i s
c o n t a i n e
d i n o u r f i n a l p r o j
e c t r e p o r t (W a l k e r, 1976). A somewhat expanded d e s c r i p t i o n o
f t h e
l a n g u a g e d e f i n i t i o n system and e x e c u t i v e and t h e
e x p e r i m e n t s c o n d u c t e d t o t e s t them i s p r e s e n t e d i n Paxton (1977; sec a l s o 1976a,b). The d i s c o u r s e component i s t r e a t e d more
f u l l y i n Grosz (1977a;
see a l s o 1977b f o r a d i s c u s s i o n o f the. c o n c e p t o f
f o c u s). F i k e s and H e n d r l x (1977) summarize t h e scheme f o r s e m a n t i c r e p r e s e n t a t i o n and t h e
p r o c e d u r e s f o r d e d u c t i v e r e t r i e v a l used i n t h e system R e f e r e n c e s t o o t h e r p a p e r s a r e i n c l u d e d i n t h e f i n a l p r o j e c t r e p o r t.
The system r e f e r e n c e d i n t h i s paper was
d e v e l o p e d j o i n t l y b y SRI and t h e System D evelopment C o r p o r a t i o n (SD C). SRI p r o v i d e d c a p a b i l i t i e s f o r
s y s t e m c o n t r o l, l a n g u a g e d e f i n i t i o n, s y n t a x,
s e m a n t i c s, and d i s c o u r s e a n a l y s i s. S
D
C p r o v i d e d
c a p a b i l i t i e s f o r s i g n a l p r o c e s s i n g, a c o u s t i c s,
p h o n e t i c s, and p h o n o l o g y, a s w e l l a s s p e c i a l system s o f t w a r e and h a r d w a r e s u p p o r t (see B e r n s t e i n, 1975). The t a s k domain s u p p l i e d d a t a management
c a p a b i l i t i e s f o r q u e r y i n g a f i l e o f i n f o r m a t i o n o n a t t r i b u t e s o f s h i p s f r o m t h e U.S., S o v i e t, and
B r i t i s h f l e e t s.
E a r l y i n 1976, j u s t a f t e r t h e system became
o p e r a t i o n a l, t h e c o m p u t e r f a c i l i t y a t S
D
C was removed and o u r c o l l a b o r a t i v e e f f o r t s s t o p p e d.
A l t h o u g h w e were n o t a b l e t o e x e r c i s e t h e s y s t e m
e x t e n s i v e l y o r r e
f i n e t h e i n t e r f a c e between t h e
u a r e-2: Walker 36
acoustic components and those providing higher
l e v e l language processing, we were able to c o l l e c t data on the performance of the S D C components and have used t h i s information in extensive t e s t s of our components and of the system framework. It is on the basis of these experiments t h a t we report on the SRI developments in speech understanding in t h i s paper
I I T H E O P E R A T I O N
When a speaker records an utterance, it is analyzed a c o u s t i c a l l y and p h o n e t i c a l l y , and the r e s u l t s are stored in a f i l e. When these data are a v a i l a b l e , the executive begins to p r e d i c t words and phrases on the basis of context—guided by the r u l e s f o r phrase formation in the language
d e f i n i t i o n —o r to b u i l d up phrases from words that have been i d e n t i f i e d a c o u s t i c a l l y in the utterance. As each phrase is constructed, relevant semantic and discourse i n f o r m a t i o n is checked, and if a p p r o p r i a t e , a semantic network representation of the phrase is developed. When the performance of a task r e s u l t s in the p r e d i c t i o n of a word at a s p e c i f i e d place in the utterance, a l t e r n a t i v e
phonological forms of t h a t word are mapped onto the acoustic data for t h a t place, and a score i n d i c a t i n g the degree of correspondence is
r e t u r n e d. When an i n t e r p r e t a t i o n for the e n t i r e utterance is complete, relevant s t r u c t u r e s from the semantic model of the domain and from an associated r e l a t i o n a l data base are processed to i d e n t i f y in semantic network form the content of an appropriate response. This response is then generated e i t h e r in t e x t form or through the use of a speech synthesizer.
I l l T H E L A N G U A G E DEFINITION
The input language is a subset of n a t u r a l ,
c o l l o q u i a l English t h a t is s u i t a b l e for c a r r y i n g on a
d i a l o g between a user and th
e system regarding information in the data base. The d e
f i n i t i o n of t h i s language c o n s i s t s of a l e x i c o n containin
g the vocabulary, a set of composition r u l e s f o r
combining words i n t o phrases and smaller phrases i n t o l a r g e r ones, and some g l o b a l declarations g i v i n g i n f o r m a t i o n needed by the d e f i n i t i o n
compiler, which t r a n s l a t e s the language d e f i n i t i o n i n t o an e f f i c i e n t i n t e r n a l r e p r e s e n t a t i o n , and by the executive, which operates on t h a t
r e p r e s e n t a t i o n. The lexicon is separated i n t o
c a t e g o r i e s , such as noun an
d verb, and th
e words in each category are assigned values for various
a t t r i
b u t e s , such as p a r t i
c u l a r grammatical features an
d semantic r
e p r e s e n t a t i o n s. The composition r u l e s are phrase-structure r u l e s augmented by a procedure t h a t is executed whenever the r u l e
constructs a phrase. Information provided by the procedure includes both a t t r i b u t e s of the phrase based on the a t t r i b u t e s of i t s c o n s t i t u e n t s , and f a c t o r s f o r use in judging the a c c e p t a b i l i t y of the phrase. The g l o b a l d e c l a r a t i o n s give such i n f o r m a t i o n a s l i s t s o f a t t r i b u t e s f o r the d i f f e r e n t c a t e g o r i e s. An a t t r i b u t e statement may compute values t h a t specify acoustic p r o p e r t i e s r e l a t e d to the input s i g n a l , s y n t a c t i c p r o p e r t i e s such as mood and number (s i n g u l a r or p l u r a l ), semantic properties such as the semantic network representation of the
N a t u r a l L i n g u a 37
meaning of the phrase, and discourse p r o p e r t i e s f o r anaphora and e l l i p s i s. The values of c o n s t i t u e n t a t t r i b u t e s are used in computing the a t t r i b u t e s of l a r g e r phrases, and the a t t r i b u t e s of complete i n t e r p r e t a t i o n s are used in generating responses.
The f a c t o r statements compute a c c e p t a b i l i t y r a t i n g s for an instance of the phrase. The scores for f a c t o r s are non-Boolean; that i s , they may assume a wide range of values. As a r e s u l t , a proposed instance of a phrase is not necessarily simply accepted or r e j e c t e d ; it may be rated as more or less acceptable depending on a combination of f a c t o r values. Like a t t r i b u t e s , f a c t o r s may be acoustic, s y n t a c t i c , semantic, or discourse
r e l a t e d. Acoustic f a c t o r s r e f l e c t how w e l l the words match the a c t u a l i n p u t ; s y n t a c t i c f a c t o r s deal w i t h t e s t s l i k e number agreement between
various c o n s t i t u e n t s ; semantic f a c t o r s assure t h a t the meaning of the phrase is reasonable; and
discourse f a c t o r s i n d i c a t e whether an e l l i p t i c a l or anaphoric phrase makes sense in the given d i a l o g context. The values of f a c t o r s are included in a composite score for the phrase. The scores of
c o n s t i t u e n t s are combine
d w i t h th
e
f a c t o r scores to produce the scores of l a r
g e r phrases, and the scores of complete i n t e r p r e t a t i o n s are used in s e t t i n g executive p r i o r i t i e s.
The a t t r i b u t e and f a c t o r statements in the procedural parts of the r u l e s contain s p e c i f i c a t i o n s for most of the p o t e n t i a l
i n t e r a c t i o n s among system components. A t t r i b u t e s and f a c t o r s e i t h e r have constant values or have values t h a t depend on a t t r i b u t e s of c o n s t i t u e n t s and g l o b a l i n f o r m a t i o n (such as a model of the
discourse or the r e s u l t s of p r e l i m i n a r y , l o w -l e v e l acoustic processing). By design, the a t t r i b u t e s and f a c t o r s of a phrase are not allowed to depend on the context formed by other phrases t h a t can combine w i t h it to produce l a r g e r s t r u c t u r e s. By g i v i n g up e x p l i c i t context dependency, it becomes easier to share phrases among d i f f e r e n t contexts, which allows the executive to reduce d u p l i c a t i o n of e f f o r t. However, contextual r e s t r i c t i o n s provide h e u r i s t i c information t h a t i n p r a c t i c e i s too
valuable to ignore, so the executive algorithms f o r p r i o r i t y s e t t i n g take them i n t o account by special techniques described below. E s s e n t i a l l y , we have taken the e x p l i c i t context dependencies out of the rules so t h a t phrases can be shared by d i f f e r e n t contexts, and have developed methods in the
executive so that contextual r e s t r i c t i o n s can s t i l l be used in c o n t r o l l i n g the operation of the system.
The form of the r u l e s is designed to avoid commitments to p a r t i c u l a r system c o n t r o l
s t r a t e g i e s. For example, the r u l e procedures can be executed with any subset of c o n s t i t u e n t s , so incomplete phrases can be constructed to provide intermediate r e s u l t s , and it is not necessary to acquire c o n s t i t u e n t s i n a s t r i c t l y l e f t -t o -r i g h t order This f l e x i b i l i t y has made it possible to experiment w i t h a l t e r n a t i v e system c o n t r o l s t r a t e g i e s.
IV SYNTAX
The s y n t a c t i c knowledge in the system is represented both in the phrase s t r u c t u r e p a r t of the language d e f i n i t i o n r u l e s and in the a t t r i b u t e and f a c t o r statements in the procedural p a r t of the G e -2: W a l k e r
r u l e s. Syntax provides computationally inexpensive i n f o r m a t i o n about which words or phrases may combine and how w e l l they go together. In t e s t i n g word or phrase combinations, s y n t a c t i c information alone often can r e j e c t an i n c o r r e c t phrase without r e q u i r i n g c o s t l y semantic and discourse analysis Factors are used for t r a d i t i o n a l s y n t a c t i c t e s t s such as agreement for person or number, but f a c t o r s also are used to reduce the scores of unexpected phrases. For example, WH questions t h a t are negative (e.g. "What submarine doesn't the U.S own?") are not expected to occur. A f a c t o r statement lowers the value for t h i s i n t e r p r e t a t i o n but does not e l i m i n a t e it completely, so that if no b e t t e r hypothesis can be formed to account for the input u t t e r a n c e, t h i s i n t e r p r e t a t i o n w i l l b e accepted. Since the language d e f i n i t i o n system provides the c a p a b i l i t y for evaluating phrases in context by means of non-Boolean f a c t o r s, the grammar can be tuned to p a r t i c u l a r discourse
s i t u a t i o n s and language users simply by a d j u s t i n g
f a c t o r s that enhance or diminish the a c c e p t a b i l i t y o f p a r t i c u l a r i n t e r p r e t a t i o n s. I t i s not necessary to r e w r i t e the language d e f i n i t i o n for each new problem domain
The c o n s t i t u e n t s t r u c t u r e s defined by the composition r u l e s in the system allow WH questions, How Many questions. How+Adiective questions, imperatives and statements; BE and D O verb forms are included. Noun phrases can be of a v a r i e t y of types. We have concentrated on those relevant for the domain having WH determiners (what, which, whose), q u a n t i f i e r s (a l l. any, both, each e i t h e r, every, n e i t h e r no, none, some), p a r t i t i v e expressions (containing "o f") expressions with numbers (from one through the m i l l i o n s) and u n i t s (t o n s, f e e t, k n o t s), and comparisons i n v o l v i n g numbers. There are more than 100 d i f f e r e n t kinds
of basic noun phrases, to which may be added
r e c u r s i v e l y "o f NP" expressions and some classes of p r e p o s i t i o n a l phrases. The l e x i c o n contains over 600 e n t r i e s; regular p l u r a l s, past and past
p a r t i c i p l e forms and other s u f f i x e s are handled by r u l e s.
V SEMANTICS
The system's knowledge about the domain is embodied i n-a p a r t i t i o n e d semantic network. A semantic network consists of a c o l l e c t i o n of nodes and arcs where each node represents an object (a physical o b j e c t, s i t u a t i o n, event, s e t, or the
l i k e) and each arc represents a binary
r e l a t i o n s h i p. The s t r u c t u r e of our network d i f f e r s from that of conventional networks in t h a t nodes and arcs are p a r t i t i o n e d i n t o spaces. These spaces, p l a y i n g in networks a r o l e roughly analogous to t h a t played by parentheses in l o g i c a l n o t a t i o n, group i n f o r m a t i o n i n t o bundles t h a t help to condense and organize the network's knowledge. Network p a r t i t i o n i n g serves a v a r i e t y of purposes
in the speech understanding system: encoding
l o g i c a l connectives and higher-order p r e d i c a t e s,
e s p e c i a l l y q u a n t i
f i e r s; a s s o c i a t i n
g s y n t a c t i c u n i t s w i t
h t h e
i r network images; i n t e r r e l a t i n g new inputs w i t h previous network knowledge while maintaining a d e f i n i t e boundary between the new and the o l d; simultaneously encoding in one network s t r u c t u r e
m u l t i p l e hypotheses concerning a l t e r n a t i v e incorporations of a given c o n s t i t u e n t i n t o l a r g e r phrases; sharing network representations among competing hypotheses; maintaining Intermediate
r e s u l t s during the question-answering process; and d e f i n i n g h i e r a r c h i e s o f l o c a l contexts for
discourse a n a l y s i s.
The network includes an encoding of knowledge about the domain of discourse. This model serves as a foundation on which the s t r u c t u r e s corresponding to new utterances are b u i l t; it is used to assess the f e a s i b i l i t y of combining utterance c o n s t i t u e n t s to form l a r g e r phrases; and it is a source of information f o r answering queries, supplemented by a r e l a t i o n a l data base which can be accessed d i r e c t l y from the network.
Concepts in the domain t h a t can be referenced by i n d i v i d u a l words are so l i s t e d In the l e x i c o n.
As l e x i c a l items are combined i n t o phrases, these network references are passed to semantic composition r o u t i n e s. These r o u t i n e s construct new network s t r u c t u r e s t h a t represent the meanings of the composite phrase, encoding new instances or new combinations of concepts. As phrases are combined i n t o larger phrase u n i t s the composition r o u t i n e s are applied u n t i l an i n t e r p r e t a t i o n for the e n t i r e utterance has been constructed In t h i s process, case r e l a t i o n s provide a basis f o r using s y n t a c t i c i n f o r m a t i o n in c o n s t r u c t i n g semantic
i n t e r p r e t a t i o n s; they also allow r e j e c t i n g unallowable semantic s t r u c t u r e s and blocking
s y n t a c t i c p r e d i c t i o n s f o r words t h a t cannot f i t I n the current c o n t e x t. The i n t e r p r e t a t i o n for the
e n t i r e utterance takes the form o
f a network fragment anchored to concepts in the o r i
g i n a l domain model, but maintained in a separate
p a r t i t i o n c a l l e d a scratch Space
The scoping of q u a n t i f i e r s, contained
i m p l i c i t l y o r e x p l i c i t l y i n the utterance, i s performed in a separate step a f t e r an
i n t e r p r e t a t i o n has been assigned to the t o t a l
i n p u t. Scoping is accomplished by adding new
p a r t i t i o n i n g to the network fragment without changing the topology of the e x i s t i n g s t r u c t u r e.
Once a network s t r u c t u r e encoding a f u l l y
q u a n t i f i e d i n t e r p r e t a t i o n of an Input is formulated, it is passed to a response component. For questions and commands requesting i n f o r m a t i o n, c a l l s to a deduction component are generated to
r e t r i e v e or derive the requested i n f o r m a t i o n from the network encoding of the domain model.
VI
D
ISCOURSE
The discourse component of the speech understanding system r e l a t e s a given utterance (or a p o r t i o n of i t) to the o v e r a l l d i a l o g context and to e n t i t i e s and s t r u c t u r e s in the domain. The procedures we have developed are based on
systematic studies of dialogs between two people performing some a c t i v i t y together. Contextual
i n f l u e n c e s were found to operate on two d i f f e r e n t
l e v e l s in a discourse. The g l o b a l context—the
t o t a l discourse and s i t u a t i o n a l s e t t i n g—p r o v i d e s one set of c o n s t r a i n t s on the i n t e r p r e t a t i o n of an utterance. These c o n s t r a i n t s are used in
i d e n t i f y i n g the r e f e r e n t s of d e f i n i t e noun phrases. The second set of c o n s t r a i n t s is provided by the
See Walker, 1976, and Flkes and Hendrix, 1977,
f o r a d e s c r i p t i o n of the deduction component.
immediate context of c l o s e l y preceding utterances. These c o n s t r a i n t s are used in the i n t e r p r e t a t i o n of e l l i p t i c a l expressions to expand utterance
fragments i n t o complete utterances. For the data base domain of the speech understanding system, the discourse context is l i m i t e d to a l i n e a r h i s t o r y of preceding i n t e r a c t i o n s For complex t a s k-o r i e n t e d dialogs the l i n e a r discourse h i s t o r y can be replaced by a s t r u c t u r e d h i s t o r y r e l a t e d to the
o r g a n i z a t i o n of the task being performed (see
Grosz 1977a r b).
To determine the r e f e r e n t s of d e f i n i t e noun phrases, it is necessary to group those parts of
the g l o b a l knowledge base (t h a t is the knowledge about the domain of discourse) that are in the
focus OF a t t e n t i o n of the d i a l o g p a r t i c i p a n t s. To encode t h i s focus, we have introduced a special
p a r t i t i o n i n g t h a t i s independent o f the l o g i c a l
p a r t i t i o n i n g used to represent semantic
i n f o r m a t i o n. Spaces in the focus p a r t i t i o n i n g are U3ed to group together and h i g h l i g h t those items in the knowledge base t h a t are relevant at a given point in a d i a l o g.
The c e n t r a l process necessary for r e s o l v i n g
d e f i n i t e noun phrases is f i n d i n g a network
s t r u c t u r e t h a t matches the semantic s t r u c t u r e b u i l t for the noun phrase. The matching is performed by the deduction component, which associates nodes and arcs in the network fragment corresponding to the noun phrase w i t h nodes and arcs in the knowledge base. The focus representation is used to
c o n s t r a i n the search require
d by t h i s matching process on th
e basis o
f the discourse context.
The c o n s t i t u e n t s missing from an e l l i p t i c a l utterance are found in the i n t e r p r e t a t i o n of the immediately preceding utterance. The process of
b u i l d i n g an i n t e r p r e t a t i o n for an e l l i p t i
c a l phrase e n t a i l s two steps. F i r s t, the items missing from the current utterance are foun
d in the
i n t e r p r e t a t i o n of the preceding utterance (o r,
e q u l v a l e n t l y, the s l o t t h a t the e l l i p t i c a l phrase
f i l l s i n the precedin
g utterance i s determined) Syntactic i n f o r m a t i o n plays a major r o l e in t
h
i s
i d e n t i f i c a t i o n, because the corresponding elements usually are s t r u c t u r a l u n i t s of the same type. Semantic closeness, determined from the taxonomic hierarchy of the network, also is considered. Second, a complete phrase is b u i l t using the
e l l i p t i c a l phrase and the missing constituents found in the previous utterance. The coordination o
f s y n t a c t i c and semantic i n f o r m a t i o n, achieved through network p a r t i t i o n i n g, is used to minimize the- computation r e q u i r e d.
V I I EXECUTIVE
The executive has three main r e s p o n s i b i l i t i e s: (1) it coordinates the work of the other components of the system by c a l l i n g acoustic processes and applying language d e f i n i t i o n r u l e s; (2) i t assigns p r i o r i t i e s to the various tasks in the system; and
(3) it organizes hypotheses and r e s u l t s so t h a t
i n f o r m a t i o n is shared and d u p l i c a t i o n of e f f o r t is avoided. When a successful i n t e r p r e t a t i o n has been found, the executive invokes the response
f u n c t i o n s, which produce a r e p l y.
The p r i n c i p a l data s t r u c t u r e used by the executive is c a l l e d the parse n e t. It is a network w i t h two types of nodes phrases and p r e d i c t i o n s. Phrases correspond to words or composition r u l e s from the language d e f i n i t i o n; phrases can be complete, containing a l l t h e i r c o n s t i t u e n t s, o r incomplete, w i t h some or a l l of t h e i r c o n s t i t u e n t s missing A p r e d i c t i o n is for a p a r t i c u l a r category of phrase associated w i t h a p a r t i c u l a r l o c a t i o n in the utterance. As the i n t e r p r e t a t i o n of an
utterance progresses, new phrases t h a t have been constructed from e x i s t i n g phrases or from words found in the utterance are added to the parse n e t. At the same t i m e, new p r e d i c t i o n s are made as more information is obtained. Thus, as the
i n t e r p r e t a t i o n process advances, the parse net. which holds intermediate hypotheses and r e s u l t s, grows. A complete r o o t category phrase (t y p i c a l l y, a sentence) w i t h i t s a t t r i b u t e s and f a c t o r s
c o n s t i t u t e s an i n t e r p r e t a t i o n of the utterance
There are two tasks e n t a i l e d in maintaining and evolving t h i s parse n e t: the word task and the p r e d i c t task The r o l e of the word task is to look for a p a r t i c u l a r word in a p a r t i c u l a r l o c a t i o n in the utterance. If the acoustic mapper has not been c a l l e d previously to t e s t f o r t h a t word in t h a t
l o c a t i o n, the word task c a l l s i t. If a word is found successfully in the s p e c i f i e d l o c a t i o n the word is used to b u i l d new phrases.
The r o l e of the p r e d i c t task is to make a
p r e d i c t i o n for a word or phrase t h a t can help complete an incomplete phrase. Whenever a new
c o n s t i t u e n t is i n s e r t e
d i n t o an incomplet
e phrase, any adjacent c o n s t i t u e n t s t h a t had been missing can be p r e d i c t e d. New p r e d i c t i o n s can include
p r e d i c t i o n s for p a r t i c u l a r words, leading to new instances of c a l l s on the word task.
A p r e d i c t i o n serves as an intermediary between two sets of incomplete phrases* consumer phrases that a l l are missing a c o n s t i t u e n t of the predicted category at the predicted l o c a t i o n in the i n p u t, and producer phrases t h a t a l l might supply the missing c o n s t i t u e n t s Note t h a t a phrase can be a consumer for one p r e d i c t i o n and a producer for another. The f u l l set of producer-consumer connections in the parse net makes e x p l i c i t the
d i f f
e r e n t s e n t e n t i a l contexts
f o r each phrase.
This contextual information is used by the
executive in s e t t i n g p r i o r i t i e s and in lookahead.
E s t a b l i s h i n g the p r i o r i t y of a task begins
w i t h determining the score of the phrase i n v o l v e d. The score is computed from the r e s u l t s of the acoustic mapping of any of the words contained in the phrase, from the f a c t o r statements f o r the phrase, and from the scores of the c o n s t i t u e n t s. The score is thus a l o c a l, c o n t e x t-f r e e piece of information about how good the phrase i s. A f t e r the score Is determined, the phrase is given a
r a t i n g t h a t is an estimate of the best score for an i n t e r p r e t a t i o n t h a t can be constructed for a phrase of the r o o t (sentence) category t h a t uses the given phrase. The r a t i n g for a phrase does depend on i t s consumers, t h a t i s, on the other phrases in which
it may be embedded to form a sentence. This r a t i n g is then modified depending on the c o n t r o l s t r a t e g y being used, and the r e s u l t is the p r i o r i t y of the task to be performed for t h a t phrase.
The design of the parse net was i n s p i r e d by Kaplan's (1973) m u l t i-p r o c e s s i n g consumer-producer approach.
N a t u r a l L a n g u a g e-2: w a l k e r
30
B o t h t h e word and t h e p r e d i c t t a s k can work
e i t h e r l e
f t-t o-r i
g
h t t h r o u g h a n
i n p u t o r
b i d i r e
c t i o n a l l y f r o m words s e l e c t e
d a t a r b i t r a r y
p o s i t i o n s w i t h i n a n u t t e r a n c e. The system i s
d e s i g n e d t o a l l o w c o n s t i t u e n t s o f p h r a s e s t o b e added i n any o r d e r, s o e x p e r i m e n t a t i o n w i t h a
v a r i e t y o f c o n t r o l s t r a t e g i e s has been p o s s i b l e. More i m p o r t a n t l y f r o m t h e system c o n t r o l
s t a n d p o i n t, e a c h t a s k does a l i m i t e d amount o f
p r o c e s s i n g and t h e n s t o p s a f t e r s c h e d u l i n g f u r t h e r o p e r a t i o n s f o r l a t e r. The s c h e d u l i n g does n o t
s p e c i f y a p a r t i c u l a r t i m e f o r a f u t u r e o p e r a t i o n
b u t i n s t e a d g i v e s t h e o p e r a t i o n a
c e r t a i n p r i o r i t y. The o p e r a t i o n i s p e r f o r m e
d when i t becomes t o p
p r i o r i t y. T h i s o r g a n i z a t i o n a l l o w s t h e e x e c u t i v e
t o c o n t r o l t h e o v e r a l l a c t i v i t y o f t h e system b y
s e t t i n g t a s k p r i o r i t i e s.
V I I I ENTAL RESULTS
We have e x p e r i m e n t e d w i t h two t e c h n i q u e s f o r
u s i n g t h e consumer c o n t e x t i n s e t t i n g p h r a s e
r a t i n g s I n o n e. c a l l e d t h e m e r g i n g m e t h o d, t h e
r a t i n g w i t h r e s p e c t t o a p a r t i c u l a r consumer i s formed b y a d d i n g t h e p h r a s e s c o r e and t h e consumer r a t i n g. (Whenever p o s s i b l e, r a t i n g s a r e a s s i g n e d
t o p-d o w n i n t h e p a r s e n e t s o t h a t consumer r a t i n g s a r e d i r e c t l y a v a i l a b l e f o r use i n t h i s p r o c e s s ) The p h r a s e r a t i n g i s t h e n t h e maximum r a t i n g w i t h
r e s p e c t t o any o f i t s consumers. T h i s method i s
f a s t, b u t i t l e a v e s t h e r a t i n
g u n a f f e c t e d b y t
h e consumer r e s t r
i c t i o n s t h a t a r e e x p r e s s e d i n r u l e
p r o c e d u r e s r a t h e r t h a n i n s t r u c t u r e d e c l a r a t i o n s.
A p h r a s e may s a t i s f y t h e s t r u c t u r a l r e q u i r e m e n t s o f a consumer C b u t s t i l l be i n c o m p a t i b l e w i t h C because o f c o n s t r a i n t s encoded i n C s f a c t o r
s t a t e m e n t s. F o r e x a m p l e, i f t h e o n l y s e n t e n t i a l
c o n t e x t b e i n g c o n s i
d
e r e d i s "I s i t owned b y —",
t h e s t r u c t u r a l r e q u i r e m e n t s w i l l b e s a t i s f i e d b y
any noun p h r a s e, b u t s e m a n t i c f a c t o r s w i l l r e s t r i c t t h e a l t e r n a t i v e s t o p o s s i b l e o w n e r s.
The second t e c h n i q u e f o r s e t t i n g p h r a s e
r a t i n g s i s c a l l e d t h e c o n t e x t-c h e c k i n g m e t h o d. I t t a k e s i n t o a c c o u n t t h e p r o c e d u r a l i n f o r m a t i o n i n
t h e r u l e s b y e x p l o r i n g p a t h s i n t h e p a r s e n e t and
e x e c u t i n g t h e c o r r e s p o n d i n g p r o c e d u r e s t o g a t h e r
a t t r i
b u t e and f a
c t o r i n f o r m a t i o n. Each p r o
d u c
e r-consumer p a t h
f r o m a p h r a s e P to a r o o t c a t e
g o r y
p h r a s e r e f l e c t s a way o f c o n s t r u c t i n g a n
i n t e r p r e t a t i o n u s i n g P. V a r i o u s p a t h s f r o m P a r e
f o r m e d, and t h e r a t i n
g f o r P i s i t s b e s t r a t i n g
w i t h r e s p e c t t o any o f t h e c o n s t r u c t e d p a t h s.
T o r e d u c e t h e c o s t o f r a t i n g a l t e r n a t i v e s b y
t h e c o n t e x t-c h e c k i n g m e t h o d, a h e u r i s t i c s e a r c h i s made i n t h e p a r s e n e t f o r a n e a r o p t i m a l p a t h
r a t h e r t h a n e x h a u s t i v e l y t r y i n g a l l p o s s i b i l i t i e s. The h e u r i s t i c e x p l o i t s t h e f a c t t h a t, t y p i c a l l y, when a p h r a s e i s b e i n g r a t e d, t h e h i g h e r l e v e l
p h r a s e s t h a t f o r m i t s c o n t e x t have a l r e a d y been
r a t e d. (The p a r s e n e t i s i n i t i a l i z e d s o t h a t a
c o n t e x t o f p r e v i o u s l y r a t e
d p h r a s
e s e x i s t s even when t h e s y s t e m i s d o i n g b o t t o m-u p p r o c e s s i n g.) These p r i o r r a t i n g s p r o v i d e i m p o r t a n t h e u r i s t i c
i n f o r m a t i o n. The o b j e c t i s t o f i n d t h e p a t h g i v i n g t h e b e s t s c o r e, s o t h e p a t h s w i t h t h e h i g h e s t p r i o r r a t i n g a r e e x p l o r e d f i r s t. When a c o m p l e t e p a t h i s f o u n d, one t h a t l e a d s t o a r o o t-c a t e g o r y p h r a s e,
t h e s c o r e f o r t h a t p a t h i s used a s a t h r e s h o l d t o
p r u n e o t h e r p a t h s t h a t have l o w e r e x p e c t e d r a t i n g s.
The c o n t e x t-c h e c k i n g method t a k e s more
c o m p u t a t i o n per r a t i n g a s s i g n m e n t t h a n t h e m e r g i n g metho
d b u t i t p r o d u c
e s b e t t e r p h r a s e r a t i n g s s i n c e i t g a t h e r s more i n
f o r m a t i o n i n f o r m i n
g them. The
e x p e r i m e n t a l r e s u l t s s u p p o r t t h e c o n c l u s i o n t h a t
t h e e x t r a e f f o r t s p e n t i n t h i s method i s
w o r t h w h i l e; I t l e a d s t o b e t t e r system p e r f o r m a n c e
as r e f l e c t e d in b o t h a c c u r a c y and r u n t i m e As a
b a
c k g r o u n
d f o r c o n s i d
e r a t i o n o
f t h e s e r e s u l t s i t
i s n e c e s s a r y t o c o n s i d e r b r i e f l y t h e scope o f t h e
e x p e r i m e n t a l e
f f o r t a s a w h o l e.
The e x p e r i m e n t s t o d e t e r m i n e t h e e f f e c t s o f
v a r i a t i o n s i n c o n t r o l s t r a t e g y f o r o u r speech
u n d e r s t a n d i n g system were c o n d u c t e d u s i n g a
s i m u l a t e d v e r s i o n o f t h e a c o u s t i c p r o c e s s i n g components a s i n d i c a t e d above A l t h o u g h w e l o s t
a c c e s s t o t h e mapper a s a r e s u l t o f t h e r e m o v a l o f
t h e computer f a c i l i t y o n w h i c h t h e t o t a l system was b e i n g i m p l e m e n t e d, t h e r e a r e c o m p e l l i n g r e a s o n s f o r d o i n g s i m u l a t i o n e x p e r i m e n t s. E x t e n s i v e t e s t i n g
w i t h t h e a c t u a l mapper w o u l d have been i m p o s s i b l e
b o t h because o f t h e t i m e r e q u i r e d and because o f
i n c r e a s e d demands o n memory w i t h t h e l a r g e d e l a y s
f o r page swappin
g b y t
h e t
i m e s h a r i n g s y s t e m. I n
a d d i t i o n w e were a
b l e t o s t u d y
c o n t r o l s t r a t e g i e s
t h a t o t h e r w i s e w o u l d have been t o o s l o w f o r t h e mapper
The mapper s i m u l a t i o n r e p r o d u c e s t h e o b s e r v e d mapper p e r f o r m a n c e s t a t i s t i c s f o r t h e f a l s e-a l a r m
r a t e t h e h i t s c o r e s and t h e p a r t i c u l a r f a l s e-
a l a r m words and t h e i r s c o r e s Because o f
i n s u f f i c i e n t d a t a, w e were n o t a b l e t o s i m u l a t e
more complex s t a t i s t i c s such a s t h e c o o c c u r r e n c e o f h i t s and f a l s e a l a r m s o r t h e dependence o f s c o r e s
o n p o s i t i o n w i t h i n t h e u t t e r a n c e. C o n s e q u e n t l y,
t h e e x p e r i m e n t s a r e d e s i g n e d t o emphasize
c o m p a r i s o n s between p e r f o r m a n c e l e v e l s f o r t h e
d i f f
e r e n t d e s i g n a l t e r n a t i v e s and s h o u l d n o t b e
t a k e n a s e s t i m a t e s o f t h e a b s o l u t e v a l u e o f t h e
s y s t e m's p e r f o r m a n c e w i t h a r e a l mapper For t h i s
r e a s o n w e d o n o t c o n s i d e r h e r e t h e e f f e c t i v e n e s s
o f t h e s y s t e m a s a w h o l e, a l t h o u g h t h e r e a r e
o b s e r v a t i o n s t h a t a r e r e l e v a n t f o r a n e v a l u a t i o n o f t h e o v e r a l l r e s u l t s o f t h e ARPA Speech
U n d e r s t a n d i n g Research Program (see t h e s e c t i o n s o n E x p e r i m e n t a l S t u d i e s i n P a x t o n 1977, o r W a l k e r, 1976).
I n t h e main e x p e r i m e n t o f t h e s e r i e s, t h e
p e r f o r m a n c e o f t h e speech u n d e r s t a n d i n g s y s t e m,
w i t h a l e x i c o n of 305 w o r d s, was measured on a s e t
o f 60 t e s t s e n t e n c e s, w h i l e v a r y i n g f o u r m a j o r
c o n t r o l-s t r a t e g y
d
e s i g n c h o i c e s. The s e n t e n c e s
c o v e r e
d a w i d
e r a n g e o
f v o c a b u l a r y and i n c l u d e d
q u e s t i o n s, commands, and e l l i p t i c a l s e n t e n c e s. The 60 s e n t e n c e s r a n g e d i n l e n g t h f r o m 0.8 t o 2.3
s e c o n d s. T h e r e were 10 s e n t e n c e s a t each 0.3
second i n t e r v a l. The s e n t e n c e s a v e r a g e d 5.9 w o r d s
i n l e n g t h, w i t h a maximum o f 9 w o r d s.
I n a d d i t i o n t o s t u d y i n g t h e e f f e c t s o f c o n t e x t c h e c k i n g, w e a l s o examined t h e f o l l o w i n g
a l t e r n a t i v e s:
* To i s l a n d d r i v e or. n o t: go in both
d i r
e c t i o n s from a r b i t r a r y s t a r t i n g points
i n the input versus proceed s t r i c t l y l e f t
to r i g h t from the beginning. Island
d r i v i n g allows i n t
e r p r e t a t i o n s to be b u i l t
up around words t h a t match w e l l anywhere in
the i n p u t.
* T o map a l l o r o n e: t e s t a l l t h e w o r d s a t
Natural Language-2: Walker
40
once at a given l o c a t i o n versus t r y i n g them one at a time and delaying f u r t h e r t e s t i n g when a good match is found. Mapping a l l at once i d e n t i f i e s the best acoustic
candidates and reduces the chances of f o l l o w i n g false paths, but it takes s u b s t a n t i a l l y more time.
* To focus or NOT. assign p r i o r i t i e s for
tasks focusing on selected a l t e r n a t i v e s by i n h i b i t i n g competion or proceed each time w i t h the task w i t h the highest score.
A l l combinations of the four c o n t r o l -s t r a t e g y
v a r i a b l e s were tested on the 60 sentences. This experimental design allows us to compare the 16
combinations of c o n t r o l choices and to evaluate, by analysis of variance the e f f e c t s of the c o n t r o l strategy v a r i a b l e s , t h a t is the change in
performance each produces averaged over a l l the p o s s i b i l i t i e s for the other v a r i a b l e s. The p r o b a b i l i t i e s associated with an e f f e c t are
expressed as p <.01, p< 05, and p<.10, corresponding to the d i f f e r e n t l i k e l i h o o d s that the e f f e c t is the r e s u l t of random v a r i a t i o n.
We w i l l discuss here only the r e s u l t s that show the e f f e c t s of context checking. The most important performance measures for the system are accuracy (the percentage of sentences for which the c o r r e c t sequence of words is found) and runtime (the computation required by the system, including simulated acoustic processing t i m e ). In the r e s t of t h i s s e c t i o n , these variables w i l l be considered in order as the r e s u l t s demonstrate the e f f e c t s of context checking.
F i r s t , however it should be noted that the c o n t r o l strategy a f f e c t s accuracy only i n d i r e c t l y : a l l the s t r a t e g i e s are complete in the sense t h a t they only reorder, and never e l i m i n a t e ,
a l t e r n a t i v e s. If there were no false alarms, a l l the systems would get 100% of the t e s t sentences c o r r e c t , Even w i t h false alarms the s t r a t e g i e s would get an equal percent c o r r e c t , if a l l the possible a l t e r n a t i v e s could be t r i e d before the
system picked an i n t e r p r e t a t i o n. Errors would only occur when false alarms had high enough scores to displace h i t s i n the highest rated i n t e r p r e t a t i o n s. However, in the a c t u a l system, the large number of a l t e r n a t i v e s makes i t impossible t o consider a l l o f them in the space and time a v a i l a b l e. As a r e s u l t , the order in which the a l t e r n a t i v e s are considered can a f f e c t the accuracy, and so can the demands on space and time. Control strategy thus a f f e c t s
accuracy i n d i r e c t l y by reordering a l t e r n a t i v e s and by modifying space and time requirements. To
e x p l a i n the accuracy e
f f e c t s , we must look at these other f a c t o r s.
In t h i s experiment, the storage l i m i t had an important i n f l u e n c e on accuracy. In the 960 t e s t s (60 sentences times 16 systems) 578 (60.2$) were c o r r e c t and 382 (39.8%) were wrong. Of the e r r o r s , 175 (46%) had an i n c o r r e c t i n t e r p r e t a t i o n , while 207 (54$) had no i n t e r p r e t a t i o n at a l l . Since the systems could p o t e n t i a l l y get the c o r r e c t answer, and no time l i m i t was imposed u n t i l at l e a s t one i n t e r p r e t a t i o n had been found a l l of the 207
sentences w i t h no i n t e r p r e t a t i o n were a r e s u l t of running out of storage.
The storage l i m i t used in the t e s t s was based on the number of phrases constructed When the
t o t a l reached 500, the system would stop t r y i n g new
N a t u r a l Langua 41
a l t e r n a t i v e s and if any i n t e r p r e t a t i o n had been found pick the highest rated i n t e r p r e t a t i o n as i t s answer The average number of phrases constructed over a l l systems was 204 nonterminal and 63
t e r m i n a l. The system w i t h the best accuracy, which included context checking, had the lowest average (113 nonterminals and 45 terminals) while the system with the worst accuracy, without context checking had one of the highest averages (260
nonterminals and 68 t e r m i n a l s ). Overall there was a strong negative c o r r e l a t i o n (- 93) between system accuracy and average number of phrases constructed.
For the 16 system c o n f i g u r a t i o n s , the values for accuracy ranged from 46.7$ to 73 3$ Averaged over the systems, the i n c l u s i o n of context checking provided an increase in accuracy of 11.6$, p<.05. Configurations w i t h context checking constructed on the average 240 phrases; those without constructed 294; t h i s d i f f e r e n c e is s i g n i f i c a n t , p< 01.
S u r p r i s i n g l y , context checking also r e s u l t s in a s i g n i f i c a n t reduction in the false terminal
percentage -- from 87 5$ to 86.2$ p<.01. This reduction may be evidence t h a t context checking is g i v i n g lower p r i o r i t y to looking for words adjacent to false alarms than it gives to looking next to h i t s. This change could a f f e c t the false terminal l i k e l i h o o d , since there is always a h i t adjacent to a h i t , while f a l s e alarms often have nothing but other false alarms next to them. In a d d i t i o n to i t s e f f e c t on f a l s e t e r m i n a l s , context checking may also be improving the storage requirements and accuracy by generally improving the p r i o r i t y s e t t i n g , thereby reducing the l i k e l i h o o d of f o l l o w i n g f a l s e paths.
The important r o l e of the storage l i m i t raises the question of whether the accuracy e f f e c t s would have disappeared if more storage had been
a v a i l a
b l e. We believe t h a t the e f f e
c t s woul
d hav
e been smaller but s t i l l important. The e
f f e c t s on the proportion of f a l s e terminal phrases would remain, as would the e f f e c t s on p r i o r i t i e s. A smaller percentage of f a l s e terminals and b e t t e r p r i o r i t i e s w i l l cause the system to f i n d the c o r r e c t i n t e r p r e t a t i o n sooner and. even if the storage l i m i t were r e l a x e d , the l i m i t on runtime would remain to penalize systems that were slow to f i n d the r i
g
h t answer. The e f f e c t s of c o n t r o l strategy choices on accuracy would vanish only if space and runtime l
i m i t a t i o n s were both removed.
The system runtime is another important
performance measure. Here, we w i l l use the phrase t o t a l runtime_ to r e f e r to the simulated acoustic processing, plus the actual processing time (on a D E C P P KA-10) f o r the executive and the semantic components. The executive time is mainly spent
s e t t i n g p r i o r i t i e s and p a r s i n g. The semantics time is used in c o n s t r u c t i n g semantic t r a n s l a t i o n s and in dealing w i t h anaphoric references and e l l i p s i s. The reported t o t a l runtime does not include
acoustic preprocessing or question answering, since n e i t h e r is a f f e c t e d by the experimental v a r i a b l e s. We report r e s u l t s only for t o t a l , executive, and acoustic times; semantic times are not r e p o r t e d , both because they are redundant given the other three measures, and because they are r e l a t i v e l y small in comparison to the o t h e r s.
For the 16 system c o n f i g u r a t i o n s , the values for runtime ranged from 221 to 559 seconds per sentence. Context checking was the only c o n t r o l
r e -2: W a l k e r
v a r i a b l e t o r e d u c e t o t a l r u n t i m e The d i f f e r e n c e
i n seconds p e r s e n t e n c e o f p r o c e s s i n g t i m e (f r o m 421 t o 383) was s i g n i f i c a n t, p<.01. S e p a r a t i n g
e x e c u t i v e and a c o u s t i c r u n t i m e s
f r o m t h e t o t a l
a g a i n showed t h a t i n
b o t h
c a s e s, c o n t e x t checks
d e c r e a s e t h e r u n t i m e. For e x e c u t i v e r u n t i m e, t h e
d i f f
e r e n c e i s
f r o m 117 t o 109 seconds p<,10; f o r
a c o u s t i c r u n t i m e, t h e d i f f e r e n c e i s f r o m 282 t o 254 seconds p< 01.
I t i s n o t e w o r t h y t h a t t h e e x t r a e f f o r t f o r
c o n t e x t c h e c k i n g r e s u l t e
d i n a n
e t d e c r e a s e i n
p r o c e s s i n g t i m e. For example t h e b e s t s y s t e m
c o n f i g u r a t i o n, w h i c h i n c l u
d
e d c o n t e x t c h e c k i n g,
s p e n t a n a v e r a g e o f 6.3 seconds per s e n t e n c e d o i n g e x t r a p r o c e s s i n g for t h e c o n t e x t c h e c k s; h o w e v e r,
t h i s was s t i l l 41 seconds per s e n t e n c e f a s t e r t h a n t h e system c o n f i g u r e d i n t h e same way b u t w i t h o u t
d o i n g t h
e c o n t e x t c h e c k i n g.
I n summary, c o n t e x t c h e c k i n g had u n i f o r m l y
good e f f e c t s. For b o t h a c c u r a c y and r u n t i m e, i t was w o r t h t h e e x t r a e f f o r t t o g e t b e t t e r p r i o r i t y
s e t t i n g. T h i s r e s u l t c l e a r l y depends o n t h e f a c t
t h a t w e p u t a l a r g e amount o f t h e s y s t e m's
knowledge i n t o t h e r u l e p r o c e d u r e s o f t h e l a n g u a g e d e f i n i t i o n r a t h e r t h a n i n t o t h e s t r u c t u r a l
d e c l a r a t i o n s. I t would b e o f c o n s i d e r a b l e i n t e r e s t t o p r o v i d e a d i r e c t e x p e r i m e n t a l t e s t o f t h e
e f f e c t s o f v a r y i n g t h e s t y l e o f t h e l a n g u a g e
d e f i n i t i o n. For example, w h i l e k e e p i n g t h e scope
o f t h e l a n g u a g e c o n s t a n t, a g r e a t e r amount o f t h e
l i n g u i s t i c knowledge c o u l d b e encoded i n t h e r u l e
s t r u c t u r e s r a t h e r t h a n i n t h e r u l e p r o c e d u r e s.
Such a n e x p e r i m e n t would p r o v i d e i n f o r m a t i o n a b o u t t h e p e r f o r m a n c e e f f e c t s o f t h e d i f f e r e n t
r e p r e s e n t a t i o n a l s t y l e s and would i n d i c a t e t h e
e x t e n t t o w h i c h t h e e
f f e c t s o f d e s i
g n f e a t u r e s suc
h a s c o n t e x t-c h e c k
i n g f o r a s s i g n i n g r a t i n g s a r e
d e p e n d e n t o n a p a r t i c u l a r s t y l e o f l a n g u a g e
d e f i n i t i o n. I n d r a w i n g c o n c l u s i o n s f r o m such a n
e x p e r i m e n t, we would be g e n e r a l i z i n g b o t h o v e r t h e p o p u l a t i o n o
f i n p u t s e n t e n c e s and o v e r t h e
p o p u l a t i o n o f l a n g u a g e d e f i n i t i o n s t y l e s.
IX CONCLUSION
The work on speech u n d e r s t a n d i n g at SRI has
p r o d u c e d system c o n t r o l c o n c e p t s and a s e t o f
s y s t e m components t h a t a r e w e l l-s u i t e d f o r f u r t h e r r e s e a r c h o n speech u n d e r s t a n d i n g and a l s o f o r
r e s e a r c h o n n a t u r a l l a n g u a g e u n d e r s t a n d i n g systems w i t h t e x t i n p u t. Under ARPA s u p p o r t we a r e
c o n t i n u i n g t o a p p l y t h e s e p r o
d u c t s o f t h
e speech
u n d e r s t a n d i n g p r o j e c t in a Navy command and c o n t r o l
c o n t e x t t o p r o v i
d
e n a t u r a l l a n g u a g e a c c e s s t o a
d i s t r i b u t
e d d a t a base s t o r e d o n a number o f
d i f f
e r e n t c o m p u t e r s. Under N a t i o n a l S c i e n c e
F o u n d a t i o n s u p p o r t. w e a r e e x p l o r i n g t h e
s i g n i f i c a n c e o f t h e s e p r o d u c t s f o r u n d e r s t a n d i n g
n a t u r a l l a n g u a g e d i a l o g between humans and
c o m p u t e r s f o r t h e a c c o m p l i s h m e n t o f a s t r u c t u r e d
t a s k i n a dynamic s i t u a t i o n. W e b e l i e v e t h a t t h e
e l a b o r a t i o n o
f complex knowledge s o u r c e s and t h e
d e v e l o p m e n t o f s o p h i s t i c a t e d mechanisms f o r
i n t e g r a t i n g and c o n t r o l l i n g them w i l l p r o v e t o have m a j o r i m p l i c a t i o n s f o r f u t u r e work i n b o t h
a r t i f i c i a l i n t e l l i g e n c e and c o m p u t a t i o n a l
l i n g u i s t i c s.
C o n t r a c t No. AAG29-76-C-0012.
REFERENCES
B e r n s t e i n, M o r t o n I. I n t e r a c t i v e Systems Research
F i n a l R e p o r t. TM-5243/004 System D evelopment
C o r p o r a t i o n. Santa Monica C a l i f o r n i a. November
1975.
F i k e s. R i c h a r d E., and H e n d r i x Gary G. A N e t w o r k-
Based Knowledge R e p r e s e n t a t i o n and i t s N a t u r a l
D e d u c t i o n System. P r o c e e d i n g s o f the.F i f t h
I n t e r n a t i o n a l J o i n t C o n f e r e n c e o n A r t i f i c i a l
I n t e l l i g e n c e. Cambridge, M a s s a c h u s e t t s, 22 25
August 1977.
G r o s z. B a r b a r a J. The R e p r e s e n t a t i o n and Use o f
Focus in D i a l o g U n d e r s t a n d i n g. Ph D. T h e s i s
U n i v e r s i t y o f C a l i f o r n i a, B e r k e l e y, C a l i f o r n i a,
1977 (a)
G r o s z, B a r b a r a J. The R e p r e s e n t a t i o n and Use of
Focus i n a System f o r U n d e r s t a n d i n g D i a l o g s.
P r o c e e d i n g s g_￡ t h e F i f t h I n t e r n a t i o n a l J o i n t
C o n f e r e n c e OJI A r t i f i c i a l I n t e l l i g e n c e.
C a m b r i d g e, M a s s a c h u s e t t s, 22 25 August 1977. (b)
K a p l a n Ronald M. A M u l t i-p r o c e s s i n g Approach to N a t u r a l Language. P r o c e e d i n g s N a t i o n a l
Computer C o n f e r e n c e, New Y o r k, New Y o r k, 4-8
June 1973 AFIPS P r e s s, M o n t v a l e, New J e r s e y,
1973. Pp- 435-440.
M e d r e s s, Mark F., e t a l. Speech U n d e r s t a n d i n g S y s t e m s: R e p o r t of a S t e e r i n g C o m m i t t e e. SIGART N e w s l e t t e r. A p r i l 1977, 62, 4-8.
N e w e l l A l l e n, e t a l. Speech U n d e r s t a n d i n g
Systems. N o r t h H o l l a n d P u b l i s h i n g Company,
Amsterdam, 1973.
P a x t o n. W i l l i a m H A Framework for Language U n d e r s t a n d i n g I n COLING 76, P r e p r i n t s o f t h e
6t h I n t e r n a t i o n a l C o n f e r e n c e o n C o m p u t a t i o n a l
L i n g u i s t i c s, O t t a w a, O n t a r i o. Canada, 28 J u n e-?
J u l y 1976. No. 14. (a)
P a x t o n, W i l l i a m H. E x p e r i m e n t s i n Speech
U n d e r s t a n d i n g System C o n t r o l. I n P r o c e e d i n g s o f
t h e F i r s t CSCSI/SCEIO N a t i o n a l C o n f e r e n c e,
V a n c o u v e r. B r i t i s h C o l u m b i a, Canada, 25-27
August 1976. (b)
Paxton W i l l i a m H. A Framework f o r Speech
U n d e r s t a n d i n g. P h.
D
.
D
i s s e r t a t i o n. S t a n f o r d
U n i v e r s i t y, S t a n f o r d, C a l i f o r n i a, 1977.
Reddy, D. R a j. Speech U n d e r s t a n d i n g S y s t e m s: Summary o f R e s u l t s o f t h e F i v e-Y e a r Research
E f f o r t.
D
epartment o f Computer S c i e n c e,
C a r n e g i e-M e l l o n U n i v e r s i t y, P i t t s b u r g h,
P e n n s y l v a n i a, September 1976.
W a l k e r, onald E., (E d.) Speech U n d e r s t a n d i n g R e s e a r c h. F i n a l R e p o r t, P r o j e c t 4762,
A r t i f i c i a l I n t e l l i g e n c e C e n t e r, S t a n f o r d
Research I n s t i t u t e Menlo P a r k, C a l i f o r n i a,
O c t o b e r 1976.
G r a n t No. MCS76-2200H. W a l k e r
设有定义int(精)
第七章指针 选择题 1、设有定义：int n1=0,n2,*p=&n2,*q=&n1;，以下赋值语句中与n2=n1;语句等价的是______ A）*p=*q; B）p=q; C）*p=&n1; D）p=*q; 2、若有定义：int x=0, *p=&x;，则语句printf("%d\n",*p);的输出结果是______ A）随机值B）0 C）x的地址D）p的地址 3、有以下程序 main() { int a=7,b=8,*p,*q,*r; p=&a;q=&b; r=p; p=q;q=r; printf("%d,%d,%d,%d\n",*p,*q,a,b); } 程序运行后的输出结果是______。 A）8,7,8,7 B）7,8,7,8 C）8,7,7,8 D）7,8,8,7 4、若有说明语句：double *p,a;则能通过scanf语句正确给输入项读入数据的程序段是____ A）*p=&a; scanf(“%lf”,p);B)*p=&a; scanf(“%f”,p); C) p=&a; scanf(“%lf”,*p);D)p=&a; scanf(“%lf”,p); 5、若程序中已包含头文件stdio.h，以下选项中，正确运用指针变量的程序段是______。 A）int *i=NULL; B）float *f=NULL; scanf("%d",i); *f=10.5; C）char t='m',*c=&t; D）long *L; *c=&t; L='\0'; 6、若x是整型变量，pb是基类型为整型的指针变量，则正确的赋值表达式是___ ___。 A）pb=&x; B）pb=x; C）*pb=&x; D）*pb=*x 7、若定义：int a=511,*b=&a;, 则printf("%d\n",*b);的输出结果为 A) 无确定值B) a的地址C) 512 D) 511 8、若有说明:int i，j=7，*p=&i;，则与i=j;等价的语句是________ A) I= *P; B) *P=*&J; C) i=&j; D) i=* *p; 9、若有说明：int i,j=7,*p=&i;则与i=j;等价的语句是__ ____。 A）i=*p; B）*p=*&j; C）i=&j; D）i=**p; 10、若有一些定义和语句 #include
C语言期末复习题
第一单元程序设计和Ｃ语言 一、选择题 1．C语言的基本构成单位是： A 。 A. 函数 B. 函数和过程 C. 超文本过程 D. 子程序 2．一个C语言程序总是从 B 开始执行。 A. 主过程 B. 主函数 C. 子程序 D.主程序 3．C语言的程序一行写不下时，可以。 A. 用逗号换行 B. 用分号换行 C. 在任意一空格处换行 D. 用回车符换行 4．以下叙述不正确的是： C 。 A. 在C程序中，语句之间必须要用分号";"分隔 B. 若a是实型变量，C程序中a=10是正确的，因为实型变量中允许存放整型数 C. 在C程序中，无论是整数还是实数都能正确无误地表示 D. 在C程序中，%是只能用于整数运算的运算符 5．以下不正确的C语言标识符是 D 。 A. ABC B. abc C. a_bc D. ab.c 6．下列字符串是标识符的是： A 。 A. _HJ B. 9_student C. long D. LINE 1 7．以下说法中正确的是： C 。 A. C语言程序总是从第一个定义的函数开始执行 B. 在C语言程序中，要调用的函数必须放在main()函数中定义 C. C语言程序总是从main()函数开始执行 D. C语言程序中的main()函数必须放在程序的开始部分 8．不合法的常量是： D 。 A. ...\2? B. "" C. ...3? D. (483) 9．已知各变量的类型说明如下，则以下不符合C语言语法的表达式是： A 。 int k,a,b; unsigned long w=5; double x=1.422; A. x%(-3) B. w+=-2 C. k=(a=2,b=3,a+b) D. a+=a=+(b=4)*(a=3) 10．在C语言中，字符型数据在内存中以 D 形式存放。 A. 原码 B. BCD码 C. 反码 D. ASCII码 11．若有定义：int a=7; float x=2.5; y=4.7; 则表达式x+a%3*(int)(x+y)%2/4的值是： A 。 A. 2.500000 B. 2.750000 C. 3.500000 D. 0.000000 12．设有说明：char w; int x; float y; double z;
C++期末复习题一
C++语言程序设计期末复习题一、单项选择题 1．下列符号中，不可以作为变量名的 是d。 A．list_p_9 B.PA 123 C．ready D.for 2．由C++目标文件连接而成的可执行文件的缺省扩展名为b。 A．cpp B.exe C．obj D.lik 3．在每个C++程序中都必须包含有这 样一个函数，该函数的函数名 为a。 A. main B. MAIN C. name D. functkion 4．设x和y均为bool量，则x&&y 为真的条件是a。 A. 它们均为真 B. 其中一个为 真 C. 它们均为假 D. 其中一个为假 5．下列表达式中正确的是b。 A．(k++)++ B.k---j C．k--/=5 D.(k+ 3)=5 6．执行下面程序段的输出结果 是b。 int x=4,y=-55; if (x>0) if (x>10) cout <<”AA”else cout <<”BB” else if (y<-8) if (y>-20) cout <<”CC”else cout <<”DD”; A. AA B. BB C. CC D. DD 7．下面四个程序段中，输出23个*号的程序段是c。 A. for (int i=1; i<23; i++) cout <<’*’; B. for (int i=23; i>=0; i--) cout <<’*’; C. int i=23; while (i>0) { cout <<’*’; i--; } D. int i=0; while (0<=23) { cout <<’*’; i++; } 8．在下面的一维数组定义中，哪一个有语法错误。c A.int a[ ]={1,2,3} B. int a[10]={0} C. int a[ ] D. int a[5] 9．假定a为一个整型数组名，则元素a[4]的字节地址为 c 。 A. a+4 B. a+8 C. a+16 D. a+32 10．要定义一个int型二维数组a，并使其各元素具有初值： 2 3 0 0 4 0 5 0 0 0 0 0
c语言填空题
1 若x和n均是int型变量,且x和n的初值均为5,则计算表达式 x+=n++ 后x的值为 _10_,n的值为6. 2 设i,j,k均为int型变量,则执行完下面的for循环后,k的值为___10__. for(i=0,j=10;i<=j;i++,j--) k=i+j; 3 C语言中,二维数组在内存中的存放方式为按___行__优先存放. 4 设有以下共用体类型说明和变量定义,则变量d在内存所占字节数是 _12_。 union stud { short int num; char name[8];float score[3]; double ave; } d,stu[3]; 5 设a、b、c为整型数, 且a=2、b=3、c=4, 则执行完以下语句: a*=16+(b++)-(++c); 后,a的值是 _28_. 6 若有定义:char s[ ]="china"; 则C编译系统为数组s开辟__6 ___个字节的内存单元. 7设有以下共用体类型说明和变量定义,则变量c在内存所占字节数是20。 union stud { short int num; char name[10];float score[5]; double ave; } c; 8 若a是int型变量,且a的初值为6,则计算表达式 a+=a-=a*a 后a的值为___-60 __. 9 调用 fopen 函数打开一文本文件,在"使用方式"这一项中, 为输入而打开需填入__r r+___. 10 表达式!10 的值是__0___.(填数字) 11 已知int i=4,s=0; 执行while(i<4){s+=i;i++;} 后，变量s的值是__0___. 12 已知int i,s=0;执行以下程序段后的i的值是__5__. for(i=3;i<5;i++){s+=i;} 13设int x; 经x=2&&2||5>1运算后,x的值为__1___. 14已知char s[]={'H','e','l','l','o'}; 则s数组中含有___5__个元素. 15已知 a=10,b=15,c=1,d=2,e=0,则表达式(a+b>10)||(a+b<0)的值为___1__. 16 当int x=2,y=4,z=3时,执行以下程序段后z=__-2__. if(x
1 假设所有变量均为整型
1 假设所有变量均为整型，则表达式为（X=2,Y=5,Y++,X+Y）的值是（8） 2 设a=5,b=6.c=7,d=8,m=2,n=2,则执行（M=a>b）,&&(n=c>d)后n的值为（2）。 3 执行下列的程序后，变量K中的值为（不定值） Int k=3,s[2],s[0]=k,k=s[1]*10; 4 有如下程序：main {char s[]”ABCD”,*p,for (p=s+q,p
11 下列程序中，判断语句i>j共执行的次数是（6） Main() {int i=0,j=10,k=2,s=0,for(i,j) {i++=k,if(i>j) {printf(“%d”,s);break;}s+=I；}｝12 在以下语句。则对a数组元素的引用不正确的是（（0<=i）(*(*(a+i)) Int a[10]={0123456789},*p=a 13 执行语句”printf(“%d\n”,12&012)；”的输出结果是（8） 14 在C语言中，int char和short三种类型数据在内存中所占用的字节数（由所用机器的机器字长决定） 15 以下程序的输出结果是（1） Long fun(int n) { lomg s; if(n= =111n= =2)s=2; else s=n-fun(n-1); return s;} main() { printf(“%d\n”,fun(3);) 16 已知各变量的类型如下：int i=8,k,a.b;uncigned long w=5;double x=1.42.y=5) 则以下符号c语言表达式的是：a+=a-=(b=4)*(a=3) 17 以下不正确的if语句是：if(x!=9)scanf(“%d”，&x)else sanf (“%d”,&y); 18 c语言中提供关键字有（default） 19 设整型变量abc均为2，表达式a++b++c++的值是（6）二多项选着 1 下列选项中对数组描述正确的是：1 给某一维数组所
1设有数组定义int(精)
一、是非题 1.设有数组定义：int b[ ] = { 10 , 20 , 30 , 40 , 50 , 60 , 70}; 则执行以下几个语句后的输出结果是。 int s = 0 ; for( int i = 0 ; i < b.length;i + +) if(i % 2 = = 1) s += b[i] ; System.out.println(s); 2. java里面表示字符串的类有两种：String和（）。 A) Buffer B) StringBuffer C) DataBuffer D) BufferString 3.以下程序段的结果是：（） char a[] = {'a', 'b', 'c', 'd'}; char b[] = new char[4]; b = a; for (int i = 3; i > 0; i--) System.out.print((char)b[i]); A）abcd B) dcba C) abc D) dcb 4.以下程序段的结果是：（） String str = "abcdefghijk"; String s = "bcde"; int index = 0; index = str.indexOf(s, index); str = str.substring(0, index) + str.substring(index+4); System.out.println(str); A）abcdefghijk B) afghijk C) abcde D) bcdefghijk 二、编程题 1.已知整数数组a有六个元素，其值分别为25、36、47、32、21、16，(11) 请设计一个程序求它的总和及平均值。 2.编写一个程序，用选择法对数组a[]={20,10,50,40,30,70,60,80,90,100}进行从大到小的排序。 3.编程将字符串"Mary was a"改为"Mary had a book."。
C++复习题(2012)及答案
C++复习题 一、选择题 1. C++语言是从早期的C语言逐渐发展演变而来的。与C语言相比，它在求解问题方法上进行的最大改进是（）。B A．面向过程B．面向对象C．安全性D．复用性 2. C++对C语言作了很多改进，即从面向过程变成为面向对象的主要原因是( )。D A. 增加了一些新的运算符 B. 允许函数重载，并允许设置缺省参数 C. 规定函数说明符必须用原型 D. 引进了类和对象的概念 3. 对C++语言和C语言的兼容性，描述正确的是（）。A A．C++兼容C B．C++部分兼容C C．C++不兼容C D．C兼容C++ 4. 在C++中，头文件扩展名为（）。B A. .cpp B. .h C. .1ib D. .obj 5. C++源程序文件扩展名为( ) 。A A. .cpp B. .h C. .1ib D. .obj 6. 由C++源程序文件编译而成的目标代码文件的缺省扩展名为（）。C A. .cpp B. .exe C. .obj D. .lik 7. 布尔类型标识符是（）。D A.void B.short C.long D.bool 8. 下列不是C++语言的基本数据类型的是（）。D A.字符类型 B.整数类型 C.逻辑类型 D.枚举类型 9. 用于标识十六进制前缀或后缀是( )。D A. 后缀L B.后缀e C.前缀零 D.前缀0x 10. 设x和y均为bool量，则x&&y为真的条件是( )。A A. 它们均为真 B. 其中一个为真 C. 它们均为假 D. 其中一个为假 11. 在下列成对的表达式中，运算结果类型相同的一对是( )。D A.7／2和7.0／2.0 B.7／2.0和7／2 C.7.0／2和7／2 D.7.0／2.0和7.0／2 12. 如果a=1,b=2,c=3,d=4,则条件表达式a
深入Integer与int互转
Java是一种面向对象语言，为了能将基本类型视为对象来处理，并能连接相关的方法，Java为每个基本数据类型都提供了包装类，这样便可以把这些基本类型转化为对象来 处理。 Java int与integer的区别 int与integer的区别从大的方面来说就是基本数据类型与其包装类的区别： int 是基本类型，直接存数值，而integer是对象，用一个引用指向这个对象 1.Java 中的数据类型分为基本数据类型和引用数据类型 int 是前者而integer 是后者（也就是一个类）；因此在类进行初始化时int类的 变量初始为0.而Integer的变量则初始化为null. 2.初始化时： int i =1；Integer i= new Integer(1);(要把integer 当做一个类看)； 但由于有了自动装箱和拆箱 使得对Integer类也可使用：Integer i= 1； 注意：Integer i=1编译时被翻译成Integer i=Integer.valueOf(i); int 是基本数据类型（面向过程留下的痕迹，不过是对java的有益补充），Integer 是一个类，是int的扩展，定义了很多的转换方法 类似的还有：float Float;double Double等，而且还提供了处理 int 类 型时非常有用的其他一些常量和方法 举个例子：当需要往ArrayList，HashMap中放东西时，像int，double这种内建类型是放不进去的，因为容器都是装 object的，这是就需要这些基本 类型的包装类了。 Java中int和Integer关系是比较微妙的。关系如下： 1.int是基本的数据类型； 2.Integer是int的包装类；
(完整版)C语言基础知识综合练习题
一、C语言基本知识和基本语句 （一）选择题 1．设a,b和c都是int型变量，且a=3，b=4，c=5则下面的表达式中，值为零的表达式是（）。 A）‘a’&&’b’ B) a<=b C) a || b+c&&b-c D) ! ((a
int13与扩展int13区别
关于int13与扩展int13 第一部分简介 1,1 一. 硬盘结构简介 1. 硬盘参数释疑 到目前为止, 人们常说的硬盘参数还是古老的CHS (Cylinder/Head/Sector)参数. 那么为什么要使用这些参数, 它们的意义是什么? 它们的取值范围是什么? 很久以前, 硬盘的容量还非常小的时候, 人们采用与软盘类似的结构生产硬盘. 也就是硬盘盘片的每一条磁道都具有相同的扇区数. 由此产生了所谓的3D参数(Disk Geometry). 既磁头数(Heads), 柱面数(Cylinders), 扇区数(Sectors),以及相应的寻址方式. 其中: 磁头数(Heads) 表示硬盘总共有几个磁头,也就是有几面盘片, 最大为255 (用8 个二进制位存储); 柱面数(Cylinders) 表示硬盘每一面盘片上有几条磁道, 最大为1023 (用10 个二进制位存储); 扇区数(Sectors) 表示每一条磁道上有几个扇区, 最大为63 (用6 个二进制位存储). 每个扇区一般是512个字节, 理论上讲这不是必须的, 但好象没有取别的值的.所以磁盘最大容量为: 255 * 1023 * 63 * 512 / 1048576 = 8024 GB ( 1M = 1048576 Bytes ) 或硬盘厂商常用的单位: 255 * 1023 * 63 * 512 / 1000000 = 8414 GB ( 1M = 1000000 Bytes ) 在CHS 寻址方式中, 磁头, 柱面, 扇区的取值范围分别为0 到Heads - 1, 0 到Cylinders - 1, 1 到Sectors (注意是从1 开始). 2. 基本Int 13H 调用简介 BIOS Int 13H 调用是BIOS 提供的磁盘基本输入输出中断调用, 它可以完成磁盘(包括硬盘和软盘)的复位, 读写, 校验, 定位, 诊断, 格式化等功能.它使用的就是CHS 寻址方式, 因此最大识能访问8 GB 左右的硬盘( 本文中如不作特殊说明, 均以1M = 1048576 字节为单位). 3. 现代硬盘结构简介 在老式硬盘中, 由于每个磁道的扇区数相等, 所以外道的记录密度要远低于内道, 因此会浪费很多磁盘空间(与软盘一样). 为了解决这一问题, 进一步提高硬盘容量, 人们改用等密度结构生产硬盘. 也就是说, 外圈磁道的扇区比内圈磁道多. 采用这种结构后, 硬盘不再具有实际的3D参数, 寻址方式也改为线性寻址, 即以扇区为单位进行寻址.为了与使用3D寻址的老软件兼容(如使用BIOS Int13H接口的软件), 在硬盘控制器内部安装了一个地址翻译器, 由它负责将老式3D参数翻译成新的线性参数. 这也是为什么现在硬盘的3D参数可以有多种选择的原因(不同的工作模式, 对应不同的3D参数, 如LBA, LARGE, NORMAL). 4. 扩展Int 13H 简介 虽然现代硬盘都已经采用了线性寻址, 但是由于基本Int 13H 的制约, 使用BIOS Int 13H 接口的程序, 如DOS 等还只能访问8 G 以内的硬盘空间.为了打破这一限制, Microsoft 等几家公司制定了扩展Int 13H 标准(Extended Int13H), 采用线性寻址方式存取硬盘, 所以突破了8 G 的限制, 而且还加入了对可拆卸介质(如活动硬盘) 的支持.
基本数据类型习题-答案
基本数据类型习题-答案 一、选择题 1、下列变量定义错误的是。(D) A) int a; B) double b=4.5; C) boolean b=true; D)float f=9.8; 2、下列数据类型的精度由高到低的顺序是：(B) a)float，double，int，long b)double，float，int，byte c)byte，long，double，float d)double，int，float，long 3、执行完下列代码后，(A) int a=3; char b='5'; char c=(char)(a+b); c的值是？ A)’8’ b)53 c)8 d)56 4、Unicode是一种_____________(C) A) 数据类型B)java包C）字符编码D）java类 5、6+5%3+2的值是___________(D) A)2 B）1 C）9 D）10 6、下面的逻辑表达式中合法的是__________(C) A）(7+8)&&(9-5) B）(9*5)||(9*7) C）9>6&&8<10 D）(9%4)&&(8*3) 7、java语言中，占用32位存储空间的是__________。(D) A）long，double B）l ong，float C）i nt，double D)int，float 8、假设int a=1，b=2,c=3,以下语句正确的是___________。(D) A）c=c/float(a//b) b) c=c/((float a)/b) c) c=(float)c/(a/b) d) c= c/(int)(a/(float)b) 9、2|3&5的值是________________。(C) A）1 B）2 C）3 D）5 10、指出下列正确的语句：(D) A) byte i = 389; B) long lv = i*3+4.5; C) int x = 87L； D) long l = 10; 11、指出下列类型转换中正确的是______________。（A） A）int i=’A’ B）long L=8.4f C）int i=(boolean)8.9 D)int i=8.3 12、以下的选项中能正确表示Java语言中的一个整型常量的是( )。（C）
《高级语言程序设计(C)》期末考试试题
《高级语言程序设计（C）》期末考试试题 一、选择题（本题共20道小题，共40分。） 1. 设x和y均为int型变量，则以下语句：x+=y;y=x-y;x-=y;的功能是 A)把x和y按从大到小排列 B)把x和y按从小到大排列 C)无确定结果 D)交换x和y中的值 2. 下面程序的输出是 void prtv(int *x) { printf("%d\n", ++(*x));} main() { int a=25; prtv(&a);} A) 23 B) 24 C) 25 D) 26 3. int x=10, y=20, z=30; if(x>y) z=x; x=y; y=z; 以上语句执行后x, y, z的值是 A) x=10,y=20,z=30B) x=20,y=30,z=30 C) x=20,y=30,z=10D) x=20,y=30,z=20 4. 设有以下宏定义： #define N 3 #define Y(n) ((N+1)*n) 则执行语句：z=2 *(N+Y(5+1))后,z的值为 A)出错 B)42 C)48 D)54 5. 逻辑运算符两侧运算对象的数据类型是（）。 A) 只能是0或1 B) 只能是0或非0正数 C) 只能是整型或字符型数据 D) 可以是任何类型的数据 6. 当执行以下程序段时 x=-1; do { x=x*x;} while(！x); A)循环体将执行一次 B)循环体将执行两次 C)循环体将执行无限次 D)系统将提示有语法错误 7. int x=3; do { printf("%3d",x-=2);} while(!(--x)); 以上程序段的输出结果是 A) 1 B) 3 0 C) 1-2 D) 死循环 8. main() {int k=11; printf("k=%d,k=%o,k=%x\n",k,k,k); } 以上程序段的输出结果是 A)k=11,k=12,k=11 B)k=11,k=13,k=13 C)k=11,k=013,k=0xb D)k=11,k=13,k=b 9．以下程序的输出结果是（）。 main() { int num=0; while(num<=2) { num++; printf(“%d\n”,num);} } A) 1B) 1C) 1D) 1 2 2 2
C语言综合练习题
《C语言程序设计》综合练习题 一、单项选择题 1．下列（）是字符串比较函数。 A. puts() B.gets() C. strcpy () D. strcmp() 2．构成一个完整的C源程序必须有且只有一个（）。 A. 函数 B.过程 C. 主函数 D. 程序 3. 设有int i，j，k；则表达式i=1，j=2，k=3，i&&j&&k的值为（）。 A. 1 B. 2 C. 63 D. 0 4．在C语言中，不同类型数据混合运算时，要先转化成同一类型后进行运算。设一表达式中包含有int、long、unsigned、char类型的变量和数据，则表达式最后的运算结果是（）类型数据。 A．int B．char C．unsigned D．long 5．下列（）不是构成标识符的字符。 A.字母 B.数字 C.下划线 D.标点符号 6．表达式：3>5&&-1||6<3-!-1的值是（）。 A. 0 B.1 C. 表达是不合法 D. 均不对 7. 以下标识符中能做为合法的C用户标识符的是（）。 A.A3+B3 B. float C. 3dx D. x3d 8. 以下数据中不正确的数值或字符常量是（）。 A. 0.0 B. 3E2.7 C. 9861 D. 0xabcd 9. fp=fopen(''test.txt",''r''); 语句中，r对文件处理方式是（）。 A. 只读打开文件 B. 只写打开文件 C. 追加打开文件 D. 读写打开文件 10．表示关系x<=y<=z的C语言表达式为（） A. (x<=y)&&(y<=z) B. (x<=y)and(y<=z) C. (x<=y)&(y<=z) D. (x<=y<=z) 11．如果要把常量327存入变量a中，a不能定义的类型是（）。 A. int B. char C. long D. float 12. 在变量的存储结构中，（）局部变量的初始化只有一次。 A. 自动 B. 静态 C.外部 D. 寄存器 13．下列能正确进行字符串赋值操作的语句是（）。 A. char s[5]={ "ABCDE"}; B. char s[5]={ 'a', 'b', 'c', 'd', 'e'} C. char *s;s="abcde"; D. char *s; scanf("%s",s); 14．语句if（3/4>1/2）a=1;else a=0; 运行后，a的值是（）。 A. 1 B. 0 C.与机器有关 D.语法有错 15．下列（）是合法自定义标识符。 A. 3ma B. float C. m3a D.–ab 16．设a,b和c都是int型变量，且a=3,b=4,c=5，则下列表达式中，值为0的表达式是（） A. 'a' && 'b' B. a<=b C. c>=b||b+c&&b-c D. a<=b+c&&c>=a+b 17．判断整型变量i，j可同时被2整除的表达式（i，j同时被2整除返回1，否则返回
int与Integer的区别(Java各种数据类型详细介绍及其区别)
Java各种数据类型详细介绍及其区别基本类型，或者叫做内置类型，是JAVA中不同于类的特殊类型。 Java中的简单类型从概念上分为四种：实数、整数、字符、布尔值。但是有一点需要说明的是，Java里面只有八种原始类型，其列表如下： 实数：double、float 整数：byte、short、int、long 字符：char 布尔值：boolean 复杂类型和基本类型的内存模型本质上是不一样的，简单数据类型的存储原理是这样的：所有的简单数据类型不存在“引用”的概念，简单数据类型都是直接存储在内存中的内存栈上的，数据本身的值就是存储在栈空间里面，而Java语言里面只有这八种数据类型是这种存储模型；而其他的只要是继承于Object类的复杂数据类型都是按照Java里面存储对象的内存模型来进行数据存储的，使用Java内存堆和内存栈来进行这种类型的数据存储，简单地讲，“引用”是存储在有序的内存栈上的，而对象本身的值存储在内存堆上的。 Java的简单数据讲解列表如下： int：int为整数类型，在存储的时候，用4个字节存储，范围为-2,147,483,648到2,147,483,647，在变量初始化的时候，int类型的默认值为0。 short：short也属于整数类型，在存储的时候，用2个字节存储，范围为 -32,768到32,767，在变量初始化的时候，short类型的默认值为0，一般情况下，因为Java本身转型的原因，可以直接写为0。 long：long也属于整数类型，在存储的时候，用8个字节存储，范围为 -9,223,372,036,854,775,808到9,223,372,036, 854,775,807，在变量初始化的时候，long类型的默认值为0L或0l，也可直接写为0。 byte：byte同样属于整数类型，在存储的时候，用1个字节来存储，范围为-128到127，在变量初始化的时候，byte类型的默认值也为0。 float：float属于实数类型，在存储的时候，用4个字节来存储，范围为32位IEEEE 754单精度范围，在变量初始化的时候，float的默认值为0.0f或0.0F，在初始化的时候可以写0.0。
大学计算机C语言程序设计(填空题)
一、填空共219题 第1题题号:422 设有以下结构类型说明和变量定义,则变量a在内存所占字节数是【1】 . Struct stud { char num[6]; int s[4]; double ave; } a,*p; 答案： 1). 22 第2题题号:533 设x和y均为int型变量,则以下for循环中的scanf语句最多可执行的次数是【1】.
for (x=0,y=0;y!=123&&x<3;x++) scanf ("%d",&y); 答案： 1). 3 第3题题号:496 静态变量和外部变量的初始化是在【1】阶段完成的,而自动变量的赋值是 在【2】时进行的. 答案： 1). 编译 2). 函数调用 第4题题号:96 已知a=13,b=6, a&b的十进制数值为【1】. 答案： 1). 4
第5题题号:398 程序段int k=10; while(k=0) k=k-1循环体语句执行【1】次.答案： 1). 0 第6题题号:651 设w=5;w+= -2;则w的值为【1】. 答案： 1). 3 第7题题号:258 下面程序段的输出结果是【1】. int a=12; a=a&0377;pritnf("%d\n",a); 答案： 1). 12
第8题题号:457 设a,b,c,t为整型变量,初值为a=3,b=4,c=5,执行完语句 t=!(a+b)+c-1&&b+c/2 后,t的值是【1】. 答案： 1). 1 第9题题号:402 设a取二进制数00101101,若想通过a^b运算使a的高4位取反,低4位不变,则b的 二进制数是【1】. 答案： 1). 11110000 第10题题号:311 若所用变量均已正确定义,则执行下面程序段后的值是【1】.
C++基本概念
一．C++语法的外围基础 ⒈新的语法规定与新算符 ①文件扩展名的规定 标准的C++源程序文件扩展名为.CPP，头文件扩展名为.H 或.HPP。 ②标准输入和输出符号 为便于使用，C++语法规定： 标准输出算符：cout<<“输出内容”<<…； 标准输入算符：cin>>“输入内容”>>…； 上述算符实际上是一种函数，由iostream.h头文件支持。 ③动态内存分配算符 OO程序对内存空间的动态分配的频繁程度要求简化语言的相关语法的格式。C++语法规定new算符等效于C语言中mal1oc一类的函数功能；free算符等效于C语言中free一类的函数功能。其格式为：指向对应类型的指针=new 类型描述符； delete 指向对应类型的指针； 例1：仅占一个单元空间： int *p; p=new int; /*意即占一个字长*/ 例2：仅占一个单元空间且赋初值： int *p; p=new int(20); /*意即占一个字长且赋予初值20*/ 例3：占用多个单元可按数组或指针使用： int *p;
p=new int [20]; /*意即占20个字长单元*/ delete [2]p; ④引用类型（References） 在一个程序中用不同的变量名指向同一地址的同一内容的数据类型描述称为引用。这里的引用数据类型名又称为别名。其语法格式是： 类型名＆引用型函数名或变量名[=前已声明的（常）变量名]；例： int i; int &j=i; /*j是i的别名*/ j=1; i++; cout< 基本类型，或者叫做内置类型，是JAVA中不同于类的特殊类型。 Java中的简单类型从概念上分为四种：实数、整数、字符、布尔值。但是有一点需要说明的是，Java里面只有八种原始类型，其列表如下： 实数：double、float 整数：byte、short、int、long 字符：char 布尔值：boolean 复杂类型和基本类型的内存模型本质上是不一样的，简单数据类型的存储原理是这样的：所有的简单数据类型不存在“引用”的概念，简单数据类型都是直接存储在内存中的内存栈上的，数据本身的值就是存储在栈空间里面，而Java语言里面只有这八种数据类型是这种存储模型；而其他的只要是继承于Object类的复杂数据类型都是按照Java里面存储对象的内存模型来进行数据存储的，使用Java内存堆和内存栈来进行这种类型的数据存储，简单地讲，“引用”是存储在有序的内存栈上的，而对象本身的值存储在内存堆上的。 Java的简单数据讲解列表如下： int：int为整数类型，在存储的时候，用4个字节存储，范围为-2,147,483,648到 2,147,483,647，在变量初始化的时候，int类型的默认值为0。 short：short也属于整数类型，在存储的时候，用2个字节存储，范围为-32,768到32,767，在变量初始化的时候，short类型的默认值为0，一般情况下，因为Java本身转型的原因，可以直接写为0。 long：long也属于整数类型，在存储的时候，用8个字节存储，范围为 -9,223,372,036,854,775,808到9,223,372,036, 854,775,807，在变量初始化的时候，long 类型的默认值为0L或0l，也可直接写为0。 byte：byte同样属于整数类型，在存储的时候，用1个字节来存储，范围为-128到127，在变量初始化的时候，byte类型的默认值也为0。 float：float属于实数类型，在存储的时候，用4个字节来存储，范围为32位IEEEE 754单精度范围，在变量初始化的时候，float的默认值为0.0f或0.0F，在初始化的时候可以写0.0。 double：double同样属于实数类型，在存储的时候，用8个字节来存储，范围为64位IEEE 754双精度范围，在变量初始化的时候，double的默认值为0.0。int与Integer的区别