BTH: An Efficient Parsing Algorithm for Word-Spotting
Yasuyuki KONO, Takehide YANO, and Munehiko SASAJIMA
Kansai Research Laboratories, Toshiba Corporation
8-6-26 Motoyama-Minami, Higashi-Nada, Kobe 658-0015, Japan{kono,yano,sasa}@krl.toshiba.co.jp

ABSTRACTThis paper presents a new parsing algorithm, BTH, which iscapable of efficiently parsing a keyword lattice that contains alarge number of false alarms. The BTH parser runs without
unfolding the given keyword lattice, and thus it can efficiently
obtain a set of word sequences acceptable to the given grammar
as the parser result.
The algorithm has been implemented on Windows-based PCs
and is tested by applying it to a car navigation task that has ascale of practical applications. The result indicates promise in
implementing the function of a sentence utterance-based
spontaneous speech understanding in next -generation car
navigation systems.

1. INTRODUCTION
Since spoken language is not only an essential means ofcommunication but also the most natural one for human beings.
Users desire computer systems with this type ofcommunication. We had previously developed TOSBURG-II, aspoken language dialogue system [1][2]. It picked up theacceptable keyword sequence as a sentence from the keyword
lattice obtained from a word-spotting engine for the task ofselling hamburgers with a very limited vocabulary, andperformed the semantic analysis / intention understanding. The
system recognized only meaningful words, i.e., nouns and verbs,
received a plausible keyword sequence as a sentence, andresponded to the user by synthesized voice. The TOSBURG-II
study revealed the followings: (1) by applying word-spotting
technology, it is possible to cope with phenomenacharacteristics of spoken language such as unnecessary words orunfixed forms, (2) false alarms which are unavoidable in theword-spotting process can be also corrected by sentence
analysis.
In order to expand the scale of the task which a spoken language
dialogue system is capable of executing and to apply the systemfor practical tasks, it is necessary to correspond to a large
vocabulary and a large-scale grammar. However, expansion of
vocabulary and grammar causes the number of recognized words
and the size of the corresponding keyword lattice to increase
explosively. This poses a problem in that the processing timerequired for analysis becomes huge.
We have developed BTH, Bun (meaning "sentence" in Japanese)
Template Hash, a parsing algorithm which is capable ofefficiently parsing a keyword lattice with a large number of false
alarms. When a keyword lattice is large, the list of possible word
sequence generated by unfolding the lattice is huge too. Parsing

the candidates in the list one by one causes an explosion ofcalculation time. The BTH parser runs without unfolding thegiven keyword lattice. This parser (1) holds hash tables for eachsentence-type template, (2) calculates the set of sentence-types
to which each node in the lattice can belong by referring to thetable, and (3) propagates the list to the nodes following eachnode. It can efficiently obtain a set of acceptable word sequences
to the given grammar as the parser result.
We have implemented this algorithm on PCs and tested themethod by applying it to a car navigation task. In this work, thevocabulary for recognition exceeds 700 words, and the keyword
lattice that can generate over 1,000,000 candidate word
sequences is usually obtained as a recognition result. Also,
parsing of such a large-scale lattice can usually be completed inreal time in around 1 second by a PC of some generations ago(486DX2 50MHz), i.e., about 35 MIPS. The result shows
promise in implementing the function of spoken-language
understanding from sentence utterance in next -generation car
navigation systems equipped with RISC MPUs of about 70MIPS.

2. THE BTH PARSER
Our research goal is to develop a generic framework for spoken
interfaces that runs on practical applications with considerable
scale of task. We cannot expect a 100% recognition rate withcurrent speech recognition technologies, even if strong
constraints are applied as a language model. It is especiallydifficult to correctly recognize bound words, i.e., words thathave no meanings themselves, e.g., postpositions. We havedesigned our speech understanding mechanism based on thefollowing policies:•Embodying scalability so that it works well inpractical applications.

•Analyzing/understanding a user’s spontaneousutterance with the grammar that accepts asentence as a word-sequence consisting only of
free words, i.e., words that have meanings
themselves, e.g., nouns and verbs.

