Arabic spell checking technique

• US 9,037,967 B1
• Filed: 02/18/2014
• Issued: 05/19/2015
• Est. Priority Date: 02/18/2014
• Status: Expired due to Fees

• Current Assignee: King Fahd University of Petroleum & Minerals (Government of Saudi Arabia)
• Original Assignee: King Fahd University of Petroleum & Minerals (Government of Saudi Arabia)
• Inventors: Mohammed, Sabri Abdullah, Al-Jefri, Majed Mohammed
• Primary Examiner(s): Huynh, Cong-Lac
• Application Number:
  US14/182,946
• Time in Patent Office: 455 Days
• Field of Search: 715/257
• US Class Current: 715/257
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

An Arabic spelling error detection and correction method for identifying real word spelling errors. The method uses a corpus of Arabic text alongside n-gram statistical techniques to detect erroneous words within the text. After identifying the erroneous word the method uses a dictionary formed from the corpus of Arabic text to retrieve candidate correction word to replace the erroneous word with. Using n-gram statistical models candidate correction words are generated and ranked in order of highest probable correction for the word. The generated and ranked correction words are assessed and the best correction word is selected. A final assessment of the correction is conducted and if the result is positive then erroneous word is replaced with the highest statistical correction.

Claims

1. An Arabic language spelling error detection and correction method, comprising:

comparing digitized text with a corpus database of Arabic words and sentences to identify text errors and grammatical errors in the digitized text;

identifying a plurality of candidate correction options from a dictionary of text for at least one of the text errors and the grammatical errors identified in the comparing, wherein the candidate correction options are detected with a plurality of n-gram statistic model sequences,

ranking the candidate correction options in order of highest probability of most correct alternative using the n-gram statistical model sequences,

selecting a highest probability correction word according to the context of the text,

conducting a final end of file evaluation by comparing the highest probability correction word with the corresponding text error or grammatical error to assess the accuracy of the highest probability correction word; and

initiating a word correction by substituting the text error or the grammatical error with the highest probability correction word when the accuracy of the selected word is positive.

2. The Arabic language spelling error detection and correction method in claim 1, comprising:

during the comparing, extracting words from the corpus database of Arabic words, counting the extracted words and arranging the extracted words in order of occurrence.

3. The Arabic language spelling error detection and correction method in claim 1, comprising:

forming a plurality of word dictionaries and arranging the word dictionaries in descending order based on the number of times each word occurs.

4. The Arabic language spelling error detection and correction method in claim 1, comprising:

generating a plurality of n-gram language models comprising of uni-grams, bi-grams and tri-grams.

5. The Arabic language spelling error detection and correction method in claim 1, comprising:

forming a plurality of supervised learning models incorporating one or more confusion sets, and detecting real-word Arabic spelling errors with the supervised learning models.

6. The Arabic language spelling error detection and correction method in claim 5, wherein the confusion sets are generated by collecting two types of words:

words that are recognized as correctly spelled words by an Arabic optical character recognition (OCR) system but are not the same words in the original text; and

words that have similar pronunciations.

7. The Arabic language spelling error detection and correction method in claim 6, wherein the similar pronunciation words are collected by collecting and classifying words into groups according to frequent words confused by non-native Arabic speakers.

8. The Arabic language spelling error detection and correction method in claim 1, comprising:

storing a database of commonly misspelled words and arranging the commonly misspelled words in groups according to at least one of the similarity of the sounds of the letters of the words and closeness of meaning of the words.

9. The Arabic language spelling error detection and correction method in claim 1, further comprising:

comparing a database of closely spelled words with similar sounding letters that have alternative meanings with the n-gram model to detect spelling errors.

10. The Arabic language spelling error detection and correction method in claim 1, wherein the comparing further comprises utilizing context-sensitive comparing techniques that employ syntactic and semantic knowledge of the Arabic language.

11. The Arabic language spelling error detection and correction method in claim 10, wherein identifying text errors further comprising:

for each tri-gram in a sentence under consideration

if the tri-gram {w<sub>i−

2</sub>, w<sub>i−

1</sub>, w_i} is not found, then the comparing matching is attempted using bi-grams, such that;

if both bi-grams {w<sub>i−

1</sub>, w_i}, {w_i, w_i+1} are not found, then the word w_i is flagged and categorized as a suspicious word W_s, wherein a suspicious word is any word suspected of being out of context or containing grammatical, contextual, syntactic or semantic errors.

12. The Arabic language spelling error detection and correction method in claim 11, wherein for each suspicious word W_s the method further comprising:

finding all of the W_s'"'"'s spelling variations, such that;

for each variation W_v the method further comprises;

replacing W_s with W_v

calculating the new sentence probability; and

flagging the original word as an error if the formed sentence

probability is greater than the original sentence probability.

13. The Arabic language spelling error detection and correction method of claim 1, the comparing matching further comprising:

receiving text with detected errors;

for each detected error word W_e the method further comprising;

finding all spelling variations W_v of detected error word W_e, such that for each spelling variation W_v, the method further comprises;

replacing the detected error word W_e with spelling variation W_v; and

calculating a new sentence probability for each sentence and associated spelling variation W_v within each sentence.

14. The Arabic language spelling error detection and correction method of claim 1, further comprising:

saving the sentence and spelling variation W_v with a maximum sentence probability;

flagging the sentence and associated spelling variation W_v with the maximum sentence probability as the correct alternative to the erroneous word if the maximum sentence probability of the sentence and associated spelling variation W_v is greater than the sentence probability of the sentence and error word W_e; and

outputting the correct alternative.

15. An apparatus for detecting and correcting spelling errors, the apparatus comprising:

circuitry configured

to generate a word co-occurrence model for a given set of words to be analyzed;

to generate an n-gram language model for the given set of words; and

to check an output made by the word co-occurrence model and an output made by the n-gram language model and to compare the two outputs of two models, wherein if the two outputs of the two models are determined to be the same, then this output is considered the output of the combined method of the word co-occurrence model and the n-gram language model and a correct word is output.

16. The apparatus of claim 15, wherein to generate a word co-occurrence model, the circuitry is further configured to:

tag at least one confusion set that is most probable to a context of the given set of words;

identify at least one word from a confusion set that is semantically unrelated to the word'"'"'s context; and

identify which variation of the at least one word is related to the context of the given set of words.

17. The apparatus of claim 16, wherein to generate a word co-occurrence model, the circuitry is further configured to:

identify a ±

k words window in a training corpus;

estimate the probabilities of context words surrounding the at least one word using a maximum likelihood estimate (MLE); and

select at least one word associated with the context words with the highest estimated probability.

18. The apparatus of claim 15, wherein if the two models are not in agreement, the model with a highest difference in probability is selected, wherein the difference in probability is calculated as: