DE69309465T2

DE69309465T2 - Wort/Nummer- und Nummer/Wort-Abbildung

Info

Publication number: DE69309465T2
Application number: DE69309465T
Authority: DE
Inventors: Ronald M Kaplan; Martin Kay
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1993-10-19
Filing date: 1993-10-19
Publication date: 1997-09-18
Anticipated expiration: 2013-10-20
Also published as: ES2100473T3; EP0649105A1; DE69309465D1; EP0649105B1

Description

Die vorliegende Erfindung betrifft Verfahren zum Umwandeln von Wörtern in Zahlen und Zahlen in Wörter.
Lucchesi, C.L. und Kowaltowski, T., "Applications of Finite Automata Representing Large Vocabularies", Software -- Practice and Experience, Band 23(1), Januar 1993, Seiten 15-30, beschreiben, angeregt durch das Problem der Verwirklichung eines wirksamen Rechtschreibungsprüfers, Verfahren zum Verdichten eines sehr großen Vokabulars in einen minimalen, azyklischen, deterministischen endlichen Automaten. Fig. 4 zeigt einen solchen Automaten für alle Formen von bestimmten englischen Verben. Ein Verfahren zum Konstruieren des Automaten wird beginnend auf Seite 18 beschrieben; das Verfahren umfaßt einen Minimierungsschritt. Die Datenstruktur wird auf Seiten 19-20 beschrieben: Jeder Zustand wird als ein Feld mit N Einträgen dargestellt, worin N die Größe des Alphabetes ist. Die meisten Einträge entsprechen nichtvorhandenen übergängen, und Zustandsfelder können daher so verschoben und überdeckt werden, daß bestehende Einträge nicht kollidieren. An Jeden Zustand ist ein N-Bit Vektor angefügt, der die bestehenden übergänge für den Zustand auswählt. Die Felder werden durch einen gierigen Algorithmus gepackt, der wegen des sehr großen Prozentsatzes von Zuständen mit einem, zwei oder drei übergängen fast immer optimale Ergebnisse liefert. Außerdem ist die Anzahl von bestimmten Bitvektoren viel niedriger als die Anzahl von Zuständen, so daß viele gemeinsam benutzt werden. Abgesehen vom Packen der Zustandsfelder werden kurze (relativ) und lange (absolute) Zustandsindexe verwendet. Für Portugiesisch werden Buchstaben von ihren diakritischen Zeichen abgestreift, deren Positionen nach dem Wortterminator codiert werden. Seiten 26-27 beschreiben minimal perfektes Haschieren in bezug auf Fig. 8-10. Der Automat umfaßt für jeden Zustand eine Ganzzahl, die die Anzahl von Wörtern angibt, die durch den Automaten beginnend bei diesem Zustand angenommen werden würden, und zwei einfache Funktionen implementieren eine Eins-zu-Eins-Entsprechung zwischen den Ganzzahlen 1 bis L, wo L die Anzahl von durch den Automaten angenommenen Wörtern und der Wörter selbst ist.
Um in einem digitalen Datenverarbeitungssystem eine Folge von Elementen, z.B. ein Wort, zu bearbeiten, ist es häufig erwünscht, zwischen Wörtern und Zahlen umzuwandeln. Während Wörter in der Länge stark variieren, kann die Zahl eines Wortes normalerweise digital als eine Binärzahl einer festen Länge ausgedrückt werden, die kürzer ist als die digitalen Codes für die Zeichen dieses Wortes. Das Bearbeiten der Binärzahlen ist folglich weit effizienter als das Bearbeiten der Wörter selbst. Ein weiterer Grund zum Umwandeln eines Wortes in eine Zahl ist, eine Adresse oder einen Zeiger zum Zugreifen auf für dieses Wort relevante Information zu erlangen.
Die vorliegende Erfindung befaßt sich mit dem Problem, wie eine Wortzu-Zahl- (W/N) und Zahl-zu-Wort- (N/W) Umwandlung wirksam durchzuführen ist. Die Erfindung beruht auf der Entdeckung eines Verfahrens, das eine wirksame W/N- und N/W-Umwandlung zwischen einer Liste von Wörtern und einem dichten Satz von Zahlen erlaubt, von denen jede eine eindeutige Zahl für eines der Wörter ist. Wie hierin verwendet kann der Begriff "Umwandlung" W/N- oder N/W-Umwandlung einschließen.
Erfindungsgemäß kann die W/N- oder N/W-Umwandlung zwischen einer Liste von Wörtern und einem dichten Satz von Zahlen durchgeführt werden, indem Daten, die die Wörter in der Wortliste in der Reihenfolge anzeigen, abgetastet werden, um eine genaue Zählung von überquerten Wörtern zu unterhalten. Bei der W/N-Umwandlung können Daten, die eine geordnete Wortliste anzeigen, abgetastet werden, während nach einem Wort gesucht wird und eine Zählung von Nachsilbenendungen unterhalten wird. Bei der N/W-Umwandlung können Daten, die eine geordnete Wortliste bezeichnen, abgetastet werden, während eine Zählung von Nachsilbenendungen und eine Aufzeichnung des momentanen Wortes unterhalten werden.
Um die Umwandlung effizienter durchzuführen, wird Information bereitgestellt, die es möglich macht, Teile von Daten, die eine geordnete Wortliste bezeichnen, zu überspringen. Wenn z.B. die Daten strukturiert sind, Verzweigungen zu enthalten, kann die Information das überspringen von Verzweigungen erlauben. Das Verfahren kann verwirklicht werden, indem Verzweigungsdaten in Daten eingeschlossen werden, die die geordnete Wortliste bezeichnen.
Die Verzweigungsdaten umfassen verzweigungsnehmende Information, die eine Stelle von ersten Nachsilbendaten bezeichnet, die einen ersten Satz von Nachsilbenendungen bezeichnen. Die Verzweigungsdaten umfassen außerdem Verzweigungsübergehungsinformation, die eine Anzahl von Nachsilbenendungen in dem ersten Satz bezeichnet. Die verzweigungsnehmende Information kann folglich verwendet werden, wenn in bezug auf ein Wort mit einer der Nachsilbenendungen des ersten Satzes umgewandelt wird, um zu den ersten Nachsilbendaten zu gehen. Die Verzweigungsübergehungsinformation kann andererseits verwendet werden, wenn in bezug auf ein Wort mit einer der Nachsilbenendungen eines zweiten Satzes umgewandelt wird, um die ersten Nachsilbendaten zu überspringen, während eine genaue Zählung von Nachsilbenendungen unterhalten wird. Z.B. kann während der W/N-Umwandlung, wenn die ersten Nachsilbendaten übersprungen werden, die durch die Verzweigungsübergehungsinformation angegebene Zahl zu einer Zählung von Nachsilbenendungen addiert werden. Während der N/W-Umwandlung kann andererseits die Zahl von der Zahl, die umgewandelt wird, subtrahiert werden.
Ein erfindungsgemäßes Produkt umfaßt ein Speichermedium und durch das Speichermedium gespeicherte Wortlistendaten. Die Wortlistendaten bezeichnen eine Liste von Wörtern. Die Wortlistendaten umfassen eine Vielzahl von Nachsilbenendungs-Datenelementen, die Nachsilbenendungen von Wörtern in der Liste bezeichnen. Ein erstes Nachsilbendatenelement bezeichnet einen ersten Satz von Nachsilbenendungen, und ein zweites Nachsilbendatenelement bezeichnet einen zweiten Satz von Nachsilbenendungen. Jedes Nachsilbendatenelement kann eine Folge von Bytes umfassen, von denen einige Nachsilbenendungsbytes sind, die Nachsilbenendungen bezeichnen.
Die Wortlistendaten umfassen auch ein Verzweigungsdatenelement. Das Verzweigungsdatenelement umfaßt verzweigungsnehmende Information und verzweigungsüberspringende Information, wie oben beschrieben. Das Verzweigungsdatenelement kann z.B. einen Zeiger enthalten, der an einem Verzweigungspunkt in den Wortlistendaten gelegen ist. Der Zeiger kann die Stelle einer Verzweigung bezeichnen, die Information über einen Satz von Nachsilbenendungen enthält, und eine Anzahl von Nachsilbenendungen in der Verzweigung kann an den Zeiger angefügt werden. Oder das Verzweigungsdatenelement kann einen Zeigerindex enthalten, der benutzt werden kann, um auf einen Eintrag in einer Suchtabelle zuzugreifen. Der Eintrag umfaßt einen Zeiger auf eine Verzweigung und eine Zahl von Nachsilbenendungen in der Verzweigung.
Das Verfahren kann erweitert werden, um den Speicherlatz zu vermindem, indem identische Verzweigungen zu einer einzigen Verzweigung zusammengefaßt werden, die von verschiedenen Unterlisten von Wörtern gemeinsam benutzt werden kann. An jedem Verzweigungspunkt, der zu der gemeinsamen Verzweigung führen kann, umfaßt ein Verzweigungsdatenelement verzweigungsnehmende Information, z.B. einen Zeiger zu der gemeinsamen Verzweigung, und verzweigungsüberspringende Information, z.B. eine Zahl von Nachsilbenendungen in der gemeinsamen Verzweigung. Wegen dieser Anordnung von Daten, erlauben zum Reduzieren des Speicherpiatzes eingeführte Zeiger das überspringen von Verzweigungen und verringern somit auch die Verarbeitungszeit.
Es ist nicht erforderlich, einen Zählwert für jeden Satz von Nachsilben wie in dem oben beschriebenen Verfahren von Lucchesi et al. zu speichern. Statt dessen kann ein Nachsilbendatenelement, das Nachsilbenendungen enthält, normal abgetastet werden, um festzustellen, wie viele Nachsilbenendungen es enthält. Wenn eine Verzweigung zu einem Nachsilbendatenelement übersprungen werden kann, kann jedoch die Zahl von Nachsilbenendungen gespeichert werden, so daß sie wiedergewonnen und verwendet werden kann, um einen laufenden Zählwert von Nachsilbenendungen zu aktualisieren, wenn die Verzweigung übersprungen wird.
Bei einem erfindungsgemäßen Produkt können die verzweigungsnehmende Information und die verzweigungsüberspringende Information verwendet werden, um Wort-in-Zahl- und Zahl-in-Wort-Umwandlungen durchzuführen. Ein erfindungsgemäßes Produkt kann weiter einen Prozessor umfassen, der geschaltet ist, auf die Wortlistendaten zuzugreifen.
Ein erfindungsgemäßes Verfahren zur W/N-Umwandlung kann eine Verzweigung überspringen und die Zahl von Nachsilbenendungen im Verzweigungsdatenelement verwenden, um einen laufenden Zählwert zu aktualisieren, z.B. durch Addieren der Zahl von Nachsilbenendungen zu dem Zählwert Nach überspringen einer Verzweigung am Ende eines Nachsilbendatenelements und Aktualisieren des Zählwertes kann die W/N-Umwandlung gemäß diesem Verfahren die Folge von Bytes in einem anderen Nachsilbendatenelement abtasten, wobei der Zählwert von Nachsilbenendungen für jedes Nachsilbenendungsbyte inkrementiert wird. Wenn ein Byte erreicht wird, das die Nachsilbenendung des Wortes, das umgewandelt wird, bezeichnet, kann der Zählwert von Nachsilbenendungen als die Zahl des Wortes bereitgestellt werden. Wenn das Verzweigungsdatenelement auch Markierungsinformation umfaßt, die ein Zeichen bezeichnet, das Nachsilbenendungen in einer Verzweigung vorangeht, kann das W/N-Umwandlungsverfahren durch Vergleichen eines momentanen Zeichens in dem Wort, das umgewandelt wird, mit der Markierungsinformation feststellen, ob die Verzweigung zu überspringen ist.
Desgleichen kann ein erfindungsgemäßes Verfahren zur N/W-Umwandlung eine Verzweigung zu einem Nachsilbendatenelement überspringen und die Zahl von Nachsilbenendungen in der übersprungenen Verzweigung verwenden, um einen Zählwert von Nachsilbenendungen zu aktualisieren. In diesem Fall kann die Zahl von Nachsilbenendungen von dem Zählwert subtrahiert werden, der bei der Zahl, die umgewandelt wird, beginnen kann. Wenn jedes Nachsilbendatenelement eine Folge von Bytes umfaßt, von denen einige Markierungsbytes sind, die Zeichen bezeichnen, kann das Verfahren durch Speichern von Zeichen von Markierungsbytes in einem Stapel auch eine momentane Vorsilbe speichern. Nach überspringen der Verzweigung und Subtrahieren der Zahl von Nachsilbenendungen kann das Verfahren die Folge von Bytes in einem anderen Nachsilbendatenelement abtasten, wobei der Zählwert von Nachsilbenendungen für jedes Nachsilbenendungsbyte dekrementiert und wird und die momentane Vorsilbe in dem Stapel aktualisiert wird. Wenn der Zählwert von Nachsilbenendungen null erreicht, kann die momentane Vorsilbe in dem Stapel als das Wort der Zahl bereitgestellt werden. Das Verfahren kann durch Vergleichen des momentanen Wertes des Zählwertes mit der Zahl von Nachsilbenendungen in der Verzweigung feststellen, ob eine Verzweigung zu überspringen ist, und bestimmen, ob die Nachsilbenendung des Wortes in der Verzweigung liegt.
Das oben umrissene Verfahren ist vorteilhaft, weil es Daten bereitstellt, die eine Wortliste in einer Form bezeichnen, die eine schnelle Umwandlung zwischen Wörtern und Zahlen erlaubt. Zusätzlich zur Zeiteffizienz kann auch die Raumeffizienz mit gemeinsamen Verzweigungen verbessert werden. Die Wortlistendaten können in einer Vielfalt von Anwendungen verwendet werden, einschließlich einer Einrichtung, bei der mit einem Wort verbundene Information auf der Basis der Zahl, in die dieses Wort umgewandelt wird, wiedergewonnen wird. Sie könnten auch verwendet werden, um Text zu komprimieren und zu dekomprimieren. Ausführungen der Erfindung werden, nur auf dem Wege von Beispielen, mit Bezug auf die begleitenden Zeichnungen beschrieben.
Inhalt der Zeichnungen:
Fig. 1 ist ein Zustandsübergangsdiagramm eines Auszugs aus einer Wortliste.
Fig. 2 ist eine schematische Zeichnung von Wortlistendaten, die die Wörter in dem Auszug von Fig. 1 bezeichnen.
Fig. 3 ist ein Flußdiagramm, das eine Routine zeigt, die beim Erzeugen eines Produkts verwendet werden kann, das Wortlistendaten umfaßt.
Fig. 4 ist eine schematische Darstellung eines Datenverarbeitungssystems zum Erzeugen eines Produkts, das Wortlistendaten umfaßt.
Fig. 5 ist ein Flußdiagramm, das ein Verfahren zum Umwandeln eines Wortes in eine Zahl zeigt.
Fig. 6 ist ein Flußdiagramm, das im einzelnen zeigt, wie eine alternative übergangseinheit gefunden werden kann.
Fig. 7 ist ein Flußdiagramm, das ein Verfahren zum Umwandeln einer Zahl in ein Wort zeigt.
Fig. 8 ist ein Funktionsblockschaltbild eines Verfahrens zum Verbinden von Information mit einem Wort unter Verwendung der Wort-zu-Zahl- Umwandlung.
Fig. 9 ist ein Funktionsblockschaltbild eines Verfahrens zum Verbinden von anderen Wörtern mit einem Wort unter Verwendung der Wort-zu- Zahl- und Zahl-zu-Wort-Umwandlung.
Fig. 10 ist ein Funktionsblockschaltbild eines Verfahrens zur Textkompression und -dekompression unter Verwendung der Wort-zu-Zahl- und Zahl-zu-Wort-Umwandlung.

