DE69028430T2

DE69028430T2 - Effektiver Einschränkungsalgorithmus für Spracherkennung nach dem Hidden-Markov-Modell

Info

Publication number: DE69028430T2
Application number: DE69028430T
Authority: DE
Inventors: George R Doddington; Basavaraj I Pawate
Original assignee: Texas Instruments Inc
Current assignee: Texas Instruments Inc
Priority date: 1989-04-13
Filing date: 1990-04-04
Publication date: 1997-03-27
Anticipated expiration: 2010-04-05
Also published as: EP0392728A2; JPH0362000A; EP0392728B1; EP0392728A3; DE69028430D1; US4977598A

Description

Hintergrund der Erfindung

Gebiet der Erfindung

Diese Erfindung bezieht sich allgemein auf Computerprozessoren und genauer auf einen effektiven Beschneidealgorithmus zur Reduzierung der Ladevorgänge der Zentralverarbeitungseinheit während einer Spracherkennung.

Beschreibung des Stands der Technik

Auf einer dynamischen Zeit-Verwindung (DTW) basierende Spracherkennungseinrichtungen nach dem Stand der Technik verwendeten einen traditionellen aufsteigenden Ansatz, bei dem Wort- Niveau- oder Phonetik-Niveau-Hypothesen von einer unabhängigen Wort-Hypotheseeinrichtung erzeugt wurden. Diese Hypothesen wurden dann von einer Satz-Hypotheseeinrichtung nachverarbeitet, die anwendungsspezifisches Wissen (Grammatik) verwendete, um aus allen grammatischen Anwärtern die beste Satzhypothese auszuwählen.
In jüngster Zeit wurde in "System and Method for Parsing Natural Language" (US-Patent Nr. 5 083 268, veröffentlicht am 21. Januar 1992) und in "A Chart Parser for Stochastic Unification Grammar" (EP-A-0 384 584), beide auf denselben Rechtsnachfolger wie die vorliegende Anmeldung übertragen, ein absteigender Ansatz zur Spracherkennung beschrieben. Kurz gesagt ist die Wort-Hypotheseeinrichtung nicht mehr unabhängig, sondern sie wird durch die Satz-Hypotheseeinrichtung geleitet. Beim Verarbeiten eines Blocks fordert jede aktive Satzhypothese je nach Erfordernis Daten an. Die Folge der Datenanforderungen beginnt typischerweise damit, daß ein Satz Worthypothesen anfordert (d.h. ein Anwärterwort und die Wahrscheinlichkeit seines Auftretens bei der derzeitigen Vorgeschichte). Diese Anforderungen für eine Worthypothese fordern ihrerseits wieder eine Lauthypothese an, usw. Der Prozeß endet mit einer Anforderung eines Blocks von Sprachdaten. An diesem Punkt wird der ankommende Block von Sprachdaten in dem durch diese Satzhypothese vorausgesagten Kontext bewertet. Jedes Niveau wendet die Randbedingungen grammatikartiger Strukturen, oder Hidden-Markov- Modelle (HMM), auf das nächst niedrigere Niveau der Datendarstellung an.
Fig. 1 zeigt ein Blockdiagramm eines solchen schichtweisen Grammatik- oder modellgesteuerten Ansatzes zur Spracherkennung. Er weist zwei hauptsächliche Merkmale auf: eine hierarchische Struktur, die eine Koexistenz jeder Anzahl von Niveaus von Datendarstellungen erlaubt, und ein HMM-Berechnungsfachwerk durchgehender Dichte, das den Informationsfluß auf allen Niveaus lenkt. Die Details eines Systems, wie des in Fig. 1 gezeigten, sind vollständig in "Chart Parser for Stochastic Unification Grammar" (US-Patentanmeldung Nr. 312,835) beschrieben, die auf den Rechtsnachfolger der vorliegenden Erfindung übertragen ist. Es wurde empirisch gezeigt, daß eine absteigende Erstellung von Hypothesen eine deutliche Verbesserung der Wirksamkeit gegenüber früheren aufsteigenden Systemen ermöglicht.
Unglücklicherweise stellt der absteigende, modellgesteuerte Ansatz, der in dem Spracherkennungsschema verwendet wird, hohe Anforderungen an den Computer, da er in Echtzeit arbeiten muß. Zusätzlich benötigen derzeitige Spracherkennungssysteme einen Bewertungszwischenspeicher von einigen hundert Kilobyte Datenspeicher, der im allgemeinen in einem teueren, schnellen RAM- Speicher gehalten wird. Es ist daher wünschenswert, die von der CPU verwendete Menge an schnellem RAM und dadurch die Systemkosten bei der Verarbeitung eines Spracherkennungsalgorithmus zu verringern.
EP-A-248 377 beschreibt ein Spracherkennungssystem, bei dem diese Ziele durch zwei Niveaus zur Beschneidung unwahrscheinlicher Hypothesen in dem Erkennungsprozess erreicht werden.