•Recognizing a user’s utterance by thekeyword-spotting technique. A list of possible
word sequences is obtained by parsing a
keyword-lattice generated from a word-spotting
result.

To realize our goal, it is crucial to establish the technology forpost-recognition process that can efficiently extract plausible
sentences/word-sequences by dealing with the keyword latticeobtained from the word-spotting engine. We have developed the2067

BTH parser which is capable of efficiently parsing a keyword
lattice that contains a large number of false alarms. This section
describes its features and techniques.

2.1. Keyword-Lattice Parsing Problem
One technique for parsing a lattice structure that is obtained byspeech/handwriting recognition is to sequentially apply a natural
language parser one by one to candidate sentences which aregenerated by unfolding the lattice. The TOSBURG-II employeda generalized LR parser [3], which analyzes a keyword latticegenerating midway candidates and pruning hopeless paths [1,2].
The keyword lattice, however, generated by a speech recognizer
with a large volume of vocabulary and grammar, contains
complicated structure with many nodes and forms in cases. It is
hard to analyze each candidate generated by unfolding the latticein the light of both calculation time and memory.
It is essential to retrieve huge amount of both vocabulary andgrammar to develop a speech interface of a practical application.
We collected 389 example sentence utterances that are naturaland needed by drivers who use car navigation systems withspeech recognition. They include actual utterances made by oneof us while driving a car and while being a passenger in a car.
Then we analyzed them and made grammatical rules that apply
to those examples. We also designed structures of user’sintentions by classifying the collected utterances into 5W(Where, What, Which, When, Why) and 2H (How, How-Much).
In parallel with the analysis of sentence patterns and grammar,
we picked up keywords from the example utterances. Forinstance,thesentence“Deguchi-no-mae-no-saigo-no-service-area-ha-doko? (Where isthe last service area before the exit?)" was classified into thesentence-type group of “Where”, and five words, i.e., deguchi(exit), mae (before), saigo (the last), service-area, and doko
(where), were selected as keywords. As a result of the analysis,
about 700 words were picked up as recognized keywords andwere classified into about 110 word-classes (parts of sp eeches).
Speech Input: Deguchi-no-mae-no-saigo-no-service-area-wa-doko?

koreanoaredeguchi

Startimauemaeekinai5deguchi

itsu

dono

service-area

yado

ue

ato

namae

uchi

iku

osoi

imaie

kono

ano

saigo

sou

doko

hai

iku

ato

End

5

komu

ima-no5

7

Num. of spotted words： 36
Num. of arcs：
1,646
Num. of paths： 4,562,925

Figure 1: An example of a keyword lattice obtained from theword-spotting engine.

As the vocabulary for speech recognition becomes larger, thenumber of false alarms in a recognition result increases and thecorresponding keyword lattice gets huge. Figure 1 depicts theexample keyword lattice which is obtained as the speech
recognition result when a user uttered the sentence above(“Deguchi-no-mae-no-saigo-no-service-area-ha-doko?”).
36
keywords, i.e., 5 correct and 31 false alarms, were spotted inthis example. When only connectable time constraints areapplied, over 4 million plausible word sequences can begenerated, each of which is a different path from the start node
to the end node, if the lattice is unfolded. Thus a lattice parser,
which is capable of parsing without unfolding a given
keyword-lattice and generating a set of acceptable word
sequence candidates by given grammar, is required.