A. Allgemeine Merkmale

Die allgemeinen Merkmale eines Umwandlungsverfahrens können aus Fig. 1 und 2 verstanden werden. Fig. 1 ist eine Zustandsübergangsdarstellung einer Wortliste, die 15 Wörter umfaßt: dip, dips, dipped, dipper, dipping, drip, drips, dripped, dripping, drop, drops, dropped, dropper und dropping. Andererseits zeigt Fig. 2 Wortlistendaten, die die Wörter in der Wortliste von Fig. 1 bezeichnen.
Fig. 1 zeigt eine Zustandsübergangsdarstellung einer Wortliste. Jeder übergang in Fig. 1 ist mit einem zugehörigen Buchstaben markiert, und der Zustand nach dem letzten Buchstaben eines annehmbaren Wortes ist mit einem "F" markiert, um einen gültigen Endbuchstaben anzuzeigen. Wenn die Zeichen von einem der annehmbaren Wörter beginnend beim Startzustand 10 in Folge angewandt werden, werden sie längs einer Folge von übergängen und Zuständen zu einem der mit "F" markierten Zustände führen. Das Wort "dip" führt z.B. zu Zustand 16. Die in Fig. 1 dargestellte Wortliste kann daher verwendet werden, um festzustellen, ob ein eingegebenes Wort eines der annehmbaren Wörter ist, und könnte für Rechtschreibprüfung und ähnliche Anwendungen verwendet werden.
Fig. 1 stellt die annehmbaren Wörter als links beginnend und rechts endend dar. Zu Zwecken dieser Beschreibung bedeutet der Begriff "Präfix" jede Kombination von Zeichen am Beginn eines annehmbaren Wortes und wird in Fig. 1 durch die Folge von übergängen und Zuständen, die vom Startzustand 10 zu jedem der Zustände führt, dargestellt. Der Startzustand 10 stellt somit das Ende eines Präfixes ohne Elemente dar, während der Zustand 16 das Ende der Präfixe "dip", "drip" und "drop" darstellt. Ähnlich bedeutet der Begriff "Suffix" jede Kombination von Zeichen am Ende einer annehmbaren Zeichenfolge und wird in Fig. 1 durch die Folge von übergängen und Zuständen, die von einem der Zustände zu jedem Zustand führt, der mit "F" markiert ist, dargestellt. Ein Ende-Verzweigung-Zustand stellt folglich den Anfang eines Suffixes ohne Elemente dar, während der Startzustand 10 den Anfang eines Satzes von Suffixen darstellt, der alle annehmbaren Wörter einschließt.
Es folgt, daß jeder Zustand in Fig. 1 das Ende wenigstens eines Präfixes und den Anfang wenigstens eines Suffixes darstellt. Außerdem stellt jeder der mit "F" markierten Zustände wenigstens eine Suffixendung dar, weil er, wie oben angemerkt, ein Zustand unmittelbar nach dem Endbuchstaben eines annehmbaren Wortes ist. Der Zustand 16 stellt z.B. die Suffixendung für die Wörter "dip", "drip" und "drop" dar.
Zu Zwecken der folgenden Beschreibung sind die Begriffe "Suffix" und "Präfix" nicht auf an eine Wurzel angefügte Suffixes und Präfixes beschränkt, sondern haben die oben dargelegte allgemeine Bedeutung. Diese Begriffe wären somit gleichermaßen auf eine Liste von Wörtern anwendbar, bei der die Elemente jedes Wortes in umgekehrter Reihenfolge sind, so daß Suffixe jedes Wortes mit dem ersten Element des Wortes enden und Präfixe mit dem letzten Element des Wortes beginnen.
Fig. 1 veranschaulicht verschiedene Merkmale einer Wortlistendarstellung, die wirksam gespeichert und verwendet werden kann. Die Darstellung von Fig. 1 ist azyklisch, weil keiner der übergänge aus einem gegebenen Zustand entweder direkt oder über eine Kombination von anderen übergängen zu diesem Zustand zurück führt. Dies ist bedeutsam, weil es eine endliche Zahl von annehmbaren Wörtern sicherstellt. Wenn eine Wortliste unendlich wäre, könnte sie passend gemacht werden, indem irgendwie eine endliche Zahl von annehmbaren Wörtern sichergestellt wird, z.B. durch Begrenzen der Zahl von Zyklen, die innerhalb einer einzigen Abtastung der Wortlistendarstellung gemacht werden könnte.
Außerdem ist die Wortlistendarstellung von Fig. 1 sowohl auf der linken als auch auf der rechten Seite konvergent, was bedeutet, daß sowohl Präfixe als auch Suffixe einer Anzahl von annehmbaren Wörtern gemeinsam sein können. Dies ist bedeutsam, weil die unten beschriebenen Verfahren beim Reduzieren der Größe von Daten, die eine Wortliste bezeichnen, von beiden Konvergenzen Gebrauch machen und zur selben Zeit für das Umwandlen der Wörter in einer solchen Liste in einen dichten Satz von einmaligen Zahlen sorgen. Gemeinsame Suffixe werden z.B. in Fig. 1 jeweils durch mehrfache ankommende übergänge an einen Zustand dargestellt. Die Suffixe "-ps" und "-s" sind gemeinsame Suffixe der Wörter dips, drips und drops. Fig. 1 stellt außerdem das Zusammenfallen jedes dieser gemeinsamen Suffixe in eine gemeinsam benutzte Verzweigung dar, so daß "-s" z.B. in nur einer Verzweigung und nicht einmal für jedes annehmbare Wort, das mit diesem Suffix endet, vorkommt.
Eine Wortlistendarstellung wie in Fig. 1 kann zur Umwandlung verwendet werden. Eine Zahl hönnte z.B. mit dem letzten Buchstaben jedes annehmbaren Wortes verbunden sein, so daß, wenn dieser Buchstabe zur übereinstimmung gebracht wird, die Zahl zur Verfügung steht. Dies würde jedoch das Zusammenfallen eines gemeinsamen Suffixes in eine gemeinsam benutzte Verzweigung wie in Fig. 1 gezeigt ausschließen, da jedes Suffix eine einmalige Zahl umfassen würde und folglich anders als jedes andere Suffix sein würde. Außerdem würde die N/W-Umwandlung langsam sein, weil die Wortlistendaten zuerst abgesucht würden, um die Zahl, die umgewandelt wird, zu finden, wonach das entsprechende Wort bestimmt werden würde, indem die Zeichenfolge, die zu dieser Zahl führt, gefunden wird.
Eine schnelle W/N- und N/W-Umwandlung schließt das Zusammenfallen gemeinsamer Suffixe nicht aus. Ein Wort kann in eine Zahl umgewandelt werden, indem die Zahl von Suffixendungen gezählt wird, die während der Suche nach diesem Wort durchlaufen werden. Für die Wortlistendarstellung in Fig. 1 würde z.B. die Zahl des Wortes "dip" null sein, während die Zahl des Wortes "drops" 14 sein würde. Die N/W-Umwandlung kann andererseits mit der Zahl beginnen, die für jede Suffixendung, die beim Abtasten durch die Wortlistendaten durchlaufen wird, dekrementiert wird. Wenn die Zahl null erreicht, hat die Abtastung die Suffixendung des Wortes erreicht, und dieses Wort kann auf der Basis von während der Abtastung gespeicherten Buchstaben bereitgestellt werden.
Wenn es erforderlich ist, jede Suffixendung einzeln zu zählen, muß jede Verzweigung der Wortlistendaten sowohl für die W/N- als auch die N/W-Umwandlung abgetastet werden. Die zwei übergänge, die vom Zustand 12 ausgehen, veranschaulichen dieses Problem. Der erste übergang, bezeichnet mit "I", führt zu einer großen Verzweigung, während der zweite übergang, bezeichnet mit "R", zu einer anderen großen Verzweigung führt. Wenn eine Suche das Wort "drops ei mit der Wortlistendarstellung von Fig. 1 vergleicht und wenn die Suche abhängig von dem ersten übergang vom Zustand 12 durch den ganzen Zweig gehen muß, um die Suffixendungen in diesem Zweig zu zählen, wird folglich die Suche relativ langsam sein. Dasselbe gilt für jeden der Zustände 14, 16 und 18. Zustand 16 hat z.B. einen mit "P" bezeichneten ersten Übergang, der zu einer großen Verzweigung führt, während sein zweiter mit "S" bezeichneter übergang zusammen mit dem Zustand, zu dem er führt, eine sehr kleine Verzweigung bildet.
Die notwendige Information zum überspringen einer Verzweigung und die Anzahl von Suffixendungen in der Verzweigung können in die Wortlistendaten eingeschlossen werden, um die Verzweigung überspringbar zu machen. Anstatt die Suffixendungen in einer Verzweigung zu zählen, kann dann einfach die Zahl von Suffixendungen zu der laufenden Zählung addiert oder davon subtrahiert werden. Diese Information kann in die Wortlistendaten eingeschlossen werden, indem sie mit Daten verbunden wird, die ein Verzweigungspunkt sind, von dem eine Abtastung entweder zu der überspringbaren Verzweigung oder zu einer anderen Verzweigung geht. Auf die überspringbare Verzweigung wird hierin als die nächste Verzweigung des Verzweigungspunktes verwiesen, während auf die andere Verzweigung als die alternative Verzweigung des Verzweigungspunktes verwiesen wird. Während die Wortlistendaten abgesucht werden, geht, wenn ein Zeichen von dem gesuchten Wort mit einem Zeichen in einem Verzweigungspunkt übereinstimmt, die Suche im allgemeinen zu der nächsten Verzweigung, aber wenn nicht, geht die Suche zu der alternativen Verzweigung. Daten, die kein Verzweigungspunkt sind, können trotzdem eine nächste Verzweigung haben, wobei in diesem Fall die Suche im Fall einer übereinstimmung zu der nächsten Verzweigung geht, aber im Fall einer Nichtübereinstimmung endet.
Fig. 2 zeigt gespeicherte Wortlistendaten, die die obigen Merkmale der in Fig. 1 dargestellten Wortliste implementieren. In Fig. 2 stellen die bei jeder Adresse gespeicherten Daten in der Regel einen der in Fig. 1 gezeigten übergänge dar. Diese Einheiten von Daten werden daher als übergangseinheiten bezeichnet, und jede übergangseinheit in Fig. 2 umfaßt Zeichendaten (CHAR), die ein dem übergang entsprechendes Zeichen bezeichnen, Enddaten (F), die angeben, ob der übergang eine Suffixendung ist, was bedeutet, daß der übergang in einen Endzustand eintritt und somit das letzte Zeichen eines annehmbaren Wortes darstellt, Ende-Verzweigung-Daten (EOB), die angeben, ob die übergangseinheit eine nächste Verzweigung hat, und alternative Daten (ALT), die angeben, ob die Verzweigung, die bei dem übergang beginnt, eine alternative Verzweigung hat. Die Daten CHAR, F, EOB und ALT können für jede übergangseinheit alle in einem einzigen Byte codiert werden, oder die EOB-Daten können in einem zweiten Byte mit einem besonderen EOB-Wert codiert werden, das dem ersten Byte nur folgt, wenn die Übergangseinheit keine nächste Verzweigung hat.
Die PTR-Spalte in Fig. 2 enthält Zeiger, die in Verbindung mit vier Verzweigungspunkten der Liste gespeichert werden, wobei jeder Verzweigungspunkt eine Übergangseinheit ist, die sowohl eine nächste Verzweigung als auch eine alternative Verzweigung aufweist. Der Zeiger bei Adresse 2 ist mit der übergangseinheit verbunden, die dem mit "I" bezeichneten übergang vom Zustand 12 entspricht, während der Zeiger bei Adresse 5 mit dem mit "I" bezeichneten übergang vom Zustand 14 verbunden ist. Der Zeiger bei Adresse 9 ist mit dem mit "P" bezeichneten übergang vom Zustand 16 verbunden, und der Zeiger bei Adresse 12 ist mit dem mit "E" bezeichneten übergang vom Zustand 18 verbunden. Jeder Zeiger gibt die Adresse an, bei der die nächste Verzweigung beginnt, so daß, wenn die nächste Verzweigung übersprungen wird, der Zeiger ebenso übersprungen wird, aber, wenn die nächste Verzweigung nicht übersprungen wird, der Zeiger genommen wird. Die in Fig. 2 gezeigten Zeiger erlauben somit das überspringen von Verzweigungen und dienen dazu, sowohl die Stelle der nächsten Verzweigung als auch die Stelle der alternativen Verzweigung zu bezeichnen. Eine äquivalente Liste könnte ähnlich erzeugt werden, bei der jeder Zeiger, anstatt die nächste Verzweigung anzugeben, die alternative Verzweigung angeben würde.
Zusätzliche Daten über die Zahl von Suffixendungen in einer überspringbaren Verzweigung sind in den Wortlistendaten enthalten, um während des Umwandelns das überspringen von Verzweigungen zu erlauben. Die Daten in der Spalte F-Größe in Fig. 2, gespeichert in Verbindung mit jedem Verzweigungspunkt mit einer überspringbaren nächsten Verzweigung, geben die Zahl von Suffixendungen innerhalb der nächsten Verzweigung an. Eine Zählung von Suffixendungen kann folglich unter Verwendung der F-Größe unterhalten werden, selbst wenn die nächste Verzweigung übersprungen wird. Zurück auf Fig. 1 verweisend kann z.B. das Wort "drops" schnell in eine Zahl ungewandelt werden, ohne durch die nächsten Verzweigungen der mit "I", "I" und "P" bezeichneten übergänge von den Zuständen 12, 14 bzw. 16 zu gehen.
Die Verbindung eines Zeigers und der F-Größe mit jedem Verzweigungspunkt mit einer überspringbaren nächsten Verzweigung in Fig. 2 dient somit einer Anzahl von Funktionen. Der Zeiger bezeichnet die Stelle der nächsten Verzweigung. Die Positionierung des Zeigers bezeichnet weiter die Stelle der alternativen Verzweigung, weil sich der Zeiger und F-Größe unmittelbar vor dieser Stelle befinden. Eine Abtastung der Wortlistendaten, die den Verzweigungspunkt erreicht, kann folglich mit der nächsten Verzweigung fortfahren oder sie alternativ überspringen und mit der alternativen Verzweigung fortfahren. Die F-Größe gibt die Anzahl von Suffixendungen in der nächsten Verzweigung an, so daß ein Zählwert von Suffixendungen unterhalten werden kann, selbst wenn die nächste Verzweigung übersprungen wird. Dieses Verfahren ist somit insofern ungewöhnlich, als es sowohl größere Geschwindigkeit als auch kompaktere Speicherung liefert. Größere Geschwindigkeit, weil es das überspringen von Verzweigungen erlaubt, und kompaktere Speicherung, weil es das Zusammenfallen eines gemeinsamen Suffixes in eine gemein sam benutzte Verzweigung erlaubt.
Dieses Verfahren ist auf eine Datenstruktur, z.B. einen gerichteten Graphen, anwendbar, in der Wortlistendaten gespeichert werden können, so daß sie Suffixendungen in Verzweigungen der Datenstruktur hat. Im allgemeinen können die Wortlistendaten in einer Datenstruktur gespeichert werden, die für jede Dateneinheit Information, die die Stellen der nächsten Verzweigung und der alternativen Verzweigung, falls vorhanden, angibt, Information, die angibt, ob die Dateneinheit eine annehmbare Suffixendung ist, und, wenn die Dateneinheit ein Verzweigungspunkt mit einer überspringbaren nächsten Verzweigung ist, Information umfaßt, die die Anzahl von annehmbaren Suffixendungen innerhalb der nächsten Verzweigung angibt. Im Gegensatz zu Lucchesi et al., oben zitiert, verlangt dieses Verfahren nicht, daß eine Zählung mit den Daten, die jeden übergang darstellen, eingeschlossen wird. Zählungen von Suffixendungen müssen nur eingeschlossen werden, wo sie beim überspringen von Verzweigungen verwendet werden können, weil Zählungen von Suffixendungen statt dessen durch Abtasten einer Verzweigung erlangt werden können.
Wir wenden uns nun Verfahren zu, um kompakte Wortlistendaten wie in Fig. 2 zu erzeugen und zu speichern.

