Correcting typos based on context

Recently, I needed a library to correct typos. Most open spell checkers (for example hunspell) do not take into account the context, and without it it is difficult to get good accuracy. I took Peter Norwig’s spellchecker as a basis, fastened a language model to it (based on N-grams), accelerated it (using the SymSpell approach), overcome strong memory consumption (via the bloom filter and perfect hash) and then designed it all in the form of a library on C ++ with swig binders for other languages.

Quality metrics

Before writing the spellchecker directly, you had to come up with a way to measure its quality. For these purposes, Norwig used a ready-made collection of typos, in which a list of words with errors along with the correct version is given. But in our case, this method is not suitable due to the lack of context in it. Instead, a simple typo generator was written first.

The typo generator takes the word at the input, gives the word at the output with a certain number of errors. Errors are of the following types: replacing one letter with another, inserting a new letter, deleting an existing one, and also rearranging two letters in places. The probabilities of each type of error are set separately, the overall probability of a typo (depending on the length of the word) and the probability of a second typo are also adjusted.

So far, all parameters have been selected intuitively, the probability of error is about 1 in 10 words, the probability of the simplest type of error (replacing one letter with another) is 7 times higher than other types of errors.

This model has many shortcomings - it is not based on real typo statistics, does not take into account the keyboard layout, and also does not stick together or separate words. However, for the initial version it is enough. And in future versions of the library, the model will be improved.

Now, having a typo generator, you can run any text through it and get a similar text with errors. As a metric of the quality of the spellchecker, you can use the percentage of errors remaining in the text after running it through this spellchecker. In addition to this metric, the following were used:

• percentage of corrected words (in contrast to the metric with the percentage of errors - it is considered only for words with errors, and not throughout the text)
• percentage of broken words (this is when there was no mistake in the word, and the spellchecker decided that it was there, and corrected it)
• percentage of words for which the correct option was proposed in the list of N candidates (spellcheckers usually offer several correction options)

Spellchecker Peter Norwig

Peter Norwig described a simple spellchecker. For each word, all possible variations are generated (delete + insert + replace + permutation), recursively with a depth of <= 2. The resulting words are checked for presence in the dictionary (hash table), among the many suitable options, the one that occurs most often is selected. You can read more about this spellchecker in the original article .

The main disadvantages of this spellchecker are a long time (especially in long words), lack of contextual consideration. Let's start with the correction of the latter - we will add a language model and instead of a simple frequency of occurrence of words, we will use the estimate returned by the language model.

N-gram language model

The language model is able to answer the question - with what probability is this proposal likely to occur in the language. Today, two approaches are mainly used: models based on N-grams and also based on neural networks . For the first version of the library, an N-gram model was chosen, since it is simpler. However, in the future there are plans to try the neural network model.

N-gram model works as follows. According to the text used to train the model, we go through a window of N words and count the number of times each combination occurred (n-gram). Upon request to the model, we similarly go through the window on the proposal and consider the product of the probabilities of all n-grams. The probability of meeting an n-gram is estimated by the number of such n-grams in the training text.

The probability P (w 1 , ..., w m ) to meet a sentence (w 1 , ..., w m ) of m words is approximately equal to the product of all n-grams of size n that this sentence consists of:

The probability of each of the n-grams is determined through the number of times this n-gram has met with respect to the number of times that the same n-gram has met but without the last word:

In practice, such a model is not used in its pure form, since it has the following problem. If some kind of n-gram is not found in the training text, the whole sentence will immediately receive zero probability. To solve this problem, use one of the options for smoothing (smoothing). In simple terms, this is the addition of a unit to the frequency of occurrence of all n-grams, in a more complex form, the use of lower-order n-grams in the absence of a high-order n-gram.

The most popular smoothing technique is Kneser – Ney smoothing . However, it requires additional information to be stored for each n-gram, and the gain compared to simpler smoothing is not strong (at least in experiments with small models, up to 50 million n-grams). For simplicity, we consider the probability of each n-gram as a product of n-grams of all orders as smoothing, for example, for trigrams:

Now, having a language model, we will choose among candidates for typos to correct for which the language model, taking into account the context, will give the best score. In addition, we add to the assessment a small penalty for changing the original word to avoid a large number of false positives. Changing this fine allows you to adjust the percentage of false positives: for example, in a text editor you can leave the percentage of false positives higher, and for automatic correction of texts lower.

Symspell

