Automatic Spell Checker and Correction for Under-represented Spoken Languages: Case Study on Wolof

The goal of the punctuation removal in our preprocessing step is to eliminate any non-essential punctuation marks present in the input text. These marks can hinder the efficiency of the spell checking process and may cause confusion during the analysis of the text (Rahimi and Homayounpour, 2022). By removing these marks, we ensure that the subsequent stages of the spell checking system can process the text more effectively and efficiently. The algorithm employed in this stage scans the input text and removes all instances of punctuation marks, including commas, periods, exclamation marks, and question marks. The output of this step is a cleaned text that is free of the extraneous elements and ready for focused analysis in subsequent stages of the system.

The normalization phase in our preprocessing step transforms the input text into a standardized form by converting all alphabetic characters to lowercase and removing any words outside of the Wolof language.
The conversion to lowercase is essential as many NLP techniques treat words in different cases as separate entities, and converting the text to lowercase eliminates this case sensitivity impact on the analysis (HaCohen-Kerner et al., 2020).
By removing words from foreign languages, we aim to ensure that the text being analyzed is only in the target language and minimize the effect of words that may not hold semantic significance in the context of the Wolof language. This enhances the accuracy of the analysis and reduces the likelihood of introducing errors into the results.

Tokenization is a critical step in the automatic spell checking process, as it segments the input text into smaller units referred to as tokens.
There is a range of techniques used for tokenization that vary depending on the language and task at hand. These may include splitting on whitespace and punctuation, using regular expressions, or utilizing dictionaries and morphological rules (Dalrymple et al., 2006).
The tokenization process results in units that can range from individual characters or words to phrases or even full sentences. However, word tokenization is the most commonly used form of segmentation in spell checking systems, as it separates the text into individual words and provides a solid foundation for the identification of spelling errors (Mosavi Miangah, 2013; Rahman et al., 2021; Abdulrahman and Hassani, 2022).
Word tokenization not only enhances the accuracy and efficiency of the spell checking process but also allows for an analysis of the context in which each word appears. This enables the spell checking system to make more informed suggestions for appropriate spelling corrections, ultimately improving the accuracy of the results.
In the current investigation, we are implementing the process of tokenization with a focus on word-level segmentation.

The spelling of words in the Wolof language follows certain conventions, as described by the CVC and CVCV(C) forms for monosyllabic and disyllabic words, respectively (Merrill, 2021). These conventions specify that the final consonant and vowel of a syllable cannot both be long, and strong consonants cannot appear after a long vowel or at the beginning of a word, except for prenasalized consonants.
Our error detection stage includes a validation step that rigorously checks each word in the input text against these writing conventions. If a word is found to be in compliance with these rules, it will move on to the next stage of validation. Conversely, if the word is determined to be non-compliant, it will be flagged as invalid and require correction.

In the lexicon verification phase, the spell checking system assesses each word in the input text against the Wolof lexicon to determine its validity. The lexicon, being a large repository of words, can pose challenges for quick and efficient searches. To address this, various techniques such as hash tables (Kukich, 1992), binary search (Knuth, 1998), tries data structure (Bentley and Sedgewick, 1997), and bloom filter (Bloom, 1970) have been developed to enable fast dictionary lookups.
In the present spell checker, the system uses the trie data structure, which organizes the lexicon into nodes that represent individual characters and the root node that represents the empty string. In this structure, searching for a word in the lexicon involves following the path through the trie that corresponds to the characters of the target word (Feng et al., 2012). If the end of the path is a terminal node, the word is considered to be in the lexicon and deemed valid. Conversely, if the path ends before reaching a terminal node, the word is considered incorrect and corrections are initiated.

Prior to implementing the module responsible for translating French compound sounds into Wolof, we collected a small amount of Wolof data from various sources. This data was sourced from news websites\sepfootnotewolnews, social media platforms\sepfootnotewoltwi and religious websites\sepfootnotewolrel. A thorough analysis of this data was carried out to determine the most common misspellings made by Wolof speakers when writing in the language. Our findings indicated that a significant number of these errors were due to the usage of the French alphabet instead of the Wolof alphabet. This often resulted in the presence of French compound sounds or letters that are not native to the Wolof language. Furthermore, it was observed that accents, which play a crucial role in ensuring proper pronunciation and meaning of words, were frequently neglected. To showcase these findings, Table 3 presents some of the misspellings observed and their correct Wolof equivalent.