2.2. Parsing a Keyword-Lattice with
Template Hash Tables
Based on the following viewpoints, we have developed the BTH(Bun [meaning "sentence" in Japanese] Template Hash) parser,
which is an efficient lattice parser for word-spotting thatsatisfies the above-mentioned requirements:
Real-time processing in the scale of practical applications
on conventional calculation power: Both more
vocabulary and less calculation are required to develop apractical speech interface. We aimed to realize a parserworking in real-time on 70-80 MIPS RISC MPUs, i.e., theMPUs that are expected to be applied in next -generation
car navigation systems.
Grammatical representation taking into account both therecognition method and the application: It is difficult
to construct a comprehensive and accurate grammar for
actual utterance even if the task to which it is applied islimited, because word order and syntax in actual utterance
are wide-ranging. A weakly constrained grammaticalrepresentation is required to cope with noticeable
phenomena in speech, such as inversions. On the otherhand, it is pointless for the parser to accept sentences
which the application program cannot execute. A
grammatical representation that generates very
complicated sentences, e.g., one employing recursive rules,
would be too expressive for practical use.
Parsing without unfolding the given lattice: In the case of alarge vocabulary, a recognition result lattice from aword-spotting engine includes many false alarms asmentioned above. It costs huge calculation time if theparser analyzes unfolded candidates one by one.
Therefore, a lattice parser, which is capable of parsing
without unfolding a given keyword lattice, is required.
The BTH parser embodies the following features:
Grammatical representation based on templates ofword-class sequences: The grammar is represented as aset of templates, each of which forms a word-classsequence. An interface designer collects sentences in a task
and classifies them into sentence-types, i.e., word-class2068

sequences. The parser analyzes a keyword lattice utilizing
the template sets. The grammar must be represented
non-recursively.
Generation of a hash table from the sentence-type
template: As a pre-process of the parsing, the given
sentence-type template is compiled into a hash table,
whose element is a correspondence between theappearance of a certain word-class in sentences and theestablished set of sentence-types which applies to theword-class. A Bun (meaning “sentence” in Japanese)
Template Hash table is composed of representations, eachof which means “if a word of a certain word-class isrecognized at a certain order in a sentence, the word of theorder applies to either of certain sentence-types.”
Parsing of a lattice by propagating belonging sentence-type
information: The parser scans the given lattice from thestart node. At each node, the set of sentence-types, towhich a certain node in the lattice belongs, is calculated byexamining set calculations between the corresponding
elements in the hash table and the set of sentence-types
propagated from the nodes connected just in front of thenode. Then the set is propagated from the node toconnecting node(s). By repeating the method, the set ofsentence-types to which the given lattice belongs is finallyobtained.
The detailed parsing process is described in the next subsection.

2.3. Parsing Process
To parse a keyword lattice, the BTH parser utilizes 4 kinds ofinformation structure, i.e., a dictionary of word-classes andwords, a dictionary of patterns of word-class sequences, asentence-type hash dictionary, and a list of processing nodes.
The list of processing nodes is the set of nodes that are thecurrent targets of processing. Each node in the lattice holds 3
kinds of data, i.e., a list of antecedent nodes, a list ofunprocessed antecedent nodes, and an inter-processing list,
composed of sets of sentence-types, each of which is thesentence-type to which the node belongs at a certain order.

Given a new lattice to analyze, at the beginning of the parsing
process, the BTH parser (1) copies the list of antecedent nodes
to the list of unprocessed antecedent nodes for each nodes in thelattice, (2) adds all the nodes which may possibly be heads ofresult word sequences to the list of processing nodes, and (3)sets the initial score that is obtained from the sentence-type
hash dictionary for each inter-processing list of the node in thelist of processing nodes.
Then the parser repeats the propagation process while the list ofprocessing nodes is not empty. In the propagation process, thefollowing steps are applied to each node in the list of processing
nodes:
1. Take one node as the current target from the listof processing nodes and check whether the list of
unprocessed antecedent nodes is empty. If it isnot empty, check the next node in the list ofprocessing nodes.
2. If the list of unprocessed antecedent nodes of anode X in the list of processing nodes is empty,propagate the inter-processing list of X to all
succeeding nodes and add them to the list ofprocessing nodes, and then remove X from thelist.
3. At each node to which the inter-processing listof its antecedent node is propagated, re-calculate
the inter-processing list.
If the list of processing nodes is empty when the step 3 above iscompleted, the inter-processing list of the end node is the set of
acceptable sentence-types by the lattice. The parser result, i.e.,the set of acceptable word-sequences by the lattice, is obtained
from the set of sentence-types by re-scanning the lattice. Figure
2 shows an example parser result.

