Lecture
So, we've received a query with a typo and we need to fix it. Usually the task is stated mathematically as follows:
This formulation — the most basic one — assumes that if we receive a query consisting of several words, we correct each word separately. In reality, of course, we will want to correct the entire phrase as a whole, taking into account the compatibility of neighboring words; I will talk about this below, in the section “How to correct phrases”.
There are two unclear points here — where to get the dictionary and how to compute P(w|s). The first question is considered simple. In 1990 the dictionary was assembled from the spell utility's database and from dictionaries available in electronic form; in 2009 Google took a simpler approach and just took the top most popular words on the Internet (together with popular misspellings). I took this same approach for building my own typo corrector.
The second question is harder. If only because its solution usually starts with applying Bayes' formula!
Now, instead of the original, obscure probability, we need to estimate two new, slightly more understandable ones: P(s|w) — the probability that when typing the word w one could make a typo and end up with s, and P(w) — essentially the probability of the user using the word w.
How do we estimate P(s|w)? Obviously, a user is more likely to confuse A with O than Ъ with Ы. And if we are correcting text recognized from a scanned document, there is a high probability of confusion between rn and m. Either way, we need some kind of model describing errors and their probabilities.
Such a model is called a noisy channel model (in our case the noisy channel begins somewhere in the user's Broca's area and ends on the other side of their keyboard), or more briefly an error model. This model, to which a separate section is devoted below, will be responsible for accounting for both spelling errors and, properly speaking, typos.
The probability of a word being used — P(w) — can be estimated in different ways. The simplest option is to take it as the frequency with which the word occurs in some large corpus of texts. For our typo corrector, which takes the context of the phrase into account, something more sophisticated will of course be needed — yet another model. This model is called a language model.
We provide two types of pipelines for spelling correction: levenshtein_corrector uses a simple Damerau-Levenshtein distance to find correction candidates, while brillmoore uses a statistical error model for this. In both cases, correction candidates are selected based on context using the KenLM language model .
Comparison of automatic spelling correction for the Russian language using various algorithms:
Every user has at some point made typos when typing search queries. The absence of mechanisms that correct typos leads to irrelevant results being returned, or even to no results at all. Therefore, in order to make a search engine more user-oriented, error-correction mechanisms are built into it.
The task of correcting typos may, at first glance, seem fairly simple. But if you take into account the diversity of errors, implementing a solution can turn out to be difficult. Overall, typo correction is divided into context-independent and context-dependent (where the surrounding words are taken into account). In the first case errors are corrected for each word separately, in the second – taking context into account (for example, for the phrase «она пошле домой» (she goedz home – a typo in the verb), in the context-independent case the correction is done for each word separately, where we might get «она пошел домой» (he went home – wrong gender), while in the second case the correct correction would produce «она пошла домой» (she went home – correct)).
Among the search queries of Russian-speaking users, four main groups of errors can be identified for context-independent correction alone:
1) errors within the words themselves (пмрвет → привет (hello)), this category includes all kinds of omissions, insertions and transpositions of letters – 63.7%,
2) words written together or split apart – 16.9%,
3) distorted keyboard layout (ghbdtn → привет (hello)) – 9.7 %,
4) transliteration (privet → привет (hello)) – 1.3%,
5) mixed errors – 8.3%.
Users make typos in approximately 10-15% of cases. Of these, 83.6% of queries have one error, 11.7% – two, 4.8% – more than three. Context matters in 26% of cases.
This statistics was compiled based on a random sample from Yandex's daily log back in 2013, based on 10,000 queries. There is a much earlier presentation from Yandex publicly available, from 2008, showing a similar statistical distribution . From this it can be concluded that the distribution of error types for search queries does not, on average, change over time.
In general terms, the typo-correction mechanism is based on two models: an error model and a language model. Moreover, only the error model is used for context-independent correction, while both are used at once for context-dependent correction. The error model is usually either an edit distance (the Levenshtein distance, the Damerau-Levenshtein distance, to which various weighting coefficients, methods such as Soundex, etc. can also be added – in which case the distance is called weighted), or the Brill-Moore model, which works on the probabilities of one string transitioning into another. Brill and Moore position their model as more advanced, however in one of the recent SpellRuEval competitions the Damerau-Levenshtein approach showed a better result , despite the fact that the Damerau-Levenshtein distance (clarification – the unweighted one) does not use any a priori information about typo statistics. This observation is especially telling in the case where identical training texts were used for different autocorrector implementations in the DeepPavlov library.
Obviously, the possibility of context-dependent correction complicates the construction of an autocorrector, since in addition to the error model, a language model is also needed. But if we look at the typo statistics, ¾ of all incorrectly written search queries can be corrected without context. This suggests that the benefit of even just a context-independent autocorrector alone can be quite substantial.
Also, context-dependent correction for fixing typos in queries is very resource-intensive. For example, in one of Yandex's talks, the list of word pairs for typo correction (bigrams) was 10 times larger than the number of words (unigrams), so what can be said about trigrams? Obviously, this depends heavily on the variability of the queries. It looks a bit odd when an autocorrector takes up half the memory of the product a company is offering, whose intended purpose has nothing to do with solving spelling problems. So the question of introducing context-dependent correction into the search engines of software products can be quite debatable.
At first glance, it seems that there are many ready-made solutions for any programming language that can be used without diving too deeply into the details of how the algorithms work, including in commercial systems. But in practice, developing one's own solutions is still ongoing. For example, relatively recently Joom built its own typo-correction solution using language models for search queries . Is the situation with the availability of ready-made solutions really that difficult? For this purpose, as broad a review of existing solutions as possible was carried out. Before we get to the review, let us define how the quality of an autocorrector's work is checked.
The question of checking the quality of an autocorrector's work is quite ambiguous. One of the simple approaches to checking it is through precision (Precision) and recall (Recall). In accordance with the ISO standard, precision and recall are supplemented by correctness (in English «corectness»).
Recall is calculated as follows: a list of correct words is fed to the autocorrector (Total_list_true), and the number of words that the autocorrector considers correct (Spellchecker_true), divided by the total number of correct words (Total_list_true), is taken as the recall.
To determine precision (Precision), a list of incorrect words is fed to the input of the autocorrector (Total_list_false), and the number of words that the autocorrector considers incorrect (Spell_checker_false), divided by the total number of incorrect words (Total_list_false), is defined as the precision.
How informative these metrics actually are and how useful they can be is something everyone decides for themselves. After all, in fact, the essence of this check boils down to checking whether a word occurs in the training dictionary. A more illustrative metric can be considered to be correctness, according to which, for each word in the test set of incorrect words, the autocorrector forms a list of candidate replacements that this incorrect word could be corrected to (it should be kept in mind that this list may contain words that are not present in the training dictionary). Suppose the size of this list of candidate replacements is 5. Based on the list size being 5, 6 groups will be formed, and each of our original incorrect words will be placed into one of them according to the following principle: into group 1 — if in the list of candidate replacements the word we assume to be correct is in 1st place, into group 2 if it is in 2nd place, and so on, and into the last group — if the assumed correct word does not appear in the list of candidate replacements at all. Naturally, the more words that end up in group 1 and the fewer that end up in group 6, the better the autocorrector is performing.
The authors of the approach discussed above followed it in an article , in which context-independent autocorrectors were compared with a focus on the ISO standard. That same article also provides links to other ways of assessing quality.
On the one hand, such an approach is not based on typo statistics, which could instead be used as the basis for the Brill-Moore error model , or the weighted Damerau-Levenshtein distance error model.
To check the quality of a context-independent autocorrector's work, a dedicated typo generator was built, which generated wrong-keyboard-layout typos and spelling typos based on the typo statistics published by Yandex. For spelling typos, random insertions, substitutions, deletions, and transpositions were generated, and the number of errors was also varied in accordance with this statistics. For wrong-layout errors, the correct word was converted character by character in its entirety according to a character-mapping table.
Next, a series of experiments was carried out for the entire word list of the training dictionary (the words of the training dictionary were changed into incorrect ones according to the probability of a given typo occurring). On average, the autocorrector corrects words correctly in 75% of cases. Without a doubt, this figure will decrease as the training dictionary is expanded with words close in edit distance and with a wide variety of word forms. This problem can be addressed by adding language models, but it should be kept in mind that the amount of resources required will increase considerably.
The first error models estimated P(s|w) by counting the probabilities of elementary substitutions in the training sample: how many times И was written instead of Е, how many times Т was written instead of ТЬ, ТЬ instead of Т, and so on . This produced a model with a small number of parameters, capable of learning some local effects (for example, that people often confuse Е and И).
In our research we settled on a more advanced error model, proposed in 2000 by Brill and Moore and used many times since (for example, by Google specialists ). Let us imagine that users do not think in terms of individual characters (confusing Е and И, pressing К instead of У, omitting the soft sign), but can change arbitrary chunks of a word into any other chunks — for example, replacing ТСЯ with ТЬСЯ, У with К, ЩА with ЩЯ, СС with С, and so on. Let us denote the probability that the user made a typo and wrote ТЬСЯ instead of ТСЯ as P(тся→ться) — this is a parameter of our model. If for all possible fragments α,β we can compute P(α→β), then the sought probability P(s|w) of typing the word s while trying to type the word w in the Brill and Moore model can be obtained as follows: split the words w and s in every possible way into shorter fragments so that the two words have the same number of fragments. For each split, compute the product of the probabilities of all fragments of w turning into the corresponding fragments of s. The maximum over all such splits is taken as the value of P(s|w):
Let's look at an example of the split that arises when computing the probability of typing «аксесуар» (accessory, misspelled) instead of «аксессуар» (accessory, correct):
As you've probably noticed, this is an example of a not very good split: you can see that the word parts don't line up as neatly as they could. While the values P(ак→а) and P(р→р) aren't too bad, P(су→е) and P(а→суа) will most likely make the overall «score» of this split quite poor. A better split looks something like this:
Here everything falls into place at once, and it's clear that the resulting probability will be determined mainly by the value 
.
Even though the number of possible splits for two words is on the order of 
, dynamic programming lets us make the algorithm for computing P(s|w) quite fast — in 
. This algorithm will closely resemble the Wagner-Fischer algorithm for computing the Levenshtein distance.
We'll set up a rectangular table whose rows correspond to the letters of the correct word, and whose columns correspond to the mistyped one. By the end of the algorithm, the cell at the intersection of row i and column j will contain exactly the probability of getting s[:j] when trying to type w[:i]. To compute it, it's enough to compute the values of all cells in the preceding rows and columns and run through them, multiplying by the corresponding P(α→β). For example, if we have the table filled in as
, then to fill in the cell in the fourth row and third column (shown in gray) we need to take the maximum of the values 
and 
. In doing so, we went through all the cells highlighted in green in the picture. If we also consider modifications of the form empty string P(α→empty string) and empty string P(empty string→β), we'll also need to go through the cells highlighted in yellow.
The complexity of this algorithm, as I already mentioned above, is 
: we fill in a |s|×|w| table, and filling cell (i, j) takes O(i⋅j) operations. However, if we limit consideration to fragments no longer than some bounded length L (for example, no more than two letters, as in ), the complexity drops to 
. For Russian, in my experiments I used L=3.
We've learned to find P(s|w) in polynomial time — that's good. But we need to learn to quickly find the best words across the entire dictionary. And not the best by P(s|w), but by P(w|s)! In practice, it's enough to get some reasonable top list (say, the best 20) of words by P(s|w), which we then pass to the language model to choose the most suitable corrections (more on this below).
To learn to quickly go through the whole dictionary, notice that the table shown above has a lot in common for two words with shared prefixes. Indeed, if, while correcting the word «аксесуар» (accessory, misspelled), we try to fill it in for the two dictionary words «аксессуар» (accessory) and «аксессуары» (accessories), we'll notice that the first nine rows don't differ at all! If we can organize the pass through the dictionary so that two consecutive words have sufficiently long common prefixes, we can save a lot of computation.
And we can. Let's take the dictionary words and build a trie out of them. By doing a depth-first traversal over it, we get the property we want: most steps are steps from a node to its child, where it's enough to fill in just the last few rows of the table.
This algorithm, with some additional optimizations, lets us iterate through the dictionary of a typical European language — 50-100 thousand words — within about a hundred milliseconds . And caching the results makes the process even faster.
Computing P(α→β) for all fragments under consideration — this is the most interesting and non-trivial part of building the error model. It is on these values that its quality will depend.
The approach used in [2, 4] is relatively simple. Let's find many pairs (si,wi), where wi — is the correct word from the dictionary, and si — is its misspelled variant. (Exactly how to find them — a bit below.) Now we need to extract from these pairs the probabilities of specific typos (substitutions of one fragment for another).
For each pair, let's take its components w and s and build a correspondence between their letters that minimizes the Levenshtein distance:
Now we can immediately see the substitutions: а→а, е→и, с→с, с→empty string, and so on. We also see substitutions of two or more characters: ак→ак, се→си, ес→ис, сс→с, сес→сис, есс→ис, and so on and so forth. All of these substitutions need to be counted, and each one as many times as the word s occurs in the corpus (if we took the words from a corpus, which is very likely).
After going through all the pairs (si,wi), the probability P(α→β) is taken to be the number of substitutions α→β encountered in our pairs (accounting for the frequency of the corresponding words), divided by the number of occurrences of the fragment α.
How do we find pairs (si,wi)? The following approach is proposed. Let's take a large corpus of user-generated content (UGC). In Google's case, this was simply the text of hundreds of millions of web pages; in ours — millions of user search queries and reviews. It is assumed that the correct word usually occurs in the corpus more often than any of the erroneous variants. So, for each word, let's find words from the corpus that are close to it by Levenshtein distance and are significantly less popular (say, ten times less). We'll take the more popular one as w, and the less popular one as s. This way we get a set of pairs that, while noisy, is large enough to train on.
This pair-selection algorithm leaves a lot of room for improvement. Only a frequency filter is proposed (w is ten times more popular than s), but the authors of that paper are trying to build a typo corrector without using any prior knowledge of the language. If we're only dealing with Russian, we could, for example, take a set of dictionaries of Russian word forms and keep only pairs whose word w is found in the dictionary (not the best idea, since the dictionary is unlikely to contain vocabulary specific to the service) or, conversely, discard pairs whose word s is found in the dictionary (i.e., almost certainly not a typo).
To improve the quality of the resulting pairs, I wrote a simple function that determines whether users use two words as synonyms. The logic is simple: if the words w and s frequently occur surrounded by the same words, they are probably synonyms — which, given their closeness by Levenshtein distance, means the less popular word is very likely an erroneous version of the more popular one. For these calculations I used the trigram (three-word phrase) frequency statistics built for the language model below.
So, now for a given dictionary word w we need to compute P(w) — the probability of it being used by the user. The simplest solution — take the word's frequency in some large corpus. In general, probably any language model starts with gathering a large corpus of texts and counting word frequencies in it. But we shouldn't stop there: in fact, when computing P(w) we can also take into account the phrase the word we're trying to correct belongs to, and any other external context. The task turns into computing P(w1w2…wk), where one of the wi is the word in which we corrected a typo and for which we're now calculating P(w), and the rest of the wi are the words surrounding the word being corrected in the user's query.
To learn to take them into account, it's worth going through the corpus once more and building n-gram statistics — sequences of words. Usually sequences of some bounded length are used; I limited myself to trigrams so as not to bloat the index, but it all depends on your fortitude (and the size of your corpus — on a small corpus even trigram statistics will be too noisy).
A traditional n-gram-based language model looks like this. For the phrase w1w2…wk, its probability is computed by the formula
where P(w1) — is simply the word's frequency, and P(w3|w1w2) — is the probability of word w3 given that it is preceded by w1w2 — is nothing other than the ratio of the frequency of the trigram w1w2w3 to the frequency of the bigram w1w2. (Note that this formula is simply the result of repeatedly applying Bayes' formula.)
In other words, if we want to compute мама мыла раму P(мама мыла раму) (mama washed the frame), denoting the frequency of an arbitrary n-gram as f, we get the formula
Makes sense? It makes sense. However, difficulties start when phrases get longer. What if the user enters an impressively detailed ten-word search query? We don't want to keep statistics for all 10-grams — that's expensive, and the data would most likely be noisy and not very informative. We want to get by with n-grams of some bounded length — for example, the length of 3 already proposed above.
This is where the formula above comes in handy. Let's assume that the probability of a word appearing at the end of a phrase is significantly influenced only by a few words immediately preceding it, that is, that
Setting L=3, for a longer phrase we get the formula
Note: the phrase consists of five words, but the formula only involves n-grams no longer than three. This is exactly what we were aiming for.
There's one subtle point left. What if the user enters a really strange phrase and we don't have the corresponding n-grams in our statistics at all? It would be easy to just set f=0 for unfamiliar n-grams, if we didn't have to divide by that value. This is where smoothing comes to the rescue, which can be done in various ways; however, a detailed discussion of serious smoothing approaches like Kneser-Ney smoothing is well beyond the scope of this article.
Let's discuss one last subtle point before moving on to the implementation. The problem statement I described above assumed that there's a single word that needs to be corrected. Then we refined it: this one word might be in the middle of a phrase among other words, and those need to be taken into account too when choosing the best correction. But in reality, users simply send us phrases without specifying which word is misspelled; often several words, or even all of them, need correcting.
There can be many approaches here. We could, for example, only take into account the left context of a word in the phrase. Then, going through the words left to right and correcting them as needed, we'd get a new phrase of some quality. The quality would be low if, say, the first word happened to resemble several popular words and we picked the wrong variant. The entire rest of the phrase (possibly originally completely error-free) would then get adjusted to fit the wrong first word, and we could end up with output text that's completely irrelevant to the original.
We could look at words individually and apply some classifier to determine whether a given word is a typo or not, as proposed in . The classifier is trained on the probabilities we already know how to compute, along with a number of other features. If the classifier says correction is needed — we correct it, taking the available context into account. Again, if several words are misspelled, the decision about the first one will have to rely on context that itself contains errors, which can lead to quality problems.
In our implementation of the typo corrector we used the following approach. For each word si in our phrase, let's use the error model to find the top-N dictionary words that could have been meant, concatenate them into phrases in every possible way, and for each of the resulting N^K phrases, where K — is the number of words in the original phrase, let's honestly compute the value
Here si — are the words entered by the user, wi — are the corrections picked for them (which we're now iterating over), and λ — is a coefficient determined by the relative quality of the error model and the language model (a large coefficient — means we trust the language model more, a small coefficient — means we trust the error model more), as proposed in . In total, for each phrase we multiply the probabilities of the individual words being corrected to the corresponding dictionary variants, and further multiply this by the probability of the whole phrase in our language. The result of the algorithm is the phrase of dictionary words that maximizes this value.
So, wait, what? Enumerating NK phrases?
Fortunately, because we limited the length of the n-grams, finding the maximum over all phrases can be done much faster. Recall: above we simplified the formula for P(w1w2…wK) so that it only depends on the frequencies of n-grams of length no more than three:
If we multiply this value by 
and try to maximize over wK, we'll see that it's enough to enumerate all possible wK−2 and wK−1 and solve the problem for them — that is, for the phrases w1w2…wK−2wK−1. In total, the problem is solved by dynamic programming in O(KN3).
Let me say upfront: I didn't have enough data at my disposal to set up any complex MapReduce. So I simply gathered all the texts of reviews, comments, and search queries in Russian (product descriptions, alas, come in English, and using the results of machine translation made things worse rather than better) from our service into a single text file and set a server to spend the night counting trigrams with a simple Python script.
For the dictionary I took the top words by frequency so as to get roughly a hundred thousand words. I excluded words that were too long (more than 20 characters) and too short (fewer than three characters, except for hardcoded well-known Russian words). I separately spared words matching the regex r"^[a-z0-9]{2}$" — so that iPhone model names and other interesting length-2 identifiers would survive.
When counting bigrams and trigrams, a phrase may contain a word that isn't in the dictionary. In that case, I discarded that word and split the whole phrase into two parts (before and after that word), which I processed separately. So, for the phrase «А вы знаете, что такое «абырвалг»? Это… ГЛАВРЫБА, коллега» ("Do you know what ‘abyrvalg’ means? It's… GLAVRYBA, colleague" — a line from Bulgakov's Heart of a Dog), the trigrams “а вы знаете”, “вы знаете что”, “знаете что такое” and “это главрыба коллега” would be counted (assuming, of course, that the word “главрыба” makes it into the dictionary...).
From here on, I did all the data processing in Jupyter. The n-gram statistics are loaded from JSON, post-processing is performed to quickly find words close to each other by Levenshtein distance, and for the pairs, in a loop, a (fairly cumbersome) function is called that aligns the words and extracts short corrections of the form сс→с (under the spoiler).
short corrections of the form сс→с (under the spoiler).
def generate_modifications(intended_word, misspelled_word, max_l=2):
# Align the letters of the words in a Levenshtein-optimal way, and
# extract modifications of bounded length. So that after computing the
# distance we can recover the optimal letter alignment, we'll
# store in the table, besides the distances, pointers to the previous
# cells: memo will store the mapping
# i -> j -> (distance, prev i, prev j).
# What follows is some unusually scary-looking Python code - this is what
# happens when a language is used for something it wasn't meant for!
m, n = len(intended_word), len(misspelled_word)
memo = [[None] * (n+1) for _ in range(m+1)]
memo[0] = [(j, (0 if j > 0 else -1), j-1) for j in range(n+1)]
for i in range(m + 1):
memo[i][0] = i, i-1, (0 if i > 0 else -1)
for j in range(1, n + 1):
for i in range(1, m + 1):
if intended_word[i-1] == misspelled_word[j-1]:
memo[i][j] = memo[i-1][j-1][0], i-1, j-1
else:
best = min(
(memo[i-1][j][0], i-1, j),
(memo[i][j-1][0], i, j-1),
(memo[i-1][j-1][0], i-1, j-1),
)
# Special handling for adjacent letters that got
# transposed (a common mistake when
# typing).
if (i > 1
and j > 1
and intended_word[i-1] == misspelled_word[j-2]
and intended_word[i-2] == misspelled_word[j-1]
):
best = min(best, (memo[i-2][j-2][0], i-2, j-2))
memo[i][j] = 1 + best[0], best[1], best[2]
# By the end of the loop, the Levenshtein distance between the original words # is stored in memo[m][n] .
# Now we reconstruct the optimal letter alignment.
s, t = [], []
i, j = m, n
while i >= 1 or j >= 1:
_, pi, pj = memo[i][j]
di, dj = i - pi, j - pj
if di == dj == 1:
s.append(intended_word[i-1])
t.append(misspelled_word[j-1])
if di == dj == 2:
s.append(intended_word[i-1])
s.append(intended_word[i-2])
t.append(misspelled_word[j-1])
t.append(misspelled_word[j-2])
if 1 == di > dj == 0:
s.append(intended_word[i-1])
t.append("")
if 1 == dj > di == 0:
s.append("")
t.append(misspelled_word[j-1])
i, j = pi, pj
s.reverse()
t.reverse()
# Generate modifications of length no greater than the given one.
for i, _ in enumerate(s):
ss = ts = ""
while len(ss) < max_l and i < len(s):
ss += s[i]
ts += t[i]
yield ss, ts
i += 1
The corrections counting itself looks straightforward, though it can take a long time to run.
This part is implemented as a microservice in Go, connected to the main backend via gRPC. It implements the algorithm described by Brill and Moore themselves , with some minor optimizations. In the end, it runs about twice as slow for me as the authors claimed; I won't venture to judge whether that's down to Go or to me. But in the course of profiling it, I learned a few new things about Go.
math.Max to compute a maximum. It's about three times slower than if a > b { b = a }! Just look at the implementation of this function:
// Max returns the larger of x or y.
//
// Special cases are:
// Max(x, +Inf) = Max(+Inf, x) = +Inf
// Max(x, NaN) = Max(NaN, x) = NaN
// Max(+0, ±0) = Max(±0, +0) = +0
// Max(-0, -0) = -0
func Max(x, y float64) float64
func max(x, y float64) float64 {
// special cases
switch {
case IsInf(x, 1) || IsInf(y, 1):
return Inf(1)
case IsNaN(x) || IsNaN(y):
return NaN()
case x == 0 && x == y:
if Signbit(x) {
return y
}
return x
}
if x > y {
return x
}
return y
}
math.Max.
No real surprises here: I implemented the dynamic-programming algorithm described in the section above. This component required the least work — the slowest part remains applying the error model. So, between these two layers, I additionally bolted on caching of the error model's results in Redis.
As a result of this work (which took roughly a person-month), we ran an A/B test of the typo corrector on our users. Instead of the 10% empty result pages among all search queries that we had before rolling out the typo corrector, that figure dropped to 5%; most of the remaining queries are for products that simply don't exist on our platform. The number of sessions without a second search query also increased (along with a few other UX-related metrics of this kind). Money-related metrics, however, didn't change significantly — which was unexpected and prompted us to carefully analyze and double-check the other metrics.
The review of off-the-shelf solutions was done with our own use case in mind, and priority was given to autocorrectors that satisfy three criteria:
1) implementation language,
2) license type,
3) how actively it's maintained.
In product development, Java is considered one of the most popular languages, so priority in the library search was given to it. Relevant licenses are: MIT, Public, Apache, BSD. Maintenance activity — no more than 2 years since the last update. During the search, additional information was recorded, such as the supported platform, required additional software, usage specifics, possible difficulties on first use, and so on. Links to the main and useful source resources are given at the end of the article. Overall, if we don't limit ourselves to the criteria above, the number of existing solutions is large. Let's briefly look at the main ones, and cover just a few in more detail.
Historically, one of the oldest autocorrectors is Ispell (International Spell), written in 1971 in assembly, later ported to C, which uses the Damerau-Levenshtein edit distance as its error model. There's even a Russian-language dictionary for it. It was later succeeded by two autocorrectors, HunSpell (formerly MySpell) and Aspell. Both are implemented in C++ and distributed under GPL licenses. HunSpell is also distributed under GPL/MPL and is used to correct typos in OpenOffice, LibreOffice, Google Chrome, and other tools.
For the web and browsers there's a whole range of JS-based solutions (these include: nodehun-sentences, nspell, node-markdown-spellcheck, Proofreader, Spellcheck-API — a group of solutions based on the Hunspell autocorrector; grunt-spell — for NodeJS; yaspeller-ci — a wrapper for the Yandex.Speller autocorrector, distributed under MIT; rousseau — Lightweight proofreader in JS — used for spellchecking).
The category of paid solutions includes: Spellex; Source Code Spell Checker — as a desktop application; for JS: nanospell; for Java: Keyoti RapidSpell Spellchecker, JSpell SDK, WinterTree (for WinterTree you can even buy the source code for $5000).
The autocorrector by Peter Norvig is very popular; its Python source code is publicly available in the article «How to Write a Spelling Corrector» . Based on this simple solution, autocorrectors have been built in other languages, for example: Norvig-spell-check, scala-norvig-spell-check (in Scala), toy-spelling-corrector — Golang Spellcheck (in Go), pyspellchecker (in Python). Naturally, there's no question here of language models or context-dependent correction.
For text editors, in particular for VIM there are vim-dialect and vim-ditto — distributed under a public license; for Notepad++, DspellCheck was developed in C++, under a GPL license; for Emacs there's a tool for automatically detecting the language while typing, called guess-language, distributed under a public license.
There are also separate services from the search giants: Yandex.Speller — from Yandex, its wrapper was mentioned above, and google-api-spelling-java (from Google, respectively).
Free libraries for Java: languagetool (licensed under LGPL), integrates with the Lucene text-search library and allows the use of language models, requires Java version 8 to run; Jazzy (an Aspell analog) is distributed under the LGPLv2 license and hasn't been updated since 2005, though it was moved to GitHub in 2013. A separate solution modeled after this autocorrector was made ; Jortho (Java Orthography) is distributed under GPL and allows free use exclusively for non-commercial purposes, with an additional fee for commercial use; Jaspell (licensed under BSD, not updated since 2005); Open Source Java Suggester — not updated since 2013, distributed by SoftCorporation LLC, and allows commercial use; LuceneSpellChecker — the Lucene library's autocorrector, written in Java and distributed under the Apache license.
For a long time, the problem of typo correction was tackled by Wolf Garbe, who proposed the SymSpell (MIT licensed) and LinSpell (LGPL licensed) algorithms, with C# implementations that use the Damerau-Levenshtein distance for the error model. A distinctive feature of their implementation is that when generating possible errors for an input word, only deletions are used, instead of all possible deletions, insertions, substitutions and transpositions. Compared to Peter Norvig's autocorrector implementation, both algorithms therefore run faster, and the speed gain grows substantially once the Damerau-Levenshtein distance becomes greater than two. Also, because only deletions are used, dictionary-building time is reduced. The difference between the two algorithms is that LinSpell is more memory-efficient and slower at search, while SymSpell is the opposite. In a later version, SymSpell also corrects merged/split-word errors. Language models are not used.
Among the most recent and promising autocorrectors that work with language models and correct context-dependent typos are Yandex.Speller, JamSpell [10] and DeepPavlov [11]. The last two are distributed freely: JamSpell (MIT), DeepPavlov (Apache).
Yandex.Speller uses the CatBoost algorithm, works with several languages, and corrects all sorts of errors, even taking context into account. It is the only solution found that corrects wrong-keyboard-layout errors and transliteration. The solution is versatile, which makes it popular. Its drawback is that it is a remote service, and the limitations and terms of use can be read here [12]. The service works with a limited number of languages, and you cannot add your own words or control the correction process yourself. According to the resource, based on the results of the RuSpellEval competition, this autocorrector showed the highest correction quality. JamSpell is the fastest known autocorrector (a C++ implementation), and ready-made bindings for other languages are available. It corrects errors only within the words themselves and works with a specific language. It cannot be used at the unigram or bigram level. Achieving acceptable quality requires a large training text.
DeepPavlov has some decent groundwork, though integrating these solutions and subsequently maintaining them in your own product can cause difficulties, since working with them requires setting up a virtual environment and using an older version of Python 3.6. DeepPavlov offers a choice of three ready-made autocorrector implementations, two of which use the Brill-Moore error model and two of which use language models. It corrects only spelling errors, while the variant with an error model based on the Damerau-Levenshtein distance can also correct merged-word errors.
I'll also mention one more modern approach to typo correction, based on the use of word vector representations (Word Embeddings). Its advantage is that it can be used to build an autocorrector that corrects words with context taken into account. You can read more about this approach here [13]. But to use it for correcting typos in search queries you would need to accumulate a large query log. Moreover, the model itself may turn out to be quite memory-heavy, which would complicate integration into a product.
Among the ready-made solutions for Java, the autocorrector from Lucene was chosen (distributed under an Apache license). It allows correcting typos within words. The training process is fast: for example, building the special dictionary data structure – an index for 3 million lines – took 30 seconds on an Intel Core i5-8500 3.00GHz, 32 Gb RAM, Lucene 8.0.0. In earlier versions the time could be up to twice as long. The size of the training dictionary is 3 million lines (~73 Mb txt file), and the index structure is ~235 Mb. For the error model you can choose the Jaro-Winkler, Levenshtein, Damerau-Levenshtein, or N-Gram distance, and you can add your own if needed. If necessary, it is possible to plug in a language model [14]. The models have been known since 2001, but no comparison of them with well-known modern solutions was found in the public domain. The next step will be to test how they perform.
The resulting Lucene-based solution corrects only errors within the words themselves. It is not hard to add correction for a garbled keyboard layout to any similar solution, using a corresponding translation table, thereby reducing the chance of irrelevant results by up to 10% (based on typo statistics). It is also not hard to add splitting of two merged words and transliteration.
The main drawbacks of the solution include the need to know Java, and the lack of detailed use cases and thorough documentation, which slows down solution development for Data Science specialists. In addition, typos with a Damerau-Levenshtein distance greater than 2 are not corrected. Again, based on typo statistics, more than 2 errors in a word occurs in fewer than 5% of cases. Is the added algorithmic complexity, and in particular the increase in memory consumption, justified? That depends on the customer's use case. If additional resources are available, then why not use them?
Most open-source spell checkers (hunspell, for example) do not take context into account, and without it, it is hard to achieve good accuracy. I took Peter Norvig's spell checker as a base, bolted on a language model (based on N-grams), sped it up (using the SymSpell approach), tackled its heavy memory consumption (via a bloom filter and a perfect hash), and then packaged all of this as a C++ library with swig bindings for other languages.
Before writing the spell checker itself, I needed to come up with a way to measure its quality. Norvig used a ready-made collection of typos for this purpose, which contains a list of misspelled words together with the correct variant. But in our case this approach does not work, because it lacks context. Instead, the first step was to write a simple typo generator.
The typo generator takes a word as input and produces a word with some number of errors as output. The errors are of the following types: replacing one letter with another, inserting a new letter, deleting an existing one, and swapping two letters. The probability of each error type is configured separately, and the overall probability of making a typo (depending on word length) and the probability of making a repeated typo are also configurable.
So far all the parameters have been chosen intuitively: the error probability is about 1 in 10 words, and the probability of the simplest error type (replacing one letter with another) is 7 times higher than that of the other error types.
This model has many drawbacks — it is not based on real typo statistics, does not take keyboard layout into account, and neither merges nor splits words. Nevertheless, it is enough for an initial version. In future versions of the library, the model will be improved.
Now, having a typo generator, we can run any text through it and get an equivalent text with errors. As a quality metric for the spell checker we can use the percentage of errors remaining in the text after running it through the spell checker. In addition to this metric, the following were used:
Peter Norvig described a simple version of a spell checker. For each word, all possible edit variants are generated (deletions + insertions + substitutions + transpositions), recursively to a depth <= 2. The resulting words are checked for presence in the dictionary (a hash table), and among the set of matching variants, the most frequent one is chosen. You can read more about this spell checker in the original article.
The main drawbacks of this spell checker are its slow running time (especially on long words) and the lack of context awareness. Let's start by fixing the latter — we'll add a language model and, instead of a simple word-frequency count, use a score returned by the language model.
| An n-gram is a sequence of n elements. For example, a sequence of sounds, syllables, words or letters. |
A language model can answer the question — how likely is a given sentence to occur in the language. Nowadays, two approaches are mainly used: models based on N-grams, and models based on neural networks. For the first version of the library, an N-gram model was chosen, since it is simpler. However, there are plans to try a neural-network model in the future.
The N-gram model works as follows. We slide a window of N words over the text used to train the model and count how many times each combination (n-gram) occurred. When querying the model — we slide the window over the sentence in the same way and compute the product of the probabilities of all the n-grams. We estimate the probability of encountering an n-gram from the number of such n-grams in the training text.
The probability P(w1,..., wm) of encountering a sentence (w1,..., wm) of m words is approximately equal to the product of all the n-grams of size n that make up this sentence:
The probability of each n-gram is determined by the number of times this n-gram occurred relative to the number of times the same n-gram occurred without its last word:
In practice, this model is not used in its pure form, because it has the following problem. If some n-gram did not occur in the training text — the whole sentence immediately gets a zero probability. To solve this problem, one of the smoothing variants is used. In its simple form, this means adding one to the occurrence frequency of all n-grams; in a more complex form — using lower-order n-grams when a higher-order n-gram is absent.
The most popular smoothing technique is Kneser–Ney smoothing. However, it requires storing additional information for each n-gram, and the gain compared to simpler smoothing turned out to be not very large (at least in experiments with small models, up to 50 million n-grams). For simplicity, as smoothing we will take the probability of each n-gram as the product of n-grams of all orders, for example for trigrams:
Now, having a language model, among the candidates for correcting a typo we will choose the one for which the language model, taking context into account, gives the best score. In addition, we'll add a small penalty to the score for changing the original word, to avoid a large number of false positives. Adjusting this penalty lets you control the false-positive rate: for example, in a text editor you can leave the false-positive rate higher, while for automatic text correction — lower.
The next problem with Norvig's spell checker is its low speed for cases where no candidates were found. For instance, on a 15-letter word the algorithm takes about a second, and such performance is hardly enough for practical use. One way to speed up performance is the SymSpell algorithm, which, according to its authors, works a million times faster. SymSpell
продолжение следует...
Часть 1 Typo Correction Algorithms With and Without Context
Часть 2 Perfect Hash - Typo Correction Algorithms With and Without Context
Comments