B. Wortlistenerzeugung

Zwei wichtige Faktoren beim Erzeugen eines Produkts, das Wortlistendaten wie in Fig. 2 enthält, sind die Bestimmung der F-Größen und die Zuweisung der Zeiger. Nach dem Behandeln eines Verfahrens zum Bestimmen der F-Größen werden wir in einiger Ausführlichkeit ein System zur Verwendung dieses Verfahrens und eine Anzahl anderer Verfahren behandeln, um Zeiger zuzuweisen und ein Produkt zu erzeugen, das Wortlistendaten wie in Fig. 2 enthält.
1. Berechnung der F-Größe. Fig. 3 zeigt eine rekursive Routine, die verwendet werden kann, um die Anzahl von Suffixendungen innerhalb jeder überspringbaren Verzweigung zu erlangen. Die Routine von Fig. 3 betrifft spezifisch die Codierung einer FSM-Datenstruktur.
Die Routine von Fig. 3 beginnt in Kasten 20 mit dem Empfang eines Zustandes, von dem eine Verzweigung der FSM-Datenstruktur abhängen kann.
Der erste Aufruf der Routine wird den Startzustand der FSM-Datenstruktur liefern, aber nachfolgende rekursive Aufrufe der Routine von Fig. 3 werden andere Zustände innerhalb der FSM-Datenstruktur liefern. Als Folge führt die Routine von Fig. 3 eine. Abtastung durch die ganze FSM- Datenstruktur durch, nach der die Dateneinheit für jeden Zustand Information enthält, die die F-Größe angibt, wobei die F-Größe die Anzahl von annehmbaren Wörtern ist, die Endungen innerhalb der von diesem Zustand abhängenden Verzweigung haben. Die F-Größe aller Zustände wird folglich zu null initialisiert, bevor die Routine von Fig. 3 ausgeführt wird. Während sie durch die Zustände geht, berechnet sie die F-Größe jedes Zustandes und ändert auch ein Flag innerhalb jedes Zustandes, um anzuzeigen, daß dieser Zustand besucht worden ist.
Die Routine von Fig. 3 fährt fort mit dem Prüfen, ob der empfangene Zustand vorangehend in dieser Abtastung besucht worden ist, Kasten 22. Wenn ja, gibt die Routine in Kasten 24 ein Abtastergebnis an die Routine, die sie aufrief, zurück, angedeutet bei B. Das Abtastergebnis ist die F-Größe des empfangenen Zustandes, wie bei dem vorangehenden Besuch berechnet.
Wenn andererseits die Prüfung in Kasten 22 feststellt, daß der Zustand vorher nicht besucht worden ist, dann stellt die Prüfung in Kasten 26 fest, ob der Zustand irgendwelche übrigen ausgehenden übergänge hat, die während der momentanen Abtastung nicht untersucht worden sind. Wenn nicht, wird das Abtastergebnis in Kasten 24 wie oben zurückgegeben. Wenn ja, wird der Zustand, der das Ziel des obersten übrigen übergangs ist, in Kasten 28 einem rekursiven Aufruf der Routine von Fig. 3 bei A' zur Verfügung gestellt, was einen bei A beginnenden Aufruf zur Folge hat. Wenn dieser Aufruf sein Abtastergebnis bei B zurückgibt, wird dieses Ergebnis durch die aufrufende Routine bei B' empfangen, und die aufrufende Routine geht zu Kasten 30, um die F-Größe ihres Zustandes zu aktualisieren, indem sie das Abtastergebnis zu dem vorherigen Wert ihrer F-Größe addiert und außerdem die F-Daten des Zielzustandes des obersten übergangs addiert, die eins sein werden, wenn der Zustand eine Suffixendung ist, und die andernfalls null sein werden. Die Routine kehrt dann zu der Prüfung von Kasten 26 zurück, um festzustellen, ob ausgehende übergänge von diesem Zustand übrigbleiben, um abgetastet zu werden.
Die Reihenfolge, in der die übergänge jedes Zustandes durch die Routine von Fig. 3 abgetastet werden, wird von der Reihenfolge abhängen, in der sie innerhalb der Dateneinheit jedes Zustandes angeordnet sind. Um die Wörter so zu speichern, daß ihre entsprechenden Zahlen ihrer alphabetischen Ordnung entsprechen, können die übergänge in alphaberischer Reihenfolge angeordnet werden. Um jedoch eine kompakte codierte FSM-Datenstruktur zu erlangen, können die übergänge sortiert werden, z.B. nach Maßgabe der Anzahl von eingehenden übergängen zum Zielzustand jedes übergangs oder nach Maßgabe der Häufigkeit des Vorkommens des Zeichens in diesem übergang, wobei der erste übergang von jedem Zustand das Zeichen mit der geringsten Häufigkeit aufweist. Diese oder andere Sortierverfahren können beim Beseitigen von Redundanz helfen. Verfahren zum Beseitigen von Redundanz durch Minimieren einer FSM-Datenstruktur können auch verwendet werden.
Obwohl es die Berechnung von F-Größe möglich macht, Information mit einer Verzweigung zu verbinden, die die Anzahl von Suffixendungen, die sie enthält, angibt, ist eine Anzahl von anderen Prozessen erforderlich, um ein Produkt zu erzeugen, das eine kompakte Wortliste des in Fig. 2 gezeigten Typs umfaßt.
2. Wortlistensystem. Fig. 4 zeigt ein Datenverarbeitungssystem 100, das verwendet werden kann, um ein Produkt zu erzeugen, das eine gespeicherte Wortliste umfaßt. Die CPU 2 empfängt die zu codierende FSM- Datenstruktur über den FSM-Eingangspuffer 104 und liefert, wenn die Codierung vollendet ist, eine Ausgangsdatei über den Puffer 106. Während des Codierens führt sie im Programmspeicher 110 gespeicherte Software aus, die umfaßt: eine Hauptcodierungsroutine 112, Informationssammelunterroutinen der Zustandseinheit 114 einschließlich der oben mit Bezug auf Fig. 3 beschriebenen Routine, eine Zeigergrößenund Indexzuweisungsunterroutine 116, eine übergangseinheiterzeugungsund Lokalisierungsunterroutine 118, eine Dateischreibunterroutine 120 und eine Bytewertzuweisungsunterroutine 122. Während der Ausführung dieser Software speichert die CPU 102 Daten im Arbeitsdatenspeicher 130 und gewinnt Daten daraus zurück, in dem die Dateneinheit SU jedes Zustandes und die Information über die ausgehenden übergänge TU dieses Zustandes zusammen mit einer Anzahl von Tabellen gespeichert werden.
Im allgemeinen können die in Fig. 4 gezeigten Unterroutinen wie in der Europäischen Patentanmeldung Nr. 93 305 651.7, eingereicht am 19. Juli 1993, hierin als die "Codierungsanmeldung" bezeichnet, beschrieben implementiert werden. Wie in der Codierungsanmeldung beschrieben wird Information über jeden Zustand gesammelt, die eine Zählung von Zeigern, die diesen Zustand betreten, bezeichnet als InPointers, und einen Preis für den Zustand umfaßt; der die benötigte Speichermenge angibt, um den Teil der Datenstruktur, der von dem Zustand abhängt, zu speichern. Außerdem enthält eine Liste, bezeichnet als Root-List, Blöcke von Übergangseinheiten, auf die immer mit Zeigern zugegriffen wird.
Die Zustandseinheit-Informationssammelunterroutinen 114 umfassen eine Routine, die prüfen kann, ob der erste von dem Zustand ausgehende übergang ein besonderer nicht-letzter Übergangs ist, hierin als ein "Epsilon"- oder "Leerzeichenfolge"-Übergang bezeichnet. Wenn ja, wird, anstatt InPointers für den momentanen Zustand zu inkrementieren, er für das Ziel des Epsilon-Übergangs inkrementiert. Solche Übergänge können manchmal verwendet werden, um die Menge gemeinsamer Daten zu erhöhen. Diese Routine kann eine Prüfung durchführen und die Kosten dieses Zustandes unverändert lassen, wenn ein Nicht-Letzter-Epsilonübergang ermittelt wird. Außerdem kann die Routine das Ergebnis mit den maximalen Zustandskosten vergleichen. Wenn das Ergebnis die Maximalkosten übersteigt und wenn dies nicht der letzte Übergang des momentanen Zustandes ist, werden die Kosten des Ziels auf die Kosten eines kurzen Zeigers gesetzt und InPointers des Ziels wird inkrementiert. Außerdem kann diese Routine beim ersten Besuch eines Zustandes ein Anzeichen in dem Zustand speichern, daß die von ihm abhängende Verzweigung In-Line und nicht durch einen Zeiger gespeichert werden wird, selbst wenn diese Verzweigung eine gemeinsame Verzweigung ist.
3. Zeigerzuweisungs- und andere Unterroutinen. Eine Anzahl von Verfahren sind besonders nützlich in bezug auf die Zeigergrößen- und Indexzuweisung.
a. Gesamtzeigerzuweisungsunterroutine. Die Zeigergrößen- und Indexzuweisung kann mit wenigen Unterschieden im allgemeinen den in der Codierungsanmeldung beschriebenen Verfahren folgen.
Die Unterroutine, die Zeigergrößen und Indizes zuweist, schließt auch Information in die Wortlistendaten ein, so daß eine Verzweigung übersprungen werden kann; die Information kann, wenn vorteilhaft, Zeiger umfassen. Wie unten bemerkt ist ein Unterschied, daß die Unteroutine auch die F-Größe in Betracht zieht, die in Verbindung mit jedem Zeiger gespeichert wird und folglich die Zeigerzuweisungsentscheidung beeinflußt.
Beim Sortieren der Zustände vor dem Zuweisen von Zeigern kann die Unterroutine Zustände mit höherem InPointers vor Zuständen mit niedrigerem InPointers plazieren. Zustände mit gleichen InPointers können nach F-Größe sortiert werden, wobei kleinere F-Größen größeren vorangehen.
Beim Speichern der Wortlistendaten wird die passende F-Größe in bezug auf jeden Dreibyte-Zeiger gespeichert, so daß die F-Größe wiedergewonnen werden kann, wenn die Verzweigung, auf die gezeigt wird, übersprungen wird. Jeder Ein- oder Zweibyte-Zeigerindex kann andererseits benutzt werden, um auf eine Suchtabelle zuzugreifen, die den passenden Dreibyte-Zeiger und F-Größe enthält, so daß die F-Größe in bezug auf jedes Vorkommen eines Ein- oder Zweibyte-Zeigerindexes nicht gespeichert werden muß.
Wenn die F-Größe für einen Dreibyte-Zeiger unmittelbar nach dem Zeiger gespeichert wird, belegt jeder Dreibyte-Zeiger zusammen mit seiner F- Größe mehr als drei Bytes. Z.B. kann jeder Dreibyte-Zeiger mit F-Größe vier Bytes lang sein, wenn die F-Größe ein einziges Byte ist. Ähnlich kann jeder Dreibyte-Zeiger mit F-Größe sechs Bytes lang sein, wenn die F-Größe zwei Bytes ist und ein zusätzliches Byte mit nur Nullen vor der F-Größe eingefügt wird, um die Zweibyte-F-Größe anzuzeigen, und so weiter, wenn größere F-Größen benötigt werden. Es wäre möglich, Längen von vier oder fünf Bytes zu verwenden, um das zusätzliche Byte mit nur Nullen wegzulassen, aber dies würde erfordern, daß die Länge aus dem Bytewert des ersten Bytes jedesmal decodiert werden muß, wenn ein Dreibyte-Zeiger angetroffen wird. F-Größen von zwei Byte sind in bezug auf F-Größen von einem Byte so selten, daß die durch Vermeidung dieser Decodierung gewonnene Einfachheit die Raumkosten der Verwendung einer Länge von sechs Bytes anstatt einer Länge von fünf Bytes aufwiegt. In der folgenden Erörterung werden Zeiger/F-Größe-Kombinationen von vier Bytes, sechs Bytes oder länger alle als lange Zeiger behandelt, im Gegensatz zu den Ein- und Zweibyte-Zeigeradressen, die als kurze Zeiger behandelt werden.
Die Unterroutine, die Übergangseinheiten erzeugt und Stellen zuweist, kann die F-Größe jedes Zustandes in Betracht ziehen. Wenn eine Bytestelle einem Zeiger zugewisen wird, kann die F-Größe angefügt werden, ob die Bytestelle in die codierte Datenstruktur oder in die passende Zeigertabelle einzuschließen ist.
In der Unterroutine, die die Datei schreibt, können Startzustandstabellen geschrieben werden, um die F-Größen einzuschließen, bei denen das Zählen zu beginnen ist, wenn die Wortlistendaten bei einem gegebenen Übergang betreten werden. Die F-Größe, bei der zu beginnen ist, wird eins weniger sein als die Zahl, die dem ersten Wort in der Wortdatenliste entspricht, die mit dem Zeichen beginnt, das diesem übergang entspricht. Außerdem kann die F-Größe in Betracht gezogen werden, indem die angehängte F-Größe in jeden in die Zeigertabellen oder in die Datenstruktur geschriebenen Zeiger eingeschlossen wird.
b. Zuweisung von kurzen Zeigern. Die Gesamtzeigerzuweisungsunterroutine kann eine Unterroutine aufrufen, die die Zuweisung kurzer Zeiger durchführen kann. Die Zuweisung kurzer Zeiger kann auch F-Größe in Betracht ziehen.
Beim Bestimmen, ob ein kurzer Zeiger vorteilhaft ist, kann die Unterroutine feststellen, ob ein Zustand eine Zeigergröße von zwei oder nur zwei InPointers aufweist. In diesem Fall fügt, wenn die F-Größe des Zustandes größer als 255 ist, das Vergrößern des mit einem Zeiger verbundenen F-Größenfeldes von einem auf zwei Bytes für Werte größer als 255 ein unnötiges Byte für jeden der anderen Tabelleneinträge hinzu, was nachteilig sein würde. Es ist folglich angebracht, das Zuweisen kurzer Zeiger bei dem Zustand anzuhalten. Sortieren der Zustände garantiert, daß alle späteren Zustände ebenfalls F-Größen größer als 255 aufweisen, so daß keine weiteren kurzen Zeiger verwendet werden.
Wenn der momentane Zeigerindex vorteilhaft ist und wenn die F-Größe des momentanen Zustandes nicht größer als 255 ist, so daß sie in ein einziges Byte in der Suchtabelle passen wird, können die momentane Zeigerindexgröße und der nächste Index dieser Größe zugewiesen werden. Eine weitere Unterroutine, die die F-Größe in Betracht zieht, kann aufgerufen werden, um festzustellen, ob die momentane Zeigergröße vorteilhaft ist. Diese Unterroutine kann die Kosten eines gegebenen Zustandes schätzen, bevor die Kosten aller von ihm abhängenden Zustände genau bestimmt worden sind. Sie kann sicherstellen, daß ein Zeiger nur zugewisen wird, wenn es vorteilhaft ist, indem die Kosten der Verzweigung, die von diesem Zeiger abhängen würde, bereitgestellt werden.
Noch eine weitere Unterroutine kann aufgerufen werden, um festzustellen, ob es vorteilhaft ist, den letzten Einbyte-Zeigerindex in einen Zweibyte-Zeigerindex zu ändern, um zusätzliche 255 Zweibyte-Zeigerindizes zu haben. Diese Unterroutine kann auch die Unterroutine aufrufen, die feststellt, ob der momentane Zeiger vorteilhaft ist, um ein Ergebnis zu erlangen, das die Kosten der von einem Zustand abhängenden Verzweigung angibt.
Wenn die Kosten der Verzweigung zwei oder weniger betragen, wäre es nicht von Vorteil, einen Zweibyte-Zeigerindex zuzuweisen. Andernfalls stellt die aufrufende Unterroutine fest, ob die F-Größe des Zustandes größer als 255 ist, wobei in diesem Fall jeder eingehende Zeiger ein Dreibyte-Zeiger anstelle eines Zweibyte-Zeigerindexes sein würde.
Wenn die F-Größe 255 oder weniger beträgt, wird die Länge des Tabelleneintrags, die für einen zusätzlichen Zweibyte-Zeigerindex benötigt wird, von dem Produkt aus zweimal der Anzahl von Zweibyte-Zeigerindizes subtrahiert, was gleich InPointers sein wird, und diese Differenz wird zu einer Variablen Benefit addiert, die den Gesamtnutzen des Zweibyte-Zeigerindexes verfolgt. Wenn aber die F-Größe 255 übersteigt, wird die Länge des Eintrags von dem Produkt aus viermal InPointers subtrahiert, und diese Differenz wird zu Benefit addiert. Der Faktor von zwei, der mit InPointers multiplziert wird, ist der Nutzen aus der Änderung eines Dreibyte-Zeigers mit einer Einbyte-F-Größe in einen Zweibyte-Zeigerindex. Der Faktor von vier ist der Nutzen aus der Änderung eines Dreibyte-Zeigers mit einem Byte aus nur Nullen und einer Zweibyte-F-Größe in einen Zweibyte-Zeigerindex.
In jedem Fall wird, wenn Benefit geeignet erhöht worden ist, sein Wert benutzt, um festzustellen, ob eine Änderung in der Zeigerzuweisung gemacht werden sollte.
c. Zuweisung von langen Zeigern. Die Gesamtzeigerzuweisungsunterroutine kann auch eine Unterroutine aufrufen, die die Zuweisung langer Zeiger durchführt. Die Zuweisung langer Zeiger kann auch F-Größe in Betracht ziehen.
Die Zuweisungsunterroutine für lange Zeiger kann, wenn ein Zustand Inpointers aufweist, feststellen, ob die F-Größe des Zustandes 255 übersteigt. Wenn ja, ist ein sechs Byte langer Zeiger mit angehängter F-Größe erforderlich.
Eine andere Unterroutine kann aufgerufen werden, um die Zeigergrößen einiger Zustände zu justieren.
Wenn einem Zustand ein langer Zeiger zugewiesen werden wird, kann diese Unterroutine feststellen, ob F-Größe 255 übersteigt. Wenn ja, wird ihr ein Sechsbyte-Zeiger zugewiesen. Wenn nicht, wird ihr ein Vierbyte-Zeiger zugewiesen.

