DE4323241A1

DE4323241A1 - Verfahren und Computersystem zur Suche fehlerhafter Zeichenketten in einem Text

Info

Publication number: DE4323241A1
Application number: DE4323241A
Authority: DE
Inventors: Andreas Arning
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1993-07-12
Filing date: 1993-07-12
Publication date: 1995-02-02
Also published as: EP0635795A3; EP0635795A2; US5715469A; JPH0778165A

Description

Die Erfindung betrifft ein Verfahren und ein Computersystem zur Suche und/oder Korrektur einer fehlerhaften Zeichenkette in einem Text.

In bekannten Textverarbeitungssystemen erfolgt die Speicherung des eingegebenen Texts getrennt von einem "Lexikon". Das zu dem Textverarbeitungssystem gehörende "Lexikon" ist eine Datei, welche eine mehr oder weniger umfassende Liste bekann ter Wörter und gegebenenfalls auch deren flektierte Formen - also deren Konjugationen und Deklinationen - enthält. Zur Suche von Fehlern in dem Text wird jedes einzelne Wort in dem Lexikon gesucht. Falls ein Wort nicht in dem Lexikon enthalten sein sollte, gibt das Textverarbeitungssystem eine Fehlermel dung ab und fordert den Benutzer zu einer Überprüfung des entsprechenden Wortes auf. Solche Systeme sind beispielsweise aus den US-Patenten 4 689 678, 4 671 684 und 4 777 617 be kannt.

Ferner ist beispielsweise aus der US-Patentschrift 4 674 065 ein Textverarbeitungssystem bekannt, das auf einer statisti schen N-gram Analysetechnik des Textes beruht. Dem Benutzer werden dabei mögliche richtige Alternativen eines als falsch erkannten Wortes zur Auswahl angezeigt.

Ein Überblick über bekannte Techniken zur automatischen Kor rektur von Wörtern in einem Text bietet die Veröffentlichung "Techniques for Automatically Correcting Words in Text" von Caron Kukich, ACM Computing Surveys, Volume 24, No. 4, Dezem ber 1992.

Den bekannten Verfahren zur Fehlersuche und Fehlerkorrektur ist gemeinsam, daß ein vom zu überprüfenden Text getrenntes Lexikon als Vergleichsnormal verwendet wird. Dadurch bedingt ist bei den bekannten Systemen ein relativ großer Speicher platz für die Speicherung des Lexikons vorgesehen, der dann für andere Anwendungen nicht mehr zur Verfügung steht.

Weitere Nachteile der Verwendung eines Lexikons sind, daß in dem Lexikon selbst i.a. einige Fehler enthalten sind, so daß es als Vergleichsnormal nicht zuverlässig ist. Schließlich läßt sich das verwendete Lexikon selbst nicht mittels eines Textverarbeitungssystems auf Fehler überprüfen, da ein Lexikon ohnehin bereits das zuverlässigste zur Verfügung stehende Vergleichsnormal ist. Ferner muß das Lexikon ständig aktuali siert werden, wodurch sich weitere Fehler in dem Lexikon einschleichen können. Die Verwendung bekannter Textverarbei tungssysteme ist zur Überprüfung mehrsprachiger Texte prak tisch ungeeignet, da durch die Verwendung eines Lexikons alle fremdsprachigen Wörter, die nicht in dem Lexikon vorkommen, als fehlerhaft angezeigt werden. Dasselbe trifft auch auf einsprachige Texte zu, die ungewöhnliche Wörter oder Wortneu schöpfungen enthalten, wie auch auf Computercode oder Texte, die mit Lautschriftinformation oder Formatierungs-Steuerzei chen versehen sind. In diesen Fällen zeigen bekannte Textver arbeitungssysteme eine Vielzahl von an sich richtigen Zeichen ketten als fehlerhaft an, da diese Zeichenketten nicht in dem Lexikon gespeichert sind. Dieses Problem tritt besonders stark zu Tage, falls der zu überprüfende Text ein Abkürzungslexikon oder Formellexikon ist oder falls der Text Eigennamen enthält, die ebenfalls nicht in dem Lexikon gespeichert sind.

Der Erfindung liegt daher die Aufgabe zugrunde, ein verbesser tes Verfahren und Computersystem zur Suche und/oder Korrektur einer fehlerhaften Zeichenkette in einem Text zu schaffen.

Die der Erfindung zugrunde liegende Aufgabe wird durch die in den Patentansprüchen 1 oder 13 aufgeführten Merkmale gelöst.

Vorteilhafte Ausgestaltungen sind in den weiteren Ansprüchen angegeben.

Durch die Erfindung erübrigt sich die Speicherung eines Lexi kons, so daß auch die damit einhergehenden oben beschriebenen Nachteile des Standes der Technik weitgehend behoben sind. Im Gegensatz zu vorbekannten Textverarbeitungssystemen wird nach der Erfindung der Text nicht anhand eines Lexikons überprüft, sondern der Text selbst einer statistischen Analyse unterwor fen, die als Grundlage für die Fehlersuche dient. Dazu bedarf es keiner externen Lexika. Für die Suche fehlerhafter Schreib weisen einer vom Benutzer vorgegebenen fehlerfreien Zeichen kette, die in dem Text vorkommt, bildet die Auftretenshäufig keit der fehlerfreien Zeichenkette in dem Text die Grundlage. Die Auftretenshäufigkeit der fehlerfreien Zeichenkette dient als Maßstab für die Wahrscheinlichkeit, daß eine mögliche fehlerhafte Zeichenkette in dem Text tatsächlich eine fehler hafte Zeichenkette ist, die der fehlerfreien Zeichenkette entspricht. Die so erkannte fehlerhafte Zeichenkette kann dann - sofern sie mehrfach in dem Text vorkommt - automatisch in dem gesamten Text durch deren entsprechende fehlerfreie Zei chenkette ersetzt werden.

In einer Ausführungsform der Erfindung wird zunächst die von dem Benutzer spezifizierte und in dem Text vorkommende fehler freie Zeichenkette nach zumindest einer Regel verändert, so daß eine oder mehrere mögliche fehlerhafte Zeichenketten erzeugt werden. Zur Entscheidung, ob eine mögliche fehlerhafte Zeichenkette tatsächlich eine der vom Benutzer spezifizierten fehlerfreien Zeichenkette entsprechende fehlerhafte Zeichen kette ist, wird dann die Auftretenshäufigkeit der betreffenden möglichen fehlerhaften Zeichenkette in dem Text ermittelt. Die Auftretenshäufigkeiten der fehlerfreien und der möglichen fehlerhaften Zeichenkette werden verglichen, wobei dieser Vergleich die Entscheidungsgrundlage dafür bildet, ob die betreffende mögliche fehlerhafte Zeichenkette tatsächlich die gesuchte fehlerhafte Zeichenkette; ist. Der Vergleich der Auftretenshäufigkeiten nutzt die Tatsachen daß ein in dem Text häufig vorkommendes Wort mit großer Wahrscheinlichkeit auch einmal fehlerhaft eingegeben wurde. Je größer also das Ver hältnis der Auftretenshäufigkeit der fehlerfreien Zeichenkette zur Auftretenshäufigkeit der möglichen fehlerhaften Zeichen kette ist, desto größer ist auch- die Wahrscheinlichkeit, daß die mögliche fehlerhafte Zeichenkette tatsächlich eine ge suchte fehlerhafte Zeichenkette ist.

Um diese Suche nach fehlerhaften Zeichenketten in dem Text noch effektiver zu gestalten, wird nach einer bevorzugten Ausführungsform der Erfindung die zur Veränderung der fehler freien Zeichenkette verwendete Regel bzw. die verwendeten Regeln so gewählt, daß psychologische und/oder durch das verwendete Computersystem, insbesondere durch dessen Tastatur, bedingte mögliche Fehlerquellen simuliert werden. Für durch die Tastatur bedingte Eingabefehler bedeutet dies beispiels weise, daß anstelle des gewünschten Zeichens ein Nachbar dieses Zeichens auf der Tastatur getroffen wird. Tritt bei spielsweise aufgrund der verwendeten Tastatur häufig der Fall auf, daß das Zeichen "b" anstelle seines benachbarten Zeichens "v" getroffen wird, so kann dies durch eine entsprechende Regel berücksichtigt werden. Durch Anwendung der entsprechen den Regel wird dann ein in der fehlerfreien Zeichenkette vorkommendes Zeichen "v" durch das Zeichen "b" ausgetauscht, so daß aus der fehlerfreien Zeichenkette eine mögliche fehler hafte Zeichenkette erzeugt wird, die mit großer Wahrschein lichkeit auch tatsächlich in dem Text vorkommt. Für eine einzige fehlerfreie Zeichenkette kann dieser Vorgang anhand verschiedener Regeln wiederholt werden, um verschiedene Feh lermöglichkeiten zu simulieren.

