KR100509917B1 - Apparatus and method for checking word by using word n-gram model - Google Patents

Abstract

The present invention relates to a spacing and spelling correction device and method using a word n-gram, word n-gram DB for storing the word n-gram; A word n-gram construction unit for extracting a word n-gram by receiving refined and error-free language data and storing the extracted word n-gram in a word n-gram DB; Receives the target language data to be verified and changes each word included in the language data into a structure that is mapped to one symbol, and the word n that searches for the same word by searching the word n-gram DB for the changed word. -gram search and verification unit; Spacing and Pasting Errors / Typographical Corrections for Correcting Spacing and Pasting Errors and Typos for Words Not Validated by the Word n-gram Search and Verification Unit; A statistic-based part-of-speech tagging system that selects and applies the highest probability value by performing morphological tagging on a word modified by a spacing and pasting error / typing correction unit; It is provided with a correction sentence output unit for outputting the corrected target language data while being processed by the spacing and pasting error / typo correction and statistics-based part-of-speech tagging system for the target language data. Therefore, the spacing and spelling errors with respect to the input target language data can be automatically corrected.

Description

Spacing and spelling correction apparatus and method using word engrams {APPARATUS AND METHOD FOR CHECKING WORD BY USING WORD N-GRAM MODEL}

The present invention relates to a spacing and spelling correction device and method using a word n-gram, in particular, to construct and verify a word n-gram language model using a large amount of refined corpus (corpus) The present invention relates to an apparatus and method for extracting an unverified word list by applying a word n-gram language model to a corpus, and recognizing and correcting a spacing error and a spelling error.

Typically, a number of methods have been studied for language models, but the most studied are statistical language models, which use chain probability of words such as Unigram, Bigram, Trigram, and the like. However, such a statistical language model does not automatically correct a word or sentence spacing error and a spelling error of an input sentence, and also cannot correct a typo and correct a spacing error of a syllable pair.

On the other hand, other conventional techniques disclosed in relation to the language model include "Method for Recognizing and Correcting Hangul Documents Using Syllable Viograms" published on January 5, 2001, 2001-0000673, and September 15, 1998. -047272, "Automatic Spacing Correction Method Using Mutual Information in a Text Editor", and the like.

As described above, the disclosed prior art will be described in detail, "a method for recognizing and correcting an error in a Hangul document using syllable viagram characteristics", unlike a conventional statistical language model, extracts a pair of bigram syllables and a frequency from a corpus, Recognition of spacing errors in Hangul documents by using a feature. According to the prior art, spelling correction is possible, but it differs from the verification method using the actual word n-gram in the present invention in that it is verified using morpheme tagger. There is this.

Next, "Automatic spacing correction method using mutual information in the text editor" is an automatic correction of the input text to match the spacing and procedure automatically by performing the function of automatic spacing and spell check using mutual information in the text editor. It relates to a spacing correction method, the prior art is only for spacing and is not suitable for spell correction is different from the spacing and spelling correction method proposed in the present invention.

Therefore, the above-described prior patents cannot automatically correct a spacing error and a misspelling of an input sentence by word or sentence unit, and also cannot correct a typo and correct a spacing error of a syllable pair. Still remains.

Accordingly, the present invention has been made to solve the above-described problems, the object of the present invention is to construct a word n-gram language model using a large amount of refined corpus, the word n-gram language model for the corpus to be verified The word list is extracted from the unvalidated word list, and the word list is used to correct errors by applying grammar rules, morpheme analysis, proper noun estimation, and foreign language estimation. A spelling correction device and method are provided.

According to an embodiment of the present invention for achieving the above object, a spacing and spelling correction apparatus using a word en-gram includes a word n-gram DB for storing a word n-gram; A word n-gram construction unit for extracting a word n-gram by receiving refined and error-free language data and storing the extracted word n-gram in a word n-gram DB; Receives the target language data to be verified and changes each word included in the language data into a structure that is mapped to one symbol, and the word n that searches for the same word by searching the word n-gram DB for the changed word. -gram search and verification unit; Spacing and Pasting Errors / Typographical Corrections for Correcting Spacing and Pasting Errors and Typos for Words Not Validated by the Word n-gram Search and Verification Unit; A statistic-based part-of-speech tagging system that selects and applies the highest probability value by performing morphological tagging on a word modified by a spacing and pasting error / typing correction unit; It includes a correction sentence output unit for outputting the target language data has been corrected while the process is processed by the spacing and pasting errors / typo correction and statistics-based part-of-speech tagging system for the target language material.