Taking into consideration the common errors observed in the analysis of Wolof language data, our system is designed to assess each word for the presence of French compound sounds or letters that are extraneous to the Wolof alphabet. Should such sounds be detected, the module will translate them into their corresponding Wolof counterparts. Letters not belonging to the Wolof alphabet will be systematically eliminated. Upon completing these transformations, the output will be directed to the next phase of the correction process and candidate suggestions module.

In the current system, to generate potential alternatives for misspelled words, we have implemented a lexicographical distance comparison method. This process involves determining the minimum number of edit operations, such as insertion, deletion, transposition, and substitution, necessary to change one word into another (Vienney, 2004). The more significant the disparities between two words, the greater the lexicographical distance between them. Out of various lexicographical distance metrics, the Levenshtein Distance (Levenshtein, 1965) is the most commonly utilized. It quantifies the difference between two strings based on the three fundamental string operations: substitution, insertion, and deletion.
Let $Lev_{\alpha,\beta}$ be the Levenshtein distance between the subsequence formed with the $\alpha$ first characters of a word $W_{1}$ and the subsequence formed with the $\beta$ first characters of a word $W_{2}$. The Levenshtein distance between the two subsequences $W_{1}$ and $W_{2}$ (of length $|W_{1}|$ and $|W_{2}|$ respectively) can be recursively calculated using Formula 1 (Levenshtein, 1965).

