How do you spell boscodictiasaur? how we correct spelling and complete queries
0x65.dev
0x65.dev
An FST is the better choice. We (https://www.bestprice.gr/) used SymSpell in the past, but have since switched to an FST based design, where the FST is used to match prefixes. We also store all queries encoded in the FST, together with their frequency, sorted by the query.
For each distinct corrected prefix, we determine the range in that (query, frequency) list using binary search, and then just iterate in that list from [first, last] in that range, and compute a score based on a language model and the edit cost(prefix to corrected prefix) (i.e noisy channel).
We encode many different rules in the FST including language domain ones, and building the index takes a few seconds for millions of queries. The language model is based on 5-grams and Stupid Backoff.
As for prefixes and typos, in our case, the FST is used for both matching a prefix and spelling correction of the prefix.
The first character is treated specially; the chance of getting the first character wrong is very low(according to our findings) so only completions/corrections that score very high get to be matched.
Just to provide some additional information, our library Keyvi(https://github.com/KeyviDev/Keyvi) has a very fast implementation of an FST based spell correct.
We built our own FST, which is somewhat similar to the design of the Rust fst crate ( https://blog.burntsushi.net/transducers/#fst-construction ).
SymSpell can be augmented with a Weighted Edit distance giving a higher priority to pairs that are close to each other on the keyboard layout or which sound similar (e.g. Soundex or other phonetic algorithms which identify different spellings of the same sound). There are two SymSpell implementations with a Weighted Edit distance available: https://github.com/MighTguY/customized-symspell https://github.com/searchhub/preDict
So we used 3 indices (one for unigrams, bigrams, and trigrams respectively) -- and during query processing we would segment the input query and for each segment we ‘d consult any of those 3 indices that made sense and would keep the top-K ones, and then we ‘d proceed to the next segment and we ‘d consider the n-gram sequence of the “suffix” and “prefix” matches between the “carried” top-K from the previous segment and the current/next segment, and so on, until we have exhausted the query. Segmentation was particularly hard to get right.
It was a fairly involved process but it was what worked for us -- again, SymSpell is _very_ fast for short tokens, but we had to execute maybe 1000s of such SymSpell queries when processing an input query and it adds up quickly. (We will probably open-source our SymSpell implementation soon).
Unfortunately, we had trouble getting the performance to a point where they could replace this system. It is definitely something we will revisit soon though!
Europe has failed to build its own digital infrastructure. US companies such as Google have thus been able to secure supremacy. They ruthlessly exploit our data. They skim off all profits. They impose their rules on us. In order not to become completely dependent and end up as a digital colony, we Europeans must now build our own independent infrastructure as the foundation for a sovereign future.
Why not post this article to the European "HN"? Would hate for the US Hacker News to be ruthlessly providing traffic to a company whose stated mission is anti-US.