Browse Prior Art Database

Parallel Best-First Search for Determining Phonetic Baseforms

IP.com Disclosure Number: IPCOM000122298D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 3 page(s) / 113K

Publishing Venue

IBM

Related People

Epstein, ME: AUTHOR

Abstract

In the Tangora (1,2) a best-first search algorithm is used to generate a phonetic baseform for a word given its spelling and one utterance. This algorithm is now modified to allow using more than one speech processor (SP) adapter in parallel.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Parallel Best-First Search for Determining Phonetic Baseforms

      In the Tangora (1,2) a best-first search algorithm is
used to generate a phonetic baseform for a word given its spelling
and one utterance.  This algorithm is now modified to allow using
more than one speech processor (SP) adapter in parallel.

      The algorithm for determining phonetic baseforms (1) used in
the Tangora (2) requires a best-first search (3,4). This is used
because it quickly finds a solution that is near the optimal.  The
best-first search control strategy is now slightly modified to lend
itself to parallelization, which will allow multiple speech processor
adapters to work concurrently.

      The algorithm previously described in [1] follows the standard
best-first search control strategy.  The most promising node, along
with all those within a specified threshold up to a maximum number,
are removed from the priority queue [5] of the frontier nodes.  Each
of these is given to a generator which creates possible descendants.
These are then evaluated and added to the search tree and priority
queue.  The control strategy used previously was thus:
1.   Remove the next node from the list of nodes to be expanded.
2.   Generate its list of successors.
3.   Build the structure used by the speech processor adapter to
evaluate the successor's acoustic scores.
4.   Send the structure to the SP.
5.   Compute the spelling-to-sound rule score [6,7] for the node's
successors while the SP is determining each successor node's acoustic
score.
6.   Wait for the SP to finish.
7.   Merge the scores from the SP with the spelling-to-sound rule
scores computed on the PC.
8.   Add the promising nodes back into the search tree, and go to
step 1.

      In order to allow several SP adapters to be used
simultaneously, several steps in the control strategy had to be
modified.  Rather than expanding each node individually, as is done
in the standard best-first search, now as many nodes are expanded in
parallel as there are SP adapters using the following control
strategy:
1.   For each SP adapter:
      a.   Remove the next node from the list of nodes to be
expanded.
      b.   Generate its list of successors.
      c.   Build the structure used by the SP to evaluate the
successor's acoustic scores.
      d.   Send the structure to the next available SP.
      e.   Compute the spelling-to-sound rule score [6,7] for the
node's successors while the SP is determining each successor node's
acoustic score, and go to step a.
2.   For each remaining node on the list of nodes to be expanded:
      a.   Remove the next node from the list of nodes to be
expanded.
      b.   Generate its list of successors.
      c.   Build the structure used by the SP, but save it.
      d.   Wait for the next SP to complete processing the structure
it was already sent, and upload the acoustic scores when don...