In this text I will explain what is spell correction in the area of search functionality, how it works in Google, Amazon and Pinterest and will demonstrate how to make your own implementation from the ground up using custom search engine Manticore Search. also known as: Spell correction Auto correction Text correction Fixing a spelling error Typo tolerance “Did you mean?” and so on is a software functionality that suggests you alternatives to or makes automatic corrections of the text you have typed in. The concept of correcting typed text dates back to the 1960s, says Brad Myers, a professor of interface design at Carnegie Mellon University. This’s when a computer scientist named Warren Teitelman who also invented the “undo” command came up with a philosophy of computing called D.W.I.M., or “Do What I Mean.” Rather than programming computers to accept only perfectly formatted instructions, Teitelman said we should program them to recognize obvious mistakes. The first well known product which provided spell correction functionality was Microsoft Word 6.0 released in 1993. Nowadays people can’t imagine their real life without messaging, searching, browsing and using different business applications: text editors, content management systems (CMS), customer relationship management systems (CRM) and others. And in all of them people do typing mistakes, forget proper spelling of words, sometimes are wrong with grammar and so on. This is absolutely fine, everybody makes mistakes. What a good software does is helping you fix those mistakes the easiest and most efficient way. There are many approaches how it can do that: both from how it looks for a user and what value it brings and how it’s made under the hood. In this article we will focus specifically on search systems as for them it’s especially important to correct your search query before (or while) it’s processed since otherwise your search results may be absolutely wrong. Different approaches to autocorrect In terms of user experience we can split the approaches into 2 groups: within the first one a system tries to correct your text right as you type it within another it takes it as a given and gives you suggestions afterwards In most cases these approaches are combined so a system tries to correct you as you type and if it thinks there’s still some issue — suggests you a correction after you get the search results. — corrects wrong typed query immediately Autocorrect — another big feature many modern sites have which is often combined with the autocorrect functionality Autocomplete — it’s kind of a mix of autocomplete and autocorrect which often looks like suggesting you smth a little bit different from what you’re typing in, but still making sense (see the picture below) Suggestions of mistakes — another nice feature is mistake highlighting. It can also be done both as you type and afterwards Highlighting — many systems recommend you refined search queries not only while you are typing, but when displaying the search results too. We call it “did you mean … ?”. In its turn there are 2 patterns: “Did you mean” Search by your original search query and just show you the recommended one (as Google does) Or search by the refined one and suggest to “search for <original query> instead” As you type components: After the query: Let me demonstrate you with pictures how different popular sites use the aforementioned techniques. as the site #1 in the Internet does everything: autocorrect, autocomplete, suggestions, mistake highlighting and “did you mean”. Google uses a prediction service to help complete searches and even URLs typed in the address bar: These suggestions or predictions (as Google names that) are based on related web searches, your browsing history, and Google’s websites ranking. Google uses e-Commerce oriented search algorithm called A9. What differs it from Google’s algorithm is that it puts a strong emphasis on sales conversions. Amazon In terms of Amazon’s autocorrect implementation it consists of all the previously mentioned components, but since it’s a marketplace its suggestions ranking formula seems to include the factor of how attractive a suggestion can be to you in terms of sales. also has its own algorithm based on internal domain/pins/pinners relevance. Pinterest How it works Let’s now think about how spell correction can be done. There are few ways, but the important thing is that there is no purely programmatic way which will convert your mistyped “ipone” into “iphone” (at least with decent quality). Mostly there has to be a the system is based on. The data set can be: data set A dictionary of properly spelled words. In its turn it can be: Based on your real data. The idea here is that mostly in the the spelling is correct and then for each typed word the system just tries to find a word which is most similar to that (we’ll speak about how exactly it can be done shortly) dictionary made up from your data Or can be based on an which has nothing to do with your data. The problem which may arise here is that your data and the external dictionary can be too different: some words may be missing in the dictionary, some words may be missing in your data. E.g. like in these cases: external dictionary But it might still make sense for smaller data collections as then there’s a higher chance the search query will be corrected at all Not just dictionary-based, but , like if I search for “white ” Google understands that I mean a bear: context-aware ber But if I change it to “dark ” it understands I mean beer: ber The context may be not just a neighbor word in your query, but your location, date of time, current sentence’s grammar (to let’s say change “there” to “their” or not), your search history and virtually any other things that can affect your intent. Another classical approach is to use as the data set for spell correction. It’s even more utilized in autocomplete functionality, but makes sense for autocorrect too. The idea here is that mostly users are right with spelling, therefore we can use words from their search history as a source of truth even if we don’t have the words in our documents nor we use an external dictionary. Context-awareness is also possible here. previous search queries Another approach is to use your users’ previous search queries and/or your dictionary and/or documents to figure out some and use just them to correct new search queries. There’s even a patent about this correction rules https://patents.google.com/patent/US6618697B1/en For all the approaches can be used different algorithms of searching and evaluation of candidate spell corrections: From simplest like just comparison of a given word with all the words in the dictionary Early rejects algorithms that allow to narrow down the list of candidates significantly (that we will look in details below) Finite automatons to improve performance of finding candidates (Lucene’s way) of different kinds Probabilistic models, e.g. Hidden Markov Model that Etsy utilize on a basis of previous search queries To different machine learning techniques that often require large training data Looking at how fast AI, machine learning and semantic search have been evolving lately I believe in this decade the landscape of spell correction techniques may change dramatically, but for now the above approaches seem to be most used. And most solutions are based on your existing data collection and the dictionary made up from it. How to write your custom auto-correct Here I will describe a part of my own experience with making a website search with help of Manticore Search. I discovered this product about a year ago while working on some clients projects and I’m still using it in few of my projects due to its lightweight and fast search with a lot of out of the box functions. Let’s now speak about what tools you can use to add the autocorrect functionality to your system and at the same time go a little bit deeper into understanding how at least simpler techniques work. Todo that we will take one of popular custom search engines as they often provide the functionality we’re looking for. I like Manticore Search as in contrast to more known Elasticsearch, it is much more lightweight, easier to deal with as it’s SQL-native and works faster in most cases. It’s so SQL native that you can even connect to it with a standard MySQL client. They provide an official docker image, so I’ll use that to demonstrate how autocorrect works in Manticore Search: ➜ ~ docker ac28e94b3ca728fb431ba79255f81eb31ec264b5d9d49f1d2db973e08a32b9f run --name manticore -d manticoresearch/manticore 1 And inside the container I’ll run mysql to connect to the Manticore Search server running there: ➜ ~ docker exec -it manticore mysql
Welcome the MariaDB monitor. Commands ; \g.
Your MySQL id : Copyright © , , Oracle, MariaDB Corporation Ab others. help. clear the . to end with or connection is 1 Server version 5.5 .21 2000 2018 and Type 'help;' or '\h' for Type '\c' to current input statement It ships with 2 test tables that we can use for a quick play with spell correction: MySQL [(none)]> show tables; -----------+ | pq     | percolate | 2 rows in set (0.00 sec) +--------+ | Index  | Type      |
+--------+-----------+ | testrt | rt        |
+--------+-----------+ Let’s check the schema of testrt: MySQL [(none)]> describe testrt; -------- | id      | bigint |            |
| title   | field  | stored     |
| content | field  | stored     | 4 rows in set (0.00 sec) +---------+ +------------+ | Field   | Type   | Properties |
+---------+--------+------------+ | gid     | uint   |            |
+---------+--------+------------+ and insert few documents into it. Let it be movie titles: > (title) ( ),( ),( ),( ),( ),( ),( ),( ),( ),
( s List'); , ( sec) MySQL [(none)] insert into testrt values 'The Godfather' 'The Wizard of Oz' 'Combat!' 'The Shawshank Redemption' 'Pulp Fiction' 'Casablanca' 'The Godfather: Part II' 'Mortal Kombat' '2001: A Space Odyssey' 'Schindler\' Query OK 10 rows affected 0.00 We can now see all our documents in the index: MySQL [(none)]> select from testrt;
+---------------------+------+--------------------------+---------+
| | | | |
+---------------------+------+--------------------------+---------+
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
+---------------------+------+--------------------------+---------+
10 rows in set (0.00 sec) * id gid title content 1657719407478046741 0 The Godfather 1657719407478046742 0 The Wizard of Oz 1657719407478046743 0 Combat! 1657719407478046744 0 The Shawshank Redemption 1657719407478046745 0 Pulp Fiction 1657719407478046746 0 Casablanca 1657719407478046747 0 The Godfather: Part II 1657719407478046748 0 Mortal Kombat 1657719407478046749 0 2001: A Space Odyssey 1657719407478046750 0 Schindler's List What has just happened: when we inserted the titles not just Manticore Search saved them as is, but it made a lot of things essential for natural language processing (NLP): tokenization (to split the titles into words), normalization (to lowercase everything) and many other things, but there was one important for us which is that it has split the words into trigrams they consist from. For example “Combat!” (or actually “combat” after normalization) was split into . So why is that important? “com”, “omb”, “mba”, “bat” To answer that let’s assume we make a mistype in “combat” and type “comabt” instead. If we now want “combat” to be found how would we do that? The options are: We could go through our whole dictionary and compare each word with our keyword (“comabt”), then we would evaluate the difference between the 2 words. It’s called the Levenshtein distance. There are to calculate it for a given pair of words, but the problem is that even if you can do that fast for 2 words it may take you a while to compare each word from your dictionary with the given word few ways So it would be good to compare not all dictionary words, but only those that have higher chance to be a correction for the given word. And here comes the idea of trigrams — if we split all the dictionary words into trigrams and the search keywords too we can now operate those smaller tokens to find the candidates. So in this case what’s done internally is that Manticore Search first splits “comabt” into infixes: “com”, “oma”, “mab” and “abt” and then finds the corresponding words in the dictionary as when the document was inserted it also did the same. Since the complexity of this algorithm is not very high (much lower than comparing each word with each other) Manticore quickly finds that there’s a word “combat” which also has “com” and it’s the only candidate word. So all it has to do after that is to make sure the candidate word doesn’t differ very much from the given word. It calculates the Levensthein distance, figures it’s not greater than the limit (4 by default) and returns the candidate: MySQL [(none)]> call qsuggest( , ); ---------- 1 row in set (0.00 sec) 'comabt' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | combat  | 2        | 1    |
+---------+----------+------+ In other cases there may be more candidates. For example if you search for “combat” there is one word in the dictionary which exactly matches your query (the Levenshtein distance is 0), but there’s another which you might mean and CALL SUGGEST returns it too: MySQL [(none)]> call qsuggest( , ); ---------- | combat  | 0        | 1    | 2 rows in set (0.00 sec) 'combat' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | kombat  | 1        | 1    |
+---------+----------+------+ If you enter 2 words CALL QSUGGEST only process your last one: MySQL [(none)]> call qsuggest( , ); ---------- | combat  | 0        | 1    | 2 rows in set (0.00 sec) 'mortal combat' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | kombat  | 1        | 1    |
+---------+----------+------+ So how do I use this functionality in my application?” you may ask. It’s quite simple. Just: keep sending the search query to CALL QSUGGEST after each new character and show it’s output to the user Here’s the log of what it would give in the case of our dataset, note the input (after “call qsuggest”) and the output (in column “suggest”): MySQL [(none)]> call qsuggest( , );
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest( , );
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest( , );
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest( , ); ---------- 1 row in set (0.01 sec)
MySQL [(none)]> call qsuggest( , ); ---------- 1 row in set (0.00 sec)
MySQL [(none)]> call qsuggest( , ); ---------- 1 row in set (0.00 sec)
MySQL [(none)]> call qsuggest( , );
Empty set (0.01 sec)
MySQL [(none)]> call qsuggest( , );
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest( , );
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest( , ); ---------- | combat  | 2        | 1    | 2 rows in set (0.00 sec)
MySQL [(none)]> call qsuggest( , ); ---------- | combat  | 1        | 1    | 2 rows in set (0.00 sec)
MySQL [(none)]> call qsuggest( , ); ---------- | combat  | 0        | 1    | 2 rows in set (0.00 sec) 'm' 'testrt' 'mo' 'testrt' 'mor' 'testrt' 'mort' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | mortal  | 2        | 1    |
+---------+----------+------+ 'morta' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | mortal  | 1        | 1    |
+---------+----------+------+ 'mortal' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | mortal  | 0        | 1    |
+---------+----------+------+ 'mortal c' 'testrt' 'mortal co' 'testrt' 'mortal com' 'testrt' 'mortal comb' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | kombat  | 3        | 1    |
+---------+----------+------+ 'mortal comba' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | kombat  | 2        | 1    |
+---------+----------+------+ 'mortal combat' 'testrt' +---------+ +------+ | suggest | distance | docs |
+---------+----------+------+ | kombat  | 1        | 1    |
+---------+----------+------+ Conclusions Autocorrect is a very nice feature commonly used in many systems that helps users to find better results and site owners to not lose a user frustrated about no results due to a mistype or an incorrect query There are many ways how it can be implemented Google’s, Amazon’s, Pinterest’s, Etsy’s and other big sites’ implementations seem to be rather complicated and based on a non-trivial algorithms But in many cases something much simpler may also make sense Manticore Search can be used to provide needed functionality. By the way there’s an interactive course about it on their website

Amazon

Google

How To Develop Your Custom Autocorrect Implementation with Manticore [A Step by Step Guide]

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Bite-Sized Tips To Make Chinese Full-Text Search

3 Years After Forking Sphinx: A Brief Report on Manticore Search

Designing a search experience your users will come back for: a guide for web platform owners

40 Stories To Learn About Elasticsearch

A Hierarchy of Search

A Look at Using Elixir Streams, Elasticsearch & AWS S3

Bite-Sized Tips To Make Chinese Full-Text Search

3 Years After Forking Sphinx: A Brief Report on Manticore Search

Designing a search experience your users will come back for: a guide for web platform owners

40 Stories To Learn About Elasticsearch

A Hierarchy of Search

A Look at Using Elixir Streams, Elasticsearch & AWS S3

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps