FR2911201A1 - Written text editing method for correcting spelling error, involves calculating difference between apparition frequency of one n-gram in text and in language using n-gram by n-gram technique - Google Patents

Abstract

The method involves establishing text and language distributions of frequencies to which N-grams in a text and a language are appeared, respectively, where n-grams can be groups of characters. The distributions are compared between them. A language (18), whose language distribution has a large similarity with the text distribution, is determined as a language of a written text (15). The text is processed according to the language determination. The difference between the apparition frequency of one n-gram in the text and in the language is calculated using an n-gram by n-gram technique.

Description

Method for editing a text expressed in one language

  TECHNICAL FIELD OF THE INVENTION The subject of the present invention is a method of editing a written document: a text. An essential aim of the method according to the invention is to recognize, automatically and systematically the language of the text, even if this text includes errors related, for example, to typing errors or misrecognitions of characters. a handwritten text.

  The field of the invention is, in general, that of the word processor. In this field, orthographic correction and translation using dictionaries are particularly known. As a treatment, it is also known to recognize handwritten characters or voice recognition that require the use of a database relating to the letters of different alphabets. For word processing software and / or character or voice recognition to be effective, it must include a dictionary module that corrects errors in a reference language. One of the means of the invention is to automatically determine, by a machine, the dictionary that corresponds to a given text. BACKGROUND ART OF THE INVENTION A first dictionary search method includes verifying that all the words of the text are present in the same dictionary. This method, besides imposing a large memory capacity (as many times as there are languages to test), does not solve the problem of misspellings. To search among all the possible dictionaries, which is the most appropriate, in the state of the art, it is also known to use a semantic approach. With such an approach, one counts in the text frequencies of appearance of words. These frequencies of appearance of words are compared with frequencies of appearance of these same words in a set of texts of the language. If the comparison is favorable, it is decided to consider that the text is expressed in that language. A constraint also exists for this second method: it is necessary to have a consequent dictionary, about 40 000 words, for each language. Moreover, in terms of calculations, in embedded environments, this method is too heavy. Another method, disclosed in US / 1006,002,588, is to use occurrence frequencies of groups or sequences of n letters called n-grams, where n is a non-zero positive integer. This method makes it possible to use a much smaller number of data. For example, for an alphabet of 26 letters, we will have: - 263 = 17,576 combinations for trigrams; - 262 = 676 combinations for bigrams.

  According to this document, we obtain a statistical profile representing the probability for each n-gram to belong to a given language. This statistical profile is then processed by multiplying each of its probabilities with each other, so as to calculate an overall probability. The overall probability for several candidate languages is calculated. The highest overall probability is then chosen to determine the candidate language that will be considered as the language of the text. With this state of the art, a problem remains. If the text studied includes a n-gram that does not exist in a candidate language, for example "zz" in the case of a bigram, there is for this n-gram a zero probability of belonging to said language. As a result, the overall probability is zero because it is the result of the multiplication of probabilities specific to each n-gram between them. Such an erroneous n-gram, which can be caused in particular by a typo or a bad character recognition, prevents the recognition of a language. Moreover, not all possible n-grams are necessarily present in the studied text and / or some n-grams are there several times. For those who are there several times, their presence is taken into account several times. The latter method has a lack of flexibility vis-à-vis the errors due in particular to misidentifications of characters or typing errors. The frequencies of appearance of n-grams are already used in the field of language processing, in particular for speech recognition. One such method of voice recognition is to analyze frequencies of appearance of n-grams to choose one word among others.

  This voice recognition method is not used to recognize the language used. In particular, a speech recognition method requires a priori knowledge of the language in which the speaker speaks. There can be no question of looking for it.

  GENERAL DESCRIPTION OF THE INVENTION The object of the invention proposes a solution to the problem just described. In the invention, it is proposed to minimize the overall computation load and to make the analysis of a written text more flexible with regard to errors due in particular to bad character recognition and / or typing errors. For this purpose, in the invention, it is proposed to recognize the writing language of a written text by establishing statistics relating to a frequency distribution of occurrence of groups of letters, or n-grams, in this text, n being a nonzero positive integer, and comparing it with reference statistics relating to n-gram frequency distributions in several languages to determine the nearest one. More precisely, the comparison of the distribution of the text with the respective distributions of the predefined languages is performed by calculating, n-gram per n-gram, a difference between a probability of presence of the n-gram in the language and a statistics of presence of the same n-gram in the text. In one example, the sum of all the absolute values of the differences separating the n-grams is used to define a possible similarity. Other mathematical methods exist to quantify these differences, namely the sum of the squares of said deviations, or the maximum of the absolute values of said deviations or others. Thus, a typo and / or a poor handwritten character recognition, generating at least one erroneous n-gram, are negligible compared to the quantity of n-grams correctly distributed. Moreover, this process represents a smaller workload than in the state of the art. The invention therefore essentially relates to a method of editing a text expressed in a language, comprising steps in which: - one receives, in an apparatus, a sequence of binary information corresponding to characters of an alphabet; - On a device of the device, a text corresponding to the received characters is edited; the text is fragmented into a plurality of groups of n characters called n-grams, n being a non-zero positive integer; - a text distribution of frequencies is established in which the n-grams appear in the text; a frequency-language distribution is established in which the n-grams appear in one language; this last operation is repeated for a certain number of known languages, each known language being characterized by a frequency distribution of appearance of n-grams; comparing said text and language distributions with each other; - the language whose language distribution has a greater similarity to the text distribution is determined as the language of the text and the text is processed according to this determination; characterized in that it comprises the following steps: - one calculates, n-gram per n-gram, the difference between the frequency of appearance of an n-gram in the text and in the language. In addition to the main features which have just been mentioned in the preceding paragraph, the method according to the invention may have one or more additional characteristics among the following: the possible combinations made with the set of letters of the alphabet of the language with one or two space characters placed before or after one (n-1) gram or before and after one (n-2) gram; n-grams are groups of two characters called bigrams; n-grams are groups of three characters called trigrams; the comparison of the distributions comprises a step of adding, for all the n-grams, all the absolute values of the differences separating them; the comparison of the distributions comprises a step of addition, for all the n-grams, of all the squares of the gaps separating them; the comparison of the distributions comprises a step of determining the maximum of all the absolute values of the differences separating them; - differences are only retained if they subscribe to a certain criterion; - the criterion to which the differences must subscribe is to present a value below a threshold; - the criterion to be used for the differences is to present a minimum value; the treatment carried out by the method is a spelling correction; the processing performed by the method is an automatic translation of the received text into a language set by the device. The invention and its various applications will be better understood by reading the following description and examining the figures that accompany it. BRIEF DESCRIPTION OF THE FIGURES These are presented only as an indication and in no way limitative of the invention. The figures show: in FIG. 1, an exemplary implementation of the method according to the invention in a terminal; - In Figure 2, an example of a comparison of a distribution of bigrams of a text with distributions of n-grams of three distinct languages.

  DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS OF THE INVENTION The various elements appearing in several figures will have kept, unless otherwise specified, the same reference. FIG. 1 shows an exemplary implementation of the method according to the invention in a terminal. In a preferred example, the terminal is a multi-function printer 1. Alternatively, the invention can be implemented in a mobile phone. The invention is particularly useful if it is applied to a mobile device. The first use envisaged is that of multi-function printers 1 as part of a scanning with character recognition. Such digitization is performed when the multi-function printer 1 has an optical reader to produce a digital image of a text placed on a reading glass, or scrolling in front of a reading bar, of this optical reader. The digital image is then converted to text by character recognition software. It may be convenient to search automatically for the language of the text. The multi-function printer 1 comprises, connected by a bus 2 of addresses, data and commands: a microprocessor 3, a screen 4, a keyboard 5, a program memory 6, a data memory 7 and an interface 8. The program memory 6 includes, for this purpose, possibly a general program 9, possibly a scanning program 10, possibly a character recognition program 11, according to the invention, a language recognition program 12, possibly a translation program 13 and possibly a spell check program 14. In one example, the program 9 is according to the invention, a handwritten text 20 is received by the multi-function printer 1, for example in the form of a paper document with characters of an alphabet. In one example, the alphabet used is the Latin alphabet that contains 26 letters. The handwritten text 20 is digitized by the scanning program 10 of the multi-function printer 1 as a digital image. The digitized characters are then recognized by the character recognition program 11 and converted to obtain the initial text 15. In a variant, the initial text 15 is received by an interface 8 connected to the bus 2, or even by a reader of the card reader type. memory, also connected to the bus 2 and receiving a removable memory loaded with the text to edit. There are many types of removable memory cards, usually associated each with a proprietary exchange protocol. For example, the removable memory may be a chip carrier having a user's manual of the multi-function printer 1. When the initial text is received by the multi-function printer 1, it can be received in the form a paper document with handwritten characters of an alphabet. The language for writing the text 15 must be recognized by the language recognition program 12, by means of the operating system of the multi-function printer 1. The data memory 7 comprises: an initial text 15, information 16 on the language of the initial text, a dictionary 17, information on a language 18 of the user and a final text 19. The information 16 is the information sought. of the process according to the invention. In all cases, the apparatus 1 receives a sequence of binary information corresponding to characters of an alphabet. Once the handwritten characters and the writing language recognized, or even before recognition of the language, the received text 15 is edited on a device of the device, or even printed on paper. Alternatively, the edition can be voice. In this case, the device is a speaker. However, in the sense of the invention, it is possible not to edit the received text as is or to edit it once treated (redacted spelling mistakes for example). In the literal sense, in the invention, it is furthermore considered that the editing is carried out simply because the text is at least stored in the memory 7, whether it is viewed, printed or broadcast later, or immediately or not. . The edited text of the invention corresponding to the characters received is thus either the initial text 15 or the treated text 19.

  The program 12 for recognizing the writing language of the text 15 comprises the steps in which: the original text is fragmented into a plurality of groups of n characters called n-grams. In a preferred example, n = 2, i.e. bigrams are used. Alternatively, n = 3, i.e. trigrams are used. Bigrams have the advantage of increasing the speed of treatment; - we establish a text distribution of frequencies to which the bigrams appear in the text; a language frequency distribution is established in which the bigrams appear in a language a; the latter operation is repeated for a certain number of known languages R and y, each known language R and y being characterized by a distribution of frequencies of appearance of bigrams; comparing said text and language distributions with each other by calculating n-gram per n-gram, bigram by bigram in the example, the difference between the frequency of appearance of an n-gram in the text and in the language a, R and y and summing all the absolute values of said deviations. Other mathematical methods exist to quantify these deviations, namely the sum of the squares of said deviations or the maximum of the absolute values of said deviations. - language is defined as the language whose language distribution has a greater similarity to the text distribution. This similarity is determined by retaining only those deviations that subscribe to a certain criterion: to present a minimum value. As a variant, the criterion to which the deviations must subscribe may be to present a value below a threshold. The initial text 15 is then processed according to this determination. In one example, it is translated by the translation program 13, by means of an appropriate dictionary 17 to obtain a final text 19 written in the language 18 chosen by a user of the multi-function printer 1; the final text (displayed on screen 4). Many other treatments of written documents can benefit from identification of the writing language. For example: the document can be classified in the data memory 7 differently according to its language; - A spellcheck program 14 can select a suitable dictionary 17 rather than use a general dictionary containing all possible languages. They should therefore gain speed, memory consumption and quality of result. Figure 2 shows an example of comparing a distribution of n-grams of a text with n-grams distributions of three distinct languages a, 13 and y. In this embodiment of the method according to the invention, it is considered that the received text is arbitrarily composed in a language comprising only letters a, b c and d. The alphabet of the language is, however, expanded by a special character _ corresponding to the space present at the beginning and / or end of a word. The method of the invention proposes to fragment the text into a plurality of groups of n characters called n-grams. 30 With bigrams, the letters present in the language offer a set of 24 possible bigrama combinations. But in a text, not all combinations are necessarily present. Here for example, the bigram "aa", "a" and "cc" are not written in the text. A text distribution of frequencies is then established in which the 35 bigrams appear in the text. By text distribution is meant the presence statistics of the bigrams considered in the text to be studied. Quite simply, we count the number of appearances of each of them in the text. This number is divided by the total number of n-grams, bigrams, and text.

  We have established beforehand, on a set of texts known in a language, or even on a dictionary of this language a, a language distribution of frequencies to which the bigrams appear in this language a. This operation is repeated for a certain number of known languages R and y. Each known language R and y is characterized by a distribution of occurrence frequencies of bigrams. These language distributions represent the probability of the presence of n-grams, bigrams, in the language. While the text distribution is calculated by the apparatus 20, the language distributions are stored in advance in the memory 7.

  To simplify the explanation, these text and language distributions a, R and y have been represented graphically. This representation shows the calculated differences between the appearance of a bigram in the language and in the text. These differences are rated as positive or negative. The text and language distributions a, R and y are then compared with each other. In this embodiment of the method according to the invention, the comparison is made by calculating the sum of all the absolute values of the differences separating them. With the values displayed, the result of this sum is 243 for the language a distribution, 451 for the language distribution R and 763 for the language distribution y. The language with the smallest gap is therefore chosen. Other mathematical methods exist to quantify these deviations, namely the sum of the squares of said deviations. In this case, the results are respectively 4080 for the language distribution a, 11033 for the language distribution R and 29345 for the language distribution y.

  Another method is that of the maximum of the absolute values of said deviations. The results are then 27 for language distribution a, 37 for language distribution 13 and 73 for language distribution y. Each of the three methods leads here to the same conclusion: it is the language distribution with which the difference 243, 4080 or 27 is the smallest compared to the text distribution. The difference between the language a distribution and the text distribution, for each bigram, is symbolized by the hatched area in Figure 2, The language has a maximum similarity with the text; it is therefore considered to be that of the text.

  The peculiarities of the method related to the calculation of deviations should be highlighted. For example, typos or misrecognitions of handwritten characters that may have generated here the wrong bigram "ac". Indeed, the latter does not exist in the language a. On the one hand, the difference in value determined for the bigram "ac" between the text distribution and the language distribution a is negligible in the addition operation described above, with regard to the twenty-three other bigrams correctly distributed in the text. On the other hand, it may be possible not to take into account the n-grams that appear in the text when they would not appear in the language. In the latter case, in the comparison, the differences are retained only if they subscribe to a criterion. The criterion here is that of the presence of the n-gram in the language. Another criterion is to neglect deviations below a threshold. For example, if we neglect the differences less than 10, the first method gives a result of 195 (instead of 243) for the language a, while the result is almost unchanged for languages 13 and y. The use of a criterion thus makes it possible to speed up the calculation and to be more selective. Once the language of the text thus determined, the text can be processed. In the latter case, it can either be edited as is, be corrected, or still be translated. For example, if a text is received in a language a and if a user of the device, here of the mobile terminal, has chosen a language 13 in zone 18 in the data memory 7, it is possible to translate the text of the language a to language R.

