DE69132761T2

DE69132761T2 - Hochgeschwindigkeitserkennung einer Wortreihe verbunden mit einer Grammatik durch dynamische Programmiervergleiche

Info

Publication number: DE69132761T2
Application number: DE69132761T
Authority: DE
Inventors: Takao Watanabe
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1990-11-28
Filing date: 1991-11-27
Publication date: 2002-07-11
Anticipated expiration: 2011-11-28
Also published as: CA2056294A1; US5287429A; CA2056294C; JPH04195099A; EP0488208A3; DE69132761D1; EP0488208B1; EP0488208A2; JP2697302B2

Description

HOCHGESCHWINDIGKEITSERKENNUNG EINER WORTREIHE VERBUNDEN MIT EINER GRAMMATIK DURCH DYNAMISCHE PROGRAMMIERVERGLEICHE

Diese Erfindung betrifft ein Erkennungsverfahren für verbundene Worte, zum automatischen Erkennen einer Eingangsreihe von Worten, die von einer Eingangsfolge von Eingangsmustermerkmalsvektoren repräsentiert werden, als einer optimalen Wortverknüpfung.
Die Worteingangsreihe wird aus einer Wortgruppe erster bis N-ter Worte ausgewählt und wird im wesentlichen zusammenhängend unter Befolgung einer im Fachgebiet bekannten regulären Grammatik oder einer Grammatik regulärer Sprachen ausgesprochen. Jede Verknüpfung ist eine aus der Wortgruppe selektierte und unter Befolgung der Grammatik verknüpfte Wortreihe. Die Grammatik spezifiziert einen Satz von Übergangsregeln für die ersten bis N-ten Worte und eine Gruppe von Endzuständen der Verknüpfungen. Die Übergangsregel für ein beliebig aus der Wortgruppe ausgewähltes n-tes Wort definiert eine Kombination des n-ten Wortes und eines Zustandspaares, das aus einem Anfangs- und einem Endzustand des n-ten Wortes besteht.
Ein Erkennungssystem für verbundene Worte zur Anwendung bei der Durchführung des Erkennungsverfahrens für verbundene Worte ist in dem Hiroaki Sakoe erteiltem U. S. Patent Nr. 4,555,796 beschrieben. Das Erkennungssystem für verbundene Worte nutzt einen DP (dynamischen programmierenden) Vergleichsalgorithmus auf der Basis einer im Fachgebiet bekannten Rahmensynchronisation. Das heißt, das gemäß einem DP- Algorithmus und unter Befolgung der regulären Grammatik betreibbare Erkennungssystem für verbundene Worte wird synchron mit einer sukzessiven Spezifikation der Eingangsmustermerkmalsvektoren der Eingangsreihe in folgender Weise in Betrieb gesetzt.
In dem Patent von Sakoe weist das Erkennungssystem für verbundene Worte einen Referenzmusterspeicher zum Speichern von das erste bis N-te Worte repräsentierenden Referenzmuster-Merkmalsvektoren auf. Die das n-te Wort repräsentierenden Referenzmuster-Merkmalsvektoren sind der Reihe nach als erste bis J-te Merkmalsvektoren gemäß der Aussprache des nten Wortes numeriert.
Eine Steuerschaltung dient zum Erzeugen eines Grundzeittaktsignals, das sukzessiv den entsprechenden Eingangsmustermerkmalsvektoren zugeordnete erste bis I-te Perioden spezifiziert, eines Wortspezifizierungssignals, welches während eine i-te Periode als jede von den ersten bis I-ten Perioden spezifiziert ist, die ersten bis N-ten Worte spezifiziert, und eines Zustandsspezifizierungssignals, welches während die ite Periode spezifiziert ist, die Zustandspaare der ersten bis N-ten Worte spezifiziert.
Eine Abstandsberechnungsschaltung reagiert auf die Eingangsfolge und ist mit dem Referenzmusterspeicher und der Steuerschaltung verbunden, um, während das n-te Wort in der i-ten Periode spezifiziert ist, mehrere Abstände zwischen dem der i-ten Periode zugeordneten Eingangsmustermerkmalsvektor und den ersten bis J-ten Merkmalsvektoren zu berechnen.
Eine Minimumsuchschaltung ist mit der Steuerschaltung und der Abstandsberechnungsschaltung verbunden, um, während das n-te Wort und jedes Zustandspaar des n-ten Wortes in der i- ten Periode spezifiziert sind, einen Referenzwert g(n, i, j) für das n-te Wort und jedes Zustandspaar unter einer Grenzbedingung iterativ den ersten bis J-ten Merkmalsvektoren entsprechend unter Verwendung der für die n-ten Worte vor der iten Periode berechneten Abstände zu berechnen, wobei n das nte Wort repräsentiert, i die i-te Periode repräsentiert, und j einen Merkmalsvektor repräsentiert, der jeden von den ersten bis J-ten Merkmalsvektoren repräsentiert.
Die Minimumsuchschaltung dient dazu, um, während die i-te Periode spezifiziert ist, ein Minimum T(q, i) der Referenzwerte zu finden, die für die Worte mit Zustandspaaren einschließlich des Endzustands q jedes Zustandspaares berechnet wurden.
Die Minimumsuchschaltung dient zur Entscheidung dieses speziellen Wortes und dieses speziellen Anfangszustandes des speziellen Wortes, für welches das Minimum gefunden wird. Die Grenzbedingung ist gegeben durch T(p, i-1), wobei p den Anfangszustand jedes Zustandspaares darstellt.
Eine Anfangsperioden-Selektionsschaltung ist mit der Steuerschaltung und der Minimumsuchschaltung verbunden, um, während die i-te Periode spezifiziert ist, eine spezielle Periode von den ersten bis (i-1)-ten Perioden bezogen auf den speziellen Anfangszustand und das spezielle Wort zu selektieren.
Eine Entscheidungsschaltung ist mit der Steuerschaltung, der Minimumsuchschaltung und der Anfangsperioden-Selektionsschaltung verbunden, um die optimale Verknüpfung zu entscheiden, in dem sie sich, nach Ablauf der I-ten Periode, auf die in den ersten bis I-ten Perioden gefundenen Minima und die speziellen Worte, die speziellen Anfangszustände und die speziellen Anfangsperioden bezieht, welche in den ersten bis Iten Perioden entschieden werden.
Zusammengefaßt arbeitet das in dem U. S. Patent Nr. 4,555,796 offenbarte Erkennungssystem für verbundene Worte synchron mit einer sukzessiven Spezifikation der Eingangsmustermerkmalsvektoren der Eingangsreihe, um eine Echtzeitverarbeitung der Eingangsreihe wie ein System zur Ausführung der vorliegenden Erfindung auszuführen.
Zu diesem Zweck weist das System von US 4,555,796 eine Steuereinrichtung zum Erzeugen eines Grundzeittaktsignals auf, welches sukzessiv erste bis I-te den entsprechenden Eingangsmustermerkmalsvektoren der Eingangsreihe zugeordnete Perioden spezifiziert (Spalte 20, Zeilen 4-12). Jede von einer Änlichkeits-(oder Abstands [Antonym])-Berechnungseinrichtung, Extremwert-(oder Minimum [Antonym])-Sucheinrichtung und Anfangsperioden-Selektionseinrichtung, führt eine vorbestimmte Operation durch, während die (der i-ten der vorliegenden Beschreibung entsprechende) m-te Periode auf der Basis des Grundzeittaktsignals spezifiziert ist und weitere Signale von der Steuereinrichtung erzeugt werden. Jede von der Ähnlichkeits-Berechnungseinrichtung, Extremwert-Sucheinrichtung und Anfangsperioden-Selektionseinrichtung, führt wiederholt die vorbestimmte Operation aus, sobald eine von den den entsprechenden Eingangsmustermerkmalsvektoren der Eingangsreihe zugeordneten ersten bis I-ten Perioden als die m-te (oder i-te) Periode spezifiziert ist.
Da das Erkennungssystem für verbundene Worte synchron zu der sukzessiven Spezifikation der Eingangsmustermerkmalsvektoren der Eingangsreihe arbeitet, kann das Erkennungssystem für verbundene Worte eine Echtzeitverarbeitung der Eingangsreihe durchführen. Es wird angenommen, daß das n-te Wort in einer mehrfachen Anzahl K der Übergangsregeln als das n-te Wort eines ersten bis K-ten Vorkommens erscheint. In diesem Falle definieren die Übergangsregeln für das n-te Wort des ersten bis K-ten Vorkommens unterschiedliche Anfangszustände, welche sich voneinander unterscheiden. Es ist daher erforderlich, die Verarbeitung für das n-te Wort des ersten bis K-ten Vorkommens unabhängig durchzuführen. Dieses führt zu einem erhöhten Berechnungsaufwand.
Es ist daher eine Aufgabe dieser Erfindung, ein Erkennungsverfahren für verbundene Worte bereitzustellen, welches ein Erkennungsergebnis mit einem verringerten Berechnungsaufwand erzielen kann.
Es ist eine weitere Aufgabe dieser Erfindung, ein Erkennungsverfahren des beschriebenen Typs für verbundene Worte bereitzustellen, welches das Erkennungsergebnis mit hoher Geschwindigkeit bereitstellen kann.
Weitere Aufgaben der Erfindung werden im Verlaufe der Beschreibung ersichtlich.
Die Aufgaben der vorliegenden Erfindung werden durch das von Anspruch 1 offenbarte Verfahren gelöst.
Die vorliegende Erfindung betrifft ein Verfahren zur Erkennung einer von einer Eingangsfolge von Eingangsmustermerkmalsvektoren repräsentierten Worteingangsfolge als eine optimale Wortverknüpfung. Die Worteingangsfolge wird aus einer Wortgruppe erster bis N-ter Worte selektiert und unter Befolgung einer regulären Grammatik im wesentlichen zusammenhängend ausgesprochen. Jede Verknüpfung ist eine aus der Wortgruppe selektierte und unter Befolgung der Grammatik selektierte Reihe von Worten. Die Grammatik spezifiziert eine Gruppe von Übergangsregeln für die ersten bis N-ten Worte und eine Gruppe von Endzuständen der Verknüpfungen. Ein beliebig aus der Wortgruppe gewähltes n-tes Wort erscheint in einer mehrfachen Anzahl K von Übergangsregeln als das n-te Wort des ersten bis K-ten Vorkommens. Jedes von den n-te Worten des ersten bis K-ten Vorkommens definiert eine Kombination des nten Wortes und eines Zustandspaares, das aus einem Anfangs- und einem Endzustand des n-ten Wortes besteht.
Gemäß der vorliegenden Erfindung weist das vorstehende erwähnte Verfahren die Schritte auf: (A) Speichern von Referenzmuster-Merkmalsvektoren, welche die ersten bis N-ten Worte repräsentieren, wobei die das n-te Wort repräsentierenden, Referenzmuster-Merkmalsvektoren fortlaufend als erster bis Jter Merkmalsvektor gemäß der Aussprache des n-ten Wortes numeriert sind; (B) Erzeugen eines Grundzeittaktsignals, das sukzessiv erste bis I-te Perioden spezifiziert, die den entsprechenden Eingangsmustermerkmalsvektoren zugeordnet sind, eines Wortspezifizierungssignals, welches, während eine i-te Periode als jede von den ersten bis I-ten Perioden spezifiziert ist, die ersten bis N-ten Worte spezifiziert, und eines Zustandsspezifizierungssignals, welches, während die i-te Periode spezifiziert ist, die Zustandspaare der ersten bis Nten Worte spezifiziert; (C) Selektieren als Antwort auf die Eingangsfolge und die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das nte Wort in der i-ten Periode spezifiziert ist, eines von dem n-ten Wort des ersten bis K-ten Vorkommens als das selektierte n-te Wort; (D) Berechnen als Antwort auf die Eingangsfolge und die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das n-te Wort in der iten Periode spezifiziert ist, mehrerer Abstände zwischen dem der i-ten Periode zugewiesenen Eingangsmustermerkmalsvektor und den ersten bis J-ten Merkmalsvektoren nur für das selektierten n-te Wort; (E) Berechnen als Antwort auf die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das n-te Wort und jedes Zustandspaar des n-ten Wortes in der i-ten Periode spezifiziert ist, eines Wiedervorkommenswertes g (n, i, j) nur für das selektierte nte Wort und des Zustandspaars für das selektierte n-te Wort unter einer Grenzbedingung iterativ den ersten bis J-ten Merkmalsvektoren entsprechend unter Verwendung der die für das selektierte n-te Wort vor der i-ten Periode berechneten Abstände, wobei n das n-te Wort repräsentiert, i die i-te Periode repräsentiert und j einen j-ten Merkmalsvektor repräsentiert, der jeden von den ersten bis j-ten Merkmalsvektoren repräsentiert, wobei der zuletzt erwähnte Berechnungsschritt den Wiedervorkommenswert für ein nicht selektiertes n-tes Wort unter Verwendung des Wiedervorkommenswertes für das selektierte n-te Wort und der Grenzbedingungen für das selektierte und das nicht selektierte n-te Wort abschätzt, das nicht selektierte n-te Wort ein verbleibendes von dem nten Wort des ersten bis K-ten Vorkommens ist, das nicht durch den Selektionsschritt selektiert ist, der zuletzt erwähnte Berechnungsschritt, während die i-te Periode spezifiziert ist, ein Minimum T(q, i) der Wiedervorkommenswerte findet, die für die Worte mit Zustandspaaren einschließlich des Endzustands q jedes Zustandspaares erhalten wurden, der zuletzt erwähnte Berechnungsschritt dieses spezielle Wort und diesen speziellen Anfangszustand des speziellen Wortes, für welches das Minimum gefunden wird, entscheidet, wobei die Grenzbedingungen durch T(p, i-1) gegeben sind, wovon p den Anfangszustand von jedem Zustandspaar repräsentiert; (F) Selektieren als Antwort auf die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während die i-ten Periode spezifiziert ist, einer speziellen Periode aus den ersten bis (i-1)-ten Perioden unter Bezugnahme auf den speziellen Anfangszustand und das spezielle Wort; und (G) Entscheiden der optimalen Verknüpfung durch Bezugnahme nach Ablauf der I-ten Periode auf die in den ersten bis I-ten Perioden gefundenen Minima, und auf diejenigen speziellen Worte, diejenigen speziellen Anfangszustände, und diejenigen speziellen Anfangsperioden, welche in den ersten bis I-ten Perioden entschieden werden, wobei der zuerst erwähnte Selektionsschritt zur Selektion des einen von dem n-ten Wort des ersten bis K- Vorkommens, das einen Minimumwert der Grenzbedingungen T(p, i-1) aufweist, als das selektierte n-te Wort dient.
Im Vergleich zu der vorliegenden Erfindung befaßt sich US 4,555,796 nicht mit der Tatsache, daß das n-te Wort als der erste bis K-te Vorkommen in den durch die Grammatik definierten Übergangsregeln erscheint.
Daher offenbart US 4,555,796 nicht, daß eines von dem nten Wort des ersten bis K-ten Vorkommens als das selektierte n-te Wort von dem ersten Selektionsschritt in der i-ten Periode selektiert wird, in welcher der n-te Eingangsmustermerkmalsvektor spezifiziert ist.
US 4,555,796 offenbart auch nicht, daß Abstände in der iten Periode nur für das selektierte n-te Wort zwischen dem der i-ten Periode zugeordneten Eingangsmuster-Merkmalsvektoren und den Referenz-Merkmalsvektoren für das n-te Wort durch den ersten Berechnungsschritt berechnet werden und daß der Wiedervorkommenswert g(n, i, j) durch den zweiten Berechnungsschritt in der i-ten Periode nur für das selektierte nte Wort unter der Grenzbedingung T(p, i-1) iterativ den Referenz-Merkmalsvektoren entsprechend unter Verwendung der für das selektierte n-te Wort vor der i-ten Periode berechneten Abstände berechnet wird.
Zusätzlich offenbart US 4,555,796 auch nicht, daß der Wiedervorkommenswert für das nicht selektierte n-te Wort abgeschätzt wird, indem der Wiedervorkommenswert für das selektierte n-te Wort und die Grenzbedingungen T(p, i-1) für die selektierten und nicht selektierten n-ten Worte verwendet wird und daß das vorstehend erwähnte eine von dem n-ten Wort des ersten und bis zu dritten Vorkommens so selektiert wird, daß es einen Minimalwert von den T(p, i-1)'s aufweist.