Then, the spacing and spelling correction method using the word en-gram according to another embodiment of the present invention for achieving the above-described object is refined to receive the language data without error error word n-gram to extract the word n-gram Storing in a DB; Receiving a target language material to be verified, and changing each word included in the language material into a structure in which a single symbol is mapped, and searching for a word word by searching a word n-gram DB for the changed word; If the same word does not exist in the search step, the spacing and pasting error is applied to the result of correcting the spacing and pasting error and the typographical error. Modification step; And outputting the corrected target language data for the target language data to be verified.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a block diagram of a word spacing and spelling correction apparatus using a word n-gram according to the present invention, a word n-gram construction unit 10 and a word n-gram search and verification unit ( 20), a spacing and pasting error / typing correction unit 30, a statistics-based part-of-speech tagging system 40, and a modified sentence output unit 50.

The word n-gram constructing unit 10 has a word n-gram extractor 11 internally, and the provided word n-gram extractor 11 is provided from a purified text language material (corpus) DB (S1). The word-word n-gram is extracted by inputting refined and error-free text language data, and the extracted word-n-gram is provided to the word-n-gram DB (S2).

Here, the word n-gram DB (S2) is stored so that it can be processed by mapping a number, an English letter, a symbol, and other foreign words into a single symbol representing each word. Do not include in gram.

In other words, when the word n-gram stored in the word n-gram DB (S2) is explained in more detail, when the word "ABCDE" exists, the 1-gram is composed of A, B, C, D, and E, respectively. 2-gram is composed of AB, BC, CD, DE, and 3-gram is composed of ABC, BCD, and CDE. In this way, the word n-gram is configured by replacing letters, numbers, symbols, other foreign words, and the like with one symbol so as to increase the hit ratio in the word n-gram searcher 23.

The word n-gram retrieval and verification unit 20 includes a token separator 21, a word n-gram searcher 23, and a morpheme tagger 41, of which the token separator 21 is provided. Receives the target language data to be verified from the text corpus DB (S6) and separates them into English letters, numbers, symbols, Korean characters, and Chinese characters. The structure is changed to a structure in which a symbol is mapped to a symbol representing the symbol and provided to the word n-gram searcher 23.

The word n-gram searcher 23 searches the word n-gram DB S2 for the word output from the token separator 21 to find out whether the same word exists.

Here, the search order by the word n-gram searcher 23 is 3-gram → 2-gram → 1-gram. However, it is preferable not to search up to 1-gram because a word having a small number of syllables, that is, a word of one syllable has a lot of ambiguity.

The spacing and pasting error / error correction unit 30 includes a modifier 31 based on a rule for spacing and pasting, a modifier 32 based on a word n-gram, a proper noun estimator 33, A foreign language estimator 34, a corrector 35 based on a tagger, a corrector 36 based on a rule for correcting a typo, and a corrector 37 based on an algorithm are provided.

The modifier 31 according to the rule modifies the spacing and pasting of the sentence according to the definition rule stored in the spacing paste rule DB (S7) to reflect the spacing and paste rule defined and stored according to the spelling established by the Ministry of Education. . For example, "about" is a suffix that must be unconditionally pasted in the first word, or "unless" is unconditionally skipped and is stored in the spaced pasting rules DB (S7).

The modifier 32 by the word n-gram, if there are unverified words among the target languages to be verified provided in the token separator 21 to the word n-gram finder 23, then the back and forth for the unvalidated words. Various lists can be created by pasting or cutting words together, and checking whether the created list exists in the word n-gram DB (S2) so that multiple candidate lists can appear. Here, the criterion for selecting one of the candidate lists is the frequency of use of the words stored in the word n-gram DB (S2). If the frequency is the same, the sentence is composed of sentences including several words before and after the sentence. And morphological tagging to select the one with the highest probability.

The proper noun estimator 33 is a user input dictionary and a name / name / mutual dictionary for word lists that have not yet been verified even after the corrector 31 according to the rule and the corrector 32 based on the word n-gram. Use DB (S8) to determine whether the word is included in the word, and correct it, or if "C", "kun", "sheep", or "doctor" appears in the word before or after, correct it to be a proper noun. .

The foreign language estimator 34 is a foreign language dictionary DB for word lists that have not yet been validated even though the corrector 31 according to the rule and the corrector 32 based on the word n-gram and the proper noun estimator 33 are used. A function of extracting the foreign word is performed by using S9. The foreign word may be detected using a Hidden Markov Model (HMM).

Tagger modifier 35 is still validated while passing through modifier 31 by rule and modifier 32 by word n-gram, proper noun estimator 33 and foreign language estimator 34. After dividing each word list by syllable, it is combined with several words and provided to the morph tagger 41 to perform morphological tagging to select a word combination having the highest probability.

The modifier 36 by the rule corrects using a typo correcting rule stored in the typo correcting rule DB S10. In addition, the typo is corrected using the corrector 37 based on an algorithm for correcting the typo.

That is, the modifier 37 based on the algorithm includes a modifier 31 based on a rule and a modifier 32 based on a word n-gram, a proper noun estimator 33, a foreign language estimator 34, and a tagger. If a problem word is generated while passing through the modifier 35, the word list is to be modified by using only 1-gram in the word n-gram DB (S2).

When the modifier 37 by the algorithm describes the word list in more detail, that is, several phonemes in the first part of the algorithm or several phonemes in the latter part produce the same word list. In this case, a word having the same number of syllables is selected first. If the number of syllables is not the same, a word is selected by selecting the word closest to the number of syllables.

Here, the reason for calculating using syllables is that the main error of a typo is made by adding a phoneme, and the main error at the time of keyboard input appears due to wrong input of a key nearby. In this case, a plurality of words with the closest number of syllables may exist.

Next, as a process for narrowing the list generated by the above-described procedure, the one with the closest number of phonemes is selected for a word having the same syllable number or a near syllable number. Here, a word having a lot of the same phoneme comes first, and a plurality of lists may exist even through such a process.

When there are a plurality of lists, the word n-gram searcher 23 selects the best value in the word 3-gram or 2-gram by concatenating words before and after.

Lastly, if the word is not in 3-gram or 2-gram, or if the frequency is the same, then the front and back 2 to 3 words are connected to the morpheme tagger 41 and the morpheme tagging is used to select the one with the highest probability. .

The statistics-based part-of-speech tagging system 40 has an internal morpheme tagger 41, and the provided morpheme tagger 41 includes a part-of-speech accessible information DB (S3), a morpheme dictionary DB (S4), and a part-of-speech 3. A block that performs morphological tagging on a sentence input using a gram DB (S5), and includes a corrector 32 by a word n-gram in a spacing and pasting error / correction correction unit 30, and a tagger. Morphological tagging is performed on the result of the corrector 35, the corrector 36 based on the rule, and the corrector 37 based on the algorithm, and selects the value having the highest probability. Here, the statistics-based part-of-speech tagging system 40 analyzes the raw or tagged corpus including natural language usages and subsidiary information of the real world, and uses the probability obtained by extracting statistical information about natural language to probability the importance of natural language processing. It is a system to solve the problem.

The correction sentence output unit 50 outputs a sentence that has been corrected by the spacing and pasting error / error correction unit 30 with respect to the target language data in the target language data DB S6.

Referring to the flowchart of FIG. 2, the spacing and spelling correction method using the word n-gram according to the present invention will be described in more detail based on the above-described configuration.

First, the word n-gram extractor 11 in the word n-gram construction unit 10 receives the word language data that is refined from the purified text language data (corpus) DB (S1) without error and receives the word n-gram. The extracted word n-gram is stored in the word n-gram DB (S2) (step 201).

In this state, the token separator 21 in the word n-gram retrieval and verification unit 20 receives the target language data to be verified from the target language data (Text corpus) DB (S6). , Chinese characters, etc. are changed into a structure in which each of them is mapped to one symbol representing each of them, and provided to the word n-gram searcher 23 (step 203).

The word n-gram finder 23 searches the word n-gram DB (S2) for the word output from the token separator 21, and the search order is 3-gram → 2-gram → 1-gram. Proceed to search if the same word exists (step 204).

If the same word exists in the search step 204, since the target language data is a refined language data, the target language data input to the target language data DB S6 is provided to the corrected sentence output unit 50 and outputted. Step 205).

If there is an unequal word in the search step 204, the unequal target language material is applied to the spacing and pasting error / error corrector 30 (step 206).

Spacing and pasting error / corrector 31 according to the rules in the typo corrector (30) is not the same according to the definition rules stored in the space spacing paste rule DB (S7) defined and stored according to the spelling established by the Ministry of Education. Modify your language resources. For example, the criteria "about" must be pasted unconditionally in the first word or "unconditionally skipped before" is structured and stored in the spacing paste rule DB (S7) (step 207).

Subsequently, when the correction is not completed even by the corrector 31 according to the rule, the correction operation proceeds by the corrector 32 by the word n-gram. That is, the modifier 32 by the word n-gram makes various lists by pasting or cutting the unverified words together with the front and back words, and confirms whether the created list exists in the word n-gram DB (S2). To generate several candidate lists (step 208).

Here, the criterion for selecting one among a plurality of candidate lists is a frequency (eg, the most frequently appeared word) stored in the word n-gram DB (S2). If the frequency is the same, a sentence including a few words before and after A configuration is provided to the morpheme tagger 41 to perform morpheme tagging to select the highest probability value (step 209).

Subsequently, the proper noun estimator 33 is applied to the lists that have not yet been verified even through the modifier 31 based on the rule and the modifier 32 based on the word n-gram. That is, the proper noun estimator 33 determines and corrects whether the corresponding word is included here using the user input dictionary and the person / name / territory dictionary DB (S8). For example, if "C", "group", "sheep", "doctor", etc. appear in the front and back words, it is determined that the proper noun is corrected (step 210).

Next, the foreign language estimator 34 provides the corrector 31 according to the rule, the corrector 32 based on the word n-gram, and the word lists that have not yet been verified even through the proper noun estimator 33. Correction is performed. That is, the foreign language estimator 34 extracts the foreign word using the foreign language dictionary DB S9, and the foreign word is detected by the HMM model (step 211).

Subsequently, the word list that has not been verified yet is passed through the corrector 31 based on the rule and the corrector 32 based on the word n-gram, the proper noun estimator 33, and the foreign word estimator 34. Modification is performed by the modifier 35 by tagger (step 212). That is, the modifier 35 by tagger divides the word by syllable, and then combines the word into syllables to provide the stemmer tagger 41 with morpheme tagging to select the word combination having the highest probability value (step 213). .

Next, regarding the correction of a typo, the modifier 36 according to the rule corrects a typo correction rule stored in the typo correction rule DB (S10) for word lists that have not been verified by the spacing and pasting error correction. Correct it using In addition, the typo is corrected using the corrector 37 by the algorithm for correcting the typo (step 214).

That is, the modifier 37 based on the algorithm includes a modifier 31 based on a rule and a modifier 32 based on a word n-gram, a proper noun estimator 33, a foreign language estimator 34, and a tagger. When the unverified word lists are generated through the modifier 35, the word lists are made by using only 1-gram in the word n-gram DB (S2) ( Step 215).

When the modifier 37 according to the algorithm generates a word list, that is, a word list is created in the first part of the phoneme, or several phonemes in the latter part are created. In this case, a word having the same number of syllables is selected first. If the number of syllables is not the same, a word is selected by selecting the word closest to the number of syllables.

Here, the reason for calculating using syllables is that the main error of a typo is made by adding a phoneme, and the main error at the time of keyboard input appears due to wrong input of a key nearby. In this case, a plurality of words with the closest number of syllables may exist.

Next, as a process for narrowing the list generated by the above-described procedure, the closest number of phonemes is selected for a word having the same syllable number or a near syllable number. Here, a word having a lot of the same phoneme comes first, and a plurality of lists may exist even through this process (step 216).

When there are a plurality of lists, the word n-gram searcher 23 selects the best value in the word 3-gram or 2-gram by concatenating words before and after (step 217).

Lastly, if the word is not in 3-gram or 2-gram, or if the frequency is the same, the front and rear 2 ~ 3 words are connected and provided to the stemmer tagger 41 to perform stemming tagging to select the one with the highest probability. (Step 218).

The target language data that has been corrected by the spacing and pasting error / error correction unit 30 for the target language data in the target language data DB S6 is output through the modified sentence output unit 50 (step 219).

On the other hand, the spacing and pasting error / corrector 31 according to the rules for spacing pasting provided in the correction unit 30, the word n-gram corrector 32, the proper noun estimator 33 and Alternatively, the foreign language estimator 34, the corrector 35 by tagger, the corrector 36 by rule for correcting a typo, and the corrector 37 by algorithm may be performed in numerical order. It is not greatly affected by.

The present invention described above constructs a word n-gram language model using a large amount of refined corpus, extracts and extracts an unverified word list while applying a word n-gram language model to a corpus to be verified. By correcting the error by using grammar rules, morpheme analysis, proper noun estimation, and foreign language estimation, the corrected spacing and spelling errors can be corrected automatically. In addition, it can be applied to a text editor to implement the automatic spacing function of sentence units, and it is also possible to correct typos, and to recognize and correct the spacing or spelling errors of syllable pairs recognized through a text recognizer or a speech recognizer It can be effective.

1 is a block diagram of a spacing and spelling correction device using a word en-gram according to the present invention,

