Model for evaluating the properties of spelling correction algorithms and its use for Ukrainian applications

Abstract

A significant part of the methods and approaches to automatic spelling correction is language-dependent since they are focused on grammatical rules and phonetics of a particular language. The vast majority of works in this field is devoted to texts in English, a smaller part – to other Germanic languages, a very small part – to Slavic languages and the smallest part – to the Ukrainian language. A special toolkit (a simulation model (SM)) and the evaluation results of the corrective properties of some algorithms in relation to the correction of typical typing errors in Ukrainian words, taking into account the preliminary dictionary indexation, are considered in the article. SM has a modular structure and is configurable for specific dictionaries, types of errors and index generation algorithms. For the «dictionary – type of errors – algorithm» combination SM distorts the words of the given dictionary with a mistake and searches for the «closest» words-candidates to correct the wrong word. A general algorithm for processing a word with an error includes pre-selection (PS) of a set of words-candidates according to the rules of the indexing algorithm, and final selection (FS) as a prioritization of the selected words and narrowing the search area for a «correct» word according to the accepted proximity criteria for the word to be corrected, and various selection criteria. A trial simulation was performed for Soundex and Metaphone phonetic algorithms adapted to the Ukrainian language. An ensemble of errors is a set of typing errors which includes four different basic single misspellings (replacements, insertions, omissions and rearrangement of letters), as well as double errors which are a mixture of basic errors. 59,6 million words with errors were processed; the average time for processing one word was 0,07 ms. The simulation results contain the total number of corrected words grouped by the type of error, the number of correct words-candidates offers, the number of incorrect offers, the number of missing offers and the average number of candidates in the offers at the PS and FS stages.