The next problem with the Norweg spellchecker is the low speed of work for cases when there were no candidates. So, on a word of 15 letters, the algorithm works for about a second, such a performance is hardly enough for practical use. One of the options for speeding up performance is the SymSpell algorithm., which, according to the authors, works a million times faster. SymSpell works by the following principle: for each word from the dictionary, deletions are added to a separate index, or rather, all words obtained from the original by deleting one or more letters (usually 1 and 2), with reference to the original word. At the time of the search for candidates, similar deletions are made for the word and their presence in the index is checked. Such an algorithm correctly handles all cases of errors - replacing letters, rearrangements, adding and deleting.

For example, consider a replacement (in the example we will only consider distance 1). Let the original dictionary contain the word " test ". And we typed the word " tempo ". The index will contain all deletions of the word “ test ”, namely: eats , tst , tet , tes . For the word “ tempo ” the deletions will be: emt , tmt , tet , emt . The removal of “ tet ” is contained in the index, which means that the word “ test ” corresponds to the word with a typo “ temt ”.

Perfect hash

The next problem is memory consumption. The model, trained on a text of two million sentences (one million from Wikipedia + one million from news texts) occupied 7 GB of RAM. About half of this volume was used by the language model (n-grams with the frequency of occurrence) and the other half was used by the index for SymSpell. With such memory consumption, application usage became not very practical.

I did not want to reduce the size of the dictionary, since quality was beginning to noticeably sag. As it turned out, this is not a new problem. Scientific articles suggest different ways to solve the problem of memory consumption by the language model. One of the interesting approaches (described in the article Efficient Minimal Perfect Hash Language Models ) is to use perfect hash (or rather, the CHD algorithm) to store information about n-grams. Perfect hash is a hash that does not give collisions on a fixed data set. In the absence of collisions, the need for storing keys disappears, since there is no need to compare them. As a result, one can keep in memory an array equal to the number of n-grams in which to store their frequency of occurrence. This gives a very strong memory savings, since the n-grams themselves take up much more space than their frequency of occurrence.

But there is one problem. When using the model, n-grams will come into it, which have never been found in the training text. As a result, perfect hash will return a hash of some other, existing n-gram. To solve this problem, the authors of the article suggest storing an additional hash for each n-gram, according to which it will be possible to compare whether the n-grams coincide or not. If the hash is different, this n-gram does not exist and the frequency of occurrence should be considered zero.

For example, we have three n-grams: n1, n2, n3, which met 10, 15, and 3 times, as well as an n-gram n4 that did not appear in the source text:

We have created an array in which we store the frequencies of occurrence, as well as an additional hash. We use the value of perfect-hash as the index of the array:

Suppose we meet an n-gram n1. Its perfect-hash is 1, and second-hash 42. We go to the array at index 1, and compare the hash that lies there. It coincides, which means the frequency of the n-gram 10. Now consider the n-gram n4. Its perfect-hash is also 1, but the second-hash is 18. This is different from the hash that is at index 1, which means the frequency of occurrence is 0.

In practice, a 16-bit CityHash was used as a hash. Of course, the hash does not exclude false positives completely, but reduces their frequency to such that this does not affect the final quality metrics.

The frequency of occurrence itself was also encoded more compactly, from 32-bit numbers to 16-bit ones, by non-linear quantization . Small numbers corresponded as 1 to 1, larger ones as 1 to 2, 1 to 4, etc. Quantization again did not affect the final metrics.

Most likely, you can package both the hash and the frequency of occurrence even stronger - but this is already in the next versions. In the current version, the model shrank up to 260 MB - more than 10 times, without any drawdown in quality.

Bloom filter

In addition to the language model, there was still an index from the SymSpell algorithm, which also took up a lot of space. I had to think about it a little longer, since there were no ready-made solutions for this. In scientific articles about the compact representation of the language model, a bloom filter was often used . It seemed that he could help in this task. It was not possible to apply the bloom filter directly to the forehead - for each word from the index with deletions, we needed links to the original word, and the bloom filter does not allow storing values, only checking for the presence of it. On the other hand - if the bloom filter says that such deletion is in the index - we can restore the original word for it by performing inserts and checking them in the index. The final adaptation of the SymSpell algorithm is as follows:

We will store all deletions of words from the original dictionary in the bloom filter. When searching for candidates, we will first make deletions from the original word to the desired depth (similar to SymSpell). But, unlike SymSpell, the next step for each deletion will be to insert, and check the resulting word in the original dictionary. And the index with deletions stored in the bloom filter will be used to skip inserts for those deletions that are not in it. In this case, false positives are not afraid of us - we just do a little extra work.

The performance of the resulting solution practically did not slow down, and the used memory was reduced very significantly - up to 140 MB (about 25 times). As a result, the total memory size was reduced from 7 GB to 400 MB.

results

В таблице ниже приведены результаты для английского текста. Для обучения использовались 300К предложений из википедии и 300К предложений из новостных текстов (тексты взяты здесь). Исходная выборка была разбита на 2 части, 95% использовалось для обучения, 5% для оценки. Результаты:

JamSpell — получившийся в итоге спелл-чекер. Dummy — корректор который ничего не делает, приведён для того чтобы было понятно какой процент ошибок в исходном тексте. Norvig — спелл-чекер Питера Норвига. Hunspell — один из самых популярных open-source спелл-чекеров. Для чистоты эксперимента — так же была проведена проверка на художественном тексте. Метрики по тексту "Приключения Шерлока Холмса":

JamSpell показал лучшее качество и производительность по сравнению со спеллчекерами Hunspell и Норвига в обоих тестах, как в кейсе с одним кандидатом, так и в кейсе с лучшими 7 кандидатами.

В следующей таблице приведены метрики для разных языков и для обучающей выборки разных размеров:

Итоги

В результате получился качественный и быстрый спелл-чекер, который превосходит аналогичные открытые решения. Примеры использования — текстовые редакторы, мессенджеры, предобработка грязного текста в задачах машинного обучения и т. п.

Исходники доступны на github, под MIT лицензией. Библиотека написана на C++, биндинги для других языков доступны через swig. Пример использования в python:

import jamspell
corrector = jamspell.TSpellCorrector()
corrector.LoadLangModel('model_en.bin')
corrector.FixFragment('I am the begt spell cherken!')
# u'I am the best spell checker!'
corrector.GetCandidates(['i', 'am', 'the', 'begt', 'spell', 'cherken'], 3)
# (u'best', u'beat', u'belt', u'bet', u'bent', ... )
corrector.GetCandidates(['i', 'am', 'the', 'begt', 'spell', 'cherken'], 5)
# (u'checker', u'chicken', u'checked', u'wherein', u'coherent', ...)

Дальнейшие доработки — улучшение качества языковой модели, уменьшение потребления памяти, добавление возможности обрабатывать склеивания и разделения слов, поддержка особенностей разных языков. Если кто-то захочет поучаствовать в улучшении библиотеки — буду рад вашим pull-реквестам.

Ссылки

• Исходники JamSpell: github.com/bakwc/JamSpell
• How to Write a Spelling Corrector, Peter Norvig: norvig.com/spell-correct.html
• Hunspell: github.com/hunspell/hunspell
• Language Modeling with N-grams, Daniel Jurafsky & James H. Martin: web.stanford.edu/~jurafsky/slp3/4.pdf
• Understanding LSTM Networks, Christopher Olah: colah.github.io/posts/2015-08-Understanding-LSTMs/
• N-GRAM LANGUAGE MODELING USING RECURRENT NEURAL NETWORK ESTIMATION, Google Tech Report, Ciprian Chelba, Mohammad Norouzi, Samy Bengio: static.googleusercontent.com/media/research.google.com/ru//pubs/archive/46183.pdf
• An empirical study of smoothing techniques for language modeling, Stanley F. Chen and Joshua Goodman: u.cs.biu.ac.il/~yogo/courses/mt2013/papers/chen-goodman-99.pdf
• 1000x Faster Spelling Correction algorithm, Wolf Garbe: blog.faroo.com/2012/06/07/improved-edit-distance-based-spelling-correction/
• Efficient Minimal Perfect Hash Language Models, David Guthrie, Mark Hepple, Wei Liu: www.lrec-conf.org/proceedings/lrec2010/pdf/860_Paper.pdf
• Perfect hash function, wikipedia: en.wikipedia.org/wiki/Perfect_hash_function
• Hash, displace, and compress. Djamal Belazzougui1, Fabiano C. Botelho, Martin Dietzfelbinger : cmph.sourceforge.net/papers/esa09.pdf
• Bloom Filter, habrahabr : habrahabr.ru/post/112069/
• Leipzig Corpora Collection: wortschatz.uni-leipzig.de/en/download/