Die Wahrscheinlichkeit, daß durch die Anwendung einer bestimm ten Regel eine mögliche fehlerhafte Zeichenkette erzeugt wird, die tatsächlich eine gesuchte fehlerhafte in dem Text vorkom mende Zeichenkette ist, kann - je nach der verwendeten Regel - von dem Benutzer oder dem verwendeten Computersystem oder auch von beiden gleichzeitig abhängen. Diese Wahrscheinlichkeit kann zeitlichen Schwankungen unterworfen sein, etwa weil der Benutzer bestimmte Fehlertypen zu vermeiden lernt, weil sich der Benutzer ändert und der andere Benutzer im Vergleich zum vorherigen zu anderen Fehlertypen neigt oder weil das verwen dete Computersystem durch ein anderes mit einer anderen Tasta tur ausgetauscht wird. Dies kann durch ein Verfahren zum maschinellen Lernen berücksichtigt werden, das die Erfolgs wahrscheinlichkeiten der verwendeten Regeln registriert. Wird mittels des Verfahrens zum maschinellen Lernen erkannt, daß eine Regel besonders häufig zur Auffindung einer fehlerhaften Zeichenkette führt, so wird diese Regel bevorzugt zur Anwen dung kommen und mit einem Faktor gewichtet werden. Eine Ini tialisierung dieser Faktoren kann auch mittels einer Trai ningssequenz gefunden werden.

Nach einer weiteren bevorzugten Ausführungsform wird der gesamte Text automatisch überprüft. Hierzu werden zunächst die Auftretenshäufigkeiten sämtlicher in dem Text vorkommenden unterschiedlichen Zeichenketten ermittelt. Diejenigen Zeichen ketten, deren Auftretenshäufigkeit größer als ein bestimmter Schwellwert ist, werden als fehlerfreie Zeichenketten defi niert. Denn eine sehr häufig in einem Text vorkommende Zei chenkette ist mit hoher Wahrscheinlichkeit fehlerfrei. Die so definierten fehlerfreien Zeichenketten bzw. deren Auftretens häufigkeit dienen dann als Grundlage für die Fehlersuche.

Nach einer weiteren bevorzugten Ausführungsform betrifft die Erfindung ein System zur Zeichenerkennung, welches ein System zur maschinellen optischen Zeichenerkennung beinhaltet. Das System zur maschinellen optischen Zeichenerkennung kann bei spielsweise zur Eingabe eines gedruckten Textes in ein Compu tersystem dienen, wobei der von dem System zur maschinellen optischen Zeichenerkennung gelieferte Rohtext, der in das Computersystem eingegeben wird, nicht fehlerfrei ist. Dies kann einerseits darauf beruhen, daß in dem gedruckten Text Fehler enthalten sind oder daß das System zur maschinellen optischen Zeichenerkennung nicht fehlerfrei arbeitet. Der in das Computersystem eingegebene Rohtext wird mittels des Compu tersystems erfindungsgemäß auf Fehler überprüft, so daß insbe sondere auch Unzulänglichkeiten des Systems zur maschinellen optischen Zeichenerkennung hierdurch weitgehend korrigiert werden können. Ein auf einer N-gram Technik beruhendes Verfah ren zur Unterstützung einer zeichenerkennenden Vorrichtung ist aus der US 4 058 795 bekannt.

Nach einer weiteren bevorzugten Ausführungsform betrifft die Erfindung ein System zur automatischen Aufnahme eines Diktats, welches ein System zur Spracherkennung beinhaltet. Systeme zur Spracherkennung sind an sich beispielsweise aus den US-Patenten 4 783 803, 4 741 036, 4 718 094 und 4 164 025 bekannt.

Das System zur Spracherkennung erzeugt einen im allgemeinen Fehler behafteten Rohtext, der in ein Computersystem eingege ben wird. Mittels des Computersystems findet dann die erfin dungsgemäße Fehlersuche und/oder Korrektur in dem Rohtext statt.

Nach einer weiteren bevorzugten Ausführungsform betrifft die Erfindung ein Speichermedium, welches für den Einsatz in einem programmierbaren Computersystem geeignet ist. Dem Speicherme dium ist durch einen physikalischen und/oder chemischen Vor gang ein Programm zur Ausführung eines erfindungsgemäßen Verfahrens eingeprägt. Durch diesen physikalischen und/oder chemischen Vorgang erhält das Speichermedium die Eigenschaft, mit dem programmierbaren Computersystem so zusammenwirken zu können, daß das an sich für beliebige Zwecke geeignete pro grammierbare Computersystem zu einem erfindungsgemäßen Compu tersystem umgewandelt werden kann.

Ausführungsbeispiele der Erfindung sind in der Zeichnung dargestellt und werden im folgenden näher beschrieben.

Es zeigen:

Fig. 1 ein schematisches Flußdiagramm einer ersten Ausfüh rungsform,

Fig. 2 ein schematisches Flußdiagramm einer zweiten Ausfüh rungsform der Erfindung,

Fig. 3 eine Darstellung einer zur Speicherung von Zeichen ketten bevorzugten Speicherstruktur gemäß der Erfin dung,

Fig. 4 ein erfindungsgemäßes Computersystem.

Das in Fig. 1 dargestellte Flußdiagramm kann sich beispiels weise auf ein erfindungsgemäßes Textverarbeitungssystem bezie hen, in das bereits ein zu überprüfender Text eingegeben worden ist. In einem Schritt 10 wählt der Benutzer eine feh lerfreie Zeichenkette S_i, die in dem eingegebenen Text vor kommt, aus. Ziel des erfindungsgemäßen Verfahrens ist es nun, zumindest eine fehlerhafte Zeichenkette F_i in dem Text zu suchen, die der ausgewählten fehlerfreien Zeichenkette S_i entspricht, d. h. beispielsweise gegenüber der fehlerfreien Zeichenkette S₁ einen Schreibfehler aufweist.

Dazu wird in dem Schritt 11 eine mögliche fehlerhafte Zeichen kette f_ÿ erzeugt. Die mögliche fehlerhafte Zeichenkette f_ÿ geht aus der fehlerfreien Zeichenkette S_i durch Anwendung einer Regel R_j hervor. In dem Schritt 11 werden dabei vorzugs weise durch Anwendung der Regel R_j bezüglich verschiedener Buchstaben und/oder Buchstabenpositionen mehrere mögliche fehlerhafte Zeichenketten f_ÿ aus der fehlerfreien Zeichenket te S_i erzeugt.

In einem Schritt 12 wird zum Vergleich der Auftretenshäufig keit H(S_i) der fehlerfreien Zeichenkette S_i und der Auftre tenshäufigkeit H(f_ÿ) der möglichen fehlerhaften Zeichenkette f_ÿ ein Wert α_ÿ berechnet.

In einem Schritt 13 wird der in Schritt 12 berechnete Wert α_ÿ mit einem Schwellwert β verglichen. Trifft die Bedingung α_ÿ < β zu, so wird in Schritt 14 als Ergebnis der Suche defi niert, daß die mögliche fehlerhafte Zeichenkette f_ÿ die ge suchte fehlerhafte Zeichenkette F_i ist. Dieses Ergebnis kann zur automatischen Korrektur aller vorkommenden Zeichenketten F_i in dem Text verwendet werden. Vor dieser Korrektur kann das so ermittelte Ergebnis dem Benutzer zur Kontrolle angezeigt werden. In diesem Fall wird die automatische Korrektur nur dann vorgenommen, falls der Benutzer dem vorgeschlagenen Ergebnis zustimmt.

Trifft die Bedingung α_ÿ < β nicht zu, so wird der Index j in einem Schritt 15 um eins erhöht. Dies hat zur Folge, daß in dem darauffolgenden Schritt 11 zur Erzeugung einer weiteren möglichen fehlerhaften Zeichenkette eine andere Regel R_j+1 verwendet wird. Die so erzeugte weitere mögliche fehlerhafte Zeichenkette f_i+1,j+1 stellt einen weiteren Kandidaten dar, der einer fehlerhaften Zeichenkette F_i entsprechen könnte. In den nachfolgenden Schritten 12 und 13 wird wiederum ermittelt, ob dies tatsächlich der Fall ist und gegebenenfalls wird in Schritt 14 das entsprechende Ergebnis definiert.

Nach dem in Fig. 1 dargestellten Flußdiagramm wird das Ver fahren dann beendet, sobald eine fehlerhafte Zeichenkette F_i in dem Schritt 14 ermittelt wurde. Es kann jedoch auch so sein, daß auch in diesem Fall noch weitere mögliche fehler hafte Zeichenketten f_ÿ mittels anderer Regeln R_j gebildet werden. Dies entspricht den oben beschriebenen Schritten 15 und 11. Dadurch können noch weitere fehlerhafte Zeichenketten F_i gefunden werden, die beispielsweise durch andere Eingabe fehler aus der in Schritt 10 ausgewählten fehlerfreien Zei chenkette S_i hervorgegangen sind.

