DE69829074T2

DE69829074T2 - IDENTIFICATION OF LANGUAGE AND SYMBOLS FROM TEXT-REPRESENTATIVE DATA

Info

Publication number: DE69829074T2
Application number: DE69829074T
Authority: DE
Inventors: David Robert POWELL
Original assignee: Microsoft Corp
Current assignee: Microsoft Corp
Priority date: 1997-12-11
Filing date: 1998-12-04
Publication date: 2005-06-30
Anticipated expiration: 2018-12-05
Also published as: DE69829074D1; EP1498827A3; EP1038239B1; WO1999030252A1; ATE289434T1; DE69838763D1; US6157905A; EP1498827B1; JP4638599B2; EP1498827A2; JP2001526425A; DE69838763T2; EP1038239A1

Abstract

The present invention provides a facility for identifying the unknown language of text represented by a series of data values in accordance with a character set that associates character glyphs with particular data values. The facility first generates a characterization that characterizes the series of data values in terms of the occurrence of particular data values on the series of data values. For each of a plurality of languages, the facility then retrieves a model that models the language in terms of the statistical occurrence of particular data values in representative samples of text in that language. The facility then compares the retrieved models to the generated characterization of the series of data values, and identifies as the distinguished language the language whose model compares most favorably to the generated characterization of the series of data values. <IMAGE>

Description

Die Erfindung liegt auf dem Gebiet der Textanalyse, insbesondere der statistischen Textanalyse.The The invention is in the field of text analysis, in particular the statistical text analysis.

HINTERGRUND DER ERFINDUNGBACKGROUND THE INVENTION

Es ist für moderne Computersysteme üblich, Einrichtungen zum Speichern und zum Verarbeiten von Daten bereitzustellen, die einen Text darstellen. Datenkörper, die durch ein Computersystem gespeichert sind und ein Textdokument darstellen, werden als „digitale Dokumentdarstellungen" (digital document representations) bezeichnet. Digitale Dokumentdarstellungen werden in einem Computersystem wie andere Daten gespeichert, nämlich als Reihenfolge von Werten, die „Bytes" genannt werden. Text wird in diese Bytewerte mittels einer „Zeichenfolge" (character set) konvertiert, eine Abbildung zwischen den Werten der verschiedenen Zeichen, die in dieser Schrift folgend als Zeichenglypt bezeichnet werden, und den verschiedenen Bytewerten. Zeichenfolgen, die auch als „Codeseiten" (code pages) bezeichnet werden, werden im allgemeinen von Standardisierungsorganisationen, wie z. B. das American National Standards Institute („ANSI") oder der International Standards Organisation („ISO"), definiert. Einige Zeichenfolgen, die „Zeichenfolgen mit mehreren Bytes" (multiple-byte character sets) genannt werden, bilden jeden Zeichenglypt auf einen Wert ab, der aus zwei oder mehr Bytes besteht. Es ist im allgemeinen möglich, das Dokument korrekt anzuzeigen, das durch eine digitale Dokumentendarstellung dargestellt ist, wenn nur die Zeichenfolge bekannt ist, die verwendet wurde, um die digitale Dokumentendarstellung zu erzeugen. Es ist im allgemeinen ebenso möglich, eine digitale Dokumentendarstellung von ihrer momentanen Zeichenfolge in eine andere Zielzeichenfolge zu konvertieren, wenn nur die momentane Zeichenfolge der digitalen Dokumentendarstellung bekannt ist.It is for modern computer systems common, Provide facilities for storing and processing data, which represent a text. Data body passing through a computer system are stored and represent a text document, are called "digital Document presentations "(digital document representations). Digital document presentations are stored in a computer system like other data, namely as Order of values called "bytes". Text is written to these byte values using a "character set" converts a mapping between the values of the different characters, which are referred to in this document as Zeichenglypt, and the different byte values. Strings, also known as "code pages" are generally used by standardization organizations, such as For example, the American National Standards Institute ("ANSI") or International Standards Organization ("ISO"), defined Strings containing "strings with several bytes "(multiple-byte character sets) form each glyph glyph to one Value consisting of two or more bytes. It is in general possible, to display the document correctly, through a digital document representation if only the string that uses is known was created to create the digital document representation. It is generally also possible a digital document representation of their current string to convert to another target string, if only the current one String of digital document representation is known.