$$Lev_{\alpha,\beta}=\left\{\begin{array}[]{ll}\max(\alpha,\beta)\hskip 25.6073pt\textbf{if }\min(\alpha,\beta)=0\\ \min\left\{\begin{array}[]{l}lev_{\alpha-1,\beta}+1\\ lev_{\alpha,\beta-1}+1\\ lev_{\alpha-1,\beta-1}+1_{(W_{1\alpha}\neq W_{2\beta})}\end{array}\right.\end{array}\right.$$

(1)

The Levenshtein distance, computed using its recursive equation, can be computationally expensive (Gusfield, 1997), especially for large distances as it has an exponential time complexity of $O(3^{min(|W_{1}|,|W_{2}|)})$. To address this issue, our approach combines two techniques: dynamic programming and the trie data structure.
Dynamic programming (Almudevar, 2001), as a technique for solving problems by decomposing them into more manageable subproblems and storing the solutions, helps reduce the number of redundant calculations by providing a more efficient storage of intermediate results. When applied to the Levenshtein distance, it allows for the intermediate results of partial computations to be stored in a matrix, leading to a more efficient calculation of the final result.
By combining dynamic programming and the trie data structure, our approach effectively prunes the search space and avoids redundant calculations. This provides a powerful combination for computing the Levenshtein distance in a fast and efficient manner, even for large inputs.
In the standard Levenshtein distance, all edit operations are assigned a uniform cost of 1. However, considering the findings discussed earlier, a cost matrix was introduced to allow for the assignment of varying costs to different edit operations. This allows for a more nuanced representation of the importance of each operation. The cost for insertions and deletions remains at 1 for all characters. Substitution operations between source and target characters are assigned a cost of 1 if the character couple is listed in Table 4, otherwise, a cost of 2 is assigned.

Our suggestion module generates potential candidate words for a given misspelled word through the computation of the edit distance between the misspelled word and each valid word in the Wolof lexicon. For each candidate word, the cost of transforming the misspelled word into the candidate word is provided.

In the following phase of our methodology, the candidate words generated from the previous stage are subjected to evaluation. The ranking is performed based on the proximity of the candidate words to the misspelled word, with the candidate word having the smallest edit cost being assigned the highest rank. The candidate word with the lowest edit cost is determined to be the closest match and is therefore selected as the most likely substitution for the incorrect word.

It is determined by calculating the ratio of correctly recognized valid words in the text by the spell checker, to the total number of accurate words in the same text, as shown in Formula 2 (Starlander and Popescu-Belis, 2002).

$$R_{c}=\frac{T_{p}}{T_{p}+F_{n}}$$

(2)

It is expressed as the fraction of incorrect words in the text detected by the spell checker, compared to the overall number of incorrect words in the text, as shown in Formula 3 (Starlander and Popescu-Belis, 2002).

$$R_{i}=\frac{T_{n}}{T_{n}+F_{p}}$$

(3)

It is calculated by dividing the total number of valid words accurately recognized by the spelling checker by the sum of valid words recognized by the spell checker and the quantity of invalid words that were not identified by the spell checker as incorrect, as shown in Formula 4 (Starlander and Popescu-Belis, 2002).

$$P_{c}=\frac{T_{p}}{T_{p}+F_{p}}$$

(4)

It is determined by dividing the number of accurate flags made by the spell checker by the total number of flags issued by the system, as shown in Formula 5 (Starlander and Popescu-Belis, 2002).

$$P_{i}=\frac{T_{n}}{T_{n}+F_{n}}$$

(5)

It enables the calculation of the harmonic mean between lexical recall and lexical precision, as shown in Formula 6 (Starlander and Popescu-Belis, 2002).

$$Fm_{c}=\frac{2}{\frac{1}{R_{c}}+\frac{1}{P_{c}}}$$

(6)

The Error F-measure is calculated by computing the harmonic mean of lexical recall and lexical precision, as shown in Formula 7 (Starlander and Popescu-Belis, 2002).

$$Fm_{i}=\frac{2}{\frac{1}{R_{i}}+\frac{1}{P_{i}}}$$

(7)

It quantifies the probability of any word, whether correct or incorrect, being processed correctly by the spelling checker. It is calculated using Formula 8 (Starlander and Popescu-Belis, 2002).

$$PA=\frac{T_{p}+T_{n}}{T_{p}+T_{n}+F_{p}+F_{n}}$$

(8)

It measures the ability of our spell checker to suggest accurate spelling alternatives for a misspelled word. Let $S$ denote a proper recommendation for an incorrect word and $N$ represent the total number of misspelled words. The Suggestion Adequacy of our system is calculated using Formula 9 (Starlander and Popescu-Belis, 2002).

$$SA=\frac{1}{N}\sum_{i=1}^{n}S_{i}$$

(9)

As previously stated, our spell checker systematically selects the first word in the list of recommendations as the most likely substitution for the misspelled word. However, as selecting the initial option in the recommended list may not always be the appropriate choice, we will utilize the $MRR$ metric to assess the ranking methodology. Let $N$ be the total number of incorrect words and $Rank_{i,c}$ be the position of the correct suggestion in the list of suggestion for the $i^{th}$ misspelled word in $N$. The $MRR$ is computed using the Formula 10 (Voorhees and Garofolo, 2000).

$$MRR=\frac{1}{N}\sum_{i=1}^{N}\frac{1}{Rank_{i,c}}$$

(10)

The results of our spell checker, as demonstrated in Table 6, exhibit a remarkable level of proficiency in various aspects of spelling correction.

The recall score of 95.16% ($R_{c}$) and 100% ($R_{i}$) depicts the comprehensive nature of the lexicon utilized by the spell checker, as well as its relatively unspoiled status.
The spell checker exhibits an exceptional level of precision, with a score of 100% ($P_{c}$) and 97.46% ($P_{i}$), indicating its reliability in accurately identifying spelling errors as well as valid words.
The F-measure scores of 97.52% ($Fm_{c}$) and 98.71% ($Fm_{i}$) demonstrate the spell checker’s avoidance of simplistic strategies, thereby ensuring its efficiency.
The spell checker’s suggestion accuracy ($SA$) score of 93.33% attests to the suitability and veracity of the most probable alternative to the misspelled word presented to the end-user.
The mean reciprocal rank ($MRR$) score of 96.04% highlights the quality of the ranking of suggestions presented by the spell checker.
Finally, the overall linguistic performance of the spell checker, as indicated by its predictive accuracy ($PA$) score of 98.31%, is of a highly satisfactory nature.

To fully understand and identify the linguistic limitations of our spell checker, we conducted an investigation into the edit distances of the misspelled words for which the system produced an incorrect suggestion. The outcome of this study is presented in Table 7.

After a thorough examination of the results displayed, we surprisingly noted that there was no significant linear correlation between the edit distance of a misspelled word and the probability of the spell checker generating incorrect suggestions. These findings are in line with those displayed in Table 5. The majority of words in our misspelled word corpus had an edit distance of 3, which increased the likelihood of the spell checker producing a wrong suggestion for misspelled words with an edit distance of 3. Additionally, as misspelled words with edit distances of 11, 12, and 13 were under-represented in our corpus, the spell checker’s suggestions for these words were all accurate. This reinforces our conclusion that the higher the frequency of misspelled words with a specific edit distance, the greater the chances of the spell checker generating inaccurate suggestions for misspelled words with that same edit distance.