In diesem Fall ist es auch möglich, daß zunächst in mehreren aufeinanderfolgenden Schritten 14 verschiedene fehlerhafte Zeichenketten F_i als Ergebnis der Suche definiert werden und diese fehlerhafte Zeichenketten dem Benutzer sodann nach den entsprechenden Werten α_ÿ sortiert angezeigt werden. Da die Werte α_ÿ ein Maß für die Wahrscheinlichkeit darstellen, daß eine mögliche fehlerhafte Zeichenkette f_ÿ tatsächlich eine in dem Text vorkommende fehlerhafte Zeichenkette F_i ist, werden dem Benutzer dadurch die Ergebnisse deren Zutreffenswahr scheinlichkeit nach sortiert angezeigt.

Im Gegensatz zu bekannten Lexikon oder N-gram basierten Syste men bildet hier also nicht eine extern abgespeicherte Infor mation - etwa in Form eines separat gespeicherten Lexikons - die Grundlage für die Fehlersuche, sondern der zu überprüfende Text selbst. Nach der Erfindung wird die sonst extern abge speicherte Information aus dem zu überprüfenden Text selbst durch Ermittlung der Auftretenshäufigkeit H(S_i) gewonnen. Nimmt die Auftretenshäufigkeit H(S_i) große Werte an, wird nämlich erfindungsgemäß davon ausgegangen, daß eine ver gleichsweise in dem Text selten vorkommende mögliche fehler hafte Zeichenkette f_ÿ tatsächlich einer gesuchten fehler haften Zeichenkette F_i entspricht. Hierzu bedarf es keinerlei extern abgespeicherter Informationen, wodurch auch der ent sprechende Aufwand entfällt.

Vorzugsweise sind die im Schritt 11 zur Erzeugung der mög lichen fehlerhaften Zeichenketten f_ÿ verwendeten Regeln R_j so gewählt, daß psychologische und/oder durch das verwendete Computersystem, insbesondere durch dessen Tastatur, bedingte mögliche Fehlerquellen simuliert werden. Psychologisch be dingte Fehler sind beispielsweise solche Schreibfehler, die beim Korrektur lesen besonders schlecht gefunden werden - wie etwa Schreibfehler in besonders langen Wörtern. Ein durch die Tastatur bedingter Fehler ist beispielsweise eine durch Prel len der Tastatur bedingte unbeabsichtigte Buchstabenver doppelung. Eine unbeabsichtigte Mehrfacheingabe oder Aus lassung eines Zeichens mittels einer Tastatur kann auch da durch entstehen, daß die Tastatur einen schlecht definierten Druckpunkt aufweist.

Die in dem Schritt 12 erfolgende Berechnung des Wertes α_ÿ kann nach einer Rechenvorschrift

(1) Φ_ÿ (H(f_ÿ), H(S_i)) = α_ÿ

erfolgen. Diese Rechenvorschrift kann dabei vorzugsweise die Form

haben, wobei Φ_ÿ eine von der Auftretenshäufigkeit H(f_ÿ) und der Auftretenshäufigkeit H(S_i) abhängige Funktion ist, der Wert Ψ ein Faktor ist und der Wert eine Potenz darstellt.

Der Faktor Ψ kann dabei nach der Formel

(3) Ψ = [L(S_i)]^p

berechnet werden, wobei mittels der Funktion L die Länge der Zeichenkette S_i oder, mit anderen Worten, die Anzahl der in der Zeichenkette S_i beinhalteten Zeichen ermittelt wird. Der Wert p stellt eine Potenz dar, die vorzugsweise quadratisch oder kubisch ist.

Der in der Formel (2) enthaltene Quotient

ist maßgeblich für die Errechnung des Werts A_ÿ. Der Grund hierfür ist, daß dieser Quotient umso größer wird, je öfter die fehlerfreie Zeichenkette S_i und je seltener die generierte mögliche fehlerhafte Zeichenkette f_ÿ in dem Text auftritt. Die Bildung dieses Quotienten beruht auf der Erfahrung, daß eine Zeichenkette, die sehr oft in einem Text vorkommt, mit hoher Wahrscheinlichkeit fehlerfrei ist, und daß ferner die Wahrscheinlichkeit dafür, daß die betreffende Zeichenkette auch einmal fehlerhaft - z. B. aufgrund eines Eingabefehlers - in den Text vorkommt umso größer wird, je häufiger die fehler freie Zeichenkette in dem Text ist. Mittels des Korrekturfak tors Ψ kann zusätzlich berücksichtigt werden, daß mit zuneh mender Länge einer Zeichenkette auch die Wahrscheinlichkeit wächst, daß die Zeichenkette einen Fehler beinhaltet, insbe sondere auch deswegen, weil Fehler in langen Zeichenketten vom Benutzer im allgemeinen schlecht erkannt werden. Ferner wird durch den Faktor Ψ berücksichtigt, daß mit zunehmender Wort länge die Wahrscheinlichkeit dafür abnimmt, daß eine Verände rung der fehlerfreien Zeichenkette S_i nach einer Regel R_j auf eine andere in dem Text vorkommende fehlerfreie Zeichenkette S_i führt. Dies hat besonders starken Einfluß auf die Berech nung des Wertes α_ÿ, falls für die Potenz p etwa der Wert 2 oder 3 gewählt wird. Der Wert hat in dem in Fig. 1 gezeigten Ausführungsbeispiel den Wert 1. Wählt man den Wert -1, so ist lediglich in dem Schritt 13 die Bedingung α_ÿ < β durch die Bedingung α_ÿ < β auszutauschen. Der einfachen Darstellung halber wird im weiteren nur noch der Fall = 1 betrachtet, ohne die Allgemeingültigkeit einzuschränken.

Der mittels der Formel (2) berechnete Wert α_ÿ wird demzufolge umso größer, je größer die Wahrscheinlichkeit ist, daß eine mögliche fehlerhafte Zeichenkette f_ÿ tatsächlich eine gesuch te fehlerhafte Zeichenkette F_i ist. In dem Schritt 13 wird daher überprüft, ob die so gefundene auf einem Vergleich der Auftretenshäufigkeiten H(S_i) und H(f_ÿ) basierende Aussage ein hinreichendes Maß an Sicherheit für die Definition eines Ergebnisses in dem Schritt 14 begründet. Die Wahl des entspre chenden Schwellwertes β hängt dabei von den Bedürfnissen des Benutzers ab: Bei einem großen Schwellwert β ist das in dem Schritt 14 ermittelte Ergebnis mit an Sicherheit grenzender Wahrscheinlichkeit richtig, während jedoch auch zu einem richtigen Ergebnis führende mögliche fehlerhafte Zeichenketten f_ÿ in dem Schritt 13 verworfen werden. Das Gegenteil ist bei einer Wahl eines kleinen Wertes für den Schwellwert β der Fall.

Die folgende Tabelle gibt einige Beispiele für mögliche Regeln R_j an. Ferner ist für jede Regel ein Beispiel angegeben, welches eine fehlerfreie Zeichenkette S_i und die entsprechende mögliche fehlerhafte Zeichenkette f_ÿ sowie den dazugehörigen Wert α_ÿ enthält. Hinter den Zeichenketten S_i und f_ÿ sind jeweils die entsprechenden Auftretenshäufigkeiten in dem untersuchten Text angegeben. Der untersuchte Text ist der Sportteil der Frankfurter Rundschau 1988.

Tabelle 1