Zusammenfassung der Erfindung

Hinsichtlich obiger, mit dem Stand der Technik verbundener Probleme ist es ein Ziel der vorliegenden Erfindung, ein Verfahren zur Reduzierung der Ladevorgänge der Zentralverarbeitungseinheit durch effektives Beschneiden auf zwei Niveaus zu verwirklichen: Durch Verwenden einer Schwellenbewertung und durch Beeinflussen des Zustands, auf den Rückwärtszeiger verweisen.
Ein weiteres Ziel der vorliegenden Erfindung ist, ein Verfahren zu verwirklichen, das in Echtzeit arbeitet und das die Menge an schnellem RAM, die von einem Zentralprozessor bei der Verarbeitung eines Spracherkennungsalgorithmus benötigt wird, kostenwirksam verringert und dadurch die Berechnungszykluszeit minimiert.
Gemäß der vorliegenden Erfindung ist ein Verfahren zur Reduzierung der Ladevorgänge einer Zentralverarbeitungseinheit während einer Spracherkennung verwirklicht, die hierarchische Grammatikschichten umfaßt und bei der Modelle dieser hierarchischen Schichten mehrere Zustände verwenden, die wenigstens einen Startzustand und einen Haltzustand umfassen, wobei zu irgendeinem Zeitpunkt nur einer dieser mehreren Zustände als der aktuelle Zustand bestimmt ist, umfassend:
(a) es wird eine Erkennungsbewertung für den informationstragenden aktuellen Zustand berecnet;
(b) es wird diese Erkennungsbewertung mit einem vorherbestimmten Schwellenwert verglichen, um zu entscheiden, ob der informationstragende aktuelle Zustand aufrechterhalten werden soll;
(c) es wird ein verfügbarer Platz in einem Bewertungszwischenspeicher mit wenigstens einem Platz ausfindig gemacht;
(d) es werden Informationen bezüglich des aktuellen Zustands in dem verfügbaren Platz gespeichert;
(e) es wird ein Bewertungszwischenspeicherplatz-Rückwärtszeiger gesetzt;
(f) es wird ein Wert in dem Feld für den letzten Zeitpunkt in dem verfügbaren Platz gleich einem aktuellen Zeitindex der Zentralverarbeitungseinheit gesetzt;
(g) es wird ein Zeitwert, der dem aktuellen Zeitindex des Schritts (f) entspricht, nach hinten zu allen Bewertungszwischenspeicherplätzen entlang einem Pfad mit der besten Erkennungsbewertung weitergegeben, der zu dem verfügbaren Platz führt, der Informationen über den aktuellen Zustand beinhaltet;
(h) es wird eine Parsing-operation an einem nächsten aktuellen Zustand durchgeführt; und
(i) es werden die Schritte (a) bis (h) wiederholt, bis alle Zustände erledigt worden sind.
Diese Ziele werden bei einem bevorzugten Ausführungsbeispiel durch Verwendung eines Algorithmus erreicht, der die CPU instruiert, die zuvor berechnete Wahrscheinlichkeitsbewertung des aktuellen Zustands mit einem vorbestimmten Schwellenwert zu vergleichen und Hypothesen zu verwerfen, die Zustände mit Wahrscheinlichkeitsbewertungen unter solch einer Schwelle aufweisen. Nach der Bestimmung, daß der aktuelle Zustand aufrechterhalten werden soll, wird die CPU angewiesen, einen verfügbaren Platz in dem Bewertungszwischenspeicher ausfindig zu machen, in dem die Information über den aktuellen Zustand dann gespeichert wird. Die CPU macht einen verfügbaren Platz ausfindig, indem ein aktueller Zeitindex mit dem zu jedem Bewertungszwischenspeicherplatz gehörenden Zeitindex verglichen wird. Wenn diese gleich sind, ist der Platz nicht verfügbar; wenn der aktuelle Zeitindex größer ist, ist der Platz verfügbar.
Nachdem die Information über den aktuellen Zustand gespeichert ist, setzt die CPU den Rückwärtszeiger des aktuellen Zustands, um auf den Startzustand des aktuellen besten Pfads zu zeigen, falls der aktuelle Zustand ein abgeschlossenes Modell repräsentiert. Ungeachtet des Status des aktuellen Zustands ordnet die CPU dann den aktuellen Zeitindex den Zeitindices aller Plätze entlang des besten Pfads zu dem aktuellen Zustand zu. Die CPU berechnet daraufhin die Wahrscheinlichkeitsbewertung des nächsten aktuellen Zustands und der Algorithmus wiederholt sich, bis alle Zustände vervollständigt sind.
Diese und andere Merkmale der Erfindung werden dem Fachmann aus der folgenden detaillierten Beschreibung eines bevorzugten Ausführungsbeispiels in Verbindung mit den beiliegenden Zeich-nungen offensichtlich werden, die folgendes darstellen:

Beschreibung der Zeichnungen

Fig. 1 ist ein Blockdiagramm eines schichtweisen Grammatikansatzes zur Spracherkennung;
Fig. 2 ist eine typische Flußdiagrammdarstellung eines Links- Nach-Rechts Hidden-Markov-Modells;
Fig. 3 ist ein beispielhaftes Flußdiagramm von Zustandspfaden der obersten Schicht, basierend auf einem typischen Satzmodell;
Fig. 4 ist eine beispielhafte Flußdiagrammdarstellung von Zustandspfaden, die für das Satzmodell der Fig. 3 erzeugt wurden und die auf einem Hidden-Markov-Modell basieren;
Fig. 5 ist eine Blockdarstellung eines Bewertungszwischenspeichers, der die vorliegende Erfindung verwenden kann; und
Fig. 6 ist ein Flußdiagramm eines bevorzugten Ausführungsbeispiels der vorliegenden Erfindung.

Beschreibung eines bevorzugten Ausführungsbeispiels

Der Algorithmus der vorliegenden Erfindung kann auf jedem Zentralverarbeitungssystem implementiert werden, was Mehrfachverarbeitungssysterne einschließt, wie beispielsweise die Calypso, entwickelt von Texas Instruments, Inc. Durch Verwenden des Algorithmus auf einem Mehrfachprozessor ist man in der Lage, die HMM Schichten auf mehrere Prozessoren zu verteilen, wodurch es Spracherkennungssysternen möglich ist, ein größeres Vokabular zu erkennen.
Fig. 2 zeigt eine typische Darstellung eines Links-Nach-Rechts Hidden-Markov-Modells (HMM). Bei diesem Beispiel ist der Zustand 0 der Startzustand und Zustand 4 ist der Haltzustand.
Bei einer gegebenen Beobachtungsfolge S&sub0; liegt das Problem darin, die einzige, beste Zustandsfolge zur Erklärung der beobachteten Daten zu finden. Der Viterbi Algorithmus (G. David Fourney Jr., "The Viterbi Algorithm", Proc. of the IEEE, Band 61, Nr. 3, März 1973) wird zum Auffinden dieser besten Zustandsfolge verwendet. Dies wird dargestellt durch pathscoret(j) = max[pathscoret-l(i) + 1n(aij)] + dj l≤i≤n
backpointert(j) = argmax[pathscoret-l,(i)aij + ln(aij)] l≤i≤n
wobei
dj = Wahrscheinlichkeit, daß der Zustand j der Beobachtung S&sub0; zu der Zeit t entspricht,
aij - übergangswahrscheinlichkeit vom Zustand i zum Zustand j,
n - Anzahl der Zustände in dem Modell.
Ein beispielhaftes Flußdiagramm von Pfaden der Zustände der obersten Schicht, basierend auf einer Satzmodellgrammatik, ist in der Fig. 3 gezeigt. Während das Modell durch den Prozessor bewertet wird, werden verschiedene Zustandspfade, die als Verzweigungen dargestellt sind, in Kenntnis der gerade verarbeiteten gesprochenen Eingabe und der verschiedenen programmierten Grammatiken als hypothetisch möglich angesehen. Die gezeigten Hypotheseverzweigungen werden als Ergebnis vorprogrammierter Grammatiken oder Regeln erzeugt, die nur spezifizieren, daß bestimmte Wörter anderen Wörtern folgen können. Die Verwendung solcher Regeln ist im Stand der Technik gut bekannt und wird hier nicht erläutert werden.
Fig. 4 ist eine beispielhafte Darstellung der Zustandspfade, die für das Satzmodell der Fig. 3 erzeugt wurden und die auf einem Hidden-Markov-Modell basieren. HMMS werden im allgemeinen auf andere Schichten der Spracherkennungsgrammatik als das Satzmodell der obersten Schicht angewandt, wie beispielsweise das Wort- oder Satzteil-Niveau und tiefer. Ebenfalls sollte bemerkt werden, daß, auch wenn nur zwei Niveaus (Fig. 3 und 4) gezeigt sind, der Algorithmus der vorliegenden Erfindung erweitert werden kann, um zusätzliche Grammatikschichten bis hinunter zu Block-Niveau-HMMS einzuschließen. Zusätzlich können auf diesem Niveau vorprogrammierte Regeln ebenfalls spezifizieren, welche Buchstaben anderen Buchstaben folgen können.
Betrachtet man nun sowohl Fig. 3 als auch Fig. 4, berechnet ein Prozessor die Anfangswahrscheinlichkeit für den Knoten 60 (Fig. 3), der vor dem Wort "set" erscheint. Um zu bestimmen, ob das Wort "set" gesprochen wurde, gibt der Prozessor diese Wahrscheinlichkeit zu dem Startzustandsknoten 60 der Fig. 4 weiter, und er beginnt eine Parsing-operation. Während der Prozessor bestimmt, daß ein Buchstabe gesprochen wurde, addiert er die Wahrscheinlichkeit, daß dieser Buchstabe gesprochen wurde, zu der bereits existierenden Anfangswahrscheinlichkeit hinzu. Während jeder Buchstabe als gesprochen bestimmt wird, fährt der Prozessor fort, Wahrscheinlichkeiten zu addieren, bis er an dem Haltzustandsknoten 40 anlangt, an dem er die gesamte Wahrscheinlichkeit dafür hat, daß er das Wort "set" gesehen hat. Zu diesem Zeitpunkt gibt der Prozessor diese Wahrscheinlichkeit zu dem Knoten 40 der Fig. 3 zurück.
An diesem Punkt zeigt der Prozessor an, daß er wahrscheinlich das Wort "set" gesehen hat, und er erzeugt zwei Hypothesen dafür, was das nächste Wort sein könnte: "altitude" oder "value". Der Prozeß des Weitergebens von Wahrscheinlichkeitsbewertungen nach hinten und vorne zwischen verschiedenen Grammatikschichten schreitet fort, bis der vollständige gesprochene Satz erkannt ist. Wie zuvor angedeutet wurde, können viele Grammatikschichten vorhanden sein, wobei der Prozessor bei dem Bemühen, die fortlaufende gesprochene Eingabe zu erkennen, Wahrscheinlichkeiten bis zu dem Block-Niveau herunter und wieder herauf weitergibt.
Immer wenn die Wahrscheinlichkeit eines Zustands, der auch als Knoten bezeichnet wird, eines HMM berechnet ist, wird er als bewertet betrachtet. Die Bewertung wird an einem Platz eines Puffers im Speicher gesichert, der als Bewertungszwischenspeicher 12 bezeichnet wird. Fig. 5 zeigt solch einen Bewertungszwischenspeicher 12 mit N Plätzen. Jeder Platz speichert die Pfadbewertung für einen speziellen Zustand, einen Rückwärtszeiger zu seinem vorhergehenden Zustand und weitere Hilfsinformationen. Ein Platz speichert daher verschiedene 16-Bit- Informationswörter. Als Beispiel ist Platz 5 mit acht 16-Bit- Informationswörtern A-H dargestellt. Eines der 16-Bit-Wörter A-H bezeichnet den aktuellen Zeitindex des Platzes. Ein weiteres Wort, beispielsweise das Wort E, bezeichnet die Position des Platzes in dem Bewertungszwischenspeicher 12, der Information über den vorhergehenden Zustand enthält. Die Information, die in dem Wort E gespeichert ist, wird als Rückwärtszeiger bezeichnet. Die verbleibenden Worte enthalten zusätzliche Hilfsinformation, wie beispielsweise die Wahrscheinlichkeitsbewertung des besten Pfades, usw.
Bei fortlaufender Worterkennung wird jedes HMM für jeden Eingabeblock mehrere Male bewertet. Folglich kann der Bewertungszwischenspeicher 12, abhängig von der Komplexität des Satzmodells der obersten Schicht der Fig. 3, mehrere hundert Kilobyte belegen, was die Datenspeicherkapazität einer typischen Zentralverarbeitungseinheit ohne weiteres überschreitet.
Die verschiedenen vorausgesagten Satz-Niveau-Hypothesen müssen gespeichert werden, falls die Hypothese, die anfangs die beste Pfadwahrscheinlichkeit hat, später durch eine konkurrierende Hypthese umgangen wird. Während der ersten Wörter eines Satzes ist die Anzahl konkurrierender Hypothesen hoch. Eine umfangreiche Buchhaltung und daher eine vergleichbare Menge CPU- Speicher ist erforderlich, um diese Hypothesen zu verwalten. Die vorliegende Erfindung verwirklicht ein genaues Beschneideverfahren, um diese Speicher- und CPU-Verarbeitungssanforderungen zu verringern, wie in der folgenden Erörterung dargelegt wird.
Der Algorithmus der vorliegenden Erfindung verwendet zwei Beschneideniveaus. Wenn bestimmte Satzpfade bester Bewertung mit hoher Wahrscheinlichkeit gefunden werden, ist der Abstand zwischen dem besten und dem zweitbesten Satz typischerweise groß und die Anzahl der aktiven Hypothesen kann, basierend auf ihren jeweiligen Wahrscheinlichkeitsbewertungen, beschnitten werden. Das erste Beschneideniveau, wie es in der vorliegenden Erfindung ausgeführt ist, beinhaltet daher das Berechnen einer Wahrscheinlichkeitsschwelle als ein Bruchteil der Wahrscheinlichkeit der aktuellen wahrscheinlichsten Hypothese. Diese wird dann normiert und gleich -1 gesetzt. Hypothesen unterhalb dieser Schwelle werden aufgegeben.
Es sei beispielsweise angenommen, daß der Satzpfad 1 die beste Pfadwahrscheinlichkeitsbewertung von -0,2 hat, Satzpfad 2 eine Wahrscheinlichkeitsbewertung von -0,5 hat, und Satzpfad 3 eine Wahrscheinlichkeitsbewertung von -0,8 hat. Die beste Wahrscheinlichkeit hat den am wenigsten negativen Wert, so daß -0,2 eine bessere Wahrscheinlichkeit als -0,5 ist und daher Pfad 1 gewinnt. Falls der Bediener die maximale Differenz zwischen der besten Pfadbewertung und der Abschneide-Schwelle gleich 0,4 setzt, beträgt der Abschneide-Schwellenwert -0,6 (-0,2 - 0,4 = -0,6). Daher wird die CPU die Pfade 1 und 2 aufrechterhalten und den Pfad 3 verwerfen oder beschneiden.
Ein Beispiel der Wirkung der Beschneideschwelle auf die benötigte Größe des Bewertungszwischenspeichers (bezüglich der Anzahl der Plätze) und die Wirksamkeit der Erkennungseinrichtung ist in Tabelle 1 unten gezeigt. Wie zu sehen ist, wurde bei Anwendungen mit kleinem Vokabular, wie beispielsweise eine fortlaufende Ziffernerkennung, empirisch herausgefunden, daß eine robuste Wirksamkeit mit 2000 für den Bewertungszwischenspeicher belegten Plätzen aufrechterhalten werden kann. Es sollte jedoch bemerkt werden, daß die Anzahl der erforderlichen Plätze von der betreffenden Anwendung abhängt. Tabelle 1: Beschneideschwelle und Speichergröße
Um die Ladevorgänge der CPU weiter zu reduzieren, wird von der vorliegenden Erfindung ein zweites Beschneideniveau verwendet. Diese zweite Niveau beinhaltet, den Prozessor zu unterstützen schnell verfügbare Plätze in dem Bewertungszwischenspeicher aufzufinden und einen Rückwärtszeiger eines Zustands innerhalb eines Modells auf seinen Startzustand zu setzen.
Nach der Bestimmung, daß der aktuelle Zustand aufrechterhalten werden soll, weist der Algorithmus der vorliegenden Erfindung die CPU an, einen verfügbaren Platz in dem Bewertungszwischenspeicher 12 aufzufinden. Entsprechend einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung findet die CPU einen verfügbaren Platz durch Vergleichen des aktuellen Zeitindex mit dem Inhalt des Felds für den letzten Zeitpunkt, das jedem Bewertungszwischenspeicherplatz zugeordnet ist, auf.
Jeder Bewertungszwischenspeicherplatz weist zwei Zeit-Felder auf, ein Feld für den Erzeugungszeitpunkt, das den Zeitindex enthält, zu dem der Platz erzeugt wurde, und ein Feld für den letzten Zeitpunkt, das den Zeitindex des besten Pfads enthält, auf dem dieser Zustand liegt. Alle Plätze auf dem besten Pfad haben denselben Zeitindex-Wert in ihren jeweiligen Feldern für den letzten Zeitpunkt gespeichert und solch ein Wert ist gleich dem aktuellen Zeitindex. Ein Platz wird als frei bezeichnet, wenn der Zeitindex, der in dem Feld für den letzten Zeitpunkt enthalten ist, kleiner ist als der Wert des aktuellen Zeitindex minus eins.
Auf diese Weise kann die CPU schnell einen verfügbaren Platz auffinden, indem nur ein Wort eines Platzes herausgezogen (gelesen) wird, um den Inhalt eines zu einem Platz gehörenden Felds für den letzten Zeitpunkt mit dem aktuellen Zeitindex zu vergleichen. Wenn ein Platz gefunden wird, dessen Zeitindex kleiner ist als der Wert des aktuellen Zeitindex minus eins, hat die CPU einen verfügbaren oder "freien" Platz aufgefunden. Sie wird dann fortfahren, um den Inhalt des verfügbaren Platzes mit Information zu überschreiben, die den aktuellen Zustand betrifft, einschließlich dem Erzeugungszeitindex und dem Zeitindex des Felds für den letzten Zeitpunkt.
Um das Beschneiden eines Platzes in dem besten Pfad zu vermeiden, muß der aktuelle Zeitindex zu allen Plätzen in dem besten Pfad weitergegeben werden. Mit anderen Worten muß der aktuelle Zeitindex, falls die Information des aktuellen Zustands in einem Platz gespeichert ist, entlang all der Plätze, die den besten Pfad enthalten, der zu dem Platz des aktuellen Zustands führt, nach hinten weitergegeben werden. Dieses Weitergeben des Zeitindex nach hinten erhöht jedoch die CPU-Ladevorgänge. Das bevorzugte Ausführungsbeispiel der vorliegenden Erfindung verringert diese Ladevorgänge durch Setzen des Rückwärtszeigers eines Zustands innerhalb eines Modells auf seinen Startzustand.
Als Beispiel sei erneut Fig. 3 betrachtet. Falls der Prozessor bestimmt hat, daß er das Wort "equal" gesehen hat, nachdem die Information, die den aktuellen Zustand oder den Knoten 50 betrifft, in einem verfügbaren Platz gespeichert wurde, würde der Prozessor dann den aktuellen Zeitindex nach hinten zu den jeweiligen Plätzen, die den Knoten 46, den Knoten 40 und den Knoten 60 enthalten, weitergeben. Auf dem Wort-Niveau der Fig. 4 würde der Prozessor den aktuellen Zeitindex nur zu den jeweiligen Plätzen, die die Knoten 40 und 60 enthalten, nach hinten weitergeben. Auch wenn der Prozessor wahrscheinlich das Wort "set" gesehen hat, sind daher die Knoten, durch die das Wort "set" einer Parsing-operation unterzogen wurde, nicht wichtig, sondern nur die Start- und Haltzustände oder -Knoten.
Es sei bemerkt, daß der beste Pfad eines Satzes von Interesse ist und nicht der beste Pfad innerhalb eines Wortmodells. Innerhalb eines Modells, wo der Großteil der CPU-Ladevorgänge auftritt, müssen die Indices des besten Pfads auf diese Weise daher nicht weitergegeben werden, so daß Zeit für das Weitergeben nach hinten eingespart wird und die Berechnungszykluszeit dadurch deutlich verkürzt wird. Ebenfalls sei bemerkt, daß dadurch, daß der Prozessor den aktuellen Zeitindex nicht zu den Plätzen, die die Knoten 62, 64 und 66 enthalten, nach hinten weitergibt, diese Plätze keine aktualisierten Zeitindices, die in deren jeweiligem Feld für den letzten Zeitpunkt enthalten sind, aufweisen, die dem aktuellen Zeitindex entsprechen und daher für den Prozessor verfügbar sein werden, wenn dieser später nach einem freien Platz sucht, wodurch CPU- Speicher und Berechnungszykluszeit eingespart wird.
Fig. 6 ist ein Flußdiagramm eines bevorzugten Ausführungsbeispiels der vorliegenden Erfindung, wie es oben im Detail erläutert wurde.

Claims

1. Verfahren zur Reduzierung der Ladevorgänge einer Zentralverarbeitungseinheit während einer Spracherkennung, die hierarchische Grammatikschichten umfaßt, und bei der Modelle dieser hierarchischen Schichten mehrere Zustände verwenden, die wenigstens einen Startzustand und einen Haltzustand umfassen, wobei zu irgendeinem Zeitpunkt nur einer dieser mehreren Zustände als der aktuelle Zustand bestimmt ist, umfassend:

(a) es wird eine Erkennungsbewertung für den informationstragenden aktuellen Zustand berechnet;

(b) es wird diese Erkennungsbewertung mit einem vorherbestimmten Schwellenwert verglichen, um zu entscheiden, ob der informationstragende aktuelle Zustand aufrechterhalten werden soll;

(c) es wird ein verfügbarer Platz in einem Bewertungszwischenspeicher mit wenigstens einem Platz ausfindig gemacht;

(d) es werden Informationen bezüglich des aktuellen Zustands in dem verfügbaren Platz gespeichert;

(e) es wird ein Bewertungszwischenspeicherplatz-Rückwärtszeiger gesetzt;

(f) es wird ein Wert in dem Feld für den letzten Zeitpunkt in dem verfügbaren Platz gleich einem aktuellen Zeitindex der Zentralverarbeitungseinheit gesetzt;

(g) es wird ein Zeitwert, der dem aktuellen Zeitindex des Schritts (f) entspricht, nach hinten zu allen Bewertungszwischenspeicherplätzen entlang einem Pfad mit der besten Erkennungsbewertung weitergegeben, der zu dem verfügbaren Platz führt, der Informationen über den aktuellen Zustand beinhaltet;

(h) es wird eine Parsing-operation an einem nächsten aktuellen Zustand durchgeführt; und

(i) es werden die Schritte (a) bis (h) wiederholt, bis alle Zustände erledigt worden sind.

2. Verfahren zur Reduzierung der Ladevorgänge einer Zentralverarbeitungseinheit nach Anspruch 1, bei dem der Schritt (c) des Ausf indigmachens eines verfügbaren Platzes umfaßt:

(j) es wird ein Wert in dem zu einem Platz gehörenden Feld für den letzten Zeitpunkt ausgelesen;

(k) es wird der Wert in dem zu einem Platz gehörenden Feld für den letzten Zeitpunkt mit dem aktuellen Zeitindex der Zentralverarbeitungseinheit verglichen;

(l) es wird angezeigt, daß der Platz verfügbar ist, wenn der aktuelle Zeitindex minus eins kleiner als der Wert in dem Feld für den letzten Zeitpunkt ist;