C. W/N-Umwandlung

Die Wort-zu-Zahl-Umwandlung kann auf verschiedene Weise erfolgen. Die W/N-Umwandlung kann wie die N/W-Umwandlung eine gespeicherte Wortliste, z.B. einen gerichteten Graphen, verwenden, der Verzweigungen umfaßt, die während der Umwandlung übersprungen werden können. Fig. 5 zeigt eine W/N-Umwandlungsroutine, die zur Verwendung mit einer wie oben beschrieben gespeicherten Wortliste geeignet ist.
In Fig. 5 beginnt die W/N-Umwandlung in Kasten 400, wo das erste Zeichen des Wortes umgewandelt und eine Variable ZAHL initialisiert wird. ZAHL wird schließlich den Wert der Zahl annehmen, in die das Wort umgewandelt wird. Für die einfache Wortliste von Fig. 2 wäre es möglich, mit der ersten Stelle der Wortlistendaten und mit ZAHL gleich null zu beginnen, aber für eine typische große Datenstruktur wird das erste Zeichen des Wortes benutzt werden, um auf eine ersten Zeichentabelle zuzugreifen, um die Anfangsstelle dieses Zeichens innerhalb der Wortlistendaten zu finden und eine Zahl eins weniger als die Zahl des ersten angenommenen Wortes, das mit diesem Zeichen beginnt, zu finden, auf die ZAHL initialisiert ist. Dann beginnt der Prozeß des Abgleichens des Wortes, das umgewandelt wird, mit der Prüfung in Kasten 402. Die auf jedem Byte durchgeführten Prüfungen können auf der Art und Weise beruhen, in der Übergangseinheiten beim Erzeugen der Wortlistendaten in Bytes codiert wurden, beruhen aber in jedem Fall auf dem codierten Byte, das die Daten CHAR, F, EOB und ALT seiner Übergangseinheit angibt.
Wenn das momentane Zeichen des Wortes den CHAR-Daten der momentanen Übergangseinheit entspricht, stellt eine weitere Prüfung in Kasten 404 fest, ob dies das letzte Zeichen des Wortes ist, das umgewandelt wird. Wenn ja und wenn die Prüfung in Kasten 406 ergibt, daß die F-Daten der momentanen Übergangseinheit gesetzt sind, wird in Kasten 408 ZAHL zurückgegeben, und die Umwandlung ist vollendet. Wenn aber die F- Daten nicht gesetzt sind oder wenn das momentane Zeichen nicht das letzte Zeichen ist, aber die Prüfung in Kasten 410 ergibt, daß die EOB-Daten der momentanen Übergangseinheit gesetzt sind, dann befindet sich das Wort nicht in der Wortliste, und nichts wird in Kasten 412 zurückgegeben. Andernfalls stellt die Prüfung in Kasten 414 fest, ob die F-Daten der momentanen Übergangseinheit gesetzt sind, und wenn ja, wird in Kasten 416 ZAHL inkrementiert. Die Routine geht in Kasten 418 zu dem nächsten Zeichen in dem Wort und zu der nächsten Stelle in den Wortlistendaten. Wenn aber die Prüfung in Kasten 420 ergibt, daß die nächste Stelle einen Zeiger oder einen Zeigerindex enthält, geht in Kasten 422 die Routine zu der Stelle, die durch den Zeiger an dieser Stelle oder durch den Zeiger angegeben wird, der aus der passenden Zeigertabelle unter Verwendung des Zeigerindexes wiedergewonnen wurde. Weil dem Zeiger gefolgt wird, anstatt ihn zu überspringen, wird in diesem Fall F-Größe nicht in Betracht gezogen.
Wen andererseits die Prüfung in Kasten 402 ergibt, daß das momentane Zeichen nicht den CHAR-Daten der momentanen Übergangseinheit entspricht, ist es noch möglich, daß3 das Wort in der Wortliste ist, wenn die ALT-Daten der momentanen Übergangseinheit gesetzt sind. Wenn die Prüfung in Kasten 426 ergibt, daß dies der Fall ist, wird die Unterroutine GoToAlt in Fig. 6 ausgeführt, wie in Kasten 430 gezeigt. Wenn aber nicht, wird nichts in Kasten 428 zurückgegeben, weil das Wort nicht in der Wortliste sein kann.
In Fig. 6 beginnt GoToAlt in Kasten 440 mit dem Feststellen, ob die EOB-Daten der momentanen Übergangseinheit gesetzt sind (in diesem Fall müssen die F-Daten auch gesetzt sein, da jeder Zustand der Wortlistendaten, der ein Verzweigungsende ist, auch endgültig sein muß). Wenn ja, enthält die nächste Stelle in der Datenstruktur entweder die Alternative oder einen Zeiger auf die Alternative, so daß3 in Kasten 442 ZAHL und die Stelle inkrementiert werden. Dann endet GoToAlt und kehrt zu der Routine von Fig. 5 zurück, wo durch die Prüfung in Kasten 420 die Alternative gefunden wird.
Wenn andererseits die Prüfung in Kasten 440 ergibt, daß EOB nicht gesetzt ist, werden in Kasten 450 die F-Daten der momentanen Übergangseinheit geprüft, und in Kasten 452 wird ZAHL inkrementiert, wenn die F-Daten gesetzt sind. GoToAlt inkrementiert dann in Kasten 454 die Stelle und initialisiert in Kasten 456 eine Variable AltCount zu eins (1). Bis AltCount null (0) erreicht, wie durch die Prüfung in Kasten 458 ermittelt, geht GoToAlt in der unten beschriebenen Weise durch die Stellen. Wenn aber AltCount null erreicht, endet GoToAlt und kehrt zu der Routine von Fig. 5 zurück, wo durch die Prüfung in Kasten 420 die Alternative gefunden wird.
Während sie durch Stellen geht, prüft GoToAlt in Kasten 460, ob das Byte an der momentanen Stelle einerseits eine codierte Übergangseinheit ist, so daß es CHAR-Daten enthält, oder andererseits ein Zeiger oder ein Zeigerindex ist. Im Fall eines Zeigers oder Zeigerindexes wird in Kasten 462 AltCount dekrementiert, und der Zeiger oder Zeigerindex wird übersprungen. Die Länge des zu überspringenden Zeigers oder Zeigerindexes kann aus dem Wert an dieser Stelle bestimmt werden außer, daß die Länge von langen Zeigern, ob vier oder sechs, aus dem Wert bestimmt wird, der den drei Adressenbytes folgt, wie oben beschrieben. Außerdem wird in Kasten 464 die F-Größe der übersprungenen Verzweigung zu ZAHL addiert. Die F-Größe wird entweder direkt von einer an den Zeiger angehängten Stelle oder von einer geeigneten Suchtabelle wiedergewonnen. Nach dem Addieren der F-Größe kehrt Go- ToAlt zurück, um in Kasten 458 zu prüfen, ob AltCount null erreicht hat.
Wenn andererseits die Prüfung in Kasten 460 anzeigt, daß das Byte an der momentanen Stelle eine Übergangseinheit ist, so daß es CHAR-Daten enthält, prüft GoToAlt in Kasten 466, ob die F-Daten der momentanen übergangseinheit gesetzt sind, und wenn ja, inkrementiert ZAHL in Kasten 468. Ähnlich prüft GoToAlt in Kasten 470, ob die EOB-Daten gesetzt und die ALT-Daten gelöscht sind, und wenn ja, dekrementiert AltCount in Kasten 472. Dann prüft GoToAlt in Kasten 474, ob die ALT- Daten gesetzt und die EOB-Daten gelöscht sind, und wenn ja, inkrementiert Altcpount in Kasten 476. Nachdem ZAHL und AltCount auf diese Weise justiert wurden, inkrementiert GoToAlt in Kasten 478 die Stelle, bevor sie zu der Prüfung in Kasten 458 wie oben zurückkehrt.
Die Routine von Fig. 5 und 6 führt somit eine W/N-Umwandlung durch, weil sie jedes Wort in einer Wortliste in eine einmalige Zahl umwandelt. Eine zusätzliche Prüfung kann am Anfang der Routine von Fig. 5 hinzugefügt werden, um zu prüfen, ob die Wortlistendaten eine Null- Zeichenfolge akzeptieren, wenn eine Null-Zeichenfolge empfangen wird. Das erste akzeptierte Wort, ob Null-Zeichenfolge oder nicht, wird in null umgewandelt werden, und das letzte akzeptierte Wort wird in die Ganzzahl eins weniger als die Anzahl annehmbarer Wörter umgewandelt.
Zeichen können unter Verwendung von ESC-Codes besonders codiert werden. Wenn dies gemacht wird, wird innerhalb der Routine von Fig. 5 eine Anzahl zusätzlicher Schritte unternommen. Nach Empfangen jedes Zeichens eines Wortes, ob in Kasten 400 oder in Kasten 418, ist es erforderlich, die ESC-Codedaten des Zeichens zu prüfen, um die Anzahl von ESC-Codes zu bestimmen, die in den Wortlistendaten vor dem Zeichenbyte gefunden werden. Dann muß, wann immer in Kasten 402 eine Übereinstimmung vorkommt, geprüft werden, ob alle erwarteten ESC-Codes empfangen worden sind. Wenn die EOB-Daten der momentanen Übergangseinheit nicht gesetzt sind und wenn alle ESC-Codes vor dem Zeichenbyte empfangen worden sind, wird die nächste übereinstimmung in Kasten 402 die CHAR-Daten der nächsten Übergangseinheit mit dem Zeichencodefeld des Zeichens, das abgeglichen wird, vergleichen. Wenn aber die EOB- Daten nicht gesetzt sind und mehr ESC-Codes erwartet werden, wird die Anzahl von übrigen ESC-Codes herabgesetzt, bevor fortgefahren wird. Auf diese Weise werden die ESC-Codes in der gespeicherten Wortliste decodiert, während im allgemeinen der Routine von Fig. 5 gefolgt wird.
Die Umwandlung eines Wortes in eine Zahl umfaßt somit das Durchgehen durch eine gespeicherte Wortliste, während eine Zählung der Zahl von Übergangseinheiten mit gesetzten F-Daten unterhalten wird, von denen jede eine Suffixendung angibt. Wenn das Wort zur Übereinstimmnung gebracht wird, ist diese Zählung die Zahl des Wortes. Der Hauptvorteil gegenüber dem einfachen sequentiellen Absuchen der Liste ist, daß in einer schnellen Operation ganze Zweige übersprungen werden können.
Das oben beschriebene Verfahren besitzt gegenüber dem oben beschriebenen Verfahren von Lucchesi et al. die folgenden Vorteile: das oben beschriebene Verfahren kann mit den Bytecodierungsverfahren der Codierungsanmel dung verwendet werden, um sehr kompakte Wortlistendaten zu erlangen. Das oben beschriebene Verfahren erfordert nicht die Speicherung von Daten, die eine Zählung für jeden Zustand angeben, wie bei dem Verfahren von Lucchesi et al. Statt dessen speichert das oben beschriebene Verfahren nur eine Zählung mit einem Zeiger, und Zeiger werden nur eingeschlossen, um einen Nutzen in Raum oder Zeit oder beiden bereitzustellen, so daß für viele Zustände keine zusätzlichen Daten, die eine Zählung angeben, gespeichert werden. Die zusätzlichen Daten, die erforderlich sind, um Daten zu speichern, die Zählungen angeben, betragen daher für das oben beschriebene Verfahren etwa 2- 2.5%, während etwa 35% an zusätzlichen Daten für das Verfahren von Lucchesi et al. erforderlich sind, weil jeder Übergang die gleiche Menge an Platz belegt.

D. N/W-Umwandlung

Die N/W-Umwandlung kann ebenfalls auf verschiedene Weise erfolgen, vorausgesetzt, die N/W-Umwandlung kehrt die W/N-Umwandlung um. Fig. 7 zeigt eine Routine zur N/W-Umwandlung, die für eine wie oben beschrieben gespeicherte Wortliste und für die oben beschriebenen W/N-Umwandlungsverfahren geeigenet ist. Im allgemeinen geht die Routine von Fig. 7 durch eine gespeicherte Wortliste, um die abzugleichende Zahl für jedes Byte mit gesetzten F-Daten zu dekrementieren. Die Zahl erreicht null am Ende des Wortes, das der Zahl, die umgewandelt wird, entspricht, und dieses Wort wird dann zurückgegeben.
In Fig. 7 beginnt die N/W-Umwandlung bei Kasten 500 mit einer Variablen ZAHL und einem leeren Stapel. Dieser Stapel wird von der Routine von Fig. 7 verwaltet, so daß er das Wort enthält, das der Zahl, die umgewandelt wird, entspricht, wenn die Routine endet. Alles, was nötig ist, um das entsprechende Wort zurückzubringen, ist folglich, den Inhalt des Stapels zu entladen und bereitzustellen.
Bei einer einfachen Wortliste wie der von Fig. 2 wäre es möglich, bei dem ersten Eintrag zu beginnen, wobei ZAHL die volle Zahl ist, die umgewandelt wird. Bei einer größeren Wortliste kann jedoch Zahl, die umgewandelt wird, benutzt werden, um direkt zu bestimmen, welches das erste Zeichen des Wortes ist, basierend auf einer ersten Zeichentabeile, die die Zahl enthält, die dem Wort entspricht, das unmittelbar dem ersten Wort beginnend mit jedem Zeichen vorangeht. Die umzuwandelnde Zahl kann mit diesen ersten Zeichenzahlen verglichen werden, um die größe zu finden, die kleiner als sie ist und die Differenz zwischen der Zahl, die umgewandelt wird, und dieser ersten Zeichenzahl ist der Anfangswert von ZAHL. Die momentane Stelle wird dann auf den ersten Zeichenübergang des Zeichens gesetzt, das dieser ersten Zeichenzahl entspricht. Wenn sich aber die Zahl, die umgewandelt wird, als größer erweist als die Zahl, die dem letzten Wort in den Wortlistendaten entspricht, wird nichts zurückgegeben. Außerdem werden, wenn die Zahl, die umgewandelt wird, null ist, die Wortlistendaten zu Anfang geprüft, um festzustellen, ob sie die Null- Zeichenfolge akzeptieren, und wenn ja, wird die Null-Zeichenfolge zurückgegeben. In der Regel wird jedoch die Routine zum Rest der in Fig. 7 gezeigten Routine gehen.
Die Prüfung in Kasten 502 stellt fest, ob das Byte an der momentanen Stelle eine Übergangseinheit ist, d.h., CHAR-Daten hat, oder ein Zeiger oder ein Zeigerindex ist. Wenn es eine Übergangseinheit ist, wird das Byte in Kasten 504 auf den Stapel geschoben, und die Stelle wird inkrementiert, um zu der nächsten Stelle in der FSM zu gehen. Wenn die Prüfung in Kasten 508 ergibt, daß3 die F-Daten der Übergangseinheit gesetzt sind, stellt die Prüfung in Kasten 510 fest, ob ZAHL gleich null ist. Wenn ZAHL null erreicht, wird in Kasten 512 das Wort in dem Stapel bereitgestellt, und die Umwandlung ist vollendet. Wenn aber ZAHL noch nicht null ist, wird ZAHL in Kasten 514 dekrementiert. Die Prüfung in Kasten 516 stellt dann fest, ob die EOB-Daten der Übergangseinheit gesetzt sind. Wenn ja, werden in Kasten 518 die Zeicheneinträge in dem LIFO-Stapel beginnend bei dem zuletzt geladenen gelöscht, bis ein Eintrag mit seinen ALT-Daten gesetzt erreicht wird, weil das gesuchte Wort seine Endung nicht in dieser Verzweigung hat. Dann kehrt die Routine zurück, um in Kasten 502 das Byte an der nächsten Stelle zu prüfen.
Wenn andererseits das Byte an der momentanen Stelle ein Zeiger oder ein Zeigerindex ist, vergleicht die Prüfung in Kasten 520 die F-Größe der Verzweigung, zu der der Zeiger oder der Zeigerindex führt, mit ZAHL. Die F-Größe wird entweder von ihrer Position in bezug auf den Zeiger oder, wenn die momentane Stelle einen Zeigerindex hat, von dem Suchtabelleneintrag zurückgewonnen, der diesem Index entspricht. Wenn die F-Größe größer als ZAHL ist, wird in Kasten 522 die Stelle auf die Stelle gesetzt, die durch den Zeiger oder durch den mit dem Zeigerindex wiedergewonnenen Zeiger angegeben wird, weil das gesuchte Wort innerhalb der Verzweigung der Wortdatenliste endet, die von dem Zeiger abhängt. Das Byte an dieser Stelle wird dann beginnend mit der Prüfung in Kasten 502 verarbeitet.
Wenn F-Größe kleiner als oder gleich ZAHL ist, wird sie in Kasten 524 von ZAHL subtrahiert. Die Routine geht dann in Kasten 526 zu der nächsten Stelle nach dem Zeiger oder dem Zeigerindex. Außßerdem wird der Schritt in Kasten 518 wie oben beschrieben ausgeführt, um Einträge aus dem Stapel zu löschen bis einer, der seine ALT-Daten gesetzt hat, erreicht wird. Die Routine kehrt dann zu der Prüfung in Kasten 502 zurück.
Beim Zurückgeben des Wortes aus dem Stapel in Kasten 512 ist es erforderlich, die codierten Übergangseinheiten zu decodieren, um die entsprechenden Zeichen zu erlangen. Wenn, wie oben beschrieben, ESC- Codes verwendet wurden, um die Zeichen in den Wortlistendaten zu codieren, umfaßt das Decodieren die Prüfung auf ESC-Codes. Wenn ein ESC- Code gefunden wird, wird die Zahl von aufeinanderfolgenden ESC-Codes gezählt, bis ein Code, der kein ESC-Code ist, gefunden wird. Die Zahl von ESC-Codes wird dann zusammen mit diesem Code in der Zeichencodetabelle benutzt, um den Ausgangscode für das passende Zeichen, z.B. einen ASCII-Code, zu finden.
Die N/W-Umwandlung ist folglich wie die W/N-Umwandlung imstande, über Verzweigungen der Wortlistendaten zu springen, während eine Zählung von Wortenden unterhalten wird. Weil mit jedem Verzweigungspunkt mit einer nächsten überspringbaren Verzweigung eine F-Größe verbunden ist, kann diese F-Größe verwendet werden, um die Zählung aufrechtzuerhalten. Des weiteren ist mit jedem solchen Verzweigungspunkt die notwendige Information verbunden, um die nächste Verzweigung zu überspringen, und diese Information kann in den Wortlistendaten durch Codieren jedes Zeigers oder Zeigerindexes gespeichert werden, um seine Länge anzugeben, und durch Positionieren der alternativen Verzweigung unmittelbar nach dem Zeiger (mit angehängter F-Größe) oder dem Zeigerindex, der zu der überspringbaren Verzweigung führt. Als Folge kann die Suche schnell durch die Wortlistendaten voranschreiten, wenn die Umwandlung vonstatten geht.