Regel R₁: Vertauschung von zwei aufeinanderfolgenden Buchstaben.
Beispiel:
f₁₁ = "Olmypischen"(1)
S₁ = "Olympischen"(875)
α₁₁ = 1164625
Regel R₂: Auslassung eines mindestens zweimal vorkommen den Buchstabens.
Beispiel:
f₂₂ = "Präsidumssitzung"(1)
S₂ = "Präsidiumssitzung"(7)
α₂₂ = 40824
Regel R₃: Auslassung eines höchstens einmal vorkommenden Buchstabens.
Beispiel:
f₃₃ = "Diziplinen"(1)
S₃ = "Disziplinen"(89)
α₃₃ = 118459
Regel R₄: Verdopplung eines Buchstabens.
Beispiel:
f₄₄ = "Baskettball"(2)
S₄ = "Basketball"(179)
α₄₄ = 89500
Regel R₅: Ersetzung eines Buchstabens.
Beispiel:
f₅₅ = "Golopprennbahn"(1)
S₅ = "Galopprennbahn"(34)
α₅₅ = 93296
Regel R₆: Hinzufügung eines Buchstabens, der noch nicht in dem Wort vorkommt.
Beispiel:
f₆₆ = "Wiederanspfiff"(1)
S₆ = "Wiederanpfiff"(47)
α₆₆ = 103259
Regel R₇: Hinzufügung eines Buchstabens, der bereits in dem Wort vorkommt.
Beispiel:
f₇₇ = "Ablöseseumme"(1)
S₇ = "Ablösesumme"(91)
α₈₈ = 157248
Regel R₈ Verdopplung des falschen Buchstabens, hier: LINKER Nachbar.
Beispiel:
f₈₈ = "Spvvg"(4)
S₈ = "Spvgg"(142)
α₈₈ = 4435
Regel R₉: Verdopplung des falschen Buchstabens im Wort, hier: RECHTER Nachbar.
Beispiel:
f₉₉ = "Sperrwerfen"(1)
S₉ = "Speerwerfen"(19)
α₉₉ = 25289
Regel R₁₀: ANSTELLE des gewünschten Buchstabens wurde der RECHTE Nachbar auf der Tastatur getroffen.
Beispiel:
f_{10 10} = "erfolgteich"(1)
S₁₀ = "erfolgreich"(290)
α_{10 10} = 385990
Regel R₁₁: ZUSÄTZLICH zum gewünschten Buchstaben wurde der RECHTE Nachbar auf der Tastatur getroffen; Ein fügung VOR dem beabsichtigten Buchstaben.
Beispiel:
f_{11 11} = "Cjhristian"(1)
S₁₁ = "Christian"(175)
α_{11 11} = 127575
Regel R₁₂: ZUSÄTZLICH zum gewünschten Buchstaben wurde der RECHTE Nachbar auf der Tastatur getroffen; Ein fügung NACH dem beabsichtigten Buchstaben.
Beispiel:
f_{12 12} = "Verletzunmg"(1)
S₁₂ = "Verletzung"(153)
α_{12 12} = 153000
Regel R₁₃: ANSTELLE des gewünschten Buchstabens wurde der LINKE Nachbar auf der Tastatur getroffen.
Beispiel:
f_{13 13} = "Problene"(1)
S₁₃ = "Probleme"(290)
α_{13 13} = 148480
Regel R₁₄: ZUSÄTZLICH zum gewünschten Buchstaben wurde der LINKE Nachbar auf der Tastatur getroffen; Ein fügung VOR dem beabsichtigten Buchstaben.
Beispiel:
f_{14 14} = "Hoffnungsträgwer"(1)
S₁₄ = "Hoffnungsträger"(18)
α_{14 14} = 73728
Regel R₁₅: ZUSÄTZLICH zum gewünschten Buchstaben wurde der LINKE Nachbar auf der Tastatur getroffen; Ein fügung NACH dem beabsichtigten Buchstaben.
Beispiel:
f_{15 15} = "Qualkifikation"(1)
S₁₅ = "Qualifikation"(255)
α_{15 15} = 560235
Regel R₁₆: Variierung der Groß-/Kleinschreibung des ERSTEN Buchstabens.
Beispiel:
f_{16 16} = "olympiastadion"(1)
S₁₆ = "Olympiastadion"(5)
α_{16 16} = 13720
Regel R₁₇: Variierung der Groß-/Kleinschreibung des ZWEI- TEN Buchstabens.
Beispiel:
f_{17 17} = "SChwalbach"(1)
S₁₇ = "Schwalbach"(38)
α_{17 17} = 38000
Regel R₁₈: Auslassung eines Doppelbuchstabens, so daß er nur einzeln auftritt.
Beispiel:
f_{18 18} = "Etapensieger"(1)
S₁₈ = "Etappensieger"(37)
α_{18 18} = 81289
Regel R₁₉: Verdopplung eines doppelt auftretenden Buch stabens, so daß er dreifach auftritt.
Beispiel:
f_{19 19} = "UdSSSR"(1)
S₁₉ = "UdSSR"(740)
α_{19 19} = 92500

Die Regeln R_j sind dann optimal ausgewählt, wenn im wesent lichen nur die Schreibweisenvarianten in dem Schritt 11 gene riert werden, die den beobachteten Fehlertypen am besten entsprechen. Dabei haben sich besonders die folgenden Regeln bewährt: Regel R₁ (Vertauschung von zwei aufeinanderfolgenden Buchstaben: aus "abcba" also "bacba", "acbba", "abbca" und "abcab"), die Regel R₂ (Auslassung eines mindestens zweimal vorkommenden Buchstabens, d. h. Weglassen einzelner Buchstaben, aber nur solcher, die in der Zeichenkette noch mindestens ein weiteres Mal vorkommen: aus "abcba" also "bcba", "acba", "abca" und "abcb"), sowie die Regel R₇ (Hinzufügung einzelner Buchstaben, aber nur solcher, die in der Zeichenkette noch mindestens ein weiteres Mal vorkommen: aus "abc" also "aabc", "abac", "abca", "babc", "abbc", "abcb", "cabc", "acbc", "abcc"; nicht dagegen "abdc" o. ä.).

Die Regel R₂ dient dabei vor allem zur Simulierung einer möglichen psychologischen Fehlerquelle. Auslassungen von Buchstaben entstehen nämlich bei der manuellen Eingabe sehr leicht, werden aber bei einem Korrekturlesen dann schwieriger gefunden, wenn der ausgelassene Buchstabe in der Zeichenkette noch einmal vorkommt - quasi weil er dann nicht ganz so stark "vermißt" wird.

Dagegen dienen die Regeln R₁₀ bis R₁₅ zur Simulierung techni scher Unzulänglichkeiten des verwendeten Eingabemittels - in diesem Fall einer Tastatur. Die technische Unzulänglichkeit der Tastatur äußert sich in diesem Beispiel in einer ergono misch ungünstigen Ausbildung der Tasten, so daß häufig auf der Tastatur benachbarte Tasten fehlerhaft betätigt werden.

Eine weitere mögliche Regel ist die Ersetzung von optisch ähnlichen Buchstaben in der fehlerfreien Zeichenkette, also z. B. Ersetzung von "c" durch "e". Bei einem erfindungsgemäßen Textverarbeitungssystem können durch Anwendung dieser Regel durch technische Unzulänglichkeiten bedingte Fehlerquellen - wie etwa mangelnde Auflösung - des zur Anzeige des Textes dienenden Bildschirms simuliert werden. In einem erfindungsge mäßen System zur Zeichenerkennung können durch diese und ähnliche Regeln technische Unzulänglichkeiten des Systems zur maschinellen optischen Zeichenerkennung simuliert werden, da optisch ähnliche Buchstaben durch solche Systeme oft nicht richtig erkannt werden. In analoger Weise können in einem erfindungsgemäßen System zur automatischen Aufnahme eines Diktats technische Unzulänglichkeiten des dazugehörigen Sys tems zur Spracherkennung simuliert werden. Durch die entspre chenden Regeln werden dann phonetisch ähnliche Buchstaben vertauscht, also z. B. "m" durch "n", da Systeme zur Spracher kennung oft solche Fehler produzieren. Es versteht sich, daß sich die genannten Regeln nicht nur auf Worte, sondern auf beliebige zusammenhängende Zeichenketten beziehen können.

Bei der Berechnung des Wertes α_ÿ in dem Schritt 12 kann zu sätzlich ein lexikon-basiertes Verfahren verwendet werden. Die mögliche fehlerhafte Zeichenkette f_ÿ wird dann mittels des lexikon-basierten Verfahrens zusätzlich überprüft. Falls die Zeichenkette f_ÿ in dem Lexikon enthalten ist, d. h. falls es sich um eine an sich gültige Zeichenkette G_i handelt, so spricht dies zunächst dagegen, daß die mögliche fehlerhafte Zeichenkette f_ÿ tatsächlich fehlerhaft ist. Jedoch ist dies keinesfalls sicher, da ein Fehler in der entsprechenden feh lerfreien Zeichenkette S_i zufälligerweise ebenfalls auf eine gültige Zeichenkette G_i führen kann, d. h. die mögliche fehler hafte Zeichenkette f_ÿ kann sowohl als gültige Zeichenkette G_i in dem Lexikon vorkommen, als auch tatsächlich eine fehler hafte Zeichenkette F_i sein. Allerdings spricht - wie gesagt - eine gewisse Wahrscheinlichkeit dagegen, daß es sich bei einer möglichen fehlerhaften Zeichenkette f_ÿ, die als gültige Zeichenkette G_i in dem Lexikon vorkommt, tatsäch lich um eine fehlerhafte Zeichenkette F_i handelt. Dies kann bei der Berechnung des Wertes α_ÿ dadurch berücksichtigt werden, daß der aus der Formel (2) resultierende Wert von α_ÿ verändert wird, falls es sich bei der Zeichenkette f_ÿ um eine gültige Zeichenkette G_i handelt. Die Veränderung kann durch Multiplikation des aus der Formel (2) erhaltenen Werts mit einem Faktor zwischen 0 und 1 erfolgen. Der Faktor 0 bedeutet hierbei, daß in jedem Fall eine gültige Zeichenkette G_i als fehlerfrei definiert wird. In diesem Fall würde jedoch eine vorteilhafte Eigenschaft des erfindungsgemäßen Verfahrens - nämlich die Berücksichtigung des Kontexts - verlorengehen. So wurde etwa mittels des erfindungsgemäßen Verfahrens in einem Handbuch für die Datenverarbeitung das Wort "director" als fehlerhafte Schreibweise des Worts "directory" gefunden, obwohl es sich bei dem Wort "director" um ein gültiges Wort handelt. Die Berücksichtigung des Kontexts ist implizit in dem erfindungsgemäßen Verfahren beinhaltet, da die Auftretenshäu figkeiten H(S_i) und H(f_ÿ) miteinander verglichen werden. Vorteilhafterweise wird daher der Faktor deutlich größer als 0 gewählt.

Die Berechnung des Wertes α_ÿ in dem Schritt 12 kann überdies durch ein Verfahren zum maschinellen Lernen beeinflußt werden. Das Verfahren zum maschinellen Lernen ordnet einer verwendeten Regel R_ÿ eine Faktor δ_j(B) zu. Der Faktor δ_j(B) ist veränder lich und kann einerseits durch den Benutzer und andererseits durch die Art der verwendeten Hardware beeinflußt werden. Führt die Anwendung einer Regel R_j überdurchschnittlich häufig dazu, daß ein Fehler in dem Text gefunden wird, so weist das Verfahren zum maschinellen Lernen der Regel R_j einen entspre chenden Faktor δ_j(B), der größer als 1 ist, zu. Im gegentei ligen Fall weist das Verfahren zum maschinellen Lernen der Regel R_j einen Faktor zu, der kleiner als 1 ist. Der im Schritt 12 aus der Formel (2) gewonnene Wert α_ÿ wird also zusätzlich mit dem zu der angewendeten Regel R_ÿ gehörenden Faktor δ_j(B) multipliziert, so daß die unterschiedliche Er folgswahrscheinlichkeit der Regeln R_j Eingang in die Berech nung des Wertes α_ÿ findet. Die Regeln R_j können entsprechend deren Faktoren δ_j(B) so sortiert werden, daß zuerst die er folgversprechendsten Regeln R_j, denen ein relativ großer Faktor δ_j(B) zugeordnet ist, in dem Schritt 11 angewendet werden. Erfolgt der Ablauf des erfindungsgemäßen Verfahrens vollautomatisch, d. h. ohne daß dem Benutzer die ermittelten Fehler als Vorschlag angezeigt werden, so ist für das Ver fahren zum maschinellen Lernen die in dem Schritt 14 statt findende Definition maßgeblich. Erfolgt ein Vorschlag an den Benutzer, so ist dessen Akzeptanz einer als fehlerhaft vor geschlagenen Zeichenkette für das Verfahren zum maschinellen Lernen und damit zur Bestimmung der Faktoren δ_j(B) maßgeblich. Das Verfahren zum maschinellen Lernen kann beispielsweise durch ein neuronales Netz gegebenenfalls zusammen mit einem Expertensystem realisiert sein.

Durch die Verwendung eines Systems zum maschinellen Lernen kann also eine benutzer- und/oder hardware-spezifische Ka librierung erfolgen. So ist z. B. die Vertauschung von "y" und "z", etwa in "Szstem", nur bei solchen Benutzern zu erwarten, die ständig zwischen deutscher und amerikanischer Tastatur wechseln müssen, nicht aber bei Erstellern von Zeitungstexten, die im allgemeinen nur mit einem Tastaturtyp arbeiten. Da es auch entsprechende Wortpaare gibt, die keinen Fehler dar stellen, z. B. Holy und Holz, ist es von Vorteil, solche Ver tauschungen nur dann als mögliche Fehler zu berücksichtigen, wenn es vom Anwendungsgebiet her auch sinnvoll ist. Ein hard ware-bedingter Fehlertyp, der durch das Verfahren zum ma schinellen Lernen berücksichtigt werden kann, ist z. B. das unbeabsichtigte, gleichzeitige Berühren zweier benachbarter Tasten auf der Tastatur, etwa in "Sysrtem". Die Wahrschein lichkeit dieses Fehlertyps wird von der verwendeten Tastatur - insbesondere deren Druckpunkt und der evtl. vorgesehenen Abgabe eines akustischen Signals bei Betätigung einer Taste - abhängen. Ferner kann durch das Verfahren zum maschinellen Lernen auch berücksichtigt werden, daß bereits vor Anwendung des erfindungsgemäßen Verfahrens andere Rechtschreibprüfungs methoden zur Anwendung gekommen sind, die bestimmte Fehler arten schlecht erkennen. Diejenigen Regeln R_j, die diese Fehlerarten simulieren, erhalten dann eine besonders große Gewichtung durch den Faktor δ_j(B).

Die Benutzer und/oder hardware-spezifische Kalibrierung kann auch durch direkte Eingabe der Benutzer und/oder hardware spezifischen Gewichtungsfaktoren δ_j(B) erfolgen. Die zu einem bestimmten Benutzer oder zu einer bestimmten Hardware oder zu einer bestimmten Kombination von Benutzer und Hardware gehö renden Faktoren δ_j(B) können dann in getrennten Datensätzen gespeichert werden. Erfolgt ein Wechsel des Benutzers und/oder der Hardware, so wird der aktuelle Datensatz von Faktoren δ_j(B) durch den zu dem neuen Benutzer und/oder der neuen Hardware gehörigen Datensatz von Faktoren δ_j(B) ausgetauscht, so daß dieser Datensatz der neue aktuelle Datensatz ist. Der aktuelle Datensatz der Faktoren δ_j(B) dient dann zur Gewich tung der aus der Formel (2) in dem Schritt 12 erhaltenen Werte. Der Wert α_ÿ ergibt sich also aus der Multiplikation des aus der Gleichung (2) erhaltenen Werts mit dem zu der angewendeten Regel R_j gehörenden Faktor δ_j(B). Der so erhal tene aktuelle Datensatz von Faktoren δ_j(B) kann auch als Satz von Ausgangswerten der Faktoren δ_j(B) für das Verfahren zum maschinellen Lernen dienen, so daß das Verfahren bereits von Benutzer und/oder hardware-spezifischen Gewichtungsfaktoren δ_j(B) ausgehen kann, die dann noch weiter automatisch opti miert werden. Erfolgt ein Wechsel des Benutzers und/oder der Hardware, so kann der so optimierte Datensatz zur späteren Verwendung der optimierten Faktoren δ_j(B) als Ausgangswerte gespeichert werden.

Ferner ist es vorteilhaft eine Ausnahmentabelle vorzusehen, in der häufige Wortpaare, also z. B. form/from oder three/there gespeichert sind. In dieser Tabelle können auch Eigennamen gespeichert werden, z. B. Helmut/Hellmut oder Hausmann/Hauss mann, die auch durch Schreibfehler entstanden sein könnten, damit diese Worte nicht als mögliche fehlerhafte Zeichenketten in dem Schritt 12 ausgewertet werden. Bei einer in dem Schritt 11 erzeugten möglichen fehlerhaften Zeichenkette f_ÿ wird überprüft, ob diese Zeichenkette f_ÿ in der Ausnahmentabelle enthalten ist. Sollte dies der Fall sein, so wird danach nicht der Schritt 12, sondern der Schritt 15 ausgeführt.

Die Fig. 2 zeigt das Flußdiagramm einer zweiten bevorzugten Ausführungsform der Erfindung. In dem Schritt 20 wird zunächst für jede in dem Text vorkommende Zeichenkette Z_i deren Häu figkeit H(Z_i) in dem Text bestimmt. Jede lückenlose Folge aus Buchstaben und/oder beliebiger anderer Zeichen kann dabei - je nach Anwendungsfall - als Zeichenkette Z_i definiert werden.

In einem Schritt 21 werden die auftretenden Zeichenketten Z_i zusammen mit deren entsprechender Auftretenshäufigkeit H(Z_i) paarweise in einer Tabelle abgespeichert. In dem Schritt 22 wird die Bedingung H(Z_i) < γ überprüft. Der Wert γ ist ein Schwellwert für die Auftretenshäufigkeit H(Z_i), oberhalb dessen die entsprechenden Zeichenketten Z_i als fehlerfreie Zeichenketten S_i definiert werden. Ist also die Auftretens häufigkeit H(Z_i) einer bestimmten Zeichenkette Z_i größer als der Schwellwert γ, so wird diese bestimmte Zeichenkette Z_i als fehlerfreie Zeichenkette S_i definiert. Die Grundlage hierfür ist, daß eine Zeichenkette, die relativ oft in einem Text vorkommt, mit großer Wahrscheinlichkeit eine fehlerfreie Zeichenkette bzw. ein korrekt buchstabiertes Wort der jewei ligen Sprache ist.