Kurzbeschreibung der Zeichnungen

In den Zeichnungen ist:
Fig. 1 ein Zustandsübergangsdiagramm von Zuständen zur Verwendung bei der Beschreibung eines herkömmlichen Erkennungsverfahrens für verbundene Worte;
Fig. 2 ein Programm zur Verwendung bei der Beschreibung des herkömmlichen Erkennungsverfahrens für verbundene Worte;
Fig. 3 ein Zustandsübergangsdiagramm von Zuständen zur Verwendung bei der Beschreibung eines Erkennungsverfahrens für verbundene Worte gemäß einer Ausführungsform dieser Erfindung;
Fig. 4 ein Programm zur Verwendung bei der Beschreibung eines Erkennungsverfahrens für verbundene Worte gemäß der Ausführungsform dieser Erfindung; und
Fig. 5 ein Blockschaltbild eines Erkennungssystem für verbundene Worte zur Verwendung bei der Ausführung des Erkennungsverfahrens für verbundene Worte gemäß der Ausführungsform dieser Erfindung.

Beschreibung der bevorzugten Ausführungsform

Unter Bezugnahme auf Fig. 1 und 2 wird zuerst für ein besseres Verständnis dieser Erfindung ein herkömmliches Erkennungsverfahren für verbundene Worte beschrieben. Das herkömmliche Erkennungsverfahren für verbundene Worte ist im wesentlichen zu dem in der Einführung dieser Beschreibung beschriebenen Erkennungsverfahren für verbundene Worte äquivalent.
Das Erkennungsverfahren für verbundene Worte dient zur automatischen Erkennung einer Eingangsreihe A aus Worten als ein optimale Wortverknüpfung. Die Eingangsreihe A aus Worten wird von einer Eingangsfolge erster bis I-ter Eingangsmuster- Merkmalsvektoren a1 bis a1 wie z. B.:
A = a&sub1;, a&sub2;, ... aI
repräsentiert. Die Eingangsreihe A aus Worten wird aus einer Wortgruppe erster bis N-ter Worte ausgewählt und im wesentlichen unter Befolgung einer regulären Grammatik zusammenhängend ausgesprochen. Bei der Selektion der Worte ist laut Grammatik eine Wiederholung zulässig. Es ist möglich, die ersten bis N-ten Worte durch fortlaufende natürlichen Zahlen zu identifizieren oder zu bezeichnen. Es wird angenommen, daß die Wortgruppe aus den ersten bis N-ten Worten 1 bis N besteht.
Jede von den Wortverknüpfungen ist eine Reihe aus der Wortgruppe selektierter und unter Befolgung der Grammatik verknüpfter Worte. Die Grammatik spezifiziert eine Gruppe von Übergangsregeln für die ersten bis N-ten Worte und eine Gruppe von Endzuständen der Verknüpfungen. Die Übergangsregel für ein beliebig aus der Wortgruppe selektiertes n-tes Wort n definiert eine Kombination des n-ten Wortes n und eines Zustandspaares, das aus Anfangs- und Endzuständen des n-ten Wortes n besteht.
In Fig. 1 ist der Zustandsübergang von einem Anfangszustand S0 zu einem ersten möglichen Zustand S1 über zwei verschiedene Pfade für aus der Wortgruppe selektierte unterschiedliche Worte möglich. Dem ersten möglichen Zustand S1 folgt ein zweiter möglicher Zustand S2 über einen Pfad für ein Wort, welches aus der Wortgruppe ausgewählt ist und welches in Fig. 1 beispielsweise als n dargestellt ist. In dem dargestellten Beispiel definiert die Übergangsregel für das Wort n eine Kombination des Wortes n und eines Zustandspaares, das aus Anfangs- und Endzuständen p(n) und q(n) des Wortes n besteht. Zur Verallgemeinerung der Bezeichnung werden die Anfangs- und Endzustände mit p und q bezeichnet. Dem zweiten möglichen Zustand S2 folgt ein möglicher Endzustand Sf über einen weiteren Pfad für ein weiteres Wort. In gleicher Weise ist der Zustandsübergang auch von dem Anfangszustand S0 zu dem Endzustand Sf über dritte bis fünfte S3, S4 und S5 mögliche Zustände möglich. Der Zustandsübergang ist ferner von dem Anfangszustand S0 zu dem Endzustand Sf über den dritten und fünften Zustand S3 und S5 möglich.
Gemäß dem Erkennungsverfahren für verbundene Worte sind für die ersten bis N-ten Worte repräsentative Referenzmuster-Merkmalsvektoren in einem (nicht dargestellten) Referenzmusterspeicher als erste bis N-te Referenzmuster B¹ bis BN gespeichert. Ein für das n-te Wort n repräsentatives Referenzmuster Bn ist durch erste bis J-te Referenzmuster-Merkmalsvektoren b1n bis bJ beispielsweise gegeben als:
Bn = b&sub1;n, b&sub2;n, ..., bJn.
Abhängig von den Umständen wird der Affix "n" weggelassen. Die ersten bis J-ten Referenzmuster-Merkmalsvektoren b&sub1; bis bJ sind sukzessiv gemäß der Aussprache des n-ten Wortes n angeordnet. Lediglich zur Abkürzung der Beschreibung werden die ersten bis J-ten Referenzmuster-Merkmalsvektoren b&sub1; bis bJ als erste bis J-te Merkmalsvektoren b&sub1; bis bJ bezeichnet.
Ein Grundzeittaktsignal wird von einer (nicht dargestellten) Steuerschaltung erzeugt, um sukzessiv erste bis I-te Perioden zu spezifizieren, welche den entsprechenden Eingangsmuster-Merkmalsvektoren a&sub1; bis aI zugeordnet sind. Ein Wortspezifizierungssignal wird ebenfalls von der Steuerschaltung erzeugt, um die ersten bis N-ten Worte 1 bis N zu spezifizieren, während eine i-te Periode als jede von den ersten bis Iten Perioden spezifiziert ist. Ein Zustandsspezifizierungssignal wird ferner von der Steuerschaltung erzeugt, um die Zustandspaare der ersten bis N-ten Worte 1 bis N zu spezifizieren, während die i-te Periode spezifiziert ist.
Während das n-te Wort n in der i-ten Periode spezifiziert ist, werden mehrere Abstände zwischen dem der i-ten Periode zugeordneten Eingangsmuster-Merkmalsvektor und den ersten bis J-ten Merkmalsvektoren b&sub1; bis bJ mittels einer (nicht dargestellten) Abstandsberechnungsschaltung berechnet.
Während das n-te Wort n und jedes Zustandspaar des n-ten Wortes n in der i-ten Periode spezifiziert sind, wird ein Wiedervorkommenswert g(n, i, j) von einer (nicht dargestellten) Minimumsuchschaltung für das n-te Worte n und das jeweilige Zustandspaar unter einer Grenzbedingung iterativ den ersten bis J-ten Merkmalsvektoren entsprechend unter Verwendung der für das n-te Wort vor der i-ten Periode berechneten Abstände berechnet, wobei n das n-te Wort repräsentiert, i die i-te Periode repräsentiert, und j einen j-ten Merkmalsvektor repräsentiert, der jeden der ersten bis J-ten Mermalsvektoren repräsentiert.
Die Minimumsuchschaltung findet, während die i-te Periode spezifiziert ist, ein Minimum T(q, i) der für die Worte mit Zustandspaaren einschließlich des Endzustands q des jeweiligen Zustandspaares berechneten Wiedervorkommenswerte.
Die Minimumsuchschaltung entscheidet dieses spezielle Wort und diesen speziellen Anfangszustand des speziellen Wortes, für welches das Minimum gefunden wird. Die Grenzbedingung ist durch T (p, i-1) gegeben, wobei p den Anfangszustand des jeweiligen Zustandspaares darstellt.
Während die i-te Periode spezifiziert ist, wird eine spezielle Periode von einer (nicht dargestellten) Anfangsperiodenselektionsschaltung von den ersten bis zu den (i-1)-ten Perioden unter Bezugnahme auf den speziellen Anfangszustand und das spezielle Wort selektiert.
Die optimale Verknüpfung wird durch eine (nicht dargestellte) Entscheidungsschaltung entschieden, indem nach Ablauf der I-ten Periode auf das in den ersten bis I-ten Perioden gefundene Minimum und auf diejenigen speziellen Worte, diejenigen speziellen Anfangszustände und diejenigen speziellen Anfangsperioden Bezug genommen wird, welche in den ersten bis I-ten Perioden entschieden werden.
Da die Operation synchron zu einer sukzessiven Spezifikation der Eingangsmuster-Merkmalsvektoren a&sub1; bis aI der Eingangsfolge A in dem Erkennungsverfahren für verbundene Worte gesteuert wird, ist es möglich, eine Echzeitverarbeitung der Eingangsfolge A durchzuführen.
Die Verarbeitung der Eingangsfolge wird in dem Erkennungsverfahren für verbundene Worte in der in Fig. 2 dargestellten Weise durchgeführt. In Fig. 2 repräsentiert j einen Zeitpunkt eines j-ten Referenzmuster-Merkmalsvektors bin, der beliebig aus den ersten bis J-ten Referenzmuster-Merkmalsvektoren b&sub1;n bis bJn selektiert wird. Zusätzlich repräsentiert pp(n) eine Zustandsnummer des Zustands p(n) unmittelbar vor dem Erscheinen des n-ten Wortes n, und qqn repräsentiert eine weitere Zustandsnummer des Zustands q(n) unmittelbar nach dem Erscheinen des n-ten Wortes n. T(p, i) repräsentiert ein Minimum (oder einen minimalen akkumulierten Abstand), wenn die Verarbeitung den Anfangszustand p bei der i-ten Periode erreicht. N (p, i) repräsentiert eine Wortnummer des Wortes auf einem optimalen Pfad unmittelbar bevor die Verarbeitung den Zustand p bei der i-ten Periode erreicht. L(p, i) repräsentiert einen Zeitpunkt des Anfangszustandes des Wortes auf einem optimalen Pfad unmittelbar bevor die Verarbeitung den Zustand p bei der i-ten Periode erreicht. Ferner repräsentiert g (n, i, j) eine Wiedervorkommenswert für das Wort n zu einem Zeitpunkt des j-ten Referenzmuster-Merkmalsvektors bin während der i-ten Periode. Zusätzlich repräsentiert d(n, i, j) einen Abstand zwischen dem der i-ten Periode zugeordneten Eingangsmuster-Merkmalsvektor und dem j-ten Referenzmuster-Merkmalsvektor bin des Wortes n. Ferner repräsentiert 1(n, i, j) einen Zeitpunkt des Anfangszustandes des Wortes n auf einem optimalen Pfad unmittelbar bevor die Verarbeitung den j-ten Referenzmuster-Merkmalsvektor bin bei dem i-ten Intervall erreicht. Ein Symbol "arg min" repräsentiert die Selektion eines Parameter m*, der ein in ein Klammerpaar eingeschlossenes Argument minimiert.
Unter Bezugnahme auf Fig. 3 und 4 fährt die Beschreibung mit einem Erkennungsverfahren für verbundene Worte gemäß einer Ausführungsform dieser Erfindung fort. Es wird angenommen, daß das beliebig aus einer Wortgruppe ausgewählte Wort n in einer mehrfachen Anzahl Kn der Übergangsregeln als das nte Wort n des ersten bis Kn-ten Vorkommens erscheint. Jedes n-te Wort n des ersten bis Kn-ten Vorkommens definiert eine Kombination des n-ten Wortes n und eines Zustandspaares, das aus einem Anfangszustand und einem Endzustand des n-ten Wortes besteht.
Das Erkennungsverfahren für verbundene Worte weist einen ersten Schritt zum Speichern von Referenzmuster-Merkmalsvektoren auf, welche die ersten bis N-ten Worte repräsentieren. Die das n-te Wort repräsentierenden Referenzmuster-Merkmalsvektoren sind fortlaufend als erste bis J-te Merkmalsvektoren B&sub1;n bis BJn gemäß der Aussprache der n-ten Worte numeriert ist.
Das Verfahren weist ferner einen zweiten Schritt zum Erzeugen eines Grundzeittaktsignals auf, das sukzessiv erste bis I-te Perioden spezifiziert, die den entsprechenden Eingangsmustermerkmalsvektoren zugeordnet sind, eines Wortspezifizierungssignals, welches, während eine i-te Periode als jede von den ersten bis I-ten Perioden spezifiziert ist, die ersten bis Nten Worte spezifiziert, und eines Zustandsspezifizierungssignals, welches, während die i-te Periode spezifiziert ist, die Zustandspaare der ersten bis N-ten Worte spezifiziert.
Das Verfahren weist einen dritten Schritt auf, um als Antwort auf die Eingangsfolge und die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das n-te Wort in der i-ten Periode spezifiziert ist, eines von dem n-ten Wort des ersten bis K-ten Vorkommens als ein selektiertes n-te Wort zu selektieren. Das selektierte Wort wird hierin nachstehend als das n-te Wort n des selektierten Vorkommens berechnet.
Das Verfahren weist einen vierten Schritt auf, um als Antwort auf die Eingangsfolge und die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das n-te Wort in der i-ten Periode spezifiziert ist, mehrere Abstände zwischen dem der i-ten Periode zugewiesenen Eingangsmuster-Merkmalsvektor und den ersten bis J-ten Merkmalsvektoren nur für das selektierte n-te Wort zu berechnen.
Das Verfahren weist einen fünften Schritt auf, um, während das n-te Wort n und jedes Zustandspaar des n-ten Wortes n in der i-ten Periode spezifiziert ist, einen Wiedervorkommenswert g(n, i, j) nur für das selektierte n-te Wort und das Zustandspaar für das selektierte n-te Wort unter einer Grenzbedingung iterativ den ersten bis J-ten Merkmalsvektoren entsprechend unter Verwendung der Abstände, die für das selektierte n-te Wort vor der i-ten Periode berechnet wurden, zu berechnen, wobei n das n-te Wort repräsentiert, i die i-te Periode repräsentiert und j einen j-ten Merkmalsvektor repräsentiert, der jeden von den ersten bis j-ten Merkmalsvektoren repräsentiert. Der fünfte Schritt dient zur Abschätzung des Wiedervorkommenswertes für ein nicht selektiertes n-tes Wort unter Verwendung des Wiedervorkommenswertes für das selektierte n-te Wort n und der Grenzbedingungen für das selektierte und das nicht selektierte n-te Wort n. Das nicht selektierte n-te Wort n ist ein verbleibendes von dem n-ten Wort n des ersten bis K-ten Vorkommens, das nicht durch den dritten Schritt selektiert ist. Der fünfte Schritt dient, während die i-te Periode spezifiziert ist, zum Suchen eines Minimums T(q, i) der Wiedervorkommenswerte, die für die Worte mit Zustandspaaren einschließlich des Endzustands q des jeweiligen Zustandspaares erhalten wurden. Der fünfte Schritt dient zur Entscheidung dieses speziellen Wortes und dieses speziellen Anfangszustands für welches das Minimum gefunden wird. Die Grenzbedingungen sind durch T(p, i-1) gegeben, wovon p den Anfangszustand von jedem Zustandspaar repräsentiert.
Das System weist ferner einen sechsten Schritt auf, um als Antwort auf die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während die i-te Periode spezifiziert ist, eine spezielle Periode aus den ersten bis (i-1)-ten Perioden unter Bezugnahme auf den speziellen Anfangszustand und das spezielle Wort zu selektieren, und einen siebenten Schritt, um die optimale Verknüpfung zu entscheiden, indem nach Ablauf der I-ten Periode auf die in den ersten bis I-ten Perioden gefundenen Minima, und auf diejenigen speziellen Worte, diejenigen speziellen Anfangszustände, und diejenigen speziellen Anfangsperioden, welche in den ersten bis I-ten Perioden entschieden werden Bezug genommen wird.
Der dritte Schritt dient zur Selektion des vorstehend erwähnten einen von dem n-ten Wort n des ersten bis K- Vorkommens, das einen Minimumwert der Grenzbedingungen T(p, i-1) aufweist, als ein selektiertes n-tes Wort.
In Fig. 3 tritt das Wort n wiederholt in einer mehrfachen Anzahl Kn von Übergangsregeln gemäß der Grammatik auf. In diesem dargestellten Beispiel tritt das Wort n wiederholt in drei Übergangsregeln, gemäß Darstellung durch n(1), n(2), und n(3) auf. Das heißt die Anzahl Kn ist gleich 3. Die Übergangsregel für das Wort n(k) definiert eine Kombination des Wortes n(k) und eines aus einer Anfangszustandsnummer pp(k, n) des Anfangszustandes des Wortes n(k) und einer Endzustandsnummer qq(k) des Endzustandes des Wortes n(k) bestehenden Zahlenpaares, wobei k jeden Wert von 1 bis Kn repräsentiert. In dem dargestellten Beispiel sind die Anfangszustandsnummer pp(1, n) und die Endzustandsnummer qq(1, n) gleich 2 bzw. 3. Die Anfangszustandsnummer pp(2, n) und die Endzustandsnummer qq(2, n) sind gleich 4 bzw. 6. Ebenso sind die Zustandsnummern pp(3, n) und qq(3, n) gleich 5 bzw. 6.
Die Verarbeitung der Eingangsreihe A wird in dem Erkennungsverfahren für verbundene Worte in der in Fig. 4 dargestellten Art durchgeführt. In Fig. 4 repräsentiert f(n,i) einem Minimumwert der Minima oder der Grenzbedingungen T(p, i- 1) für die Worte n(1), ..., n(Kn) dar. Gemäß dieser Erfindung wird zuerst eine spezielle Übergangsregel mit dem Minimumwert f(n,i) aus den Übergangsregeln für die Worte n(1), .... n(Kn) selektiert, und dann eine Wortvergleichsverarbeitung nur für ein von der speziellen Übergangsregel definiertes spezielles Wort ausgeführt. In diesem Falle wird der Minimumwert f (n,i) in einem (später dargestellten) Übereinstimmungspuffer gespeichert. Wenn die Wortvergleichsverarbeitung für das spezielle Wort zu einen Ende kommt, werden der Wiedervorkommenswert g(n,i,Jn) und der Zeitpunkt 1(n, i, Jn) des Anfangszustands des speziellen Wortes erhalten. Für die Worte n(1), n(Kn) außer dem speziellen Wort, die nicht der Wortvergleichsverarbeitung unterzogen werden, werden die Wiedervorkommenswerte wie folgt abgeschätzt:
g(n,i,Jn) - f(n,1(n,i,Jn) + g(pp(k,n), 1(n,i,Jn)).
Das heißt eine Differenz zwischen g(pp(k,n), 1(n,i,Jn)) und f(n,1(n,i,Jn) wird zu g(n,i,Jn) hinzuaddiert.
Unter Bezugnahme auf Fig. 5 und fortgesetzten Bezug auf Fig. 4 fährt die Beschreibung mit einem Erkennungssystem für verbundene Worte zur Verwendung in dem Erkennungsverfahren für verbundene Worte gemäß der Ausführungsform dieser Erfindung fort. Ein Eingangsmusterspeicher 11 speichert die Eingangsreihe A der Worte. Ein Referenzmusterspeicher 12 speichert das Referenzmuster Bn.
Eine Abstandsberechnungsschaltung 13 liest die Eingangsreihe A und das Referenzmuster Bn aus dem Eingangs- und dem Referenzmusterspeicher 11 und 12 aus und berechnet den Abstand d(n,i,j) zwischen den Merkmalsvektoren ai und bjn, um den Abstand d(n,i,j) in einem Abstandspuffer 14 zu speichern.
Ein Wortvergleichspuffer 16 dient zum Speichern des Wiedervorkommenswertes (oder eines akkumulierten Vergleichsabstandes g(n,i,J) der durch die Wortvergleichsverarbeitung erhalten wird.
Eine Wortvergleichsverarbeitungsschaltung 15 liest während der i-ten Periode den Abstand d(n,i,j) und den akkumulierten Vergleichsabstand g(n,i-1,J) aus den Puffern 14 und 16 aus und führt die Wortvergleichsverarbeitung für jedes Wort n gemäß einer Gruppe (b) von Ausdrücken von Fig. 4 durch, um den akkumulierten Vergleichsabstand g(n,i,J) zu erhalten. Der akkumulierte Vergleichsabstand g(n,i,J) wird in dem Vergleichspuffer 16 gespeichert.
Eine Wortgrenzwert-Verarbeitungsschaltung 18 liest die Zustandsübergangsregeln und Grenzwertbedingungen aus einem Zustandsübergangsregelspeicher 17 und einen Wortgrenzwertpuffer 20 aus und berechnet Anfangswerte für die Wortvergleichsverarbeitung gemäß einer Gruppe (a) von Ausdrücken von Fig. 4, um die Anfangswerte in einem Puffer 19 für akkumulierte Abstände und in dem Wortvergleichspuffer 16 zu speichern, Die Verarbeitungsschaltung 18 berechnet gemäß einer Gruppe (c) der Ausdrücke von Fig. 4 und unter Verwendung eines Ergebnisses der Wortvergleichsverarbeitung einen akkumulierten Abstand für die Übergangsregeln, welcher nicht der Wortvergleichsverarbeitung unterworfen ist. Die Verarbeitungsschaltung 18 speichert dadurch den akkumulierten Abstand in dem Wortgrenzwertpuffer 10.
Nach Ablauf der I-ten Periode liest eine Entscheidungsschaltung 21 einen Inhalt des Wortgrenzwertpuffers 20 aus und erzeugt eine Reihe von Worten als ein Ergebnis der Erkennung unter Verwendung einer Umkehrsteuerungsprozedur gemäß den Ausdrücken von Fig. 4.

Claims

1. Verfahren zur Erkennung einer von einer Eingangsfolge von Eingangsmustermerkmalsvektoren repräsentierten Worteingangsfolge als eine optimale Wortverknüpfung, wobei die Worteingangsfolge aus einer Wortgruppe erster bis N-ter Worte selektiert und unter Befolgung einer regulären Grammatik zusammenhängend ausgesprochen wird, N eine ganze Zahl größer als Eins repräsentiert, jede Verknüpfung eine aus der Wortgruppe selektierte und unter Befolgung der Grammatik selektierte Reihe von Worten ist, die Grammatik eine Gruppe von Übergangsregeln für die ersten bis N-ten Worte und eine Gruppe von Endzuständen der Verknüpfungen spezifiziert, ein beliebig aus den ersten bis Nten Worten der Wortgruppe selektiertes n-tes Wort in einer mehrfachen Anzahl K von Übergangsregeln als das n-te Wort des ersten bis K-ten Vorkommens erscheint, jedes von dem n-ten Wort des ersten bis K-ten Vorkommens eine Kombination des n-ten Wortes und eines Zustandspaares definiert, das aus einem Anfangs- und einem Endzustand des nten Wortes besteht und das Verfahren die Schritte aufweist:

Speichern von Referenzmuster-Merkmalsvektoren, welche die ersten bis N-ten Worte repräsentieren, wobei die das n-te Wort repräsentierenden Referenzmuster-Merkmalsvektoren fortlaufend als erster bis J-ter Merkmalsvektor gemäß der Aussprache des n-ten Wortes numeriert sind, wobei J ein weitere ganze Zahl repräsentiert, die größer als Eins ist;

Erzeugen eines Grundzeittaktsignals, das sukzessiv erste bis I-te Perioden spezifiziert, die den entsprechenden Eingangsmustermerkmalsvektoren zugeordnet sind, eines Wortspezifizierungssignals, welches, während eine i-te Periode als jede von den ersten bis I-ten Perioden spezifiziert ist, die ersten bis N-ten Worte spezifiziert, und eines Zustandsspezifizierungssignals, welches, während die i-te Periode spezifiziert ist, die Zustandspaare der ersten bis N-ten Worte spezifiziert, wobei I ein weitere ganze Zahl repräsentiert, die größer als Eins ist;

Selektieren als Antwort auf die Eingangsfolge und die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das n-te Wort in der i-ten Periode spezifiziert ist, eines von dem n-ten Wort des ersten bis K-ten Vorkommens als ein selektiertes ntes Wort;

Berechnen als Antwort auf die Eingangsfolge und die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das n-te Wort in der i-ten Periode spezifiziert ist, mehrerer Abstände zwischen dem der i-ten Periode zugewiesenen Eingangsmustermerkmalsvektor und den ersten bis J-ten Merkmalsvektoren nur für das selektierte n-te Wort;

Berechnen als Antwort auf die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während das n-te Wort und jedes Zustandspaar des nten Wortes in der i-ten Periode spezifiziert sind, eines Wiedervorkommenswertes g(n, i, j) nur für das selektierte n-te Wort und des Zustandspaars für das selektierte n-te Wort und des Zustandspaars für das selektierte Wort unter einer Grenzbedingung iterativ den ersten bis J-ten Merkmalsvektoren entsprechend unter Verwendung der Abstände, die für das selektierte n-te Wort vor der i-ten Periode berechnet wurden, wobei n das n-te Wort repräsentiert, i die i-te Periode repräsentiert und j einen für jeden von den ersten bis j-ten Merkmalsvektoren repräsentativen j- ten Merkmalsvektor repräsentiert, wobei der zuletzt erwähnte Berechnungsschritt den Wiedervorkommenswert für ein nicht selektiertes n-tes Wort unter Verwendung des Wiedervorkommenswertes für das selektierte n-te Wort und der Grenzbedingungen für das selektierte und das nicht selektierte n-te Wort abschätzt, das nicht selektierte nte Wort ein verbleibendes von dem n-ten Wort des ersten bis K-ten Vorkommens ist, das nicht durch den Selektionsschritt selektiert ist, der zuletzt erwähnte Berechnungsschritt, während die i-te Periode spezifiziert ist, ein Minimum T(q, i) der Wiedervorkommenswerte findet, die für die Worte mit Zustandspaaren einschließlich des Endzustands q des jeweiligen Zustandspaares erhalten wurden, der zuletzt erwähnte Berechnungsschritt dieses spezielle Wort und diesen speziellen Anfangszustand des speziellen Wortes, für welches das Minimum gefunden wird, entscheidet, und die Grenzbedingungen durch T(p, i-1) gegeben sind, wovon p den Anfangszustand von dem jeweiligen Zustandspaar repräsentiert;

Selektieren als Antwort auf die Grundzeittakt-, die Wortspezifizierungs- und die Zustandspezifizierungssignale, während die i-te Periode spezifiziert ist, einer speziellen Periode aus den ersten bis (i-1)-ten Perioden unter Bezugnahme auf den speziellen Anfangszustand und das spezielle Wort; und

Entscheiden der optimalen Verknüpfung durch Bezugnahme nach Ablauf der I-ten Periode auf die in den ersten bis I-ten Perioden gefundenen Minima, und auf diejenigen speziellen Worte, diejenigen speziellen Anfangszustände, und diejenigen speziellen Anfangsperioden, welche in den ersten bis I-ten Perioden entschieden werden;

wobei der zuerst erwähnte Selektionsschritt zur Selektion des einen von dem n-ten Wort des ersten bis K- Vorkommens, das einen Minimumwert der Grenzbedingungen T(p, i-1) aufweist, als das selektierte n-te Wort dient.