E. Anwendungen

Die oben beschriebenen Umwandlungsverfahren sind in diversen Anwendungen nützlich, von denen einige in Fig. 8-10 gezeigt werden.
Fig. 8 zeigt die Funktion des Verbindens von Information mit einem Wort unter Verwendung der W/N-Umwandlung. In Kasten 540 werden Wörter eingegeben, und in Kasten 542 wird jedes Wort umgewandelt. In Kasten 544 wird jede Zahl mit entsprechender Information verbunden, die dann in Kasten 546 ausgegeben wird. Ein Beispiel einer solchen Anwendung könnte ein Wörterbuch sein, bei dem das Verfahren von Fig. 8 benutzt wird, um die Definition eines eingegebenen Wortes wiederzugewinnen.
Fig. 9 zeigt eine Abwandlung von Fig. 8, bei der die mit jeder Zahl verbundene Information eine oder mehr Zahlen sind, die anderen Wörtern entsprechen. In Kasten 550 werden Wörter eingegeben und in Kasten 552 in Zahlen umgewandelt. Dann wird in Kasten 554 jede Zahl mit anderen Zahlen verbunden, die irgendeine Beziehung zu ihr tragen. Diese Zahlen werden in Kasten 556 in Wörter zurückverwandelt, und die sich ergebenden Wörter werden in Kasten 558 ausgegeben. Dieses Verfahren kann z.B. in einem Thesaurus verwendet werden, um verwandte Wörter wie Synonyme und Antonyme zu erlangen. Eine Übersetzungsfähigkeit könnte bereitgestellt werden, wobei der Benutzer ein Wort in einer von einer Anzahl von Sprachen eintippt und die Einrichtung mit einer Anzahl von Gruppen von Wörtern antwortet, wobei jede dieses Wort und Synonymwörter von anderen Sprachen umfaßt.
Fig. 10 zeigt, wie das Umwandeln bei Textkompression verwendet werden könnte. Eine Serie zu komprimierender Wörter wird in Kasten 560 empfangen, und in Kasten 562 wird jedes Wort in eine Zahl umgewandelt. Dann wird die Serie von Zahlen unter Verwendung geeigneter Kompressionsverfahren komprimiert, die zusätzliche Redundanz beseitigen. Die komprimierten Daten werden dann in Kasten 566 übertragen oder gespeichert, wonach sie in Kasten 568 in eine Serie von Zahlen dekomprimiert werden. Diese Zahlen werden in Kasten 570 in Wörter umgewandelt, und in Kasten 572 wird die Serie von Wörtern genauso wie sie empfangen wurde ausgegeben.