Falls die Bedingung H(Z_i) < γ in dem Schritt 22 nicht erfüllt ist, so wird danach ein Schritt 23 ausgeführt, in dem der Index i um eins erhöht wird. In dem darauffolgenden Schritt 22 wird dann entsprechend die Bedingung H(Z_i+1) < γ für eine andere Zeichenkette überprüft.

Wird die Bedingung H(Z_i) < γ von einer Zeichenkette Z_i er füllt, so wird danach ein Schritt 24 ausgeführt. In dem Schritt 24 wird die entsprechende Zeichenkette Z_i als fehler freie Zeichenkette S_i definiert. Die darauffolgenden Schritte 11, 12, 13, 14, 15 gleichen den entsprechenden Schritten des mit Bezug auf Fig. 1 dargestellten ersten Ausführungsbei spiels. Der Schritt 24 ersetzt dabei die Funktion des Schrit tes 10 in dem ersten Ausführungsbeispiel, nämlich den der Auswahl einer spezifischen fehlerfreien Zeichenkette S_i. Sämtliche mit Bezug auf das erste Ausführungsbeispiel oben dargestellten Variationsmöglichkeiten sind auch in dem zweiten Ausführungsbeispiel möglich.

Nach Beendigung der Suche nach fehlerhaften Zeichenketten F_i der als fehlerfrei definierten Zeichenkette S_i in dem Schritt 14 wird in einem Schritt 25 die Bedingung i = i_max überprüft. Falls der Index i den Maximalwert i_max angenommen hat, so bedeutet dies, daß sämtliche in dem Text auftretende Zeichen ketten Z_i überprüft wurden, so daß in einem Schritt 27 der Ablauf beendet wird.

Falls die Bedingung i = i_max noch nicht erfüllt ist, so wird in einem Schritt 26 der Index i um eins erhöht, und daraufhin in dem Schritt 22 erneut die Bedingung H(Z_i+1) < γ für eine weitere Zeichenkette Z_i überprüft.

Der Schritt 12 zur Berechnung des Werts α_ÿ kann vorteilhaft so durchgeführt werden, daß die Auftretenshäufigkeit H(f_ÿ) aus der in dem Schritt 21 gespeicherten Tabelle ermittelt wird, so daß die Berechnung beschleunigt erfolgt. Falls eine mögliche fehlerhafte Zeichenkette f_ÿ nicht in der Tabelle vorkommt, so folgt daraus, daß deren Auftretenshäufigkeit gleich Null ist. In diesem Fall kann ohne weitere Auswertung sofort der Schritt 15 ausgeführt werden, so daß eine nächste Regel R_j zur Erzeugung einer anderen möglichen fehlerhaften Zeichenkette zur Anwendung kommt.

Das in dem Schritt 14 verwendete Ergebnis kann zur automa tischen Korrektur verwendet werden, wie bereits mit Bezug auf Fig. 1 beschrieben. Es kann jedoch vorteilhaft sein, sämtliche in dem Schritt 14 ermittelten Ergebnisse zu speichern und nach Ausführung des Schrittes 27 entsprechend des jeweils zu einem Ergebnis gehörenden Wertes α_ÿ sortieren. Dem Benutzer wird dann eine Ergebnisliste präsentiert, aus der er einzelne Ergebnisse zur automatischen Korrektur akzeptieren oder ver werfen kann. Da die Liste nach den Werten α_ÿ sortiert ist, werden die zuverlässigsten Ergebnisse zuerst angezeigt. Falls der Schwellwert β relativ groß gewählt wurde, ist dieses Vorgehen jedoch nicht erforderlich, da dann im allgemeinen praktisch alle in dem Schritt 14 ermittelten Ergebnisse zu treffend sind, so daß sofort - ohne Eingriff des Benutzers - eine automatische Korrektur erfolgen kann.

Um die Ausführungszeit des Verfahrens zu begrenzen, z. B. weil nur eine bestimmte Rechenzeit zur Verfügung steht, kann das Verfahren vorzeitig dann beendet werden, falls bereits eine bestimmte Anzahl von Fehlern gefunden wurde oder ein be stimmtes Kontingent an Rechenzeit abgelaufen ist. Zur Be schleunigung des Verfahrens kann die Erzeugung von möglichen fehlerhaften Zeichenketten f_ÿ so gesteuert werden, daß nur bei einer großen Auftretenshäufigkeit H(S_i) der zu einer möglichen fehlerhaften Zeichenkette f_ÿ gehörenden fehler freien Zeichenkette S_i sämtliche Regeln R_j herangezogen wer den. Im allgemeinen wird sich dieser Aufwand nur dann lohnen, wenn die Auftretenshäufigkeit H(S_i) sehr groß ist. Eine große Auftretenshäufigkeit H(S_i) bedingt nämlich eine große sta tistische Grundmenge, so daß die Zuverlässigkeit der Aussage in dem Schritt 14 steigt. Bei kleineren Auftretenshäufigkeiten H(S_i) kann die Menge der zur Suche einer zu einer fehlerfreien Zeichenkette S_i gehörenden fehlerhaften Zeichenkette F_i ver wendeten Regeln R_j entsprechend beschränkt werden, so daß die Schritte 11 bis 15 insgesamt schneller ausgeführt werden.

Falls vor der Ausführung des Schrittes 22 die in dem Schritt 21 erzeugte Tabelle sortiert wird, z. B. nach alphabetischer Folge der Zeichenketten, hat dies eine weitere Beschleunigung der Ausführung zur Folge. Die Suche einer möglichen fehler haften Zeichenkette f_ÿ zur Berechnung des Wertes α_ÿ in dem Schritt 12 in der Tabelle kann dann nämlich als binäre Suche ausgeführt werden. Das Verfahren der binären Suche ist an sich bekannt, z. B. aus Donald E. Knuth, "The Art of Computer Pro gramming", Band 3, Kapitel 6.2.1, Algorithmus B, Addison- Wesley Publishing Company, 1973.

In Fig. 3 ist eine weitere Möglichkeit zur Speicherung der in dem Schritt 21 erzeugten Tabelle dargestellt. Die in der Fig. 3 dargestellte Baumstruktur wird in der Literatur allgemein als "linked trie" bezeichnet, vergl. etwa Franklin Mark Liang "Word Hy-phen-a-tion by Com-put-er", Department of Computer Science, Stanford University, August 1983, Seite 11 ff. und die dortigen Zitatstellen, de la Briandais, Rene, File search ing using variable length keys, Proc. Western Joint Computer Conf. 15, 1959, 295-298 und Fredkin, Edward, Trie memory, CACM 3, Sept. 1960, 490-500 angegeben. In diesem Beispiel besteht der Baum aus Knoten 30, wobei jeder Knoten 30 Eintragungen 31 bis 34 beinhaltet. In der Eintragung 31 ist ein Buchstabe oder Zeichen gespeichert, in der Eintragung 32 ist die Häufigkeit H(Z_i) der entsprechenden Zeichenkette Z_i gespeichert, in der Eintragung 33 ist ein Zeiger auf einen Sohn - falls vorhanden - des Knotens 30 gespeichert und in der Eintragung 34 ist ein Zeiger auf einen Bruder - falls vorhanden - des Knotens 30 gespeichert. Die Eintragung 32 in einem Knoten 30 ist dann von Null verschieden, falls sich von der höchsten Ebene des Baumes ausgehend bis zu dem betreffenden Knoten 30 eine in dem Text vorkommende Zeichenkette ergibt. Dies ist in der Fig. 3 bei spielhaft anhand eines Textes gezeigt, der lediglich aus den Worten "Festung", "Feuer", "Rauch", "Frieden" und "Fest" besteht, wobei das Wort "Feuer" zweimal und das Wort "Fest" dreimal in dem Text vorkommt. Die übrigen Worte kommen nur einmal in dem Text vor.

Diese Art der Speicherung der Tabelle in dem Schritt 21 hat den Vorteil einer kompakteren Speicherung und einer weiteren Beschleunigung des Verfahrens. Der Aufbau des "linked trie" kann nämlich parallel zu der Ermittlung der einzelnen Zeichen ketten Z_i und deren Auftretenshäufigkeit erfolgen, so daß sich ein nachträgliches Sortieren erübrigt. Der zugrunde liegende Algorithmus wurde bereits von Knuth angegeben (Donald E. Knuth "The Art of Computer Programming", Addison-Wesley Publishing Company, 1973, Kapitel 6.2.2, Seite 422 ff., insbesondere Algorithmus T).

