Lecture
Это окончание невероятной информации про алгоритмы исправления опечаток.
...
works on the following principle: for each word from the dictionary, deletions are added to a separate index — more precisely, all the words obtained from the original by deleting one or more letters (usually 1 or 2), with a reference to the original word. When searching for candidates for a word, the same kind of deletions are performed and checked for presence in the index. This algorithm correctly handles all types of errors — substitutions, transpositions, insertions and deletions.
As an example, let's consider a substitution (in the example we will only consider distance 1). Suppose the original dictionary contains the word "тест" (test). And we typed the word “темт”. The index will contain all the deletions of the word “тест”, namely: ест, тст, тет, тес. For the word “темт” the deletions will be: емт, тмт, тет, емт. The deletion “тет” is present in the index, which means the word “тест” corresponds to the misspelled word “темт”.
The next problem is memory consumption. A model trained on a text of two million sentences (one million from Wikipedia + one million from news texts) took up 7 Gb of RAM. Roughly half of that volume was used by the language model (n-grams with their occurrence frequencies), and the other half — by the SymSpell index. With this level of memory consumption, practical use became not very feasible.
Reducing the dictionary size was not desirable, since quality started to drop noticeably. As it turned out — this is not a new problem. Scientific papers propose various ways to solve the problem of memory consumption by the language model. One interesting approach (described in the paper Efficient Minimal Perfect Hash Language Models) is to use a perfect hash (more precisely, the CHD algorithm) to store information about the n-grams. A perfect hash is a hash that produces no collisions on a fixed dataset. When there are no collisions, there is no longer a need to store the keys, since there is no need to compare them. As a result, you can keep in memory an array whose size equals the number of n-grams, and store their occurrence frequencies in it. This gives a very large memory saving, since the n-grams themselves take up much more space than their occurrence frequencies.
But there is one problem. When using the model, it will encounter n-grams that never occurred in the training text. As a result, the perfect hash will return the hash of some other, existing n-gram. To solve this problem, the paper's authors propose additionally storing, for each n-gram, another hash, which can be used to check whether the n-grams match or not. If the hash differs — that n-gram does not exist, and its occurrence frequency should be considered zero.
For example, suppose we have three n-grams: n1, n2, n3, which occurred 10, 15 and 3 times respectively, as well as n-gram n4, which did not occur in the source text:
We set up an array in which we store the occurrence frequencies, as well as an additional hash. We use the perfect-hash value as the array index:
| 15, 13 | 10, 42 | 3, 24 |
Suppose we encounter n-gram n1. Its perfect-hash is 1, and its second-hash is 42. We go to the array at index 1, and check the hash stored there. It matches, so the frequency of the n-gram is 10. Now consider n-gram n4. Its perfect-hash is also 1, but its second-hash is 18. This differs from the hash stored at index 1, so the occurrence frequency is 0.
In practice, CityHash, 16 bits in size, was used as the hash. Of course, the hash does not eliminate false positives entirely, but it reduces their frequency to the point where it has no effect on the final quality metrics.
The occurrence frequency itself was also encoded more compactly, converted from 32-bit numbers to 16-bit ones, via nonlinear quantization. Small numbers were mapped 1 to 1, larger ones 1 to 2, 1 to 4, and so on. Again, the quantization had no effect on the final metrics.
It is probably possible to pack both the hash and the occurrence frequencies even more tightly — but that's for future versions. In the current version, the model shrank to 260 Mb — more than a 10x reduction, without any drop in quality.
Besides the language model, there was still the index from the SymSpell algorithm, which also took up a lot of space. This one required a bit more thought, since no ready-made solution for it existed. Scientific papers on compact language-model representation often used a bloom filter. It seemed that it could help with this task too. Applying a bloom filter head-on did not work — for each word in the deletions index we needed a reference to the original word, and a bloom filter does not let you store values, only check for presence. On the other hand — if the bloom filter says that a given deletion is in the index, we can reconstruct the original word for it by performing insertions and checking them against the index. The resulting adaptation of the SymSpell algorithm turned out as follows:
We will store all deletions of words from the original dictionary in a bloom filter. When searching for candidates, we first make deletions from the source word to the required depth (similar to SymSpell). But, unlike SymSpell, the next step for each deletion is to perform insertions and check the resulting word against the original dictionary. And we use the deletions index stored in the bloom filter to skip insertions for those deletions that are absent from it. In this case, false positives are not a problem for us — we simply do a bit of extra work.
The performance of the resulting solution barely slowed down, while the memory used dropped very substantially — down to 140 Mb (roughly a 25x reduction). In the end, total memory usage went from 7 Gb down to 400 Mb.
The table below shows the results for English text. 300K sentences from Wikipedia and 300K sentences from news texts were used for training (the texts were taken here). The original sample was split into 2 parts, 95% used for training, 5% for evaluation. Results:
JamSpell — the resulting spell checker. Dummy — a corrector that does nothing, included so it is clear what percentage of errors is in the source text. Norvig — Peter Norvig's spell checker. Hunspell — one of the most popular open-source spell checkers. For the sake of a clean experiment, a check was also performed on literary text. Metrics for the text "The Adventures of Sherlock Holmes":
JamSpell showed better quality and performance compared to the Hunspell and Norvig spell checkers in both tests, both in the single-candidate case and in the case with the best 7 candidates.
The following table shows the metrics for different languages and for training samples of different sizes:
Часть 1 Typo Correction Algorithms With and Without Context
Часть 2 Perfect Hash - Typo Correction Algorithms With and Without Context
Comments