(m) es wird der Platz übergangen, wenn der aktuelle Zeitindex minus eins größer als der Wert in dem Feld für den letzten Zeitpunkt oder gleich dem Wert in dem Feld für den letzten Zeitpunkt ist; und

(n) es werden die Schritte (j) bis (m) wiederholt, bis ein verfügbarer Platz ausfindig gemacht worden ist.

3. Verfahren zur Reduzierung der Ladevorgänge einer Zentralverarbeitungseinheit nach Anspruch 1 oder 2, bei dem der Schritt (b) des Vergleichens der Erkennungsbewertung mit einem vorherbestimmten Schwellenwert umfaßt:

(o) wenn die Erkennungsbewertung größer als der vorherbestimmte Schwellenwert oder gleich dem vorherbestimmten Schwellenwert ist, wird beim Schritt (c) des Ausfindigmachens eines verfügbaren Platzes fortgefahren; und

(p) wenn die Erkennungsbewertung kleiner als der vorherbestimmte Schwellenwert ist, wird dieser Zustand ausgeschieden und zum Schritt (a) des Berechnens einer Bewertung für einen informationstragenden aktuellen Zustand zurückgekehrt.

4. Verfahren zur Reduzierung der Ladevorgänge einer Zentralverarbeitungseinheit nach Anspruch 1, 2 oder 3, bei dem der Schritt (e) des Setzens eines Bewertungszwischenspeicherplatz-Rückwärtszeigers darüber hinaus umfaßt:

(q) wenn der aktuelle Zustand aus der obersten Schicht einer Grammatik stammt, wird der Rückwärtszeiger gesetzt, um die Bewertungszwischenspeicherplatzadresse eines direkt vorhergehenden aktuellen Zustands anzuzeigen; und

(r) wenn der aktuelle Zustand nicht aus der obersten Schicht einer Grammatik stammt, wird der Rückwärtszeiger gesetzt, um den Startzustand des Modells anzuzeigen.

5. Verfahren zur Reduzierung der Ladevorgänge einer Zentralverarbeitungseinheit nach einem der vorhergehenden Ansprüche, bei dem beim Schritt (g) des nach hinten gerichteten Weitergebens eines dem aktuellen Zeitindex entsprechenden Zeitwertes zu allen Bewertungszwischenspeicherplätzen entlang dem Pfad mit der besten Erkennungsbewertung, der zu dem Platz führt, der Informationen über den aktuellen Zustand beinhaltet, die Stellen aller dieser Bewertungszwischenspeicherplätze entlang dem besten Pfad, der zu dem verfügbaren Platz führt, durch den Rückwärtszeiger angezeigt werden.