Fig. 4 zeigt ein Ausführungsbeispiel eines erfindungsgemäßen Computersystems. Das Computersystem umfaßt Speichermittel 1 zur Speicherung des zu überprüfenden Texts, Speichermittel 12 zur Speicherung der Auftretenshäufigkeiten H(Z_i) oder mit anderen Worten zur Speicherung der in dem Schritt 21 erstell ten Tabelle bzw. Baumstruktur (vergl. Fig. 2 und Fig. 3), Speichermittel 4 zur Speicherung von Regeln R_j, die in dem Schritt 11 zur Erzeugung der möglichen fehlerhaften Zeichen ketten f_ÿ verwendet werden (vergl. Fig. 1 und Fig. 2) und Prozessormittel 2 zur Ablaufsteuerung. Die Prozessormittel 2 verwenden die Auftretenshäufigkeit H(S_i) der fehlerhaften Zeichenkette F_i zur Suche der fehlerhaften Zeichenkette F_i. Die Speichermittel 1, 4, 12 und die Prozessormittel 2 sind mittels eines Bus 15 miteinander verbunden, so daß die Pro zessormittel 2 auf die verschiedenen Speichermittel zugreifen können. In diesem Ausführungsbeispiel beinhalten die Pro zessormittel Speichermittel 3 zur Speicherung einer für die Berechnung des Wertes α_ÿ in dem Schritt 12 erforderlichen Auftretenshäufigkeit H(f_ÿ), Mittel 5 zur Veränderung einer fehlerfreien Zeichenkette S_i nach einer Regel R_j, wodurch eine mögliche fehlerhafte Zeichenkette f_ÿ entsprechend dem Schritt 11 erzeugbar ist, Mittel 6 zur Ermittlung der Auftretens häufigkeit H(f_ÿ), Mittel zum Vergleich der Auftretenshäufig keiten H(f_ÿ) und H(S_i), Mittel 8 zur Zuordnung der möglichen fehlerhaften Zeichenkette f_ÿ zu der fehlerhaften Zeichenkette F_i, Mittel 11 zur Ermittlung der Auftretenshäufigkeit H(Z_i) unterschiedlicher Zeichenketten Z_i in dem Text und Vergleichs mitteln 13 zum Vergleich des Schwellwerts γ mit einer Auftre tenshäufigkeit H(Z_i). Die Mittel 3, 5, 6, 7, 8, 11, 13 sind mittels eines prozessorinternen Bus 16 miteinander verbunden. Die in den Prozessormitteln 2 beinhalteten Mittel 3, 5, 6, 7, 8, 11 und 13 sowie der Bus 16 müssen nicht als diskrete elek tronische Bauteile ausgeführt sein, sondern können durch eine entsprechende Programmierung des Prozessors 2 erzeugt werden. Ein entsprechendes zur Realisierung des erfindungsgemäßen Ver fahrens geeignetes Programm wird dabei mit dem Betriebspro gramm des Computersystems in an sich bekannter Weise so zusam menwirken, daß das Computersystem die in Fig. 4 gezeigte Konfiguration annimmt.

Die Mittel 6 zur Ermittlung der Auftretenshäufigkeit H(f_ÿ) wirken über den Bus 16 und 15 mit den Mitteln 12 zusammen, so daß aus den Mitteln 12 die gewünschte Auftretenshäufigkeit H(f_ÿ) ermittelt werden kann, falls diese dort gespeichert ist. Falls sich in der in den Mitteln 12 gespeicherten Tabelle keine Eintragung der möglichen fehlerhaften Zeichenkette f_ÿ findet, so impliziert dies eine Auftretenshäufigkeit H(f_ÿ) von Null. Die Ermittlung der Auftretenshäufigkeit ist zur Berechnung des Wertes α_ÿ in dem Schritt 12 erforderlich.

Die Mittel 7 zum Vergleich der Auftretenshäufigkeiten H(S_i) und H(f_ÿ) beinhalten Berechnungsmittel 9 zur Berechnung des Werts α_ÿ nach der Rechenvorschrift

(1) Φ_ÿ (H(f_ÿ), H(S_i)) = α_ÿ.

Dies entspricht dem in dem Schritt 12 durch Berechnung des Werts α_ÿ stattfindenden Vergleichs der Auftretenshäufigkeiten H(S_i) und H(f_ÿ).

Die Mittel 8 zur Zuordnung der möglichen fehlerhaften Zeichen kette f_ÿ zu der fehlerhaften Zeichenkette F_i beinhalten Mittel 10 zur Speicherung des Schwellwerts β für einen Ver gleich mit dem Wert α_ÿ. Der von den Mitteln 7 zum Vergleich ermittelte Wert α_ÿ wird dazu über den Bus 16 zu den Mitteln 8 zur Zuordnung übertragen. Die Mittel 8 zur Zuordnung verar beiten den Wert α_ÿ entsprechend den Schritten 13 und 14.

Die Mittel 11 zur Ermittlung der Auftretenshäufigkeit H(Z_i) wirken mit den Mitteln 1 zusammen, um einzelne Zeichenketten Z_i in dem Text zu identifizieren und die entsprechenden Auf tretenshäufigkeiten H(Z_i) zu berechnen, wie dies dem Schritt 20 entspricht.

Die Vergleichsmittel 13 beinhalten Mittel 14 zur Speicherung des Schwellwerts γ. Die Vergleichsmittel 13 wirken mit den Mitteln 11 zusammen, um diejenigen Zeichenketten Z_i, deren Auftretenshäufigkeit H(Z_i) größer als der Schwellwert γ ist, als fehlerfreie Zeichenketten S_i zu definieren. Mittels einer entsprechenden Steuerung durch ein Programm 17 kann das erfin dungsgemäße Computersystem damit die Verfahren nach den Fig. 1 und 2 ausführen. Das Programm kann in Mitteln 17 zur Programm steuerung gespeichert sein, wobei die Mittel 17 zur Programm steuerung über den Bus 15 mit den Prozessormitteln 2 zusammen wirken.

Mittels des erfindungsgemäßen Computersystems wurde der Sport teil der Frankfurter Rundschau 1988 überprüft. Der entspre chende Text besteht aus 1 671 136 Wörtern, wovon 77 745 voneinander verschieden sind. Das Computersystem be rechnete 5 849 mögliche fehlerhafte Zeichenketten f_ÿ, wovon 643 tatsächlich fehlerhafte Zeichenketten F_i sind. Es kamen dabei die in der Tabelle 1 aufgeführten Regeln R_j zur Anwen dung, wobei allein aufgrund der Anwendung der Regeln R₂ und R₃ 295 verschiedene tatsächlich fehlerhafte Zeichenketten F_i gefunden wurden.

Claims

1. Verfahren zur Suche und/oder Korrektur einer fehlerhaften Zeichenkette F_i in einem Text mit Hilfe eines Computer systems,
dadurch gekennzeichnet, daß
die Auftretenshäufigkeit H(S_i) der entsprechenden fehler freien Zeichenkette S_i in dem Text zur Suche und/oder Korrektur der fehlerhaften Zeichenkette F_i verwendet wird,
wobei die fehlerfreie Zeichenkette S_i in dem Text ent halten und der Text in dem Computersystem gespeichert ist.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß

a) die fehlerfreie Zeichenkette S_i nach einer Regel R_j verändert wird, so daß eine mögliche fehlerhafte Zeichenkette f_ÿ erzeugt wird,
b) die Auftretenshäufigkeit H(f_ÿ) der Zeichenkette f_ÿ in dem Text ermittelt wird,
c) die Auftretenshäufigkeiten H(f_ÿ) und H(S_i) ver glichen werden und
d) basierend auf dem Vergleich in Schritt c) entschie den wird, ob die mögliche fehlerhafte Zeichenkette f_ÿ die gesuchte fehlerhafte Zeichenkette F_i ist.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß in dem Schritt a) des Anspruchs 2 durch eine geeignete Wahl der Regel R_j psychologische und/oder technische durch das verwendete Computersystem, insbesondere durch dessen Bildschirm oder Tastatur, bedingte mögliche Fehlerquellen simuliert werden.

4. Verfahren nach einem der Ansprüche 2 oder 3, dadurch gekennzeichnet, daß zum Vergleich der Auftretenshäufig keit H(f_ÿ) der möglichen fehlerhaften Zeichenkette f_ÿ und der Auftretenshäufigkeit H(S_i) der fehlerfreien Zei chenkette S_i in dem Schritt c) des Anspruchs 2 die Werte H(f_ÿ) und H(S_i) nach einer Rechenvorschrift (1) Φ_ÿ (H(f_ÿ), H(S_i)) = α_ÿausgewertet werden und zur Entscheidung in dem Schritt d) des Anspruchs 2 der Wert α_ÿ mit einem Schwellwert β verglichen wird.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß die Rechenvorschrift Φ definiert ist als wobei Ψ ein Faktor ist und eine Potenz, wobei die Po tenz vorzugsweise entweder 1 oder -1 ist.