Ein Text umfaßt im allgemeinen eine Folge von Worten, die jeweils aus einer oder mehreren Sprachen stammen. Natursprachenverarbeitungswerkzeuge, wie z. B. eine Rechtschreibüberprüfung, eine Grammatiküberprüfung und Zusammenfasser, können auf solche Dokumente angewendet werden. Um ein Dokument jedoch richtig verarbeiten zu können, müssen diese Werkzeuge jedoch von der Sprache oder den Sprachen unterrichtet werden, aus denen die Worte in dem Dokument stammen. Wenn z. B. eine Rechtschreibprüfung das Wort „Bitte" in einem Dokument entdeckt, von dem bekannt ist, daß es in Deutsch verfaßt ist, betrachtet diese das Wort nicht als falsch geschrieben. Wenn jedoch die Rechtschreibprüfung dasselbe Wort in einem Dokument entdeckt, von dem bekannt ist, daß es in Englisch verfaßt ist, so betrachtet diese das Wort als eine fehlerhafte Schreibweise des Wortes „bitter". Einige Werkzeuge, die Informationen wiedergewinnen, wie z. B. Worttrenner (die die Grenzen zwischen Worten erkennen) und Wortstammbilder (die Zusätze entfernen, um verschiedene Wort aufeinander abzustimmen, die denselben Stamm haben), müssen ebenso von der Sprache oder den Sprachen unterrichtet werden, die in den digitalen Dokumentdarstellungen auftreten, an denen diese Werkzeuge angewendet werden. Zusätzlich zu den Bedürfnissen von automatisierten Werkzeugen, ist die Kenntnis der Sprache, in der das Dokument verfaßt ist, für menschliche Leser nützlich, die nur eine oder eine geringe Anzahl der großen Vielzahl von Sprachen lesen können, in denen Dokumente verfaßt werden, um zu bestimmen, ob sie das Dokument lesen können oder nicht.One Text includes in general, a sequence of words, each consisting of one or come from several languages. Natural language processing tools, such as For example, a spellchecker, a Grammar check and Summary, can be applied to such documents. But to get a document right to be able to process have to however, these tools are taught by language or languages which the words in the document come from. If z. B. a spell checker the word "please" in a document discovered, which is known to be written in German, Do not consider this word as misspelled. But when the spell checker discovered the same word in a document known to exist in Written in English is, then considers this the word as a wrong spelling the word "bitter." Some tools, recover the information, such as B. word separator (the Recognize boundaries between words) and parentheses (remove the additions, to match different word, the same tribe need to have are also taught by the language or languages that occur in the digital document representations involving these tools be applied. additionally to the needs from automated tools, is the knowledge of the language in who writes the document is for useful to human readers who read only one or a small number of the great variety of languages can, in which documents are written to determine if they can read the document or Not.

Somit ist es im allgemeinen für jede digitale Dokumentendarstellung, die gespeichert wird, wünschenswert, von einer expliziten Anzeige der Zeichenfolge, die verwendet wurde, um diese zu erzeugen, und der Sprache oder den Sprachen, von der die Worte für diese stammen, begleitet zu werden. Während eine solche Information für viele digitale Dokumentendarstellungen, insbesondere den Darstellungen, die in der jüngeren Vergangenheit erzeugt wurden, gespeichert wird, ist diese für viele andere digitale Dokumentendarstellungen nicht verfügbar. Zum Beispiel können viele der HTML- Dokumente, die über das World Wide Web verfügbar sind, nicht ihre Zeichenfolgen und Sprachen anzeigen.Consequently is it in general for any digital document representation that is saved is desirable from an explicit display of the string that was used to produce these, and the language or languages of which the words for these come to be accompanied. While such information for many digital document representations, in particular the representations, those in the recent past is not saved for many other digital document images available. For example, you can many of the HTML documents, the above the World Wide Web are available do not show their strings and languages.

Bei einigen digitalen Dokumentendarstellungen wurde eine Information, die die Zeichenfolge und die Sprache der digitalen Dokumentendarstellung identifiziert, nie mit der digitalen Dokumentendarstellung verbunden. Dies ist häufig der Fall, wenn diese Information ursprünglich in dem Computer abgelegt wurde, auf dem diese gespeichert wurde. Zum Beispiel ist diese Information implizit in digitalen Dokumentendarstellungen enthalten, die ursprünglich in einer einzelnen Sprache und in einer einzelnen Zeichenfolgeumgebung erzeugt wurden. Wenn derartige digitale Dokumentendarstellungen in ein Computersystem überführt werden, das verschiedene Sprachen und Zeichenfolgen verwendet, oder solchen Computersystemen über ein Netzwerk, wie z. B. das Internet, zur Verfügung gestellt wird, so ist die Zeichenfolge und die Sprache von solchen digitalen Dokumentendarstellungen nicht verfügbar.at some digital document images have been given information the the string and the language of the digital document representation identified, never connected to the digital document display. This is common the case, if this information was originally stored in the computer was saved on this. For example, this information is implicitly contained in digital document representations originally in a single language and in a single string environment were generated. If such digital document images be transferred to a computer system, using different languages and strings, or such Computer systems over a network, such as As the Internet is made available, so is the string and language of such digital document representations not available.

Bei anderen digitalen Dokumentendarstellungen, wurde eine Information, die in der Zeichenfolge und der Sprache der digitalen Dokumentendarstellung identifiziert wurde, zu einem gewissen Zeitpunkt mit der digitalen Dokumentendarstellung verbunden, ist jedoch momentan nicht verfügbar. Zum Beispiel kann eine solche Information in einer getrennten Datei gespeichert worden sein, die zu einem gewissen Zeitpunkt gelöscht wurde. Auf der anderen Seite kann diese Information noch vorhanden sein, jedoch ebenso nicht zur Verfügung stehen. Zum Beispiel kann die Datei, die die Information enthält, für den Benutzer nicht zugänglich sein, oder ein Programm, das versucht, die Zeichenfolge und Sprache der digitalen Dokumentendarstellung zu bestimmen. Eine derartige Information kann ferner zugänglich sein, jedoch in einem Format vorliegen, das für den Benutzer unverständlich ist, oder ein Programm, das versucht, die Zeichenfolge und Sprache der digitalen Dokumentendarstellung zu bestimmen. Daher kann aus einer Vielzahl von Gründen die Zeichenfolge und die Sprache einer digitalen Dokumentendarstellung nicht verfügbar sein.In other digital document representations, information identified in the character string and language of the digital document representation has at some point been associated with the di digital document display, but is currently not available. For example, such information may have been stored in a separate file that has been deleted at some point. On the other hand, this information may still be present, but also not available. For example, the file containing the information may be inaccessible to the user, or a program attempting to determine the character string and language of the digital document representation. Such information may also be accessible, but in a format incomprehensible to the user or a program attempting to determine the character string and language of the digital document representation. Therefore, for a variety of reasons, the character string and language of a digital document representation may not be available.

Da die erforderliche Sprache und Zeichenfolge, um digitale Dokumentendarstellungen anzuzeigen und zu verarbeiten, häufig nicht verfügbar ist, wäre ein automatisierter Zugang zum Bestimmen der Zeichenfolge und Sprache oder Sprachen einer digitalen Dokumentendarstellung, insbesondere einer, die akzeptable Speicheranforderungen mit sich bringt und einfach auf neue Zeichenfolgen und Sprachen erweiterbar ist, von großem Nutzen.There the required language and string to digital document representations display and process frequently not available is, would be an automated access to determine the string and language or languages of a digital document representation, in particular one that brings acceptable memory requirements and easy to extend to new strings and languages is of great benefit.

G. Kikui, und andere, beschreibt in „Cross-lingual Information Retrieval on the WWW", ECA196, 12^th European Conference on Artificial Intelligence, MULSAIC96 Workshop, 1996, Seiten 1-6, ein sprachenübergreifendes Suchsystem, das auf zwei AI-basierenden Modulen beruht: einem Sprachenidentifizierer, der statistische und regelbasierende Musterabbildungen verwendet, und einem schnellen MT-Modul.G. Kikui, and others, describes in "Cross-lingual information retrieval on the Web," ECA196, 12 ^th European Conference on Artificial Intelligence, MULSAIC96 Workshop, 1996, pages 1-6, a cross-language search system based AI on two Modules is based on: a language identifier that uses statistical and rule-based pattern maps, and a fast MT module.

G. Kikui beschreibt in „Identifying the coding system and language of on-line documents on the Internet", 16^th International Conference of Computational Linguistics (COLING), August 1996, Seiten 652-657, einen Algorithmus, der gleichzeitig das Codierungssystem und die Sprache eines Codestringes identifiziert, der aus dem Internet geholt wurde, insbesondere dem World Wide Web. Der Algorithmus verwendet statistische Sprachmodelle, um den korrekt decodierten String auszuwählen und um die Sprache zu bestimmen.G. Kikui describes in "Identifying the coding system and language of on-line documents on the Internet", 16 ^th International Conference of Computational Linguistics (COLING), August 1996, pages 652-657, an algorithm simultaneously encoding the coding system and the Language of a code string retrieved from the Internet, in particular the World Wide Web The algorithm uses statistical language models to select the correctly decoded string and to determine the language.

U.S. Patent Nr. 5,418,951, das Damashek erteilt wurde, mit dem Titel „Method of retrieving documents that concern the same topic", vom 23. Mai 1995, beschreibt ein Verfahren zum Identifizieren, Wiedergewinnen und Sortieren von Dokumenten anhand von einer Sprache oder einem Thema. Das Verfahren umfaßt ein Erzeugen eines n-Gramm-Arrays, ein Parsen eines identifizierten Dokumentes in n-Gramme, Zuweisen eines Gewichtes an ein jedes n-Gramm, Entfernen von Gemeinsamkeiten der n-Gramme, Vergleichen, Zuweisen von Werten, und, basierende auf Ähnlichkeitswerten, Identifizieren, Wiedergewinnen oder Sortieren des Dokumentes.U.S. Patent No. 5,418,951 issued to Damashek entitled "Method of retrieving documents that concern the same topic ", dated 23 May 1995, describes a method for identifying, recovering and Sort documents by language or topic. The method comprises generating an n-gram array, parsing an identified one Document in n-grams, assigning a weight to each n-gram, removing of common features of the n-grams, comparing, assigning values, and, based on similarity values, Identify, retrieve or sort the document.

ZUSAMMENFASSUNG DER ERFINDUNGSUMMARY THE INVENTION

In einer Ausführungsform stellt die Erfindung das computerimplementierte Verfahren nach Anspruch 1 zum Erzeugen von Modellen bereit, wobei jeder Modelltext in einer von mehreren Sprachen verfaßt ist.In an embodiment the invention provides the computer-implemented method according to claim 1 for generating models, each model text in one written in several languages is.

In einer weiteren Ausführungsform stellt die Erfindung das computerimplementierte Verfahren nach Anspruch 5 zum Identifizieren der Sprache eines Textes in einer unbekannten, unterscheidbaren Sprache bereit.In a further embodiment the invention provides the computer-implemented method according to claim 5 for identifying the language of a text in an unknown, distinguishable language.

In einer weiteren Ausführungsform stellt die Erfindung ein computerlesbares Medium bereit, das von einem Computer ausführbare Befehle zum Ausführen eines Verfahrens entsprechend der Erfindung umfaßt.In a further embodiment For example, the invention provides a computer-readable medium that can be used by a computer-readable medium Computer executable Commands to execute a method according to the invention.

Die Erfindung ermöglicht das Vorsehen einer Softwareeinrichtung („die Einrichtung"), die, wenn ihr Rohdaten gegeben werden, die ein Textdokument darstellen, das in irgendeiner Sprache mittels irgendeiner Zeichenfolge verfaßt ist, automatisch die Sprache und die Zeichenfolge identifiziert. Die Einrichtung erzeugt zuerst ein statistisches Modell des Dokumentes in einer jeden einer Anzahl von bekannten Sprachen und Zeichenfolgen in einer „Trainingsphase", und wendet diese Modelle sodann an, um die Sprache und Zeichenfolge eines eingegebenen Dokumentes in einer „Erkennungsphase" zu identifizieren.The Invention allows the provision of a software device ("the device") that, when its raw data which represent a textual document in any one of them Language is written using any string, automatically the language and identifies the string. The device generates first a statistical model of the document in each of a number of known languages and strings in a "training phase", and applies them Models then enter the language and string of an input Document in a "recognition phase" to identify.

Die von der Einrichtung verwendeten statistischen Modelle der Sprachen und Zeichenfolgen sind angepaßt, um Zeichenwerte hervorzuheben, die dazu neigen, zwischen verschiedenen Sprachen und Zeichenfolgen unterschiedlich zu sein, während gleichzeitig die Datenmenge in den Modellen, die den Zeichenwerten zugeordnet ist, die nicht dazu neigen, zwischen Sprachen und Zeichenfolgen unterschiedlich zu sein, mittels einer spezialisierten, reduktiven Abbildung verringert wird.The Statistical models of languages used by the institution and strings are customized to highlight character values that tend to be between different ones Languages and strings to be different while at the same time the amount of data in the models associated with the character values is that does not tend to be between languages and strings to be different, by means of a specialized, reductive Figure is reduced.

In der Trainingsphase erzeugt die Einrichtung die statistischen Modelle der Sprachen und Zeichenfolgen, die in der Erkennungsphase verwendet werden, um die Sprache und Zeichenfolge der eingegebenen Dokumente zu identifizieren. Für jede zu untersuchende Kombination aus Sprache und Zeichenfolge liest die Einrichtung Beispieldokumente, von denen die Sprache und Zeichenfolge bekannt ist, die jeweils eine Folge von Bytewerten umfassen. Die Einrichtung führt sodann die Schritte aus: (A) Abbilden der Bytewerte aus der Folge von 256 verschiedenen, möglichen Werten, die in einem Byte dargestellt werden können auf eine kleinere Anzahl von möglichen Werten, (B) Aufzeichnen der Häufigkeiten, mit der jede verschiedene, gleichlange Folge von abgebildeten Bytewerten, oder n-Grammen, in der abgebildeten Version des Dokumentes auftritt, (C) Zusammenfassen dieser Häufigkeitsverteilungen für jede Sprache und jede Zeichenfolge, und (D) Normalisieren der Häufigkeitsverteilungen über die Sprachen und die Zeichenfolgen. Bevorzugt werden n-Gramme verschiedener Länge wie auch verschiedene Abbildungen verwendet, abhängig von den Charakteristika einer jeden Sprache und einer jeden Zeichenfolge. Die Einrichtung stellt ferner die Häufigkeitsverteilungen ein, um n-Gramme mit hoher Häufigkeit zu betonen, deren Auftreten dazu neigt, ein Dokument in einer Sprache und einer Zeichenfolge von Dokumenten in anderen Sprachen und anderen Zeichenfolgen zu unterscheiden, und häufig auftretende n-Gramme abzuwerten, deren Auftreten nicht dazu fuhrt, ein Dokument einer Sprache und einer Zeichenfolge von Dokumenten anderer Sprachen und Zeichenfolgen zu unterscheiden.In In the training phase, the device generates the statistical models the languages and strings used in the recognition phase be the language and string of the entered documents to identify. For Each combination of language and string to be examined reads the establishment example documents, of which the language and string is known, each comprising a sequence of byte values. The Establishment leads then the steps of: (A) mapping the byte values from the sequence of 256 different, possible Values that can be represented in one byte to a smaller number of possible Values, (B) recording the frequencies, with each different, same length sequence of mapped byte values, or n-grams, in the illustrated version of the document, (C) Summarizing these frequency distributions for every Language and each string, and (D) normalizing the frequency distributions over the Languages and the strings. Preference is given to n-grams of various types Length like also used different pictures, depending on the characteristics every language and every string. The device also provides the frequency distributions one to n-grams with high frequency to emphasize whose occurrence tends to be a document in a language and a string of documents in other languages and others To distinguish between strings and to devalue frequently occurring n-grams, whose appearance does not lead to a document of a language and a String of documents of other languages and strings differ.

In der Erkennungssphase verwendet die Einrichtung die normalisierten und eingestellten Häufigkeitsverteilungen, die in der Trainingsphase erzeugt wurden, um die Sprache und Zeichenfolge für ein eingegebenes Dokument zu identifizieren, dessen Sprache und / oder Zeichenfolge unbekannt ist. Die Einrichtung bildet zuerst die Bytewerte eines eingegebenen Dokumentes auf eine kleine Anzahl von möglichen Werten ab, wobei dieselbe(n) Abbildung(en) wie in der Trainingsphase verwendet wird (werden). Die Einrichtung bestimmt sodann die Häufigkeit, mit der jedes n-Gramm in dem abgebildeten, eingegebenen Dokument auftritt. Für jede Sprache wird die Häufigkeit, mit der jedes n-Gramm in dem abgebildeten, eingegebenen Dokument auftritt, mit der Häufigkeit desselben n-Gramm, die in den Trainingshäufigkeitsverteilungen für die momentane Sprache ermittelt wurden, multipliziert und diese Produkte werden addiert. Die Summe für jede Sprache bildet die relative Wahrscheinlichkeit, daß die Sprache diejenige ist, in der das eingegebene Dokument geschrieben ist. Nachdem die Sprache mit der größten Summe bestimmt wurde, wird dieses Erkennungsverfahren wiederholt, wobei die Zeichenfolgeverteilungen für diese Sprache verwendet werden, um festzustellen, in welcher der bekannten Zeichenfolgen für die identifizierte Sprache das eingegebene Dokument geschrieben ist.In In the recognition phase, the device uses the normalized ones and set frequency distributions, that were generated in the training phase to the language and string for a to identify the document entered, its language and / or String is unknown. The device first forms the byte values a typed document to a small number of possible ones Values, with the same image (s) as in the training phase is (are) used. The device then determines the frequency with the every n-gram in the depicted document entered occurs. For every language becomes the frequency, with the every n-gram in the depicted document entered occurs, with frequency of the same n-grams used in the training frequency distributions for the current Language were determined, multiplied and these products become added. The sum for each language forms the relative probability that the language is the one in which the entered document is written. After this the language with the largest sum was determined, this recognition method is repeated, wherein the string distributions for This language can be used to determine in which of the known strings for the identified language written the entered document is.

Die Einrichtung analysiert bevorzugt aufeinanderfolgende Einheiten von Trainingsdokumenten und eingegebenen Dokumenten, deren Länge der Länge eines typischen Absatzes entspricht. Wenn ein Dokument Text in mehr als einer Sprache oder einer Zeichenfolge enthält, kann die Einrichtung auf diese Weise jeder dieser Sprachen und Zeichenfolgen identifizieren.The Device preferably analyzes successive units of Training documents and entered documents whose length is the Length of one typical paragraph corresponds. If a document contains text in more than contains a language or a string, the device can identify each of these languages and strings in this way.

Die Einrichtung verwendet ferner bevorzugt ähnliche statistische Analysetechniken, um die Sprache oder Sprachen der digitalen Dokumentendarstellungen zu identifizieren, die in der großen Unicodezeichenfolge erstellt sind. Beim Identifizieren einiger Gruppen von ähnlichen Sprachen in digitalen Unicodedokumentendarstellungen verwendet die Einrichtung bevorzugt anwenderspezifische reduktive Abbildungen, die automatisch erzeugt werden, um zwischen Sprachen in der Gruppe zu unterscheiden.The Device preferably also uses similar statistical analysis techniques, to the language or languages of the digital document representations to identify the one created in the large Unicode string are. When identifying some groups of similar languages in digital Unicode document representations use the device preferred user-specific reductive mappings that are generated automatically be used to distinguish between languages in the group.

KURZE BESCHREIBUNG DER FIGURENSHORT DESCRIPTION THE FIGURES

1 ist ein detailliertes Blockdiagramm, daß das Computersystem zeigt, auf dem die Einrichtung bevorzugt ausgeführt wird. 1 Figure 11 is a detailed block diagram showing the computer system on which the device is preferably executed.

2 ist ein Übersichtsflußdiagramm, das die Phasen darstellt, in denen die Einrichtung arbeitet. 2 is a summary flowchart that shows the phases in which the device works.

3 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung in der Trainingsphase bevorzugt ausgeführt werden. 3 FIG. 10 is a flow chart showing the steps that are preferably performed by the device in the training phase. FIG.

4 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung bevorzugt ausgeführt werden, um die Modelle für die Zeichenfolge und die primäre Sprache zu erweitern, die für eine bestimmte digitale Beispieldokumentendarstellung entsprechend Schritt 304 identifiziert wurden. 4 FIG. 5 is a flow chart showing the steps preferred by the device to expand the character string and primary language models corresponding to a particular sample digital document representation 304 were identified.

5 ist ein Flußdiagramm, das die Schritte zeigt, die von Einrichtung bevorzugt ausgeführt werden, um eine Charakterisierung einer digitalen Beispieldokumentendarstellung zu erzeugen. 5 FIG. 10 is a flowchart showing the steps preferred by the device to generate a characterization of a sample digital document representation. FIG.

6 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung bevorzugt ausgeführt werden, um die Zeichenfolge und Sprache einer eingegebenen digitalen Dokumentendarstellung, für die diese Information nicht bekannt ist, zu identifizieren. 6 FIG. 12 is a flowchart showing the steps preferred by the device. FIG to identify the string and language of an input digital document representation for which this information is unknown.

7 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um die Zeichenfolge und/oder Sprache der eingegebenen digitalen Dokumentendarstellung zu erkennen. 7 Figure 4 is a flowchart showing the steps that are preferably performed by the device to recognize the character string and / or language of the input digital document representation.

8 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung bevorzugt ausgeführt werden, um mehrere Sprachen wie auch Zeichenfolgen einer eingegebenen digitalen Dokumentendarstellung zu erkennen. 8th Figure 3 is a flow chart showing the steps that are preferably performed by the device to recognize multiple languages as well as strings of an input digital document representation.

9 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung bevorzugt ausgefürt werden, um eine Zeichenfolge für die eingegebene, digitale Dokumentendarstellung von den Zeichenfolgen auszuwählen, die für Segmente der eingegebenen, digitalen Dokumentendarstellung bestimmt wurden. 9 Fig. 5 is a flowchart showing the steps preferred by the device to select a character string for the input digital document representation from the strings determined for segments of the input digital document representation.

10 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung in der Trainingsphase ausgeführt werden, um eine anwenderspezifische reduktive Abbildung für eine Unicodesprachengruppe zu erstellen, die verwendet wird, um zwischen Sprachen der Sprachengruppe zu unterscheiden. 10 Figure 13 is a flowchart showing the steps that are preferably performed by the device in the training phase to create a custom reductive map for a Unicode language group that is used to distinguish between languages of the language group.

11 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung bevorzugt ausgeführt werden, um die Sprachen zu erkennen, die in einer eingegebenen digitalen Dokumentendarstellung verwendet werden, die in einer Unicodezeichenfolge erstellt ist. 11 Figure 13 is a flow chart showing the steps that are preferably performed by the device to recognize the languages used in an input digital document representation created in a Unicode string.

12 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um die Sprache eines Segmentes einer eingegebenen digitalen Dokumentendarstellung zu erkennen, die in der Unicodezeichenfolge erstellt ist. 12 Figure 13 is a flow chart showing the steps that are preferably performed by the device to recognize the language of a segment of an input digital document representation created in the Unicode string.

DETAILLIERTE BESCHREIBUNG DER ERFINDUNGDETAILED DESCRIPTION OF THE INVENTION

Die vorliegende Erfindung stellt eine Softwareeinrichtung („die Einrichtung") bereit, die, wenn ihre Rohdaten zugeführt werden, die ein Textdokument darstellen, das in irgendeiner Sprache mit irgendeiner Zeichenfolge erstellt wurde, automatisch diese Sprache und diese Zeichenfolge identifiziert. Die Einrichtung erzeugt zuerst ein statistisches Modell der Dokumente in jeder aus einer Vielzahl von bekannten Sprachen und Zeichenfolgen in einer „Trainingsphase" und wendet diese Modelle dann an, um die Sprache und Zeichenfolge eines eingegebenen Dokumentes in einer „Erkennungsphase" zu identifizieren.The The present invention provides a software device ("the device") which, when supplied their raw data that are a textual document, in any language with any string was created, this language automatically and identifies this string. The device generates first a statistical model of the documents in each of a variety of known languages and strings in a "training phase" and applies them Models then enter the language and string of an input Document in a "recognition phase" to identify.

Die statistischen Modelle der Sprachen und Zeichenfolgen, die von der Einrichtung verwendet werden, sind angepaßt, um Zeichenwerte zu betonen, die dazu führen, daß zwischen verschiedenen Sprachen und Zeichenfolgen unterschieden werden kann, während gleichzeitig der Speicherplatz in den Modellen, der Zeichenwerten zugewiesen ist, die nicht dazu führen, daß zwischen Sprachen oder Zeichenfolgen unterschieden werden kann, durch die Verwendung von spezialisierten reduktiven Abbildungen minimiert wird.The statistical models of languages and strings used by the Device are adapted to emphasize character values, that lead to, that between different languages and strings can be distinguished, while at the same time the storage space in the models, the character values assigned that does not cause that between Languages or strings can be distinguished by the Minimized use of specialized reductive mappings becomes.

In der Trainingsphase erzeugt die Einrichtung die statistischen Modelle der Sprachen und Zeichenfolgen, die in der Erkennungsphase verwendet werden, um die Sprache und Zeichenfolge der eingegebenen Dokumente zu identifizieren. Für jede Kombination aus Sprache und Zeichenfolge, die untersucht werden soll, liest die Einrichtung Beispieldokumente, von denen die Sprache und Zeichenfolge bekannt ist, die jeweils eine Reihe von Bytewerten umfassen. Die Einrichtung führt sodann die folgenden Schritte aus: (A) Abbilden der Bytewerte aus der Folge von 256 verschiedenen, möglichen Werten, die in einem Byte dargestellt werden können, auf eine kleinere Anzahl von möglichen Werten, (B) Aufzeichnen der Häufigkeiten, mit der jede verschiedene Folge von abgebildeten Bytewerten fester Länge, oder „n-Gramme", in der abgebildeten Version des Dokumentes auftritt, (C) Zusammenführen dieser „Häufigkeitsverteilungen" für jede Sprache und Zeichenfolge und (D) Normalisieren der Häufigkeitsverteilungen über die Sprachen und Zeichenfolgen. Bevorzugt werden n-Gramme verschiedener Längen wie auch verschiedene Abbildungen verwendet, abhängig von den Charakteristika jeder Sprachen und Zeichenfolge. Die Einrichtung stellt ferner die Häufigkeitsverteilungen ein, um n-Gramme mit hohen Häufigkeitswerten zu betonen, deren Auftreten dazu führt, daß ein Dokument einer Sprache und Zeichenfolge von Dokumenten anderer Sprachen und Zeichenfolgen unterscheidbar ist, und n-Gramme mit hohen Häufigkeiten abzuwerten, deren Auftreten nicht dazu führt, daß ein Dokument einer Sprache und Zeichenfolge von Dokumenten anderer Sprachen und Zeichenfolgen unterscheidbar ist.In In the training phase, the device generates the statistical models the languages and strings used in the recognition phase be the language and string of the entered documents to identify. For any combination of language and string being examined should, the institution reads sample documents, of which the language and string is known, each containing a series of byte values include. The facility leads then the following steps: (A) mapping the byte values off the sequence of 256 different possible values in one Bytes can be represented on a smaller number of possible Values, (B) recording the frequencies, with the each different sequence of mapped byte values firmer Length, or "n-gramme", in the pictured Version of the document occurs, (C) merging these "frequency distributions" for each language and string and (D) normalizing the frequency distributions over the Languages and strings. Preference is given to n-grams of different lengths as well as different pictures used, depending on the characteristics every language and string. The institution also provides the frequency distributions one to n-grams with high frequency values to emphasize whose occurrence causes a document of a language and string of documents of other languages and strings is distinguishable, and to devalue n-grams with high frequencies whose Appearance does not cause the existence Document of a language and string of documents of other languages and strings is distinguishable.

In der Erkennungsphase verwendet die Einrichtung die normalisierten und eingestellten Häufigkeitsverteilungen, die in der Trainingsphase erzeugt wurden, um die Sprache und Zeichenfolge für ein eingegebenes Dokument zu identifizieren, dessen Sprache und/oder Zeichenfolge unbekannt ist. Die Einrichtung bildet zunächst die Bytewerte des eingegebenen Dokumentes auf eine kleinere Anzahl von möglichen Werten mittels der gleichen Abbildungen) ab, die in der Trainingsphase verwendet wurden. Die Einrichtung bestimmt sodann die Häufigkeiten, mit der jedes n-Gramm in dem abgebildeten, eingegebenen Dokument auftritt. Für jede Sprache wird die Häufigkeit, mit der jedes n-Gramm in dem abgebildeten, eingegebenen Dokument vorkommt, multipliziert mit der Häufigkeit, mit der dasselbe n-Gramm in den Trainingshäufigkeitsverteilungen für dieselbe Sprache vorkam, und diese Produkte werden addiert. Die Summe für jede Sprache stellt die relative Wahrscheinlichkeit dar, daß die Sprache diejenige Sprache ist, in der das eingegebene Dokument geschrieben ist. Nachdem die Sprache mit der höchsten Summe identifiziert wurde, wird dieser Erkennungsprozeß wiederholt, wobei die Zeichenfolgenverteilungen für diese Sprache verwendet werden, um festzustellen, in welcher der bekannten Zeichenfolgen für die identifizierte Sprache das eingegebene Dokument geschrieben ist.In the recognition phase, the facility uses the normalized and adjusted frequency distributions generated in the training phase to input the language and string for a given one identify a document whose language and / or string is unknown. The device first maps the byte values of the input document to a smaller number of possible values using the same maps used in the training phase. The device then determines the frequencies at which each n-gram appears in the mapped input document. For each language, the frequency at which each n-gram appears in the mapped input document is multiplied by the number of times the same n-gram occurred in the training frequency distributions for the same language, and these products are added together. The sum for each language represents the relative probability that the language is the language in which the input document is written. After identifying the language with the highest total, this recognition process is repeated using the string distributions for that language to determine in which of the known strings for the identified language the typed document is written.

Die Einrichtung analysiert bevorzugt aufeinanderfolgende Einheiten von Trainingsdokumenten und eingegebenen Dokumenten, deren Länge der Länge eines typischen Absatzes entspricht. Wenn ein Dokument Text in mehr als einer Sprache oder einer Zeichenfolge enthält, kann die Einrichtung auf diese Weise jede dieser Sprachen und Zeichenfolgen identifizieren.The Device preferably analyzes successive units of Training documents and entered documents whose length is the Length of one typical paragraph corresponds. If a document contains text in more than contains a language or a string, the device can this way identify each of these languages and strings.

Die Einrichtung verwendet ferner bevorzugt ähnliche statistische Analysetechniken, um die Sprache oder Sprachen der digitalen Dokumentendarstellungen zu identifizieren, die in der großen Unicodezeichenfolge erstellt sind. Beim Identifizieren einiger Gruppen ähnlicher Sprachen in den digitalen Unicodedokumentendarstellungen verwendet die Einrichtung bevorzugt anwenderspezifische reduktive Abbildungen, die automatisch erzeugt werden, um zwischen Sprachen in der Gruppe zu unterscheiden.The Device preferably also uses similar statistical analysis techniques, to the language or languages of the digital document representations to identify the one created in the large Unicode string are. Identifying some groups of similar languages in the digital Unicode document representations use the device preferred user-specific reductive mappings that are generated automatically be used to distinguish between languages in the group.

1 ist ein detailliertes Blockdiagramm, daß das Computersystem zeigt, auf dem die Einrichtung bevorzugt ausgeführt wird. Wie in 1 gezeigt, umfaßt das Computersystem 100 eine zentrale Prozessoreinheit (CPU) 110, Eingabe/Ausgabe-Einrichtungen 120 und einen Computerspeicher (Speicher) 130. Ein Element der Eingabe/Ausgabe-Einrichtungen ist eine Speichereinrichtung 121, wie z. B. ein Festplattenlaufwerk, ein weiteres Element ist ein computerlesbares Medienlaufwerk 122, das verwendet werden kann, um Softwareprodukte zu installieren, umfassend die Einrichtung, die auf einem computerlesbaren Medium, wie z. B. einer CD-ROM, bereitgestellt sind, ein weiteres Element ist eine Netzwerkverbindung 123, um das Computersystem 100 mit anderen Computersystemen (nicht dargestellt) zu verbinden. Der Speicher 130 umfaßt bevorzugt eine Einrichtung 131, digitale Beispieldokumentendarstellungen 132, die verwendet werden, um Modelle der Zeichenfolgen und Sprachen 133 zu erstellen, und eine eingegebene digitale Dokumentendarstellung, deren Zeichenfolge und Sprache(n) durch die Einrichtung zu bestimmen ist. Während die Einrichtung bevorzugt auf einem Computersystem für allgemeine Zwecke implementiert ist, das wie zuvor beschrieben konfiguriert ist, werden Fachleute erkennen, daß diese ebenso auf Computersystemen mit anderen Konfigurationen implementiert sein kann. 1 Figure 11 is a detailed block diagram showing the computer system on which the device is preferably executed. As in 1 shown includes the computer system 100 a central processing unit (CPU) 110 , Input / output devices 120 and a computer memory (memory) 130 , One element of the input / output devices is a memory device 121 , such as A hard disk drive, another element is a computer readable media drive 122 , which can be used to install software products, comprising the device running on a computer-readable medium, such as. A CD-ROM are provided, another element is a network connection 123 to the computer system 100 to connect with other computer systems (not shown). The memory 130 preferably comprises a device 131 , digital example document images 132 which are used to model the strings and languages 133 and an input digital document representation whose string and language (s) are to be determined by the device. While the device is preferably implemented on a general purpose computer system configured as described above, those skilled in the art will recognize that it may also be implemented on computer systems having other configurations.

2 ist ein Übersichtsflußdiagramm, das die Phasen zeigt, in denen die Einrichtung arbeitet. In Schritt 201, in der Trainingsphase, erstellt die Einrichtung Modelle der Zeichenfolgen und Sprachen, die untersucht werden sollen, wobei digitale Beispieldokumentdarstellungen verwendet werden, von denen bekannt ist, daß diese in diesen Zeichenfolgen erzeugt wurden, und von denen bekannt ist, daß diese hauptsächlich diese Sprachen enthalten. Die digitalen Beispieldokumentdarstellungen, die in Schritt 201 verwendet werden, sind bevorzugt Zeitungsausschnitte oder rechtliche Meinungen, die Themen mit im wesentlich einem Gegenstand diskutieren, für den dessen primäre Sprache kennzeichnend ist. Das heißt es werden digitale Beispieldokumentendarstellungen gesucht, die einen begrenzten Inhalt haben, wie z. B. Zeitungsartikel und juristische Meinungen, da das Vokabular, das in solchen digitalen Dokumentendarstellungen verwendet wird, wahrscheinlich dazu geeignet ist, die primäre Sprache der digitalen Beispieldokumentendarstellung von anderen Sprachen zu unterscheiden. Der Schritt 201 wird detaillierter weiter unten in Verbindung mit 3 beschrieben. 2 is a summary flowchart showing the phases in which the device works. In step 201 In the training phase, the facility creates models of the strings and languages to be examined using sample digital document representations known to have been generated in those strings and known to primarily contain those languages , The sample digital document illustrations presented in step 201 are preferred newspaper clippings or legal opinions that discuss topics with essentially one subject for which its primary language is indicative. That is, digital sample document views are searched that have limited content, such as: Newspaper articles and legal opinions, since the vocabulary used in such digital document representations is likely to distinguish the primary language of the sample digital document representation from other languages. The step 201 will be discussed in more detail below 3 described.

Die Einrichtung führt den Schritt 201 einmal aus. Nachdem der Schritt 201 ausgeführt wurde, wird die Trainingsphase beendet. Die in der Trainingsphase im Schritt 201 erzeugten Modelle werden in der Erkennungsphase verwendet, um die Zeichenfolge und Sprache(n) in jeder aus irgendeiner Anzahl von eingegebenen digitalen Dokumentendarstellungen zu erkennen. In Schritt 202 empfängt die Einrichtung eine neue eingegebene digitale Dokumentendarstellung. In Schritt 203 untersucht die Einrichtung die Zeichenfolge und Sprache(n) der eingegebenen digitalen Dokumentendarstellung, die in Schritt 202 empfangen wurde, wobei die Modelle verwendet werden, die in Schritt 201 erzeugt wurden. Die Details des Schritt 203 werden weiter unten genauer in Verbindung mit 3 beschrieben. Nachdem die Zeichenfolge und Sprache(n) der eingegebenen digitalen Dokumentendarstellung in Schritt 203 untersucht wurde, fährt die Einrichtung in Schritt 202 fort, die nächste eingegebene digitale Dokumentendarstellung zu empfangen, wodurch diese in der Erkennungsphase verbleibt. Während 2 die Einrichtung so darstellt, als ob diese niemals erneut in die Trainingsphase eintreten würde, werden Fachleute erkennen, daß es wünschenswert sein kann, die Trainingsphase zu wiederholen, um zusätzliche digitale Beispieldokumentendarstellungen den Modellen, die in der Trainingsphase erzeugt wurden, hinzuzufügen, entweder um die Einrichtung zu erweitern, so daß diese zusätzliche Sprachen und Zeichenfolgen erkennen kann, oder um die Modelle für existierende Sprachen und Zeichenfolgen zu verbessern, wobei der Text von zusätzlichen digitalen Beispieldokumentendarstellungen verwendet wird.The institution leads the step 201 once out. After the step 201 has been executed, the training phase is terminated. The in the training phase in the step 201 generated models are used in the recognition phase to recognize the string and language (s) in each of any number of input digital document representations. In step 202 the device receives a new input digital document representation. In step 203 The facility examines the string and language (s) of the input digital document representation shown in step 202 was received, using the models in step 201 were generated. The details of the step 203 will be discussed in more detail below 3 described. After the string and language (s) of the entered digital document representation in step 203 was investigated, the device moves in step 202 continue to receive the next input digital document representation, whereby this in the Erken phase remains. While 2 As the device represents as if it would never again enter the training phase, those skilled in the art will recognize that it may be desirable to repeat the training phase to add additional sample digital document images to the models generated during the training phase, either To expand the facility so that it can recognize additional languages and strings, or to enhance existing language and string models, using the text from additional sample digital document representations.

3 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung in der Trainingsphase bevorzugt ausgeführt werden. In Schritt 301 wählt die Einrichtung digitale Beispieldokumentendarstellungen aus, deren Zeichenfolgen und primäre Sprachen bekannt sind. Da die Anzahl der digitalen Beispieldokumentendarstellungen direkten Einfluß auf die statistische Genauigkeit der Modelle, die durch die Einrichtung erzeugt werden, hat, und somit auf das Performanceniveau der Einrichtung, wird bevorzugt eine große Anzahl von digitalen Beispieldokumentendarstellungen im Schritt 301 ausgewählt. In den Schritten 302 bis 304 durchläuft die Einrichtung für jede digitale Beispieldokumentendarstellung, die in Schritt 301 ausgewählt wurde, eine Schleife. In Schritt 303 erweitert die Einrichtung das Modell für die Zeichenfolge und die primäre Sprache, die für die digitale Beispieldokumentendarstellung identifiziert wurden. Schritt 303 wird weiter unten genauer in Verbindung mit 4 beschrieben. Wenn in Schritt 304 eine oder mehrere ausgewählte digitale Dokumentendarstellungen zur Verarbeitung übrigbleiben, fährt die Einrichtung mit Schritt 302 fort, die nächste ausgewählte digitale Beispieldokumentendarstellung zu verarbeiten. Sind alle ausgewählten digitalen Beispieldarstellungen verarbeitet, fährt die Einrichtung mit Schritt 305 fort. In Schritt 305 normalisiert die Einrichtung die Modelle, die als Ergebnis der Erweiterung in Schritt 303 erzeugt wurden. Die im Schritt 305 ausgeführte Normalisierung beinhaltet bevorzugt ein proportionales Erhöhen oder Erniedrigen der Zähler eines jeden Modells, so daß der gemittelte Zählwert in jedem Modell gleich ist. Im Schritt 306 stellt die Einrichtung die normalisierten Modelle ein, um deren Zeichenfolgen und Sprachen effektiver unterscheiden zu können, wobei für jedes Modell die folgenden Schritte ausgeführt werden: (a) Erhöhen der Häufigkeiten für n-Gramme, deren Häufigkeiten im Vergleich zu den Häufigkeiten für das gleiche n-Gramm in anderen Modellen am höchsten ist, und (b) Erniedrigen der Häufigkeiten für n-Gramme, deren Häufigkeiten im Vergleich mit den Häufigkeiten für dieses Modell hoch sind, jedoch nicht hoch sind im Vergleich zu den Häufigkeiten für dasselbe n-Gramm in den anderen Modellen. In einer bevorzugten Ausführungsform ist dieses Einstellen begleitet von einem Verdoppeln einer jeden Häufigkeit eines jeden Modells und folgendem Subtrahieren des Mittelwertes der entsprechenden Häufigkeiten über alle Modelle. Nach Schritt 306 sind diese Schritte und die Trainingsphase beendet. 3 FIG. 10 is a flow chart showing the steps that are preferably performed by the device in the training phase. FIG. In step 301 The facility selects digital sample document views whose strings and primary languages are known. Since the number of sample digital document images has a direct influence on the statistical accuracy of the models generated by the device, and thus on the performance level of the device, a large number of sample digital document images are preferred in the step 301 selected. In the steps 302 to 304 goes through the facility for each sample digital document representation shown in step 301 was selected, a loop. In step 303 The facility extends the string and primary language model identified for the sample digital document representation. step 303 will be discussed in more detail below 4 described. When in step 304 one or more selected digital document representations remain for processing, the device moves to step 302 progress to process the next selected sample digital document representation. Once all selected sample digital representations have been processed, the device moves to step 305 continued. In step 305 The device normalizes the models that are the result of the expansion in step 303 were generated. The in step 305 executed normalization preferably involves proportionally increasing or decreasing the counters of each model so that the averaged count is the same in each model. In step 306 the facility sets the normalized models to more effectively distinguish their strings and languages, performing the following steps for each model: (a) increasing the frequencies for n-grams, their frequencies compared to the frequencies for the same n Is highest in other models, and (b) decreasing the frequencies for n-grams whose frequencies are high compared to the frequencies for this model, but not high, compared to the frequencies for the same n-gram in the other models. In a preferred embodiment, this adjustment is accompanied by doubling each frequency of each model and then subtracting the mean of the corresponding frequencies across all models. After step 306 these steps and the training phase are over.

4 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung bevorzugt ausgeführt werden, um die Modelle für die Zeichenfolge und primäre Sprache zu erweitern, die für eine bestimmte digitale Beispieldokumentendarstellung in Übereinstimmung mit Schritt 304 identifiziert wurden. Die Einrichtung verwendet bevorzugt verschiedene reduktive Abbildungen und behält Häufigkeitsdaten für verschieden große n-Gramme, abhängig von der Art der Zeichenfolge, die verwendet wurde, um die betrachtete digitale Beispieldokumentendarstellung zu erzeugen. Wenn die betrachtete digitale Beispieldokumentendarstellung in Schritt 401 eine romanische Einzelbytezeichenfolge ist, fährt die Einrichtung in Schritt 402 fort, die Schritte 402 bis 405 auszuführen, andernfalls ist die Zeichenfolge der betrachteten digitalen Beispieldokumentendarstellung entweder eine Zeichenfolge mit mehreren Bytes (bei der jedes Zeichen durch zwei oder mehr Bytewerte dargestellt ist) oder eine Einzelbytezeichenfolge für eine nicht romanische Sprache und die Einrichtung fährt in Schritt 406 fort, die Schritte 406 und 407 auszuführen. Beispiele von romanischen Einzelbytezeichenfolgen umfassen: Microsoft Zeichenfolgen 1250 und 28592 für tschechisch, ungarisch und polnisch, Microsoft Zeichenfolge 1252 für dänisch, holländisch, englisch, finnisch, französisch, deutsch, italienisch, norwegisch, portugiesisch, spanisch und schwedisch, Microsoft Zeichenfolge 28591 für finnisch, französisch, deutsch, norwegisch, portugiesisch und schwedisch, Microsoft Zeichenfolge 28592 für deutsch, ungarisch und polnisch und Microsoft Zeichenfolge 1257 für litauisch. Beispiele für Zeichenfolgen mit mehreren Bytes oder nicht romanische Einzelbytezeichenfolgen umfassen Microsoft Zeichenfolge 936 und 950 für chinesisch, Microsoft Zeichenfolgen 932 und 51932 für japanisch, Microsoft Zeichenfolge 949 für koreanisch und Zeichenfolgen für griechisch und hebräisch. 4 FIG. 11 is a flow chart showing the steps that are preferably performed by the device to augment the character string and primary language models associated with a particular example digital document representation in accordance with step. FIG 304 were identified. The device preferably uses different reductive maps and retains frequency data for different sized n-grams, depending on the type of string used to generate the considered sample digital document representation. If the considered sample digital document representation in step 401 is a romance single byte string, the device moves in step 402 away, the steps 402 to 405 otherwise, the string of the sample digital document representation under consideration is either a multi-byte string (where each character is represented by two or more byte values) or a single-byte string for a non-Romance language and the device moves to step 406 away, the steps 406 and 407 perform. Examples of single-byte Roman character strings include: Microsoft strings 1250 and 28592 for Czech, Hungarian and Polish, Microsoft string 1252 for Danish, Dutch, English, Finnish, French, German, Italian, Norwegian, Portuguese, Spanish and Swedish, Microsoft string 28591 for Finnish, French, German, Norwegian, Portuguese and Swedish, Microsoft string 28592 for German, Hungarian and Polish and Microsoft string 1257 for Lithuanian. Examples of multi-byte strings or single-byte non-rom character strings include Microsoft string 936 and 950 for Chinese, Microsoft string 932 and 51932 for Japanese, Microsoft string 949 for Korean, and strings for Greek and Hebrew.

In den Schritten 402 bis 405 erweitert die Einrichtung sowohl ein dreidimensionales Modell der primären Sprache der digitalen Beispieldokumentendarstellung wie auch ein eindimensionales Modell der Kombination aus dieser primären Sprache und der Zeichenfolge der digitalen Beispieldokumentendarstellung mit Charakteristika der digitalen Beispieldokumentendarstellung. Das dreidimensionale Modell wird von der Einrichtung verwendet, um eingegebene digitale Dokumentendarstellungen zu erkennen, die dieselbe primäre Sprache wie diese digitale Beispieldokumentendarstellung aufweist, wohingegen das eindimensionale Modell verwendet wird, um eingegebene digitale Dokumentendarstellungen zu erkennen, die dieselbe primäre Sprache und Zeichenfolge wie diese digitale Beispieldokumentendarstellung aufweist. In Schritt 402 erzeugt die Einrichtung eine dreidimensionale Charakterisierung der betrachteten digitalen Beispieldokumentendarstellung, wobei die Abbildung, die unten in Tabelle 1 gezeigt ist, und Häufigkeitsverteilungen für Zeichentrigrame, die in der digitalen Beispieldokumentendarstellung auftreten, verwendet werden.In the steps 402 to 405 The device extends both a three-dimensional model of the primary language of the digital sample document representation as well as a one-dimensional model of the combination of this primary language and the string of digital sample document representation with characteristics of the digital sample document representation. The three-dimensional model is used by the device to recognize input digital document representations having the same primary language as this sample digital document representation, whereas the one-dimensional model is used to recognize input digital document representations having the same primary language and character string as this sample digital document representation having. In step 402 creates the on A three-dimensional characterization of the considered digital sample document representation is shown, using the mapping shown below in Table 1 and frequency distributions for character graphics that occur in the example digital document representation.

Tabelle 1: Abbildung, um eine Sprache mit romanischem SBCS zu erkennen

Table 1: Illustration to recognize a language with Romanic SBCS

Die Details des Schritts 402 zum Erzeugen einer Charakterisierung der digitalen Beispieldokumentendarstellung werden weiter unten genauer in Verbindung mit 5 beschrieben. Als Teil des Erzeugungsverfahrens bildet die Einrichtung jeden Bytewert in der digitalen Beispieldokumentendarstellung auf einen Zielwert ab, wobei die in Tabelle 1 gezeigte Abbildung verwendet wird. Basierend auf einer Feststellung, daß Sprachen, die in einer romanischen Einzelbytezeichenfolge erstellt werden, am effektivsten abhängig von den Identitäten der Buchstaben unterschieden werden können, die darin vorkommen, jedoch unabhängig von dem Kasus, bildet die in Tabelle 1 gezeigte Abbildung die Quellwerte, die jedem Buchstaben entsprechen, auf verschiedene Zielwerte ab. Zum Beispiel werden die Quellwerte 0×41 und 0×61, die den Zeichenglypten „A" und „a" entsprechen, beide auf den Zielwert 2 abgebildet, die Quellwerte 0×42 und 0×62, die die Zeichenglypte „B" und „b" darstellen, werden auf den Zielwert 3 abgebildet, usw. Bis auf die Tatsache, daß den Zielwerten Buchstaben zugeordnet werden, definiert die in Tabelle 1 gezeigte Abbildung nur zwei weitere Zielwerte: den Zielwert 1 für „ausgedehnte Zeichen", d. h. für Quellwerte die ihre hohe Bitfolge haben, d. h. 0×80-0×FF, und den Zielwert 0 für Quellwerte, die keine hohe Bitfolge aufweisen und keine Buchstaben darstellen, wobei diese Quellwerte im allgemeinen Zahlen, Interpunktionszeichen und anderen Symbolen sowie Steuerzeichen zugewiesen sind. Durch Abbilden von Quellwerten in dieser Weise reduziert die Einrichtung 256 Quellwerte auf nur 28 Zielwerte, wodurch die Speicheranforderungen für Trigramhäufigkeitsverteilungen um über 99 % reduziert werden.The details of the step 402 for generating a characterization of the sample digital document representation will be described in more detail below 5 described. As part of the generation process, the device maps each byte value in the example digital document representation to a target value using the mapping shown in Table 1. Based on a finding that languages created in a single-byte Roman string can be most effectively distinguished depending on the identities of the letters that occur therein, but independently of the case, the mapping shown in Table 1 forms the source values for each Letters correspond to different target values. For example, the source values 0x41 and 0x61 corresponding to the character glyphs "A" and "a" are both mapped to the target value 2, the source values 0x42 and 0x62 representing the character glyphs "B" and " b "are mapped to the target value 3, and so forth. Except for the fact that letters are assigned to the target values, the figure shown in Table 1 defines only two more target values: the target value 1 for" extended characters ", ie for source values have their high bit order, ie 0x80-0xFF, and the target value 0 for source values which are not high bit order and which are not letters, these source values being generally assigned numbers, punctuation marks and other symbols as well as control characters In this way, the device reduces 256 source values to only 28 target values, reducing the storage requirements for trigram frequency distributions by over 99%.

Betrachte zum Beispiel den folgenden Beispieltextstring:For example, consider the following sample text string:

Snow, called „POWDER."Snow, called "POWDER."

Die untere Tabelle 2 zeigt in ihrer „Bytewert"-Spalte die Folge von Bytewerten, die den Beispielstring in einer digitalen Beispieldokumentendarstellung ausmachen. Die „Zielwert"-Spalte der Tabelle 2 zeigt eine Folge von Zielwerten, auf die die Bytewerte abgebildet werden, wobei die in Tabelle 1 gezeigte Abbildung verwendet wird.The Table 2 below shows in its "byte value" column the sequence of byte values that the sample string in a digital sample document representation turn off. The "target value" column of Table 2 shows a sequence of target values to which the byte values are mapped, where the used in Table 1.

Tabelle 2

Table 2

Man kann aus Tabelle 2 sehen, daß jeder verschiedene Buchstabe seinen eigenen Zielwert hat. Zum Beispiel sind sowohl der kleine Buchstabe „o" wie auch der große Buchstabe „O" auf den Zielwert 16 abgebildet. Man kann ferner sehen, daß alle Interpunktionszeichenglypten, umfassend Komma, Leerzeichen, Anführungszeichen und Punkt, auf einen einzelnen Zielwert abgebildet sind, den Zielwert 0. Somit sind es die Identitäten der verschiedenen Buchstaben, die verwendet werden, um verschiedene Sprachen in digitalen Dokumentendarstellungen zu unterscheiden, die in romanischen Einzelbytezeichenfolgen erstellt sind. Die in Tabelle 1 gezeigte Abbildung kann ferner verwendet werden, um Modelle und Charakterisierungen von Zeichenfolgen, wie z. B. Microsoft Zeichenfolge 50220 für japanisch, zu erzeugen, die, im Gegensatz zu technischen Doppelbytezeichenfolgen, keine Bytewerte zwischen 0×80 und 0×FF verwenden.you can see from Table 2 that everyone different letter has its own target value. For example Both the small letter "o" and the large letter "O" are at the target value 16 pictured. It can also be seen that all punctuation glyphs, comprising comma, space, quotation marks and period a single target value, the target value 0. Thus it's the identities of different letters that are used to different To distinguish languages in digital document representations, which are created in single-byte Roman string strings. In the Table 1 can also be used to model and characterizations of strings, such as Eg Microsoft string 50220 for japanese, which, in contrast to technical double-byte strings, no byte values between 0 × 80 and 0 × FF use.

In Schritt 403 addiert die Einrichtung die dreidimensionale Charakterisierung der digitalen Beispieldokumentendarstellung, die in Schritt 402 erzeugt wurde, zu einem dreidimensionalen Modell der Sprache, die als primäre Sprache der digitalen Beispieldokumentendarstellung identifiziert wurde. Dieses Additionsverfahren beinhaltet ein Addieren der Werte eines jedes Eintrages in der dreidimensionalen Charakterisierung der digitalen Beispieldokumentendarstellung in einen entsprechenden Eintrag in dem dreidimensionalen Modell der primären Sprache. Die Schritte 404 und 405 spiegeln die Schritte 402 und 403 in dem Sinne wieder, daß Schritt 404 eine Charakterisierung der digitalen Beispieldokumentettdarstellung erzeugt und Schritt 405 diese Charakterisierung zu einem Modell einer Sprache und einer Zeichenfolge addiert. In Schritt 4O4 erzeugt die Einrichtung eine eindimensionale Charakterisierung der betrachteten digitalen Beispieldokumentendarstellung, wobei die unten in Tabelle 3 gezeigte Abbildung und Häufigkeitsverteilungen für Zeichenunigramme, die in der digitalen Beispieldokumentendarstellung auftreten, verwendet werden.In step 403 the facility adds the three-dimensional characterization of the sample digital document representation shown in step 402 to a three-dimensional model of the language identified as the primary language of the sample digital document representation. This addition method involves adding the values of each entry in the three-dimensional characterization of the sample digital document representation to a corresponding entry in the three-dimensional model of the primary language. The steps 404 and 405 reflect the steps 402 and 403 in the sense that step 404 generates a characterization of the digital sample document representation and step 405 adds this characterization to a model of a language and a string. In step 4O4 For example, the device generates a one-dimensional characterization of the considered example digital document representation, using the mapping and frequency distributions for character unigrams shown below in Table 3 that occur in the example digital document representation.

Tabelle 3: Abbildung, um Zeichenfolgen romanischer SBCS zu untersuchen.

Table 3: Figure to examine strings of Romanian SBCS.

Man kann aus Tabelle 3 sehen, daß die Abbildung zum Erkennen der richtigen Zeichenfolge aus romanischen Einzelbytezeichenfolgen jeden Quellwert mit einer hohen Bitfolge auf verschiedene Zielwerte abbildet. Zum Beispiel wird der Quellwert 0×80 auf den Zielwert 1 abgebildet, der Quellwert 0×81 wird auf den Zielwert 2 abgebildet usw. Bei Einzelbytezeichenfolgen stellen nur diese „ausgedehnten Zeichenbytewerte" verschiedene Zeichen in verschiedenen Zeichenfolgen dar, wohingegen auf der anderen Seite jeder der Bytewerte 0-0×7F üblicherweise dasselbe Zeichen in all diesen Zeichenfolgen darstellt. Es sind daher dieses ausgedehnten Zeichenbytecodes, die dazu dienen, am besten zwischen verschiedenen romanischen Einzelbytezeichenfolgen zu unterscheiden. Zusätzlich zu den 128 Zielwerten, die jeweils einem der Quellwerte zwischen 0×80 und 0×FF zugewiesen sind, definiert die Abbildung einen weiteren Zielwert: der Zielwert 0 ist allen Quellwerten zwischen 0 und 0×7F zugewiesen. Durch eine Abbildung der Quellwerte auf diese Weise reduziert die Einrichtung 256 Quellwerte auf nur 129 Zielwerte, wodurch die Speicheranforderungen für Unigrammhäufigkeitsverteilungen um nahezu 50 % reduziert sind.you can see from Table 3 that the Illustration for recognizing the correct string of Romance Single-byte strings string each source value with a high bit order to different target values. For example, the source value becomes 0 × 80 on the target value 1 is mapped, the source value 0 × 81 becomes the target value 2 mapped, etc. For single-byte strings, only these "extended Character byte values "various Characters in different strings, whereas on the other Side of each of the byte values 0-0 × 7F usually represents the same character in all these strings. There are hence this extended character byte code, which is used on the best between different romance single byte strings to distinguish. additionally to the 128 target values, each one of the source values between 0 × 80 and 0 × FF assigned the figure defines another target value: the target value 0 is assigned to all source values between 0 and 0 × 7F. By a Mapping the source values in this way reduces the setup 256 source values to only 129 target values, reducing memory requirements for unigram frequency distributions are reduced by almost 50%.

Im Schritt 404 addiert die Einrichtung die eindimensionale Charakterisierung der digitalen Beispieldokumentendarstellung, die in Schritt 404 erzeugt wurde, zu einem eindimensionalen Modell der Kombination aus der primären Sprache und Zeichenfolge der digitalen Beispieldokumentendarstellung. Nachdem der Schritt 405 vollendet ist, werden diese Schritte beendet.In step 404 the facility adds the one-dimensional characterization of the sample digital document representation shown in step 404 to a one-dimensional model of the primary language and character string combination of the sample digital document representation. After the step 405 is completed, these steps are completed.

In den Schritten 406-407 erzeugt die Einrichtung eine einzelne Charakterisierung der digitalen Beispieldokumentendarstellung und addiert diese zu einem einzigen Modell für sowohl die primäre Sprache wie auch der Zeichenfolge der digitalen Beispieldokumentendarstellung.In the steps 406 - 407 The facility generates a single characterization of the sample digital document representation and adds it to a single model for both the primary language and the sample digital document document string.

In dem Schritt 406 erzeugt die Einrichtung eine zweidimensionale Charakterisierung der digitalen Beispieldokumentendarstellung, wobei die unten in Tabelle 4 gezeigte Abbildung und Häufigkeitsverteilungen für Zeichenbigramme, die in der digitalen Beispieldokumentendarstellung vorkommen, verwendet werden.In the step 406 For example, the device generates a two-dimensional characterization of the sample digital document representation using the mapping and frequency distributions shown below in Table 4 for drawing bigrams found in the sample digital document representation.

Tabelle 4: Abbildung, um die Sprache und Zeichenfolge von nichtromanischen SBCS oder DBCS zu untersuchen.

Table 4: Figure to examine the language and string of non-Romanian SBCS or DBCS.

Man kann sehen, daß die Abbildung in Tabelle 4 im wesentlichen eine Vereinigung der verschiedenen Zielwerte ist, die durch die beiden Abbildungen definiert sind, die in Tabelle 1 und Tabelle 3 gezeigt sind. Diese Abbildung reduziert 256 Quellwerte auf 155 Zielwerte, wodurch die Speicheranforderungen für Bigrammhäufigkeitsverteilungen um mindestens 63 reduziert werden.you can see that the Figure 4 in Table 4 is essentially a union of the different target values which are defined by the two figures shown in Table 1 and Table 3 are shown. This figure reduces 256 source values to 155 target values, reducing the memory requirements for bigram frequency distributions be reduced by at least 63.

Im Schritt 407 addiert die Einrichtung die zweidimensionalen Charakterisierungen der digitalen Beispieldokumentendarstellung, die in Schritt 406 erzeugt wurden, zu einem zweidimensionalen Modell der Kombination aus der primären Sprache und Zeichenfolge der digitalen Beispieldokumentendarstellung. Nach dem Schritt 407 werden diese Schritte beendet.In step 407 the facility adds the two-dimensional characterizations of the sample digital document representation shown in step 406 to a two-dimensional model of the primary language and character string combination of the sample digital document representation. After the step 407 these steps are finished.

5 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um eine Charakterisierung einer digitalen Beispieldokumentendarstellung zu erzeugen. Die in 5 gezeigten Schritte werden bevorzugt von der Einrichtung als Teil der Schritte 402, 404 und 406 ausgeführt. Wie in den Schritten 402, 404 und 406 gezeigt, verwendet eine Charakterisierung, die entsprechend den Schritten der 5 erzeugt wurde, eine bestimmte reduktive Abbildung und hat eine spezifizierte Anzahl von Dimensionen, die direkt der Länge der n-Gramme entspricht, für die Häufigkeitsverteilungen in der Charakterisierung erhalten bleiben. Zum Beispiel verwendet die Einrichtung, in Übereinstimmung mit dem Schritt 406 für Zeichenfolgen mit mehreren Bytes und romanischen Einzelbytezeichenfolgen, die in Tabelle 3 gezeigte Abbildung und erzeugt eine zweidimensionale Charakterisierung, die die Häufigkeit eines jeden möglichen Bigramms von Zielwerten enthält. 5 FIG. 11 is a flowchart showing the steps that are preferably performed by the device to generate a characterization of a sample digital document representation. In the 5 The steps shown are preferred by the device as part of the steps 402 . 404 and 406 executed. As in the steps 402 . 404 and 406 shown uses a characterization according to the steps of 5 has a certain reductive mapping and has a specified number of dimensions directly corresponding to the length of the n-grams for which frequency distributions are preserved in the characterization. For example, the device uses, in accordance with the step 406 for multi-byte and single-byte Roman string strings, the mapping shown in Table 3 produces a two-dimensional characterization containing the frequency of each possible bigram of target values.

In dem Schritt 501 verwendet die Einrichtung die reduktive Abbildung, die für die Charakterisierung spezifiziert ist, um jedes Byte der digitalen Dokumentendarstellung von dem Quellwert für das Byte auf einen Zielwert abzubilden. Zum Beispiel würde die Einrichtung für die Zeichen, die in Tabelle 2 gezeigt sind, das Byte oder Quellwerte auf Zielwerte abbilden, die in Tabelle 2 gezeigt sind. Im Schritt 502 konstruiert und initialisiert die Einrichtung eine Matrix, die die Charakterisierung enthalten soll. Die Matrix weist eine Anzahl von Dimensionen auf, die direkt der Länge, in Zeichen, der spezifizierten n-Gramme für diese Kombination aus Sprache und Zeichenfolge entspricht. Da Schritt 406 die Verwendung von Bigrammhäufigkeitsverteilungen spezifiziert, konstruiert die Einrichtung z. B. eine zweidimensionale Matrix, wenn der Schritt 502 ausgeführt wird. Bevorzugt hat die Matrix in jeder ihrer Dimensionen eine Position für jeden möglichen Zielwert in der reduktiven Abbildung.In the step 501 the facility uses the reductive mapping specified for the characterization to map each byte of the digital document representation from the source value for the byte to a target value. For example, the facility for the characters shown in Table 2 would map the byte or source values to target values shown in Table 2. In step 502 The device constructs and initializes a matrix to contain the characterization. The matrix has a number of dimensions directly equal to the length, in characters, of the specified n-grams for that combination of speech and string matches. There step 406 specifies the use of bigram frequency distributions, the device constructs e.g. B. a two-dimensional matrix when the step 502 is performed. Preferably, the matrix has in each of its dimensions a position for each possible target value in the reductive map.

In den Schritten 503-505 durchläuft die Einrichtung eine Schleife für jedes Auftreten eines n-Grammes der spezifizierten Länge in der Folge von Zielwerten, die in Schritt 501 erzeugt wurden. Das heißt, daß wenn die Bigrammhäufigkeitsverteilungen spezifiziert sind, die Einrichtung mit dem Berücksichtigen der ersten und zweiten Zielwerte in den Folgen beginnt, dann die zweiten und dritten Zielwerte in den Folgen berücksichtigt usw., bis sie die zweitenbis-letzten und letzten Zielwerte in der Folge der Zielwerte berücksichtigt. Für das momentan betrachtete n-Grammauftreten inkrementiert die Einrichtung im Schritt 504 das Element der Matrix, die in Schritt 502 konstruiert wurde, das dem Zielwert-n-Gramm entspricht, das momentan betrachtet wird. Das heißt das Matrixelement, das inkrementiert wird, ist dasjenige, dessen erster Index den ersten Zielwert des n-Grammes aufweist, dessen zweiter Index den zweiten Zielwert des n-Grammes aufweist, usw. Wenn bspw. die Trigrammhäufigkeiten für das erste Trigramm, das in Tabelle 2 gezeigt ist, mit den Zielwerten 20, 15 und 16 zusammengeführt werden, würde die Einrichtung die Werte der Matrix an den Stellen (20, 15, 16) inkrementieren. Wenn im Schritt 505 irgendwelche Zielwen-n-Gramm-Vorkommnisse übrigbleiben, fährt die Einrichtung mit dem Schritt 503 fort, das nächste zu berücksichtigen. Andernfalls sind diese Schritte beendet. Beim Beenden dieser Schritte reflektiert die im Schritt 502 konstruierte Matrix, wie oft jedes Zielwert-n-Gramm in der digitalen Dokumentendarstellung vorkommt.In the steps 503 - 505 the device loops through for each occurrence of an n-gram of the specified length in the sequence of target values determined in step 501 were generated. That is, if the bigram frequency distributions are specified, the device starts considering the first and second target values in the sequences, then taking into account the second and third target values in the sequences, and so on, until the second to last and last target values in the sequence the target values. For the currently considered n-gram occurrence, the device increments in step 504 the element of the matrix in step 502 which corresponds to the target value n-gram currently being considered. That is, the matrix element that is incremented is the one whose first index has the first target value of the n-gram, the second index of which has the second target value of the n-gram, etc. If, for example, the trigram frequencies for the first trigram included in Table 2, are merged with the target values 20, 15 and 16, the device would increment the values of the matrix at the locations (20, 15, 16). When in step 505 any target-n-gram events remain, the facility goes to the step 503 continue to consider the next one. Otherwise, these steps are completed. When completing these steps, the one reflected in the step 502 constructed matrix of how many times each target n-gram appears in digital document representation.

6 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um die Zeichenfolge und Sprache einer eingegebenen digitalen Dokumentendarstellung zu identifizieren, für die diese Information nicht bekannt ist. In dem Schritt 601 bestimmt die Einrichtung, ob es wahrscheinlich ist, daß die eingegebene digitale Dokumentendarstellung in einer romanischen Einzelbytezeichenfolge erstellt ist. Wenn der größte Teil der Bytes der eingegebenen digitalen Dokumentendarstellung vor dem Abbilden einen Wert kleiner als 0×80 aufweist, d. h, keine hohe Bitfolge hat, bestimmt die Einrichtung, daß die eingegebene digitale Dokumentendarstellung in einer romanischen Einzelbytezeichenfolge erstellt ist und die Einrichtung fährt im Schritt 602 fort, die Schritte 602-605 auszuführen, andernfalls bestimmt die Einrichtung, daß die eingegebene digitale Dokumentendarstellung in einer Zeichenfolge mit mehreren Bytes oder einer nicht romanischen Zeichenfolge ausgedrückt ist und fährt im Schritt 606 fort, die Schritte 606 und 607 auszuführen. 6 Fig. 3 is a flow chart showing the steps that are preferably performed by the device to identify the character string and language of an input digital document representation for which this information is not known. In the step 601 the device determines whether it is likely that the input digital document representation is in a single-byte Roman string. If the majority of the bytes of the input digital document representation before mapping have a value less than 0x80, i. h, does not have a high bit string, the device determines that the input digital document representation is in a single-byte Roman string, and the device moves in step 602 away, the steps 602 - 605 otherwise, the device determines that the input digital document representation is expressed in a string of several bytes or a non-Romance string and moves in step 606 away, the steps 606 and 607 perform.

In dem Schritt 602 erzeugt die Einrichtung auf eine Weise, die ähnlich zu der des Schrittes 402 ist, eine dreidimensionale Charakterisierung der eingegebenen digitalen Dokumentendarstellung, wobei die Abbildung, die in Tabelle 1 gezeigt ist, und Trigramme verwendet werden. In dem Schritt 603 erkennt die Einrichtung die Sprache der eingegebenen digitalen Dokumentendarstellung, wobei die dreidimensionale Charakterisierung der eingegebenen digitalen Dokumentendarstellung, die in 602 erzeugt wurde, und die dreidimensionalen Modelle der Sprachen, die in Schritt 201 der Trainingsphase erzeugt wurden, verwendet werden. Dieses Erkennungsverfahren wird genauer weiter unten in Verbindung mit 7 beschrieben. In dem Schritt 604, nachdem die Sprache der eingegebenen digitalen Dokumentendarstellung erkannt wurde, erzeugt die Einrichtung eine eindimensionale Charakterisierung der eingegebenen digitalen Dokumentendarstellung auf eine Weise, die ähnlich zu der des Schrittes 404 ist, wobei die Abbildung, die in Tabelle 3 gezeigt ist, und Unigramme verwendet werden. In dem Schritt 605 erkennt die Einrichtung die Zeichenfolge der eingegebenen digitalen Dokumentendarstellung; wobei die eindimensionale Charakterisierung der eingegebenen digitalen Dokumentendarstellung, die in Schritt 604 erzeugt wurde, und die eindimensionalen Modelle der Kombinationen der Sprachen und Zeichenfolgen, die die erkannte Sprache umfassen, verwendet werden. Dieses Erkennungsverfahren wird genauer weiter unten in Verbindung mit 7 beschrieben. Nach dem Schritt 605 sind diese Schritte vollendet.In the step 602 creates the device in a way similar to that of the step 402 Figure 3 is a three-dimensional characterization of the input digital document representation using the map shown in Table 1 and trigrams. In the step 603 For example, the device recognizes the language of the input digital document representation, with the three-dimensional characterization of the input digital document representation shown in FIG 602 was generated, and the three-dimensional models of the languages in step 201 the training phase were generated used. This recognition method will be discussed in more detail below 7 described. In the step 604 After the language of the input digital document representation has been recognized, the device generates a one-dimensional characterization of the input digital document representation in a manner similar to that of the step 404 using the map shown in Table 3 and unigrams. In the step 605 the device recognizes the string of input digital document representation; the one-dimensional characterization of the input digital document representation shown in step 604 and the one-dimensional models of the combinations of the languages and strings comprising the recognized language are used. This recognition method will be discussed in more detail below 7 described. After the step 605 these steps are completed.

In dem Schritt 606 erzeugt die Einrichtung auf eine Weise, die ähnlich zu der des Schrittes 406 ist, eine zweidimensionale Charakterisierung der eingegebenen digitalen Dokumentendarstellung, wobei die Abbildung, die in Tabelle 4 gezeigt ist, und Bigramme verwendet werden. In dem Schritt 607 erkennt die Einrichtung sowohl die Sprache wie auch die Zeichenfolge der eingegebenen digitalen Dokumentendarstellung, wobei die zweidimensionale Charakterisierung der eingegebenen digitalen Dokumentendarstellung, die in Schritt 606 erzeugt wurde, und die zweidimensionalen Modelle der Kombinationen aus Sprachen und Zeichenfolgen, die in Schritt 201 der Trainingsphase erzeugt wurde, verwendet werden. Dieses Erkennungsverfahren wird ebenso weiter unten genauer in Verbindung mit 7 beschrieben. Nach dem Schritt 607 sind diese Schritte vollendet.In the step 606 creates the device in a way similar to that of the step 406 2 is a two-dimensional characterization of the input digital document representation using the map shown in Table 4 and bigrams. In the step 607 For example, the device recognizes both the language and the character string of the input digital document representation, with the two-dimensional characterization of the input digital document representation shown in step 606 and the two-dimensional models of the combinations of languages and strings that were created in step 201 the training phase was generated. This recognition method will also be discussed in more detail below 7 described. After the step 607 these steps are completed.

7 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um die Zeichenfolge und/oder Sprache der eingegebenen digitalen Dokumentendarstellung in Übereinstimmung mit den Schritten 603, 605 oder 607 zu erkennen. In diesen Schritten vergleicht die Einrichtung die vorliegende Charakterisierung der eingegebenen digitalen Dokumentendarstellung mit jedem Kandidatenmodell. Die Sprache und/oder Zeichenfolge des Kandidatenmodells, die mit der Charakterisierung der eingegebenen digitalen Dokumentendarstellung am ähnlichsten ist, wird als die der eingegebenen digitalen Dokumentendarstellung erkannt. In den Schritten 701-703 durchläuft die Einrichtung Schleifen für jedes Kandidatenmodell einer Sprache und/oder Zeichenfolge, wie in den Schritten 603, 605 oder 607 spezifiziert. In dem Schritt 702 berechnet die Einrichtung das Skalarprodukt der Matrizen, die für das betrachtete Kandidatenmodell und die Charakterisierung der eingegebenen digitalen Dokumentendarstellung stehen. Eine solche Berechnung beinhaltet das Multiplizieren des Wertes einer jeder Stelle in der Kandidatenmodellmatrix mit dem entsprechenden Wert in der Charakterisierungsmatrix und ein Addieren dieser Produkte, um einen einzigen Wert zu erhalten, der „Score" genannt wird und die Ähnlichkeit des Kandidatenmodells mit der Charakterisierung darstellt. In dem Schritt 703, wenn weitere Kandidatenmodelle zur Verarbeitung übrigbleiben, fährt die Einrichtung in dem Schritt 701 fort, das nächste Kandidatenmodell zu verarbeiten, andernfalls fährt die Einrichtung mit dem Schritt 704 fort. In dem Schritt 704 identifiziert die Einrichtung das Kandidatenmodell, für den der höchste Score im Schritt 702 berechnet wurde. In dem Schritt 705 erkennt die Einrichtung, daß die eingegebene digitale Dokumentendarstellung von der Sprache und/oder Zeichenfolge des Kandidatenmodells ist, die in Schritt 704 erkannt wurde(n). Nach dem Schritt 705 sind diese Schritte beendet. 7 FIG. 5 is a flowchart showing the steps that are preferably performed by the device to compare the character string and / or language of the input digital document representation in accordance with the steps. FIG 603 . 605 or 607 to recognize. In these steps, the device compares the present characterization of the input digital document representation with each candidate model. The language and / or character string of the candidate model most similar to the characterization of the input digital document representation is recognized as that of the input digital document representation. In the steps 701 - 703 The facility goes through loops for each candidate model of a language and / or string, as in the steps 603 . 605 or 607 specified. In the step 702 the device calculates the dot product of the matrices that represent the candidate model under consideration and the characterization of the input digital document representation. Such computation involves multiplying the value of each location in the candidate model matrix by the corresponding value in the characterization matrix and adding these products to obtain a single value called "Score" that represents the similarity of the candidate model to the characterization. In the step 703 if there are more candidate models left for processing, the facility will go to the step 701 otherwise, the device continues to move to the next candidate model 704 continued. In the step 704 The facility identifies the candidate model for which the highest score is in the step 702 was calculated. In the step 705 recognizes the facility that the input digital document representation is of the language and / or character string of the candidate model identified in step 704 was detected. After the step 705 these steps are finished.

Die Schritte, die in 6 gezeigt sind, erkennen eine einzelne dominante Sprache als die der eingegebenen digitalen Dokumentendarstellung, weil diese die eingegebene digitale Dokumentendarstellung als Ganzes beurteilen. Für eingegebene digitale Dokumentendarstellungen, die Text in mehr als einer Sprache enthalten, hat das Erkennen jeder dieser Sprachen jedoch oft erhebliche Bedeutung. 8 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um mehrere Sprachen zu erkennen, die in einer eingegebenen digitalen Dokumentendarstellung vorkommen, wie auch die Zeichenfolge zu erkennen, in der die eingegebene digitale Dokumentendarstellung erstellt ist. Diese Schritte beinhalten ein Unterteilen der eingegebenen digitalen Dokumentendarstellung in eine Anzahl von kürzeren Segmenten, ein Erkennen der Sprache und Zeichenfolge für jedes Segment und Berichten aller Sprachen, die für die Segmente erkannt wurden, wie auch der Zeichenfolge, die erkannt wurde.The steps in 6 1, recognize a single dominant language as that of the input digital document representation because they judge the input digital document representation as a whole. However, for input digital document representations containing text in more than one language, the recognition of each of these languages is often significant. 8th Figure 5 is a flowchart showing the steps that are preferably performed by the device to recognize multiple languages occurring in an input digital document representation, as well as to recognize the string in which the input digital document representation is created. These steps include dividing the input digital document representation into a number of shorter segments, recognizing the language and string for each segment, and reporting all languages recognized for the segments, as well as the string that was recognized.

In Schritt 801 unterteilt die Einrichtung die eingegebene digitale Dokumentendarstellung in Segmente. In einer ersten Ausführungsform haben diese Segmente eine Größe eines herkömmlichen Satzes oder ca. 75 Zeichen. In einer alternativen Ausführungsform haben die Segmente die Größe eines typischen Absatzes oder ca. 400 Zeichen. Diese Segmentgröße ist bevorzugt einstellbar, wodurch es möglich ist, die Einrichtung anzupassen, um einen Text in verschiedenen Sprachen in Segmenten verschiedener Größe zu untersuchen. Ein Verringern der Segmentgröße erhöht die Anzahl von Sprachen, die in einer mehrsprachigen eingegebenen digitalen Dokumentendarstellung erkannt werden können, wohingegen ein Erhöhen der Segmentgröße die Verarbeitungszeit in der Erkennungsphase reduziert.In step 801 the device segments the input digital document representation into segments. In a first embodiment, these segments have a size of a conventional set or about 75 characters. In an alternative embodiment, the segments are the size of a typical paragraph or about 400 characters. This segment size is preferably adjustable, which makes it possible to adapt the device to examine text in different languages in segments of different sizes. Reducing the segment size increases the number of languages that can be recognized in a multilingual input digital document representation, whereas increasing the segment size reduces the processing time in the recognition phase.

In den Schritten 802-804 durchläuft die Einrichtung für jedes Segment eine Schleife. In dem Schritt 803 erkennt die Einrichtung die Sprache und Zeichenfolge des betrachteten Segmentes in Übereinstimmung mit den Schritten, die in 6 gezeigt sind. Wenn weitere Segmente im Schritt 804 für die weitere Verarbeitung übrigbleiben, fährt die Einrichtung im Schritt 802 fort, diese zu verarbeiten, andernfalls fährt die Einrichtung mit Schritt 805 fort. In dem Schritt 805 berichtet die Einrichtung, daß die eingegebene digitale Dokumentendarstellung jede Sprache enthält, die in einer Iteration des Schrittes 803 für eines der Segmente erkannt wurde, in absteigender Reihenfolge der Segmentzahl, in der die Sprache erkannt wurde. In einer Ausführungsform sind die erkannten Sprachen, die im Schritt 805 berichtet werden, auf die begrenzt, die in einer Schwellwertanzahl von Segmenten größer als 1 erkannt wurden. In einer weiter bevorzugten Ausführungsform werden die berichteten, erkannten Sprachen weiter sortiert, um Doppelbytezeichenfolgensprachen oder nicht romanische Sprachen in der Liste oberhalb romanischer Einzelbytezeichenfolgensprachen darzustellen.In the steps 802 - 804 the device loops through each segment. In the step 803 the device recognizes the language and string of the considered segment in accordance with the steps described in 6 are shown. If more segments in the step 804 for further processing, the device moves in step 802 otherwise, the device will go to step 805 continued. In the step 805 the facility reports that the input digital document representation contains any language that is in an iteration of the step 803 for one of the segments, in descending order of the segment number in which the language was recognized. In one embodiment, the recognized languages that are in step 805 are limited to those detected in a threshold number of segments greater than 1. In a further preferred embodiment, the reported recognized languages are further sorted to represent double-byte string languages or non-Romance languages in the list above single-byte Roman string languages.

In dem Schritt 806 wählt die Einrichtung eine Zeichenfolge aus den Zeichenfolgen aus, die in den Iterationen des Schrittes 803 erkannt wurden. Der Schritt 806 wird genauer weiter unten in Verbindung mit 9 beschrieben. In dem Schritt 807 berichtet die Einrichtung die im Schritt 806 ausgewählte Zeichenfolge. Nach dem Schritt 807 werden diese Schritte beendet.In the step 806 The facility selects a string from the strings that are in the iterations of the step 803 were detected. The step 806 will be discussed in more detail below 9 described. In the step 807 The institution reports in step 806 selected string. After the step 807 these steps are finished.

9 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um eine Zeichenfolge für die eingegebene digitale Dokumentendarstellung aus den Zeichenfolgen auszuwählen, die für Segmente der eingegebenen digitalen Dokumentendarstellung erkannt wurden. Wenn in dem Schritt 901 alle der dedektierten Zeichenfolgen romanische Einzelbytezeichenfolgen sind, fährt die Einrichtung mit dem Schritt 902 fort, andernfalls fährt die Einrichtung mit dem Schritt 904 fort. In dem Schritt 902 wählt die Einrichtung die Sprache, die als Sprache der meisten Segmente erkannt wurde, als die Sprache der eingegebenen digitalen Dokumentendarstellung aus. In dem Schritt 903 wählt die Einrichtung die Zeichenfolge aus, die mit der Sprache erkannt wurde, die in Schritt 902 für die meisten Segmente ausgewählt wurde. Nach dem Schritt 903 werden diese Schritte beendet. In dem Schritt 904 wählt die Einrichtung die Sprache aus, die mit einer Zeichenfolge, die mehrere Bytes aufweist, oder einer nicht romanischen Einzelbytezeichenfolge, die in den meisten Segmenten erkannt wurde, erkannt wurde. In dem Schritt 905 wählt die Einrichtung die Zeichenfolge, die mehrere Byte aufweist, oder eine nicht romanische Einzelbytezeichenfolge aus, die mit der in Schritt 904 ausgewählten Sprache erkannt wurde, die für die meisten Segmente erkannt wurde. Nach dem Schritt 905 sind diese Schritte vollendet. 9 Figure 4 is a flow chart showing the steps that are preferably performed by the device to select a string for the input digital document representation from the strings that were recognized for segments of the input digital document representation. If in the step 901 all of the dedected strings are single-byte Roman string strings, the device moves to the step 902 otherwise, the device will go to the step 904 continued. In the step 902 the device selects the language recognized as the language of most segments, as the language of the entered digital document representation. In the step 903 The facility selects the string that was recognized by the language that was used in step 902 has been selected for most segments. After the step 903 these steps are finished. In the step 904 The facility selects the language recognized by a string that has multiple bytes or a non-Romance, single-byte string that has been recognized in most segments. In the step 905 The device selects the string that has multiple bytes, or a non-Romance, single-byte string that matches the one in step 904 selected language that has been recognized for most segments. After the step 905 these steps are completed.

Die obigen Ausführungen beschreiben die Verwendung der Einrichtung zum Erkennen sowohl der Zeichenfolge wie auch der Sprachen einer eingegebenen digitalen Dokumentendarstellung, von der diese Information nicht bekannt ist. Die Einrichtung ist ferner ausgelegt, die Sprachen zu erkennen, die in einer eingegebenen digitalen Dokumentendarstellung verwendet werden, von der bekannt ist, daß diese in einer bestimmten Unicodezeichenfolge erstellt ist. Die Unicodezeichenfolge, wie sie von dem Unicode-Konsortium in San Jose, Californien, USA, in The Unicode Standard, Version 2.0. definiert ist, ist eine große Zeichenfolge, die ausgelegt ist, die meisten Zeichenglypten darzustellen, die in den meisten Sprachen der Welt verwendet werden. Da die Unicodezeichenfolge den Text von so vielen verschiedenen Sprachen darstellen kann, ist es nützlich, fähig zu sein, die Sprachen, die in einer eingegebenen digitalen Dokumentendarstellung vorhanden sind, zu erkennen, von der bekannt ist, das sie in einer Unicodezeichenfolge erstellt ist. Die Unicodezeichenfolge verwendet 16-Bit Zeichenwerte, die 65536 verschiedene Zeichen ermöglichen. Die Unicodezeichenfolge ist in eine Anzahl von „Schriftbereichen" unterteilt, die die Zeichen bündelt, die im allgemeinen in einer Sprache oder in einer Gruppe von verwandten Sprachen verwendet werden. Die untere Tabelle 5 zeigt einige der „Einzelsprachen"-Schriftbereiche, die Zeichen enthalten, die nur in einer Sprache verwendet werden.The above describe the use of the means for recognizing both the String as well as the languages of an input digital Document presentation of which this information is unknown. The device is also designed to recognize the languages used in an input digital document representation which is known to be that is created in a specific Unicode string. The Unicode string, as reported by the Unicode Consortium in San Jose, California, USA, in The Unicode Standard, Version 2.0. defined is a large string, which is designed to represent most drawing glyphs that to be used in most languages of the world. Because the Unicode string is the text of so many different languages is it useful, to be able to the languages used in an input digital document representation to recognize that is known to be in one Unicode string is created. The Unicode string is used 16-bit character values that allow 65536 different characters. The Unicode string is subdivided into a number of "font ranges" that are the signs bundles, which are generally in one language or group of relatives Languages are used. Table 5 below shows some of the "single language" fonts, contain the characters that are used in one language only.

Tabelle 5: Unicodeschriftbereich für Einzelsprachen

Table 5: Unicode writing area for individual languages

Man kann aus Tabelle 5 sehen, daß z. B. der Schriftbereich von 0×0400 bis 0×04FF nur in russisch verwendet wird. Die unten gezeigte Tabelle 6 zeigt auf der anderen Seite einige der „mehrsprachigen" Schriftbereiche, die Zeichen enthalten, die jeweils in einer Gruppe von zwei oder mehr Sprachen verwendet werden.It can be seen from Table 5 that z. For example, the font range from 0x400 to 0x4FF is only used in Russian. Table 6 below shows some of the "multilingual" font on the other side Areas containing characters used in a group of two or more languages.

Tabelle 6: mehrsprachige Unicodeschriftbereiche

Table 6: Multilingual Unicode Scripts

Man kann z. B. sehen, daß der Schriftbereich von 0×4E00 bis 0×9FFF in jeder der „CJK-Gruppe"-Sprachen, chinesisch, japanisch und koreanisch, verwendet wird. In den Fällen, in denen die Zeichen in einem Segment einer eingegebenen digitalen Unicodedokumentendarstellung zum überwiegenden Teil aus einem dieser Einzelsprachenschriftbereiche stammen, erkennt die Einrichtung die Sprache des Segmentes als die einzige Sprache dieses Schriftbereiches. In den Fällen, in denen die Zeichen eines Segmentes zum überwiegenden Teil aus einem Mehrsprachenschriftbereich stammen, bildet die Einrichtung bevorzugt die Quellwerte des Segmentes ab, um eine statistische Charakterisierung des Segmentes zu erzeugen, und vergleicht sodann diese Charakterisierung mit den Modellen der Sprachen in der Sprachengruppe auf eine Weise, die zuvor beschrieben wurde.you can z. B. see that the Font area from 0 × 4E00 to 0 × 9FFF in each of the "CJK group" languages, Chinese, Japanese and Korean. In cases, in which are the characters in a segment of an input digital Unicode document representation for the most part Part of one of these individual language fonts, recognizes the device the language of the segment as the only language this writing area. In cases where the characters of a segment for the most part come from a multilingual area, forms the institution prefers the source values of the segment to a statistical one Characterization of the segment, and then compares this characterization with models of languages in language group in a way that was previously described.

Für Segmente, die zum überwiegenden Teil aus Zeichen eines Schriftbereiches oder mehrerer Schriftbereiche der „romanischen" Sprachengruppe bestehen, die die romanischen Sprachen, wie z. B. die oben aufgeführten, umfaßt, verwendet die Einrichtung bevorzugt die Abbildung, die unten in Tabelle 7 gezeigt ist, um die Quellwerte des Segmentes auf dieselben 28 Zielwerte abzubilden, wie die in Tabelle 1 gezeigte Abbildung zum Erkennen der Sprache einer romanischen Einzelbytezeichenfolge.For segments, for the most part Part of characters in a font area or multiple font areas consist of the "Romance" language group, the Romance languages, such as As those listed above, used the device prefers the picture below in Table 7 shown is the source values of the segment on the same 28 target values such as the figure shown in Table 1 to recognize the language of a romance single byte string.

Tabelle 7: Abbildung um Sprachen eines romanischen Unicode zu erkennen

Table 7: Illustration to recognize languages of a Romance Unicode

Wie weiter unten genauer beschrieben werden wird, erkennt die Einrichtung die romanische Sprache innerhalb der romanischen Gruppe durch Vergleichen einer dreidimensionalen Charakterisierung des Segmentes mittels dieser Abbildung mit den dreidimensionalen Modellen der Sprachen in der romanischen Gruppe, die bereits durch die Einrichtung in Übereinstimmung mit 3 erzeugt wurden. As will be described in more detail below, the device recognizes the Romance language within the Romansh group by comparing a three-dimensional characterization of the segment by means of this mapping with the three-dimensional models of the languages in the Romance group already by the device in accordance with 3 were generated.

Für Segmente, die zum überwiegenden Teil aus Zeichenwerten eines mehrsprachigen Schriftbereiches einer Sprachengruppe bestehen, die eine andere als die romanische Sprachengruppe ist, verwendet die Einrichtung eine anwenderspezifische Abbildung, die von der Einrichtung speziell für diese Sprachengruppe auf eine Weise erzeugt wurde, die ausgelegt ist, um zwischen den verschiedenen Sprachen der Sprachengruppe unterscheiden zu können. Diese anwenderspezifischen Abbildungen, wie z. B. die in Tabelle 7 gezeigte Abbildung, bilden von allen 65536 Unicodezeichenwerten auf eine viel kleinere Anzahl von Zielwerten, wie z. B. 256 ab. Die anwenderspezifische Abbildung für die Sprachengruppe wird verwendet, um eine eindimensionale Charakterisierung des Segmentes zu konstruieren, die sodann mit eindimensionalen Modellen der verschiedenen Sprachen in der Sprachengruppe verglichen wird, die mittels der gleichen anwenderspezifischen Abbildung erzeugt wurden.For segments, for the most part Part of character values of a multilingual font area of a Language group that is a non-Romance language group if the device uses a custom image, those set up by the institution specifically for this language group a way has been created that is designed to be between the different ones Differentiate languages of the language group. This user-specific Illustrations such. For example, as shown in Table 7 from all 65536 Unicode characters to a much smaller number of target values, such as B. 256. The user-specific picture for the Language group is used to create a one-dimensional characterization of the segment, which then with one-dimensional models compared to the different languages in the language group, generated by means of the same user-specific mapping were.

10 ist ein Flußdiagramm, das die Schritte zeigt, die von der Einrichtung bevorzugt in der Trainingsphase ausgeführt werden, um eine anwenderspezifische reduktive Abbildung für eine Unicodesprachengruppe zu erzeugen, die verwendet wird, um zwischen den Sprachen der Sprachengruppe zu unterscheiden. Diese Schritte werden bevorzugt für jede Gruppe von Sprachen ausgeführt, die in einem großen Ausmaß auf dem gleichen Schriftbereich beruhen. Zum Beispiel beruhen die chinesische, japanische und koreanische Sprache sehr auf den Schriftbereichen, die für die „CJK"-Sprachengruppe in Tabelle 6 gezeigt sind. Als ein weiteres Beispiel beruht eine Gruppe von indischen Sprachen ebenso stark auf einem einzelnen Schriftbereich. Diese Schritte werden einmalig für eine jede derartige Gruppe ausgeführt, wodurch eine anwenderspezifische Abbildung für die Gruppe erzeugt wird, die ausgelegt ist, um die Sprachen der Gruppe zu unterscheiden. In einer bevorzugten Ausführungsform hat die anwenderspezifische Abbildung 256 Zielwerte. In alternativen Ausführungsformen bildet die anwenderspezifische Abbildung auf eine Anzahl von Zielwerten ab, die größer oder kleiner als 256 ist. 10 FIG. 10 is a flowchart showing the steps performed by the device, preferably in the training phase, to generate a custom reductive map for a Unicode language group used to distinguish between the languages of the language group. These steps are preferably performed for each group of languages based to a large extent on the same font area. For example, the Chinese, Japanese, and Korean languages are very much based on the font areas shown for the "CJK" language group in Table 6. As another example, a group of Indian languages relies as much on a single font area.These steps become unique for each such group, thereby creating a custom map for the group that is designed to distinguish the languages of the group In a preferred embodiment, the custom map has 256 target values In alternative embodiments, the custom map maps to a number Target values greater than or less than 256.

In den Schritten 1001-1004 durchläuft die Einrichtung Schleifen für jede Sprache in der Sprachengruppe. In dem Schritt 1002 weist die Einrichtung beliebige Quellwerte des betrachteten, exklusiven Schriftbereiches der Sprache einen einzelnen Zielwert zu. In dem Schritt 1003 zählt die Einrichtung die Häufigkeit des Auftretens eines jeden einzelnen Quellwertes. Wenn in dem Schritt 1004 zusätzliche Sprachen zur Verarbeitung übrigbleiben, fährt die Einrichtung in dem Schritt 1001 damit fort, die nächste Sprache in der Sprachengruppe zu verarbeiten, andernfalls fährt die Einrichtung mit dem Schritt 1005 fort. In den Schritten 1005-1008 durchläuft die Einrichtung wiederum Schleifen für jede Sprache in der Sprachengruppe. In dem Schritt 1006 weist die Einrichtung Quellwerten, die nur in dem Korpus der betrachteten Sprache auftreten, einen einzelnen Zielwert zu. In dem Schritt 1007 weist die Einrichtung jeder Gruppe von 100 Quellwerten, die am häufigsten in dem Korpus der betrachteten Sprache auftreten, einen einzelnen Zielwert zu. Falls in dem Schritt 1008 weitere Sprachen zu verarbeiten sind, fährt die Einrichtung mit dem Schritt 1005 fort, die nächste Sprache in der Sprachengruppe zu verarbeiten, andernfalls fährt die Einrichtung mit dem Schritt 1009 fort. In dem Schritt 1009 weist die Einrichtung den restlichen Quellwerten die restlichen Zielwerte zu. Nach dem Schritt 1009 bildet die anwenderspezifische Abbildung jeden Quellwert auf einen der 256 Zielwerte ab und diese Schritte werden beendet.In the steps 1001 - 1004 the facility goes through loops for each language in the language group. In the step 1002 For example, the facility assigns any source values of the considered exclusive font area of the language a single target value. In the step 1003 the facility counts the frequency of occurrence of each individual source value. If in the step 1004 additional languages remain for processing, the facility goes to the step 1001 to continue processing the next language in the language group, otherwise the facility moves to the step 1005 continued. In the steps 1005 - 1008 by The facility again runs loops for each language in the language group. In the step 1006 For example, the device assigns a single target value to source values occurring only in the corpus of the language under consideration. In the step 1007 For example, the establishment of each group of 100 source values that most frequently occur in the corpus of the language under consideration will assign a single target value. If in the step 1008 further languages are to be processed, the device moves to the step 1005 Otherwise, the device continues with the step, processing the next language in the language group 1009 continued. In the step 1009 the facility assigns the remaining target values to the remaining source values. After the step 1009 The custom map maps each source value to one of the 256 target values, and these steps are terminated.

Nach dem Erzeugen von anwenderspezifischen reduktiven Abbildungen für jede Unicodesprachengruppe in Übereinstimmung mit 10, verwendet die Einrichtung bevorzugt jede anwenderspezifische Abbildung, um ein eindimensionales statistisches Modell von jeder der Sprachen in der Sprachengruppe zu erzeugen. Die Einrichtung führt ein solches Erzeugen in Übereinstimmung mit den Schritten aus, die in 3 gezeigt sind.After generating custom reductive maps for each Unicode language group in accordance with 10 , the facility preferably uses each custom map to generate a one-dimensional statistical model of each of the languages in the language group. The device performs such generating in accordance with the steps described in 3 are shown.

11 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um die Sprachen zu erkennen, die in einer eingebenen digitalen Dokumentendarstellung auftreten, die in einer Unicodezeichenfolge erstellt ist. Indem Schritt 1101 unterteilt die Einrichtung die eingegebene digitale Dokumentendarstellung in Segmente, wie z. B. Segmente von der Länge eines Absatzes mit ca. 400 Zeichen. In den Schritten 1102-1104 durchläuft die Einrichtung für jedes Segment eine Schleife. In dem Schritt 1103 erkennt die Einrichtung die Sprache des Segmentes. Dieses Erkennungsverfahren wird weiter unten in Verbindung mit 12 beschrieben. Falls in dem Schritt 1104 weitere Segmente verarbeitet werden müssen, fährt die Einrichtung mit dem Schritt 1102 fort, das nächste Segment zu verarbeiten, andernfalls fährt die Einrichtung mit dem Schritt 1105 fort. In dem Schritt 1105 berichtet die Einrichtung alle Sprache, die in dem Schritt 1103 erkannt wurden, in absteigender Reihenfolge der Anzahl der Segmente, in der die Sprache erkannt wurde. Nach dem Schritt 1105 sind diese Schritte vollendet. 11 Figure 5 is a flow chart showing the steps that are preferably performed by the device to recognize the languages that occur in an input digital document representation that is created in a Unicode string. By step 1101 the device divides the input digital document representation into segments, such as: B. Segments the length of a paragraph with approximately 400 characters. In the steps 1102 - 1104 the device loops through each segment. In the step 1103 the device recognizes the language of the segment. This recognition method will be described below in connection with 12 described. If in the step 1104 further segments must be processed, the device moves to the step 1102 otherwise, the device continues with the step 1105 continued. In the step 1105 the setup reports all the language in the step 1103 in descending order of the number of segments in which the language was recognized. After the step 1105 these steps are completed.

12 ist ein Flußdiagramm, das die Schritte zeigt, die bevorzugt von der Einrichtung ausgeführt werden, um die Sprache eines Segmentes einer eingegebenen digitalen Dokumentendarstellung zu erkennen, die in der Unicodezeichenfolge erstellt ist. In den Schritten 1201-1204 zählt die Einrichtung, wie oft Unicodezeichen in dem Segment auftreten, die sich innerhalb eines jeden Schriftbereiches befinden, die in Tabelle 5 und 6 gezeigt sind. In den Schritten 1201-1204 durchläuft die Einrichtung für jedes Auftreten eines Unicodezeichens in dem Segment eine Schleife. Falls in dem Schritt 1202 das Auftreten des Zeichens innerhalb eines Schriftbereiches liegt, fährt die Einrichtung mit dem Schritt 1203 fort, um einen Zähler für den Schriftbereich zu erhöhen, andernfalls fährt die Einrichtung mit dem Schritt 1204 fort. Falls in dem Schritt 1204 aufgetretene Unicodezeichen noch zu verarbeiten sind, fährt die Einrichtung in dem Schritt 1201 fort, das nächste aufgetretene Unicodezeichen in dem Segment zu verarbeiten, andernfalls fährt die Einrichtung mit dem Schritt 1205 fort. Falls in dem Schritt 1205 der Schriftbereich, dessen Zähler den höchsten Wert aufweist, ein Einzelsprachenschriftbereich ist, fährt die Einrichtung mit dem Schritt 1206 fort, andernfalls ist der Schriftbereich, dessen Zähler den höchsten Wert aufweist, ein mehrsprachiger Schriftbereich und die Einrichtung fährt mit dem Schritt 1207 fort. In dem Schritt 1206 erkennt die Einrichtung die Sprache des Segmentes als die Sprache des Einzelsprachenschriftbereiches. Nach dem Schritt 1206 sind diese Schritte vollendet. 12 Figure 13 is a flow chart showing the steps that are preferably performed by the device to recognize the language of a segment of an input digital document representation created in the Unicode string. In the steps 1201 - 1204 counts the number of times Unicode characters occur in the segment that are within each range of fonts shown in Tables 5 and 6. In the steps 1201 - 1204 The device loops through each occurrence of a Unicode character in the segment. If in the step 1202 If the occurrence of the character is within a writing range, the device moves to the step 1203 to increase a font area counter, otherwise the facility will move to the step 1204 continued. If in the step 1204 Unicode characters that are still to be processed have to be processed by the device in the step 1201 Otherwise, the next step is to process the next Unicode character in the segment, otherwise the device moves to the step 1205 continued. If in the step 1205 the font area whose counter has the highest value is a single language font area, the facility moves to the step 1206 otherwise, the font area whose counter has the highest value is a multilingual font area, and the facility moves to the step 1207 continued. In the step 1206 the device recognizes the language of the segment as the language of the single language font area. After the step 1206 these steps are completed.

Falls in dem Schritt 1207 die Sprachengruppe des Schriftbereiches, dessen Zähler den höchsten Wert aufweist, die romanische Sprachengruppe ist, fährt die Einrichtung mit dem Schritt 1208 fort, andernfalls fährt die Einrichtung mit dem Schritt 1210 fort. In dem Schritt 1208 erzeugt die Einrichtung eine dreidimensionale Charakterisierung des Segmentes, wobei die Abbildung verwendet wird, die in Tabelle 7 gezeigt ist, die ausgelegt ist, die Sprachen der romanischen Sprachengruppe zu unterscheiden. Der Schritt 1208 wird in Übereinstimmung mit den Schritten, die in 5 gezeigt sind, ausgeführt, wie zuvor beschrieben. In dem Schritt 1209 erkennt die Einrichtung die Sprache des Segmentes, wobei die erzeugte dreidimensionale Charakterisierung und dreidimensionale Modelle der Sprachen in der romanischen Gruppe in Übereinstimmung mit den Schritten, die in 7 gezeigt sind, verwendet werden. Nach dem Schritt 1209 sind diese Schritte vollendet.If in the step 1207 the language group of the font area whose counter has the highest value, is the Romance language group, the facility moves to the step 1208 otherwise, the device will go to the step 1210 continued. In the step 1208 the device generates a three-dimensional characterization of the segment using the mapping shown in Table 7, which is designed to distinguish the languages of the Romance language group. The step 1208 will be in accordance with the steps in 5 are shown executed as described above. In the step 1209 the device recognizes the language of the segment, with the generated three - dimensional characterization and three - dimensional models of the languages in the Romansh group in accordance with the steps described in 7 are shown used. After the step 1209 these steps are completed.

In dem Schritt 1210 erzeugt die Einrichtung eine eindimensionale Charakterisierung des Segmentes, wobei eine anwenderspezifische Abbildung der Sprachengruppe verwendet wird, die während der Trainingsphase in Übereinstimmung mit 10 erzeugt wurde. Der Schritt 1210 wird in Übereinstimmung mit den Schritten, die in 5 gezeigt sind, ausgeführt, wie zuvor beschrieben. In dem Schritt 1211 erkennt die Einrichtung die Sprache des Segmentes, wobei die eindimensionale Charakterisierung, die in dem Schritt 1210 erzeugt wurde, und eindimensionale Modelle der Sprachen der Sprachengruppe in Übereinstimmung mit den Schritten, die in 7 gezeigt sind, verwendet werden. Nach dem Schritt 1211 sind diese Schritte vollendet.In the step 1210 the device generates a one-dimensional characterization of the segment using a user-specific mapping of the language group that is in accordance with the training phase 10 was generated. The step 1210 will be in accordance with the steps in 5 are shown executed as described above. In the step 1211 the device recognizes the language of the segment, using the one-dimensional characterization, which in the step 1210 and one-dimensional models of the languages of the language group in accordance with the Steps in 7 are shown used. After the step 1211 these steps are completed.

Während diese Erfindung unter Bezug auf bevorzugte Ausführungsformen gezeigt und beschrieben wurde, werden Fachleute verstehen, daß verschiedene Änderungen und Modifikationen in Form und Detail vorgenommen werden können, ohne den Bereich der Erfindung zu verlassen. Zum Beispiel können n-Gramme von größerer Länge, als die oben beschriebene, verwendet werden, um die Genauigkeit der Einrichtung zu erhöhen. Auf der anderen Seite können n-Gramme kleinerer Länge verwendet werden, um die Speicheranforderungen der Einrichtung zu verringern. Während statistische Charakterisierungen der digitalen Dokumentendarstellungen und statistische Modelle der Sprachen und/oder Zeichenfolgen auf einfache Weise in der Einrichtung durch Verwenden eines ein- oder mehrdimensionalen Arrays von Werten zwischen 0 und 255 dargestellt werden, kann die Einrichtung auf einfache Weise ausgelegt werden, andere Speicherschemata zu verwenden, wie z. B. Arrays mit Elementen von verschiedener Größe, Sparse-Arrays oder Datenstrukturen anderer Arten. Während die Einrichtung in dieser Schrift unter Bezug auf die bestimmten Schriftnatursprachen und Zeichenfolgen beschrieben wurde, kann die Einrichtung ferner auf einfache Weise angewendet werden, um Sprachen und Zeichenfolgen aller Art, umfassend diejenigen, die momentan noch nicht verwendet werden, zu modellieren und zu erkennen.While these Has been shown and described with reference to preferred embodiments, Professionals will understand that various changes and modifications in form and detail can be made without to abandon the scope of the invention. For example, n-grams of greater length than the one described above, used to increase the accuracy of the To increase facility. On the other hand you can n-grams of smaller length used to adjust the storage requirements of the facility reduce. While statistical characterizations of digital document representations and statistical models of languages and / or strings easy way in the institution by using a on or multidimensional arrays of values between 0 and 255 the device can be designed in a simple way, to use other memory schemes such. For example, arrays of elements of different size, sparse arrays or data structures of other types. While the decor in this Writing with reference to the particular font languages and strings has been described, the device can further easily be applied to languages and strings of all kinds, including modeling those that are currently not in use and to recognize.

Claims

Computer-implemented ( 100 ) Method for generating models ( 133 ), each model text being in one of a plurality of languages, the method comprising the steps of: - receiving a plurality of sequences of data values, each sequence of data values including a sample text ( 132 ) in an identified language and wherein each data value is one of a number of possible data values; - generating a statistical model ( 133 ) for each sequence of data values representing the language regarding the statistical appearance of particular data values in the example text ( 132 ) modeled; Using a reductive mapping to map the data values of each sequence of data values from the number of possible data values to target data values within a smaller number of possible target values to produce a sequence of derived target values corresponding to the sequence of data values; and - generating a statistical model ( 133 ) of each language by counting, for each n-gram of possible target values, the number of occurrences of the n-gram in the sequence of derived target values, and combining the counted number of n-grams of target values into a model for the speech generated by the Sequence of data values, where the model ( 133 ) reflects the relative frequency of each n-gram of possible target values in all sequences of derived target values for which the speech represented by the sequence of values is identified; characterized by setting the counts of the models ( 133 ) for a more efficient differentiation of models ( 133 ) from each other by increasing the counts of high-frequency n-grams whose occurrence tends to discriminate a document of one language and a character string from other language documents and a character string, and by decreasing the counts of high-frequency n-grams whose occurrence does not tend to occur; to distinguish a document of a language and a string from documents of other languages and strings.

Method according to Claim 1, characterized in that the step of setting the counts of the models ( 133 ) comprises the steps of: - increasing the counts for n-grams whose counts have the highest relationship to the counts for the same n-grams in other models; and - decreasing the counts for n-grams whose counts are high relative to the counts for that model but high relative to the counts for the same n-grams in other models.

Method according to Claim 1, characterized in that the step of setting the counts of the models ( 133 ) doubling an n-gram number for a particular n-gram in a model ( 133 ) and subtracting an average n-gram number for the particular n-gram over multiple models ( 133 ) of the n-gram number.

Method according to one of claims 1 to 3, characterized by the further steps of: receiving an input sequence of data values representing a text in an unknown language; Applying the reductive mapping to the input sequence of data values representing the text in the unknown language to map the data values of the input sequence from the number of possible data values to a smaller number of target values, to a sequence of derived target input values corresponding to the input sequence of deriving data values representing the text in the unknown language; Generating a characterization of the input sequence of data values representing the text in the unknown language based on the sequence of derived target input values; and - identifying the language of the input sequence of data values representing the text in the unknown language based on a comparison of the generated characterization with the generated models ( 133 ).

Computer-implemented ( 100 A method of identifying the language of a text in an unknown distinguishable language, the text being represented by a text string of data values ( 134 ) which represents the text in accordance with an unknown distinguishable string connecting glyph glyphs to specific data values of an area, the method comprising the steps of: - generating a statistical model ( 133 ) according to a method according to one of claims 1 to 3 for each of a plurality of languages and storing the resulting statistical models ( 133 ); Applying a reductive mapping to the text string ( 134 ) of data values representing a text in an unknown, distinguishable language to produce a reductively-transformed, transformed string of data values representing the text string ( 134 ) data values, wherein the data values of the transformed string of data values characterize the text string of data values having an area smaller than the range of data values in the text string ( 134 ), which represents the text in the unknown, distinguishable language; Generating a statistical analysis of the transformed string of data values relating to the statistical occurrence of the particular data values in the transformed string of data values; - recovering the stored statistical model ( 133 ) for each of the several languages; Comparing the statistical analysis of the transformed string of data values with the retrieved statistical model ( 133 ) of each language; and - identifying the distinguishable language as the language among several languages whose statistical model ( 133 ) most likely corresponds to the statistical analysis of the transformed string of data values characterizing the text string of data values.

Method according to claim 5, characterized in that that everybody Data value of the text string corresponds to two bytes.

Method according to claim 5 or 6, characterized that this reductive mapping maps extended characters to a single value.

Method according to one of claims 5 to 7, characterized that this Reductive mapping characters from one byte maps to independently Case only one-byte characters, the different letters of the English Represent alphabets, to distinguish.

Method according to one of claims 5 to 8, characterized that this reductive mapping numeral and punctuation to a single value maps.

Method according to claim 5, characterized in that that this reductive mapping large and lowercase letters to a sequence of 26 values, with one Value for every different letter in the English alphabet.

Method according to claim 5, characterized in that that this reductive mapping mapping uppercase and lowercase letters of the English alphabet on a sequence of 26 different values, mapping extended characters to a single value as well as a mapping of numerals and punctuation to a same one Single value includes.

Method according to claim 5, characterized in that that this reductive mapping maps an 8-bit character to 28 values, where this mapping involves the following steps: - Mapping uppercase and lowercase letters the English alphabet on a sequence of 26 different values; - Depict extended characters to a single value; and - Depict of numerals and punctuation marks to a single value.

Computer readable medium having computer-executable instructions for performing all steps of the computer Method according to one of the preceding claims.