F. Verschiedenes

Unter bestimmten Umständen kann eine Anzahl von Modifikationen vorteilhaft sein. Bei der oben erörterten Codierung der Wortliste wird die Wortliste in der Form von übergangseinheiten codiert, und diejenigen Übergangseinheiten, die eine nächste Verzweigung oder eine alternative Verzweigung aufweisen, sind Verzweigungspunkte. Wenn ein Zustand in den Wortlistendaten eine größere Zahl ausgehender übergänge aufweist, könnte es vorteilhaft sein, die Verzweigungs- und Suffixendungsinformation mit dem entsprechenden Verzweigungspunkt dieses Zustandes in der Form einer Tabelle zu verbinden. Jeder Eintrag der Tabelle würde einem der ausgehenden übergänge entsprechen, um die Stelle der von diesem übergang abhängigen Verzweigung zu bezeichnen und eine F-Größe anzugeben. Diese F-Größe würde nicht die Anzahl von Suffixendungen in dieser Verzweigung sein, sondern würde die F-Größe aller Verzweigungen sein, die tatsächlich übersprungen werden würden, wenn diese Verzweigung genommen würde. Während der W/N-Umwandlung würde die Verzweigung genommen werden, wenn das Zeichen dieses ausgehenden Übergangs mit dem nächsten Zeichen eines Wortes, das gesucht wird, übereinstimmte. Während der N/W-Umwandlung würde die Verzweigung genommen werden, wenn die zugehörige F-Größe die größte F-Größe der Tabelle kleiner als die restliche Zahl wäre. Die Tabelleneinträge könnten auf der Basis der Zeichen der ausgehenden übergänge oder in jeder anderen geeigneten Weise geordnet werden.
Wie oben angemerkt würde eine andere Abwandlung darin bestehen, die an jedem Verzweigungspunkt gespeicherte Verzweigungsinformation zu modifizieren. Zum Beispiel könnte ein Zeiger auf die alternative Verzweigung anstatt auf die nächste Verzweigung gespeichert werden. Dieser Zeiger könnte ein relativer Zeiger sein, z.B. die Länge des nächsten Zweiges.
Eine weitere Abwandlung wäre, die Art und Weise zu modifizieren, in der Suffixendungsinformation mit dem Verzweigungspunkt verbunden wird. Anstatt an den Zeiger auf die nächste Verzweigung angehängt zu werden, könnte die Suffixendungsnummer am Anfang der nächsten Verzweigung gespeichert werden. Wenn die nächste Verzweigung Dreibyte-Zeiger auf sie hätte, würde dies ein Byte für jeden Dreibyte-Zeiger einsparen, obwohl eine größere Platzeinsparung aus der Änderung in Zweibyte-Zeigerindexe resultieren würde.

Claims

1. Erzeugnis, das umfaßt:

ein Speichermedium zum Speichern von Daten in maschinenzugänglicher Form und

durch das Speichermedium gespeicherte Wortlistendaten, wobei die Wortlistendaten eine Liste von Wörtern bezeichnen, wobei die Wortlistendaten umfassen:

eine Mehrzahl von Suffixdatenitems, die Suffixendungen von Wörtern in der Liste so bezeichnen, daß die Wortlistendaten verwendet werden können, eine Umwandlung zwischen jedem Wort in der Liste und einer betreffenden Zahl durchzuführen, wobei die Suffixdatenitems ein erstes Suffixdatenitem umfassen, das einen ersten Satz von Suffixendungen bezeichnet, die während der Umwandlung nicht übersprungen werden können, sowie ein zweites Suffixdatenitem, das einen zweiten Satz von Suffixendungen bezeichnet, die während der Umwandlung übersprungen werden können, wobei das erste Suffixdatenitem während der Umwandlung zugänglich ist, um eine Zählung von Suffixendungen in dem ersten Satz zu erlangen, wobei das zweite Suffixdatenitem während der Umwandlung zugänglich ist, um eine Zählung von Suffixendungen in dem zweiten Satz zu erlangen, und

ein erstes Verzweigungsdatenitem, wobei das erste Verzweigungsdatenitem umfaßt:

Verzweigungsnahmeinformation, die verwendet werden kann, um eine Umwandlung in bezug auf ein Wort durchzuführen, das mit einer der Suffixendungen in dem zweiten Satz endet, wobei die Verzweigungsnahmeinformation eine Stelle des zweiten Suffixdatenitems bezeichnet, und

Verzweigungsauslassungsinformation, die verwendet werden kann, um eine Umwandlung in bezug auf ein Wort durchzuführen, das nicht mit einer der Suffixendungen in dem ersten Satz endet, wobei die Verzweigungsauslassungsinformation eine Anzahl von Suffixendungen in dem zweiten Satz bezeichnet, wobei die Anzahl von Suffixendungen in dem ersten Suffixdatenitem nur durch Zugreifen auf das erste Suffixdatenitem erlangbar ist.