Claims (11)

  1 - Editing method (12) of a text (15) expressed in a language, comprising steps in which: - an apparatus (1) receives a sequence of binary information corresponding to characters of an alphabet; - On a device (4) of the device, a text corresponding to the received characters is edited; the text is fragmented into a plurality of groups of n characters called n-grams, n being a non-zero positive integer; - a text distribution of frequencies is established in which the n-grams appear in the text; a language frequency distribution is established in which the n-grams appear in a language (a; R; Y); this last operation is repeated for a certain number of known languages, each known language being characterized by a frequency distribution of appearance of n-grams; comparing said text and language distributions with each other; the language whose language distribution has a greater similarity with the text distribution is determined as the language of the text and the text is processed according to this determination, characterized in that it comprises the following steps: -gram per n-gram, the difference between the frequency of appearance of an n-gram in the text and in the language.   2 - Process according to claim 1, characterized in that widens the possible combinations made with all the letters of the alphabet of the language with one or two characters of space L) placed before or after a n-lgramme or before and after an n-2gram.   3 - Process according to at least one of claims 1 to 2, characterized in that the n-grams are groups of two characters called bigrams.   4 - Process according to at least one of claims 1 to 2, characterized in that the n-grams are groups of three characters called trigrams. 35   5 - Process according to at least one of claims 1 to 4, characterized in that the comparison of the distributions comprises a step of adding, for all the n-grams, all the absolute values of the differences separating them.   6 - Process according to one of claims 1 to 4, characterized in that the comparison of the distributions comprises a step of adding, for all n-grams, all squares deviations separating them.   7 - Method according to one of claims 1 to 4, characterized in that the comparison of the distributions comprises a step of determining the maximum of all the absolute values of the differences separating them.   8 - Method according to one of claims 1 to 7, characterized in that one holds the differences only if they subscribe to a certain criterion.   9 - Process according to one of claims 1 to 8, characterized in that the criterion to which subscribe deviations is to present a value less than a threshold. 9 - Process according to at least one of claims 1 to 8, characterized in that the criterion to which subscribe deviations is to present a minimum value.   10 - Process according to at least one of claims 1 to 9, characterized in that the processing carried out by the method is a spelling correction (14).   11 - Process according to at least one of claims 1 to 9, characterized in that the processing carried out by the method is an automatic translation (13) of the received text, in a language (18) set by the device.