6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß der Faktor Ψ definiert ist als Ψ = [L(S_i)]^p,wobei L(S_i) die Anzahl der Zeichen der fehlerfreien Zei chenkette S_i ist und p eine Potenz, wobei die Potenz p vorzugsweise gleich 2 oder 3 ist.

7. Verfahren nach Anspruch 4, 5 oder 6, dadurch gekenn zeichnet, daß in dem Computersystem ein lexikon-basiertes Verfahren implementiert ist, welches zur Ermittlung gül tiger Zeichenketten G_i verwendbar ist,
daß für eine mögliche fehlerhafte Zeichenkette f_ÿ, deren Auftretenshäufigkeit H(f_ÿ) < 0 ist, mittels des lexikon basierten Verfahrens ermittelt wird, ob es sich bei der Zeichenkette f_ÿ um eine gültige Zeichenkette G_i handelt, und daß
der Wert α_ÿ der möglichen fehlerhaften Zeichenkette f_ÿ verändert wird, falls es sich bei der möglichen fehler haften Zeichenkette f_ÿ um eine gültige Zeichenkette G_i handelt.

8. Verfahren nach einem der Ansprüche 4 bis 7, dadurch ge kennzeichnet, daß in dem Computersystem ein Verfahren zum maschinellen Lernen implementiert ist, welches einer Regel R_j einen veränderlichen Faktor δ_j(B) zuordnet, so daß der Wert α_ÿ einer durch Anwendung der Regel R_j im Schritt a) des Anspruchs 2 erzeugten möglichen fehlerhaf ten Zeichenkette f_ÿ entsprechend verändert wird.

9. Verfahren zur Suche und/oder Korrektur fehlerhafter Zei chenketten F_i in einem Text, dadurch gekennzeichnet, daß

a) die Auftretenshäufigkeiten H(Z_i) unterschiedlicher Zeichenketten Z_i in dem Text ermittelt werden, wobei diejenigen Zeichenketten Z_i, deren Auftretenshäufig keit H(Z_i) größer als ein Schwellwert γ ist, als fehlerfreie Zeichenketten S_i definiert werden,
b) die zu einer fehlerfreien Zeichenkette S_i gehörende fehlerhafte Zeichenkette F_i nach dem Verfahren einer der Ansprüche 1 bis 8 gesucht und/oder korrigiert wird.

10. Verfahren nach Anspruch 9, dadurch gekennzeichnet, daß die Zeichenketten Z_i sortiert werden und mit deren ent sprechenden Auftretenshäufigkeiten H(Z_i) in dem Computer system gespeichert werden und zur Ermittlung der Auftre tenshäufigkeit H(f_ÿ) in Schritt b) des Anspruchs 2 eine binäre Suche in den sortierten Zeichenketten Z_i durch geführt wird.

11. Verfahren nach Anspruch 10, dadurch gekennzeichnet, daß die Speicherung der Zeichenketten Z_i mit deren entspre chenden Auftretenshäufigkeiten H(Z_i) mittels einer Hash ing-Methode oder in einer Baumstruktur erfolgt, vorzugs weise in einem binären Baum oder einem linked trie.

12. Verfahren nach einem der Ansprüche 9 bis 11, dadurch gekennzeichnet, daß für verschiedene mögliche fehlerhafte Zeichenketten f_ÿ verschiedener fehlerfreier Zeichenket ten S_i die entsprechenden Werte α_ÿ berechnet werden und diejenigen möglichen fehlerhaften Zeichenketten f_ÿ, die nach der Entscheidung in dem Schritt d) des Anspruchs 2 fehlerhafte Zeichenketten F_i sind, wobei die fehlerhaften Zeichenketten F_i vorzugsweise automatisch durch die ent sprechenden fehlerfreien Zeichenketten S_i in dem gespei cherten Text ersetzt werden.

13. Verfahren nach Anspruch 12, dadurch gekennzeichnet, daß

a) die verschiedenen möglichen fehlerhaften Zeichenket ten f_ÿ nach deren entsprechenden Werten α_ÿ sor tiert werden, und daß
b) ein Kriterium für die Werte α_ÿ gewählt wird, so daß nur diejenigen möglichen fehlerhaften Zeichenketten f_ÿ in dem Schritt d) des Anspruchs 2 verwendet werden, deren Wert α_ÿ das Kriterium erfüllt, wobei das Kriterium vorzugsweise ein Schwellwert β ist.

14. Computersystem, insbesondere Textverarbeitungssystem, zur Suche und/oder Korrektur einer fehlerhaften Zeichenkette F_i in einem Text, wobei die entsprechende fehlerfreie Zeichenkette S_i in dem Text vorkommt,
mit ersten Speichermitteln (1) zur Speicherung des Texts,
mit zweiten Speichermitteln zur Speicherung der Auftre tenshäufigkeit H(S_i) der fehlerfreien Zeichenkette S_i und
mit Prozessormitteln (2) zur Verwendung der Auftretens häufigkeit H(S_i) der fehlerfreien Zeichenkette S_i zur Suche und/oder Korrektur der fehlerhaften Zeichenkette F_i.

15. Computersystem nach Anspruch 14, mit dritten Speichermitteln (3) zur Speicherung der Auf tretenshäufigkeit H(f_ÿ) einer möglichen fehlerhaften Zeichenkette f_ÿ,
mit vierten Speichermitteln (4) zur Speicherung einer Regel R_j,
wobei die Prozessormittel (2) Mittel (5) zur Veränderung der fehlerfreien Zeichenkette S_i nach der Regel R_j enthalten, so daß eine mögliche fehlerhafte Zeichenkette f_ÿ erzeugbar ist, sowie
Mittel (6) zur Ermittlung der Auftretenshäufigkeit H(f_ÿ) einer möglichen fehlerhaften Zeichenkette f_ÿ,
Mittel (7) zum Vergleich der Auftretenshäufigkeiten H(S_i) und H(f_ÿ) und
Mittel (8) zur Zuordnung der möglichen fehlerhaften Zei chenkette f_ÿ zu der fehlerhaften Zeichenkette F_i, basie rend auf einem Ausgangssignal der Mittel (7) zum Vergleich,
enthalten.

16. Computersystem nach Anspruch 15, wobei die in den Prozes sormitteln (2) enthaltenen Mittel (7) zum Vergleich Be rechnungsmittel (9) zur Berechnung eines Werts α_ÿ nach einer Rechenvorschrift (1) Φ_ÿ (H(f_ÿ), H(S_i)) = α_ÿenthalten und das Ausgangssignal den Wert α_ÿ überträgt, und die Mittel (8) zur Zuordnung Mittel (10) zur Spei cherung eines Schwellwerts β für einen Vergleich mit dem Wert α_ÿ enthalten.

17. Computersystem nach einem der Ansprüche 14 bis 16,
mit Mitteln (11) zur Ermittlung der Auftretenshäufigkeit H(Z_i) unterschiedlicher Zeichenketten Z_i in dem Text,
mit fünften Speichermitteln (12) zur Speicherung der Auftretenshäufigkeit H(Z_i),
mit Mitteln (14) zur Speicherung eines Schwellwerts γ und
mit Vergleichsmitteln (13) zum Vergleich des Schwellwerts γ mit einer Auftretenshäufigkeit H(Z_i), wobei diejenigen Zeichenketten Z_i, deren Auftretenshäufigkeit H(Z_i) größer als der Schwellwert γ ist, als fehlerfreie Zeichenketten S_i definiert sind.

18. System zur Zeichenerkennung mit einem System zur maschinellen optischen Zeichenerken nung und mit einem Computersystem nach einem der Ansprü che 14 bis 17,
wobei das System zur maschinellen optischen Zeichenerken nung einen Rohtext erzeugt und den Rohtext zur Suche und/oder Korrektur einer oder gegebenenfalls mehrerer fehlerhafter Zeichenketten F_i in das Computersystem ein gibt.

19. System zur automatischen Aufnahme eines Diktats, mit einem System zur Spracherkennung und mit einem Computer system nach einem der Ansprüche 14 bis 17,
wobei das System zur Spracherkennung einen Rohtext er zeugt und den Rohtext zur Suche und/oder Korrektur einer oder gegebenenfalls mehrerer fehlerhafter Zeichenketten F_i in das Computersystem eingibt.

20. Speichermedium, insbesondere Diskette, für ein pro grammierbares Computersystem, wobei dem Speichermedium durch einen physikalischen und/oder chemischen Vorgang ein Programm zur Ausführung eines Verfahrens nach einem der Ansprüche 1 bis 13 eingeprägt ist,
und das Speichermedium mit dem Computersystem so zusam menwirken kann, daß durch das dem Speichermedium einge prägte Programm zusammen mit einem zu dem Computersystem gehörenden Betriebsprogramm das Computersystem nach einem der Ansprüche 14 bis 17 gebildet ist.