2. Erzeugnis nach Anspruch 1, bei dem das zweite Suffixdatenitem Suffixendungen einer ersten und zweiten Unterliste der Liste von Wörtern bezeichnet, die erste und zweite Unterliste verschieden sind, das erste Verzweigungsdatenitem beim Verwenden der Wortlistendaten erreicht wird, um zwischen den Wörtern in der ersten Unterliste und ihren Zahlen umzuwandeln, wobei die Wortlistendaten weiter ein zweites Verzweigungsdatenitem umfassen, das beim Verwenden der Wortlistendaten erreicht wird, um zwischen den Wörtern in der zweiten Unterliste und ihren Zahlen umzuwandeln, wobei das zweite Verzweigungsdatenitem umfaßt:

Verzweigungsauslassungsinformation, die verwendet werden kann, um eine Umwandlung in bezug auf ein Wort durchzuführen, das nicht mit einer der Suffixendungen in dem zweiten Satz endet, wobei die Verzweigungsauslassungsinformation eine Anzahl von Suffixendungen in dem zweiten Satz bezeichnet.

3. Erzeugnis nach Anspruch 1 oder 2, bei dem das Verzweigungsdatenitem weiter Markierungsinformation umfaßt, die wenigstens einen eines Satzes von Zeichentypen bezeichnet, wobei die Suffixdatenitems weiter ein drittes Suffixdatenitem umfassen, das einen dritten Satz Suffixendungen bezeichnet, die Wortlistendaten eine Folge von Datenitems umfassen, die das Verzweigungsdatenitem, das zweite Suffixdatenitem und das dritte Suffixdatenitem einschließt, die Verzweigungsnahmeinformation weiter angibt, ob das Verzweigungsdatenitem ein nächstes Datenitem in der Folge besitzt, bei dem die Umwandlung weitergehen kann, wenn ein momentanes Zeichen in dem Wort mit der Markierungsinformation übereinstimmt, wobei das nächste Datenitem das zweite Suffixdatenitem ist, wobei die Verzweigungsauslassungsinformation weiter angibt, ob das Verzweigungsdatenitem ein alternatives Datenitem in der Folge besitzt, bei dem die Umwandlung weitergehen kann, wenn ein momentanes Zeichen in dem Wort mit der Markierungsinformation nicht übereinstimmt, wobei das alternative Datenitem das dritte Suffixdatenitem ist.

4. Erzeugnis nach Anspruch 3, bei dem das dritte Suffixdatenitem in der Folge unmittelbar dem Verzweigungsdatenitem folgt.

5. Erzeugnis nach einem der vorangehenden Ansprüche, bei dem die Verzweigungsnahmeinformation Zeigerdaten umfaßt und die Verzweigungsauslassungsinformation Nummerndaten umfaßt, wobei die Nummerndaten an die Zeigerdaten angehängt sind.

6. Erzeugnis nach einem der vorangehenden Ansprüche, bei dem die Wortlistendaten weiter eine Tabelle mit einem Eintrag umfassen, der die Verzweigungsnahmeinformation und die Verzweigungsauslassungsinformation enthält, wobei das Verzweigungsdatenitem einen Index zu dem Eintrag in der Tabelle enthält.

7. Verfahren zum Umwandeln eines Wortes in eine Zahl unter Verwendung von Wortlistendaten, wobei die Wortlistendaten eine Liste von Wörtern bezeichnen, die das Wort enthält, wobei die Wortlistendaten umfassen:

eine Mehrzahl von Suffixdatenitems, die Suffixendungen von Wörtern in der Liste bezeichnen, wobei die Suffixdatenitems ein erstes Suffixdatenitem umfassen, das einen ersten Satz von Suffixendungen be-zeichnet, die während der Umwandlung nicht übersprungen werden können, sowie ein zweites Suffixdatenitem, das einen zweiten Satz von Suffixendungen bezeichnet, die während der Umwandlung übersprungen werden können, wobei das erste Suffixdatenitem während der Umwandlung zugänglich ist, um eine Zählung von Suffixendungen in dem ersten Satz zu erlangen, wobei das zweite Suffixdatenitem während der Umwandlung zugänglich ist, um eine Zählung von Suffixendungen in dem zweiten Satz zu erlangen, und

ein Verzweigungsdatenitem, wobei das Verzweigungsdatenitem umfaßt: Verzweigungsnahmeinformation, die eine Stelle des zweiten Suffixdatenitems bezeichnet, und

Verzweigungsauslassungsinformation, die eine Anzahl von Suffixendungen in dem zweiten Satz bezeichnet,

wobei die Anzahl von Suffixendungen in dem ersten Suffixdatenitem nur durch Zugreifen auf das erste Suffixdatenitem erlangbar ist,

wobei das Verfahren umfaßt:

Zugreifen auf das erste Suffixdatenitem und Verwenden des ersten Suffixdatenitems, um eine laufende Zählung von Suffixendungen basierend auf der Anzahl von Suffixendungen in dem ersten Suffixdatenitem zu aktualisieren;

Zugreifen auf das Verzweigungsdatenitem;

wenn ein Wort, das umgewandelt wird, eine Suffixendung in dem zweiten Satz von Suffixendungen hat, Verwenden der Verzweigungsnahmeinformation, um auf das zweite Suffixdatenitem zuzugreifen, und

wenn das Wort, das umgewandelt wird, keine Suffixendung in dem zweiten Satz von Suffixendungen hat, Verwenden der Verzweigungsauslassungsinformation, um die laufende Zählung von Suffixendungen zu aktualisieren.

8. Verfahren nach Anspruch 7, bei dem der Schritt des Verwendens der Verzweigungsauslassungsinformation das Addieren der Anzahl von Suffixendungen in dem zweiten Satz zu der Zählung von Suffixendungen umfaßt.

9. Verfahren nach Anspruch 8, bei dem die Suffixdatenitems weiter ein drittes Suffixdatenitem umfassen, das einen dritten Satz von Suffixendungen bezeichnet, wobei das dritte Suffixdatenitem eine Folge von Bytes umfaßt, wobei die Bytes für jede Suffixendung in dem dritten Satz ein Suffixendungsbyte umfassen, das die Suffixendung bezeichnet, wobei das Verfahren weiter umfaßt, wenn das Wort, das umgewandelt wird, eine Suffixendung hat, die nicht in dem zweiten Satz von Suffixendungen ist:

Zugreifen auf das dritte Suffixdatenitem;

Abtasten der Folge von Bytes, Inkrementieren der Zählung von Suffixendungen für jedes Suffixendungsbyte, bis ein Suffixendungsbyte erreicht wird, das eine Suffixendung des Wortes, das umgewandelt wird, bezeichnet, und

Bereitstellen der Zählung von Suffixendungen als eine Zahl für das Wort, das umgewandelt wird.

10. Verfahren nach einem der Ansprüche 7 bis 9, bei dem das Verzweigungsdatenitem weiter Markierungsinformation umfaßt, die ein Zeichen bezeichnet, das jeder Suffixendung in dem zweiten Satz von Suffixendungen vorangeht, wobei das Verfahren weiter umfaßt:

Vergleichen eines Zeichens von dem Wort, das umgewandelt wird, mit der Markierungsinformation, um festzustellen, ob das Wort, das umgewandelt wird, eine Suffixendung in dem zweiten Satz von Suffixendungen hat.

11. Verfahren zum Umwandeln einer Zahl in ein Wort unter Verwendung von Wortlistendaten, wobei die Wortlistendaten eine Liste von Wörtern bezeichnen, die das Wort enthält, wobei die Wortlistendaten umfassen:

eine Mehrzahl von Suffixdatenitems, die Suffixendungen von Wörtern in der Liste bezeichnen, wobei die Suffixdatenitems ein erstes Suffixdatenitem umfassen, das einen ersten Satz von Suffixendungen bezeichnet, die während der Umwandlung nicht übersprungen werden können, sowie ein zweites Suffixdatenitem, das einen zweiten Satz von Suffixendungen bezeichnet, die während der Umwandlung übersprungen werden können, wobei das erste Suffixdatenitem während der Umwandlung zugänglich ist, um eine Zählung von Suffixendungen in dem ersten Satz zu erlangen, wobei das zweite Suffixdatenitem während der Umwandlung zugänglich ist, um eine Zählung von Suffixendungen in dem zweiten Satz zu erlangen, und

ein Verzweigungsdatenitem, wobei das Verzweigungsdatenitem umfaßt:

Verzweigungsnahmeinformation, die eine Stelle des zweiten Suffixdatenitems bezeichnet, und

Verzweigungsnahmeinformation, die eine Anzahl von Suffixdagen in dem zweiten Satz bezeichnet,

wobei das Verfahren umfaßt:

Zugreifen auf das Verzweigungsdatenitem;

wenn eine Zahl, die umgewandelt wird, ein Wort mit einer Suffixendung in dem zweiten Satz von Suffixendungen hat, Verwenden der Verzweigungsnahmeinformation, um auf das zweite Suffixdatenitem zuzugreifen, und

wenn die Zahl, die umgewandelt wird, ein Wort mit einer Suffixendung hat, die nicht in dem zweiten Satz von Suffixendungen ist, Verwenden der Verzweigungsauslassungsinformation, um die laufende Zählung von Suffixendungen zu aktualisieren.

12. Verfahren nach Anspruch 11, bei dem der Schritt des Verwendens der Verzweigungsauslassungsinformation das Subtrahieren der Anzahl von Suffixendungen in dem zweiten Satz von der Zählung von Suffixendungen umfaßt, wobei die Zählung von Suffixendungen als die Zahl, die umgewandelt wird, beginnt.

13. Verfahren nach Anspruch 12, bei dem die Suffixdatenitems weiter ein drittes Suffixdatenitem umfassen, das einen dritten Satz von Suffixendungen bezeichnet, wobei das dritte Suffixdatenitem eine Folge von Bytes umfaßt, wobei die Bytes für jede Suffixendung in dem dritten Satz ein Suff ixendungsbyte umfassen, das die Suffixendung bezeichnet, wobei die Bytes weiter Markierungsbytes umfassen, wobei jedes Markierungsbyte ein Zeichen in einer Suffixendung in dem dritten Satz bezeichnet, wobei das Verfahren weiter umfaßt, wenn die Zahl, die umgewandelt wird, ein Wort mit einer Suffixendung hat, die nicht in dem zweiten Satz von Suffixendungen ist:

Zugreifen auf das dritte Suffixdatenitem;

Abtasten der Folge von Bytes, Aktualisieren eines Stapels, um Zeichen zu speichern, die ein momentanes Präfix für jedes Markierungsbyte bezeichnen, und Dekrementieren der Zählung von Suffixendungen für jedes Suffixendungsbyte, bis die Zählung von Suffixendungen null erreicht und

Bereitstellen des momentanen Präfixes von dem Stapel als ein Wort für die Zahl, die umgewandelt wird.

14. Verfahren nach einem der Ansprüche 11 bis 13, weiter umfassend:

Vergleichen der Zählung von Suffixendungen mit der Anzahl von Suffixendungen in dem zweitei Satz, um festzustellen, ob die Zahl, die umgewandelt wird, ein Wort mit einer Suffixendung in dem zweiten Satz von Suffixendungen hat.