Figure 3: Sample screen of the list of word-sequences.

Figure 2: Sample screen of the parser result.

The cost of the entire parsing process can be estimated from thecost of set calculations to obtain the inter-processing list foreach node. The maximum possible number of set calculations,
i.e., unions and intersections, is equal to the number of links in2069

the lattice times the number of words in the longest word
sequence. It is the worst case, however. Much less calculation isrequired in the most cases.

3. DIALOGUE SYSTEM
We have implemented a spoken dialogue system using the BTH
algorithm, which is able to respond to queries respecting
locations made by a user while driving a car. The system iscomposed of four independent software modules, i.e., thedialogue module that employs the BTH parser, the application
module, the word-spotting engine, and text -to-speechsynthesizer. The first two modules run on a Windows NT based
PC and the other two run on an EWS. The modules run
collaboratively, communicating with each other via socket-basedmessaging. As shown in Figure 4, the application module has amap-based appearance, which is based on ProAtlas, a map
software developed by ALPS Mapping Co., Ltd. It simulates
car driving by re-playing pre-recorded position data obtained
from the GPS (Global Positioning Satellite) system.

The score of each candidate is revised taking account of the costof problem solving, and the list of the candidates is reordered.
As a result, the candidate with the best score is selected and thetext of the answer corresponding to the question is generated,e.g., “Amagasaki Service Area is the last service area before theNishinomiya Interchange,” and the dialogue module notifies thesynthesizer module of it.

4. CONCLUDING REMARKS
We have designed an efficient keyword lattice parser, BTH,
which accepts a user’s spontaneous speech input, anddeveloped a PC-based speech interface. Given a grammar
consisting of a set of production rules with neither recursive
calls nor loops, the BTH parser performs parsing without
unfolding the given keyword lattice. We have tested the parser
by applying it to a task of car navigation involving over 700
words of recognized vocabulary. The developed speech interface
is able to respond to a user’s question within a few seconds ofthe question being asked.

The application module simulates driving a car and continuously
notifies the dialogue module of the simulated current position at
regular intervals of time. When a user asks a question inJapanese,e.g.,“Deguchi-no-mae-no-saigo-no-service-area-ha-doko? (Where is
the last service area before the exit?)", the word-spotting engine
recognizes the utterance and notifies the dialogue module of aword-lattice as depicted in Figure 1.

In the case of the example task, it is common for over 100
spotted words to be notified from the recognition engine, andconsequently over 1 million possible word sequences can begenerated by unfolding the corresponding lattice even ifword-class bi-gram is applied to the lattice. Our method,however, is able to parse such a large lattice in a practical time.
The result shows promise in implementing the function of
spontaneous speech interface in practical applications.

The dialogue module analyzes the word-lattice by employing theBTH parser and obtains a list of candidate word-sequences,which is sorted in the descending order of the initial score ofeach candidate, which is calculated from phonetic scores ofwords of the candidate. Each word-sequence candidate isconverted into a user’s intention in the form of a typed feature
structure, and is resolved by using current position informationand the knowledge base. The knowledge base is a semantic
network that contains all the knowledge required to solve
questions about locations on the displayed map.

REFERENCES
1. Takebayashi, Y., Tsuboi, H., Kanazawa, H., Sadamoto,Y., Hashimoto, H., and Shinchi, H. “A Real-Time Speech
Dialogue System Using Spontaneous Speech
Understanding”, IEICE Trans. Inf. & Syst., E76-D:
112–120, 1993.
2. Takebayashi, Y., Tsuboi, H., and Kanazawa, H.
“Keyword-Spotting in Noisy Continuous Speech Using
Word Pattern Vector Subabstraction and Noise
Immunity Learning”, Proc. ICASSP ‘92, II–85–88, 1992.
3. Tomita, M. “An Efficient Word Lattice Parsing
Algorithm for Continuous Speech Recognition”, Proc.
ICASSP ‘86, 1569–1572, 1986.

Figure 4: Sample screen of the application.

2070