Figure 2 is a detailed flowchart of the spacing and spelling correction method using a word en-gram according to the present invention.

<Description of the symbols for the main parts of the drawings>

10: word n-gram construction unit 11: word n-gram extractor

20: n-gram search and verification unit

21: token separator 23: word n-gram finder

30: Spacing and Paste Errors / Typographical Corrections

31,36: Modifier by rule 32: Word n-gram corrector

33: proper noun estimator 34: foreign language estimator

35: Modifier by Tagger 37: Modifier by Algorithm

40: Statistics based part-of-speech tagging system 41: Morphological tagger

50: correction sentence output unit

Claims (11)

In the spacing and spell correction device using the word n-gram, A word n-gram DB for storing a word n-gram; A word n-gram construction unit for extracting a word n-gram by receiving a refined and error-free language data and storing the extracted word n-gram in the word n-gram DB; Receives the target language data to be verified and changes each word included in the language material into a structure that is mapped to one symbol, and searches for the same word by searching the word n-gram DB for the changed word. A word n-gram search and verification unit to perform; A spacing and pasting error / typing correction unit for correcting spacing and pasting errors and typos for words that have not been verified by the word n-gram search and verification unit; A statistic-based part-of-speech tagging system that selects and applies the highest probability value by performing morphological tagging on a word modified by the spacing and pasting error / typing correction unit; A correction sentence output unit for outputting the corrected target language data while being processed by the spacing and pasting error / error correction and the statistics-based part-of-speech tagging system with respect to the target language data; Spacing and spelling correction device using a word en-gram, characterized in that it comprises a. According to claim 1, wherein the word n-gram search and verification unit using a word en-gram characterized in that it further comprises a corrector by a rule for correcting according to the word spacing paste definition rule not verified Spacing and spelling correction. According to claim 1, For the word that is not verified by the word n-gram search and verification unit, the word is attached with the front and back words, or the word is cut to create a plurality of word list, the plurality of word list The word spacing and spelling correction device using a word en-gram, characterized in that it further comprises a modifier by word n-gram to determine whether the words included in the word n-gram DB to generate a candidate word list. The method of claim 2 or 3, wherein each word is divided into syllables for words included in word lists that have not been verified yet through a modifier according to the rule and a modifier according to a word n-gram. In addition, the word-based part-of-speech tagging system combines multiple words to form a morphological tagging and selects a word combination having the highest probability by selecting a word combination. Calibration device. According to claim 1, The first few phonemes are the same by using only 1-gram in the word n-gram DB for the words included in the word list that is not verified by the spacing and pasting error correction, Creates a list containing the same phrases with several phonemes in the latter part. If the number of syllables is the same in the list, and if the number of syllables is not the same, the algorithm that creates the word list by selecting the word closest to the number of syllables Spacing and spell correction device using a word en-gram, characterized in that it further comprises a corrector. In the spacing and spelling correction method using the word engram, Receiving language data without refined error, extracting a word n-gram, and storing the word n-gram in a word n-gram DB; Receives the target language data to be verified and changes each word included in the language material into a structure that is mapped to one symbol, and searches for the same word by searching the word n-gram DB for the changed word. Making; In the search step, if the same word does not exist, morphological tagging is performed on the result of correcting the spacing and pasting errors and typos with respect to the same word, and selecting and applying the highest value with the highest probability. Write error correction step; Outputting the corrected target language material with respect to the target language material to be verified; Spacing and spelling correction method using a word en-gram, characterized in that it comprises a. 7. The method of claim 6, further comprising outputting the input target language data when the same word is present in the search step. [8] The word engram of claim 6, further comprising a typo correcting step of correcting a typo using a typo correcting rule for word lists that are not verified by the spacing and pasting error correcting step. Spacing and spelling correction method using. The method of claim 8, wherein the step of correcting a typo when the unverified word lists are generated, by using only 1-gram in the word n-gram DB to modify the generated word list, Creates a list containing the same phrases after several phonemes in the latter part. If the number of syllables is the same in the created list, the phoneme is given priority. Spacing and spelling correction method using a word en-gram, characterized in that. 10. The word spacing and spelling correction method of claim 9, wherein a list of closest numbers of phonemes is selected for a word having the same syllable number or a near syllable number among the created list. The word n-gram searcher selects the best value from the word 3-gram or 2-gram by concatenating words before and after the plurality of selected lists. If the word does not exist in the -gram or the frequency is the same, the spacing and spelling correction method using the word en-gram, characterized in that the morphological tagging by connecting the front and back two or three words to select the one with the highest probability value.