DEV Community: Gregdevogo

Introduction to full-text operators and basic search

Gregdevogo — Wed, 30 Sep 2020 14:05:33 +0000

All search operations in Manticore Search are based on standard boolean operators (AND, OR, NOT) possible to be used in combination and free order to combine or exclude keywords in a search for more relevant results.

The default and the simplest full-text operator is AND which is assumed when you just enumerate few words in the search.

AND is a default operator with which the ‘fast slow’ query will return documents that have both terms: ‘fast’ and ‘slow’. If one term is in a document and the other is not, the document will be not included in the resulting list. By default, the words will be searched in all available full-text fields.

SELECT * FROM testrt WHERE MATCH('fast slow');

OR is used to match any term (or both). The terms are to be separated with a vertical line, e.g. ‘fast | slow’. It will find documents with either ‘fast’ or ‘slow’.

SELECT * FROM testrt WHERE MATCH('fast | slow');

he OR operator has a higher precedence than the AND, so the query ‘find me fast|slow’ can be interpreted as ‘find me (fast|slow)’:

SELECT * FROM testrt WHERE MATCH('find me fast | slow');

NOT makes sure the term marked with ‘-’ or ‘!’ is not in the results. Any documents containing such term will be excluded. E.g ‘fast !slow’ will find documents with ‘fast’ if only there’s no ‘slow’ in them. Be careful using it trying to reduce the search, as it may become too specific and can rule out good documents.

SELECT * FROM testrt WHERE MATCH('find !slow');
SELECT * FROM testrt WHERE MATCH('find -slow');

MAYBE is a special operator that works like the ‘OR’, but requires the left term to always be in the results while the right term is optional. But when both are met the document will get a higher search rank. E.g. ‘fast MAYBE slow’ will find documents with either ‘fast’ or ‘slow’, but the documents including both terms will have a higher score.

SELECT * FROM testrt WHERE MATCH('find MAYBE slow');

Usage examples

Let’s connect to Manticore using mysql client:

mysql -P9306 -h0

For boolean searches the OR ( ‘|’) can be used:

MySQL [(none)]> select * from testrt where match('find | me fast');  
+------+------+------------------------+----------------+  
| id   | gid  | title                  | content        |  
+------+------+------------------------+----------------+  
|    1 |    1 | find me                |  fast and quick|  
|    2 |    1 | find me fast           |  quick         |  
|    6 |    1 | find me fast now       |  quick         |  
|    5 |    1 | find me quick and fast |  quick         |  
+------+------+------------------------+----------------+  
4 rows in set (0.00 sec)

The OR operator has higher precedence than AND, the query ‘find me fast|slow’ is interpreted as ‘find me (fast|slow)’:

MySQL [(none)]> SELECT * FROM testrt WHERE MATCH('find me fast|slow');  
+------+------+------------------------+----------------+  
| id   | gid  | title                  | content        |  
+------+------+------------------------+----------------+  
|    1 |    1 | find me                |  fast and quick|  
|    2 |    1 | find me fast           |  quick         |  
|    6 |    1 | find me fast now       |  quick         |  
|    3 |    1 | find me slow           |  quick         |  
|    5 |    1 | find me quick and fast |  quick         |  
+------+------+------------------------+----------------+  
5 rows in set (0.00 sec)

For negations, the operator NOT can be specified as ‘-‘ or ‘!’ :

MySQL [(none)]> select * from testrt where match('find me -fast');  
+------+------+--------------+---------+  
| id   | gid  | title        | content |  
+------+------+--------------+---------+  
|    3 |    1 | find me slow |  quick  |  
+------+------+--------------+---------+  
1 row in set (0.00 sec)

It must be noted that full negation queries are not supported in Manticore by default and it’s not possible to run just ‘-fast’ (will be possible since v3.5.2).

Another basic operator is MAYBE. The term defined by the MAYBE can be present or not in the documents. If it’s present, it will influence the ranking and documents having it will be ranked higher.

MySQL [(none)]> select * from testrt where match('find me MAYBE slow');  
+------+------+------------------------+----------------+  
| id   | gid  | title                  | content        |  
+------+------+------------------------+----------------+  
|    3 |    1 | find me slow           |  quick         |  
|    1 |    1 | find me                |  fast and quick|  
|    2 |    1 | find me fast           |  quick         |  
|    5 |    1 | find me quick and fast |  quick         |  
|    6 |    1 | find me fast now       |  quick         |  
+------+------+------------------------+----------------+  
5 rows in set (0.00 sec)

Field operator

If we want to limit the search to only a specific field operator ‘@’ can be used:

mysql> select * from testrt where match('@title find me fast');  
+------+------+------------------------+---------+  
| id   | gid  | title                  | content |  
+------+------+------------------------+---------+  
|    2 |    1 | find me fast           |  quick  |  
|    6 |    1 | find me fast now       |  quick  |  
|    5 |    1 | find me quick and fast |  quick  |  
+------+------+------------------------+---------+  
3 rows in set (0.00 sec)

We can also specify multiple fields to limit the search:

mysql> select * from testrt where match('@(title,content) find me fast');  
+------+------+------------------------+----------------+  
| id   | gid  | title                  | content        |  
+------+------+------------------------+----------------+  
| 1    |    1 | find me                | fast and quick |  
| 2    |    1 | find me fast           | quick          |  
| 6    |    1 | find me fast now       | quick          |  
| 5    |    1 | find me quick and fast | quick          |  
+------+------+------------------------+----------------+  
4 rows in set (0.00 sec)

The field operator can also be used to perform a restriction for the search to be made only in the first x words. For example:

mysql> select * from testrt where match('@title lazy dog');
+------+------+----------------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                                      | content                               |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog                                |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog          |  The five boxing wizards jump quickly |
|    8 |    1 | The  brown and beautiful fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
4 rows in set (0.00 sec)

However, if we search in 5 first words only we get nothing:

mysql> select * from testrt where match('@title[5] lazy dog');  
Empty set (0.00 sec)

In some situations, the search could be performed over multiple indexes that may not have the same full-text fields.

By default specifying a field that doesn’t exist in the index will result in a query error. To overcome this, the special operator ‘@@relaxed’ can be used:

mysql> select * from testrt where match(‘@(title,keywords) lazy dog’);  
ERROR 1064 (42000): index testrt: query error: no field ‘keywords’ found in schema

mysql> select * from testrt where match('@@relaxed @(title,keywords) lazy dog');
+------+------+----------------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                                      | content                               |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog                                |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog          |  The five boxing wizards jump quickly |
|    8 |    1 | The  brown and beautiful fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
3 rows in set, 1 warning (0.01 sec

Fuzzy search

Fuzzy matching allows to match only some of the words from a query string, for example:

mysql> select * from testrt where match('"fox bird lazy dog"/3');
+------+------+----------------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                                      | content                               |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog                                |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog          |  The five boxing wizards jump quickly |
|    8 |    1 | The  brown and beautiful fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
3 rows in set (0.00 sec)

In this case we use the QUORUM operator and specify that it is fine to match only 3 of the words. The search with ‘/1’ is equivalent of the OR boolean search while the search with ‘/N’ where the N is the number of the input words is equivalent of the AND search.

Instead of an absolute number, you can also specify a number between 0.0 and 1.0 (standing for 0% and 100%), and Manticore will match only the documents with at least the specified percentage of the given words. The same example above could also have been written as “fox bird lazy dog”/0.3 and it would match documents with at least 30% of the 4 words.

mysql> select * from testrt where match('"fox bird lazy dog"/0.3');
+------+------+----------------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                                      | content                               |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog                                |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog          |  The five boxing wizards jump quickly |
|    8 |    1 | The  brown and beautiful fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
3 rows in set (0.00 sec)

Advanced operators

Besides the simpler operators there are many advanced operators that are used more seldom, but in some cases can be absolutely necessary.

One of the most used advanced operators is a phrase operator.

The phrase operator will match only if the given words are found in the verbatim specified order. This will also restrict the words to be found in the same field:

mysql> SELECT * FROM testrt WHERE MATCH('"quick brown fox"');
+------+------+-------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title            | content                               |
+------+------+-------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog            |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+-------------------------------------------------------------------+---------------------------------------+
2 rows in set (0.00 sec)

A more relaxed version of the phrase operator is the strict order operator.

The order operator requires the words to be found in the exact same order as specified, but other words are accepted between:

mysql> SELECT * FROM testrt WHERE MATCH('find << me << fast');  
+------+------+------------------------+---------+  
| id   | gid  | title                  | content |  
+------+------+------------------------+---------+  
|    2 |    1 | find me fast           |  quick  |  
|    6 |    1 | find me fast now       |  quick  |  
|    5 |    1 | find me quick and fast |  quick  |  
+------+------+------------------------+---------+  
3 rows in set (0.00 sec)

Another pair of operators who work with word positions are the start/end field operators.

These will restrict a word to be present at the start or the end of a field.

mysql> SELECT * FROM testrt WHERE MATCH('^find me fast$');  
+------+------+------------------------+---------+  
| id   | gid  | title                  | content |  
+------+------+------------------------+---------+  
|    2 |    1 | find me fast           |  quick  |  
|    5 |    1 | find me quick and fast |  quick  |  
+------+------+------------------------+---------+  
2 rows in set (0.00 sec)

The proximity operator is similar to the AND operator but adds the maximum distance between the words so they can still be considered a match. Let’s take this example with just the AND operator:

mysql> SELECT * FROM testrt WHERE MATCH('brown fox jumps');
+------+------+----------------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                                      | content                               |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog                                |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog          |  The five boxing wizards jump quickly |
|    8 |    1 | The  brown and beautiful fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
3 rows in set (0.00 sec)

Our query returns 2 results: one in which all the words are close to each other and the second where one of the words is more distant.

If we want to match only if the words are within a certain distance, we can restrict that with the proximity operator:

mysql> SELECT * FROM testrt WHERE MATCH('"brown fox jumps"~5');

mysql> SELECT * FROM testrt WHERE MATCH('"brown fox jumps"~5');
+------+------+---------------------------------------------+---------------------------------------+
| id   | gid  | title                                       | content                               |
+------+------+---------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+---------------------------------------------+---------------------------------------+
1 row in set (0.00 sec)

A more generalized version of the proximity operator is the NEAR operator. In the case of the proximity a single distance is specified over a bag of words, while the NEAR operator works with 2 operands, that can be either single words or expressions.

In the following example, ‘brown’ and ‘fox’ must be within a distance of 2 and ‘fox’ and ‘jumps’ within a distance of 6:

mysql> SELECT * FROM testrt WHERE MATCH('brown NEAR/2 fox NEAR/6 jumps');
+------+------+-------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                             | content                               |
+------+------+-------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog                       |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+-------------------------------------------------------------------+---------------------------------------+
2 rows in set (0.00 sec)

The query leaves out one document which doesn’t match the first NEAR condition (the last one here):

mysql> SELECT * FROM testrt WHERE MATCH('brown NEAR/3 fox NEAR/6 jumps');
+------+------+----------------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                                      | content                               |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
|    4 |    1 | The quick brown fox jumps over the lazy dog                                |  The five boxing wizards jump quickly |
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog          |  The five boxing wizards jump quickly |
|    8 |    1 | The  brown and beautiful fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+----------------------------------------------------------------------------+---------------------------------------+
3 rows in set (0.09 sec)

A variation of the NEAR operator is NOTNEAR, which matches only if the operands have a minimum distance between them.

mysql> SELECT * FROM testrt WHERE MATCH('"brown fox" NOTNEAR/5 jumps');
+------+------+-------------------------------------------------------------------+---------------------------------------+
| id   | gid  | title                                                             | content                               |
+------+------+-------------------------------------------------------------------+---------------------------------------+
|    7 |    1 | The quick brown fox take a step back and  jumps over the lazy dog |  The five boxing wizards jump quickly |
+------+------+-------------------------------------------------------------------+---------------------------------------+
1 row in set (0.00 sec)

Manticore can also detect sentences in plain texts and paragraphs in HTML content.

For indexing sentences, the index_sp option needs to be enabled, while paragraphs also require html_strip=1

Let’s take the following example:

mysql> select * from testrt where match('"the brown fox" jumps')\G  
*************************** 1. row ***************************  
id: 15  
gid: 2  
title: The brown fox takes a step back. Then it jumps over the lazydog  
content:  
1 row in set (0.00 sec)

The document includes 2 sentences, while the phrase is found in the first one ‘jumps’ is only in the second sentence.

With the SENTENCE operator we can restrict the search to match only if the operands are in the same sentence:

mysql> select * from testrt where match('"the brown fox" SENTENCE jumps')\G

Empty set (0.00 sec)

We can see that the document is not a match anymore. If we correct the search query so all the words are from the same sentence we’ll see a match:

mysql> select * from testrt where match('"the brown fox" SENTENCE back')\G  
*************************** 1. row ***************************  
id: 15  
gid: 2  
title: The brown fox takes a step back. Then it jumps over the lazydog  
content:  
1 row in set (0.00 sec)

To demonstrate the PARAGRAPH let’s use the following search:

mysql> select * from testrt where match('Samsung Galaxy'); +------+------+-------------------------------------------------------------------------------------+---------+ | id | gid | title | content | +------+------+-------------------------------------------------------------------------------------+---------+ | 9 | 2 | <h1>Samsung Galaxy S10</h1>Is a smartphone introduced by Samsung in 2019 | | | 10 | 2 | <h1>Samsung</h1>Galaxy,Note,A,J | | +------+------+-------------------------------------------------------------------------------------+---------+ 2 rows in set (0.00 sec)

These 2 documents have different HTML tags

If we add the PARAGRAPH only the document with the search terms found in the single tag will remain.

The more general operators are ZONE and it’s variant ZONESPAN. “zone” is text inside an HTML or XML tag.

The tags to be considered for the zones need to be declared in the ‘index_zones’ setting, like ‘index_zones = h*, th, title’.

For example:

mysql> select * from testrt where match('hello world');  
+------+------+-------------------------------+---------+  
| id   | gid  | title                         | content |  
+------+------+-------------------------------+---------+  
|   12 |    2 | Hello world                   |         |  
|   14 |    2 | <h1>Hello world</h1>          |         |  
|   13 |    2 | <h1>Hello</h1> <h1>world</h1> |         |  
+------+------+-------------------------------+---------+  
3 rows in set (0.00 sec)

We have 3 documents, where ‘hello’ and ‘world’ are found in plain text, in different zones of the same type or in a single zone.

mysql> select * from testrt where match('ZONE:h1 hello world');  
+------+------+-------------------------------+---------+  
| id   | gid  | title                         | content |  
+------+------+-------------------------------+---------+  
|   14 |    2 | <h1>Hello world</h1>          |         |  
|   13 |    2 | <h1>Hello</h1> <h1>world</h1> |         |  
+------+------+-------------------------------+---------+  
2 rows in set (0.00 sec)

In this case, the words are present in H1 zones, but they are not required to be in the same zone. If we want to limit the match to a single zone, we can use ZONESPAN:

mysql> select * from testrt where match('ZONESPAN:h1 hello world');  
+------+------+----------------------+---------+  
| id   | gid  | title                | content |  
+------+------+----------------------+---------+  
|   14 |    2 | <h1>Hello world</h1> |         |  
+------+------+----------------------+---------+  
1 row in set (0.00 sec)

Hopefully, from this article, you’ve learned how full-text search operators work in Manticore. If you are looking for a hands-on experience to learn it even better you can try our interactive course right now in your browser.

A new way of tokenization of Chinese or How to make Chinese full-text search

Gregdevogo — Thu, 10 Sep 2020 20:54:15 +0000

Today I'd like to highlight the challenge of search functionality in Chinese. In this article, we will go through the main difficulties of full-text search implementation for CJK languages and how to overcome them with the help of Manticore Search.

Chinese search difficulties

The Chinese language belongs to the so-called CJK language family (Chinese, Japanese, and Korean). They are probably the most complicated languages for full-text search implement as in them word meanings heavily depend on numerous hieroglyphs variations and their sequences and the characters are not split up into words.

Chinese languages specifics:

Chinese hieroglyphs do not have an upper or lower case. They have only one notion, regardless of the context.
There is no additional decoration for the letters, as in Arabic, for example. There are no spaces between words in sentences.

So what's the point? To find an exact match in a full-text search, we have to face the challenge of tokenization whose main task is to break down the text into low-level units of values that can be searched by the user.

Tokenization/Segmentation of Chinese

To be more specific, tokenization is the process of turning a meaningful piece of data, a word for example, into a unique identifier called a token that represents a piece of data in the system. In full-text search engines tokens serve as a reference to the original data, but cannot be used to guess those actual values.

In most languages, we use spaces or special characters to divide the text into fragments. However, in Chinese and the other CJK languages, it is not possible due to its morphological properties. However, we still need that to be done. And that process is called segmentation.

In other words for Chinese segmentation is a prerequisite to tokenization.

Here is an example showing the difference between English and Chinese tokenization.

As you see the Chinese sentence is half as short and doesn't have any spaces, commas, and is not even split into words, each word here is represented by a hieroglyphic character or few. Here is a quantitative comparison:

Another challenge is that Chinese hieroglyphs may have different meanings depending on their sequences and combinations. Let's take a look at different meanings of hieroglyphical combinations:

Here we can see the combination of two hieroglyphic characters "简单" which means "Simplicity", but if we take each of the hieroglyphs separately, they will have different meanings "简" (simple) and "单" (single).

In some cases, depending on where you put a boundary between the words the meanings may be different. For example:

The problem, as you can see, is that a group of characters can be segmented differently, resulting in different values.

Let's look at possible ways of solving the Chinese tokenization/segmentation problems.

Implementations

There are a few approaches for Chinese texts segmentation, but the main two are:

N-grams: considers the overlapping groups of "N" neighboring Chinese characters as tokens, where "N" could be 1 - Uni; 2 - Bi; 3- Tri; and so on "-grams".
Dictionary-based: performs word segmentation based on a dictionary.

The easiest way of Chinese text segmentation assumes the use of N-grams. The algorithm is straightforward, but it is known to lack in quality and gives considerable overhead that grows with the length of the text being processed because each N-gram is a separate token which makes the tokens dictionary bigger and processing a search query much more complicated. It historically was the common way of CJK texts indexation in Manticore Search.

In Manticore Search version 3.1.0 was introduced a new way of segmentation of Chinese texts based on the ICU text segmentation algorithm which follows the second approach - dictionary-based segmentation.

Benefits of using ICU

ICU is a set of open-source libraries providing Unicode and Globalization support for software applications. Along with many other features, it solves the task of text boundaries' determination. ICU algorithms locate positions of words, sentences, paragraphs within a range of text, or identify locations that would be suitable for line wrapping when displaying the text.

The algorithm of how the ICU segmentation works in Manticore can be briefly described as follows:

The original text is regarded as an array of symbols.
Then Manticore goes through the array and if it finds a set of * Chinese symbols it passes that along to the ICU library to process them.
The segmented parts of the Chinese text replace the original, unsegmented parts.
Other natural language processing algorithms (charset_table, wordforms, etc.) are applied to the modified text like in a common segmentation workflow.

To enable the ICU-Chinese segmentation, the following index configuration options must be set:

morphology = icu_chinese
charset_table = cjk / chinese

An example of configuring ICU-Chinese text tokenization

Index configuration

To set up an index for proper Chinese segmentation there are 2 index settings we need to touch: 'charset_table' and 'morphology'.
For the charset table, there is a built-in alias 'chinese' which contains all Chinese characters.

First, let's connect to Manticore:

mysql -P 9306 -h0

And create our table:

mysql> CREATE TABLE testrt (title TEXT, content TEXT, gid INT) charset_table = 'chinese' morphology = 'icu_ chinese';

Basic usage

Let's insert into the index a simple mixed Chinese-English sentence '买新的Apple电脑' ('I like Apple computers'):

mysql> INSERT INTO testrt (title, content, gid) VALUES ( 'first record', '买新的Apple电脑', 1 );

To check if our Chinese content is tokenized as expected we can run CALL KEYWORDS against our index:

mysql> call keywords('买新的Apple电脑', 'testrt');
+------+-----------+------------+
| qpos | tokenized | normalized |
+------+-----------+------------+
| 1    | 买        | 买         |
| 2    | 新的      | 新的        |
| 3    | 电脑      | 电脑        |
+------+------ ----+------------+

We can see that the Chinese text got broken into 4 words, as expected.

And now let's make a search against our content field with a query phrase 'Apple电脑' ('Apple computers'):

mysql> SELECT * FROM testrt WHERE MATCH ('@content Apple电脑');
+---------------------+------+--------------+----------------------+
| id                  | gid  | title        | content              |
+---------------------+------+--------------+----------------------+
| 5477080993472970753 |    1 | first record | 买新的Apple电脑        |
+---------------------+------+--------------+----------------------+

As we see, the search has been successfully executed and we got the expected result despite the fact that both the original sentence and the query phrase we used in this example didn't have any separators between the words.

We can use 'SHOW META' command to see extended information about the query and make sure that our sentence was properly segmented into separate words:

mysql> SHOW META;
+---------------+--------+
| Variable_name | Value  |
+---------------+--------+
| total         | 1      |
| total_found   | 1      |
| time          | 0.199  |
| keyword[0]    | 电脑    |
| docs[0]       | 1      |
| hits[0]       | 1      |
+---------------+--------+

We see that our search phrase was indeed split up into 'apple' and '电脑' ('computers') just as we supposed it to be done.

Conclusion

Implementing a Chinese full-text search is not an easy task, but Manticore Search copes with it without any troubles out of the box. So if you need a simple and reliable Chinese search for your service or application, you know what to use. You can also find this article in the form of an interactive course here.

How to highlight search results

Gregdevogo — Thu, 23 Apr 2020 13:08:40 +0000

In this tutorial you will learn how to highlight search results in Manticore >Search. You can benefit from search results highlighting if you want to improve >readability of search results in your application or a web site.

Highlighting allows you to get snippets of search results with matching keywords highlighted. It helps to improve your application’s search experience.

Introduction

You can highlight keywords in text in Manticore Search using several methods.

Statement CALL SNIPPETS allows getting a list of fragments from documents (called snippets) that contain the matches. It can be used separately from a search query to highlight a string or a list of strings. Here is an example:

CALL SNIPPETS('my text with keyword', 'index', 'keyword');

Function SNIPPET() builds a snippet from provided data and query, using specified index settings. This function is mostly used in a SELECT statement to highlight given text, field value or text fetched from another source using a UDF (user-defined function). It can be used for highlighting the same query as in the match clause or another one, it’s up to you. Like this:

SELECT SNIPPET(content,'camera') FROM index WHERE MATCH('camera');

Function HIGHLIGHT() can be used to highlight search results. This function was added in Manticore 3.2.2. It makes it easier to highlight keywords in your documents when you store them in Manticore, not just get them indexed. Here is an example of the call:

SELECT HIGHLIGHT() FROM index WHERE MATCH('text feature');

The first two ‘CALL SNIPPETS’ and ‘SNIPPET()’ provide the ability to get a list of parts of documents (called snippets) that contain the matches to the searched keyword. The last one ‘HIGHLIGHT()’ fetches all available fields from document storage and highlights them against the given query. Unlike SNIPPET(), HIGHLIGHT() supports field syntax in queries.

All three share the same highlighting options which we’ll discuss in the next steps. In this tutorial, we’ll show examples of using HIGHLIGHT().

Let’s assume you have an index called ‘highlight’ with the following settings:

index highlight
{
        type = rt
        path = highlight
        rt_field = title
        rt_field = content
        rt_attr_uint = gid
        stored_fields = title, content
        index_sp = 1
        html_strip = 1
}

Basic usage

A quick example:

First, add a document:

INSERT INTO highlight(title,content,gid) VALUES('Syntax highlighting','Syntaxhighlighting is a feature of text editors that are used for programming, scripting, or markuplanguages, such as HTML. The feature displays text, especially source code, in different colors and fonts according to the category of terms.[1] This feature facilitates writing in a structured language such as a programming language or a markup language as both structures and syntax errors are visually distinct. Highlighting does not affect the meaning of the text itself;it is intended only for human readers.',1);

And then do SELECT HIGHLIGHT():

SELECT HIGHLIGHT() AS h FROM highlight WHERE MATCH('text feature')\G
*************************** 1. row ***************************
h: Syntax highlighting is a <b>feature</b> of <b>text</b> editors that are used ... , such as HTML. The <b>feature</b> displays <b>text</b>, especially source code, in ... of terms.[1] This <b>feature</b> facilitates writing in a structured ... affect the meaning of the <b>text</b> itself; it is intended ...

By default, any of the matching words are highlighted with tag ‘bold’ and at most 5 words are picked around each match to form a passage.
Passages are separated with ‘…’ by default.

The HTML tag is used to highlight matches as the snippets are often displayed in an HTML content, but you can customise the behaviour with “before_match”, “after_match”, “around” and “chunk_separator” settings. For example:

SELECT HIGHLIGHT({before_match='*',after_match='*',around=1,chunk_separator='###'}) AS h FROM highlight WHERE MATCH('text feature')\G
*************************** 1. row ***************************
h: ### a *feature* of *text*###. The *feature* displays *text*###] This *feature* facilitates### the *text* itself###

Control size of the snippet

Default settings put a limit (under the setting with same name – “limit”) of 256 characters as maximum snippet size. You can change it like this:

SELECT HIGHLIGHT({limit=10}) AS h FROM highlight WHERE MATCH('text feature')\G
*************************** 1. row ***************************
h:  ...  a <b>feature</b> ...

Another limit which can be changed is number of words included in snippet which is defined by “limit_words”:

SELECT HIGHLIGHT({limit_words=5},'content') AS h FROM highlight WHERE MATCH('text feature')\G
*************************** 1. row ***************************
h: ... . The <b>feature</b> displays <b>text</b>, especially ...

It is also possible to limit number of passages, for example, if we want to get just one passage:

SELECT HIGHLIGHT({limit_passages=1}) AS h FROM highlight WHERE MATCH('text feature')\G
*************************** 1. row ***************************
h:  ...  languages, such as HTML. The <b>feature</b> displays <b>text</b>, especially source code, in ...

The default behavior of the HIGHLIGHT() function is to return found passages separated by defined separator within the space defined by the limit.
As it’s possible that the limit may not be enough for all passages we may get only a part of the possible passages.

To demonstrate it let’s add first a document with a longer text.

INSERT INTO highlight(title,content) values('wikipedia','Syntax highlighting is a feature of text editors that are used for programming, scripting, or markup languages, such as HTML. The feature displays text, especially source code, in different colors and fonts according to the category of terms.[1] This feature facilitates writing in a structured language such as a programming language or a markup language as both structures and syntax errors are visually distinct. Highlighting does not affect the meaning of the text itself; it is intended only for human readers. Syntax highlighting is a form of secondary notation, since the highlights are not part of the text meaning, but serve to reinforce it. Some editors also integrate syntax highlighting with other features, such as spell-checking or code folding, as aids to editing which are external to the language. Contents 1Practical benefits 2Support in text editors 3Syntax elements 3.1Examples 4History and limitations 5See also 6References Practical benefits Highlighting the effect of missing delimiter (after watch=false) in Javascript Syntax highlighting is one strategy to improve the readability and context of the text; especially for code that spans several pages. The reader can easily ignore large sections of comments or code, depending on what they are looking for. Syntax highlighting also helps programmers find errors in their program. For example, most editors highlight string literals in a different color. Consequently, spotting a missing delimiter is much easier because of the contrasting color of the text. Brace MATCHing is another important feature of many popular editors. This makes it simple to see if a brace has been left out or locate the MATCH of the brace the cursor is on by highlighting the pair in a different color. A study published in the conference PPIG evaluated the effects of syntax highlighting on the comprehension of short programs, finding that the presence of syntax highlighting significantly reduces the time taken for a programmer to internalize the semantics of a program.[2] Additionally, data gathered FROM an eye-tracker during the study suggested that syntax highlighting enables programmers to pay less attention to standard syntactic components such as keywords. Support in text editors gedit supports syntax highlighting Some text editors can also export the colored markup in a format that is suitable for printing or for importing into word-processing and other kinds of text-formatting software; for instance asa HTML, colorized LaTeX, PostScript or RTF version of its syntax highlighting. There are several syntax highlighting libraries or "engines" that can be used in other applications, but are not complete programs in themselves, for example the Generic Syntax Highlighter (GeSHi) extension for PHP. For editors that support more than one language, the user can usually specify the language of the text, such as C, LaTeX, HTML, or the text editor can automatically recognize it based on the file extension or by scanning contents of the file. This automatic language detection presents potential problems. For example, a user may want to edit a document containing: morethan one language (for example when editing an HTML file that contains embedded Javascript code), a language that is not recognized (for example when editing source code for an obscure or relatively new programming language), a language that differs FROM the file type (for example when editing source code in an extension-less filein an editor that uses file extensions to detect the language). In these cases, it is not clear what language to use, and a document may not be highlighted or be highlighted incorrectly. Syntax elements Most editors with syntax highlighting allow different colors and text styles to be given to dozens of different lexical sub-elements of syntax. These include keywords, comments, control-flow statements, variables, and other elements. Programmers often heavily customize their settings in an attempt to show as much useful information as possible without making the code difficult to read. ');

Let’s highlight it now:

SELECT HIGHLIGHT({},'content') AS h FROM highlight WHERE MATCH('syntax')\G
*************************** 1. row ***************************
h: <b>syntax</b> highlighting is a feature of ... language as both structures and <b>syntax</b> errors are visually distinct. Highlighting ... *************************** 2. row *************************** h: ... version of its <b>syntax</b> highlighting. There are several <b>syntax</b> highlighting libraries ... highlighted incorrectly. <b>syntax</b> elements Most editors with <b>syntax</b> highlighting allow different ... different lexical sub-elements of <b>syntax</b>. These include keywords, comments, ...

For the newly added document, we see the HIGHLIGHT() doesn’t give us all the passages. We can increase the limit to overcome that, the question is how far. If we use too high value, the HIGHLIGHT() returns the full body of the content (including the highlights):

SELECT HIGHLIGHT({limit=10000},'content') AS h FROM highlight WHERE MATCH('syntax')\G
*************************** 1. row ***************************
h: <b>syntax</b> highlighting is a feature of text editors that are used for programming, scripting, or markuplanguages, such as HTML. The feature displays text, especially source code, in different colors and fonts according to the category of terms.[1] This feature facilitates writing in a structured language such as a programming language or a markup language as both structures and <b>syntax</b> errors are visually distinct. Highlighting does not affect the meaning of the text itself; it is intended only for human readers. *************************** 2. row *************************** h: <b>syntax</b> highlighting is a feature of text editors that are used for programming, scripting, or markuplanguages, such as HTML. The feature displays text, especially source code, in different colors and fonts according to the category of terms.[1] This feature facilitates writing in a structured language such as a programming language or a markup language as both structures and <b>syntax</b> errors are visually distinct. Highlighting does not affect the meaning of the text itself; it is intended only for human readers. <b>syntax</b> highlighting is a form of secondary notation, since the highlights are not part of the text meaning, but serve to reinforce it. Some editors also integrate <b>syntax</b> highlighting with other features, such as spell checking orcode folding, as aids to editing which are external to the language. Contents 1Practical benefits 2Support in text editors 3Syntax elements 3.1Examples 4History and limitations 5See also 6References Practical benefits Highlighting the effect of missing delimiter (after watch=false) in Javascript <b>syntax</b> highlighting is one strategy to improve the readability and context of the text; especially for code that spans several pages. The reader can easily ignore large sections of comments or code, depending on what they are looking for. <b>syntax</b> highlighting also helps programmers find errors in their program. For example, most editors highlight stringliterals in a different color. Consequently, spotting a missing delimiter is much easier because of the contrasting color of the text. Brace MATCHing is another important feature with many popular editors. This makes it simple to see if a brace has been left out or locate the MATCH of the brace the cursor is on by highlighting thepair in a different color. A study published in the conference PPIG evaluated the effects of <b>syntax</b> highlighting on the comprehension of short programs, finding that the presence of <b>syntax</b> highlighting significantly reduces the time taken for a programmer to internalise the semantics of a program.[2] Additionally, data gathered FROM an eye-tracker during the study suggested that <b>syntax</b> highlighting enables programmers to pay less attention to standard syntactic components such as keywords. Support in text editors gedit supports<b>syntax</b> highlighting Some text editors can also export the coloured markup in a format that is suitable for printing or for importing into word-processing and other kinds of text-formatting software; for instance asa HTML, colorized LaTeX, PostScript or RTF version of its <b>syntax</b> highlighting. There are several <b>syntax</b> highlighting libraries or "engines" that can be used in other applications, but are not complete programs in themselves, for example the Generic <b>syntax</b> Highlighter (GeSHi) extension for PHP. For editors thatsupport more than one language, the user can usually specify the language of the text, such as C, LaTeX, HTML,or the text editor can automatically recognize it based on the file extension or by scanning contents of the file. This automatic language detection presents potential problems. For example, a user may want to edit a document containing: more than one language (for example when editing an HTML file that contains embedded Javascript code), a language that is not recognized (for example when editing source code for an obscure or relatively new programming language), a language that differs FROM the file type (for example when editing source code in an extension-less file in an editor that uses file extensions to detect the language). In these cases, it is notclear what language to use, and a document may not be highlighted or be highlighted incorrectly. <b>syntax</b>elements Most editors with <b>syntax</b> highlighting allow different colors and text styles to be given to dozens of different lexical sub-elements of <b>syntax</b>. These include keywords, comments, control-flow statements, variables, and other elements. Programmers often heavily customize their settings in an attempt to show asmuch useful information as possible without making the code difficult to read.

If we want just the passages rather than whole text highlighted we need to use option “force_passages”:

SELECT HIGHLIGHT({limit=10000,force_passages=1},'content') AS h FROM highlight WHERE MATCH('syntax')\G
*************************** 1. row ***************************
h: <b>syntax</b> highlighting is a feature of ... language as both structures and <b>syntax</b> errors are visually distinct. Highlighting ... *************************** 2. row *************************** h: <b>syntax</b> highlighting is a feature of ... language as both structures and <b>syntax</b> errors are visually distinct. Highlighting ... intended only for human readers. <b>syntax</b> highlighting is a form of ... it. Some editors also integrate <b>syntax</b> highlighting with other features, such ... (after watch=false) in Javascript <b>syntax</b> highlighting is one strategy to ... what they are looking for. <b>syntax</b> highlighting also helps programmers find ... PPIG evaluated the effects of <b>syntax</b> highlighting on the comprehension of ... , finding that the presence of <b>syntax</b> highlighting significantly reduces the time ... during the study suggested that <b>syntax</b> highlighting enables programmers to pay ... in text editors gedit supports <b>syntax</b> highlighting Some text editors can ... version of its <b>syntax</b> highlighting. There are several <b>syntax</b> highlighting libraries or ... themselves, for example the Generic <b>syntax</b> Highlighter (GeSHi) extension for PHP ... be highlighted incorrectly. <b>syntax</b> elements Most editors with <b>syntax</b> highlighting allow different ... different lexical sub-elements of <b>syntax</b>. These include keywords, comments, control ...

Another possible way to get the whole text with highlights applied is to simply use limit=0:

SELECT HIGHLIGHT({limit=0},'content') AS h FROM highlight WHERE MATCH('text feature')\G
*************************** 1. row ***************************
h: Syntax highlighting is a <b>feature</b> of <b>text</b> editors that are used for programming, scripting, ormarkup languages, such as HTML. The <b>feature</b> displays <b>text</b>, especially source code, in different colors and fonts according to the category of terms.[1] This <b>feature</b> facilitates writing in a structuredlanguage such as a programming language or a markup language as both structures and syntax errors are visuallydistinct. Highlighting does not affect the meaning of the <b>text</b> itself; it is intended only for human readers. *************************** 2. row *************************** h: Syntax highlighting is a <b>feature</b> of <b>text</b> editors that are used for programming, scripting, ormarkup languages, such as HTML. The <b>feature</b> displays <b>text</b>, especially source code, in different colors and fonts according to the category of terms.[1] This <b>feature</b> facilitates writing in a structuredlanguage such as a programming language or a markup language as both structures and syntax errors are visuallydistinct. Highlighting does not affect the meaning of the <b>text</b> itself; it is intended only for human readers. Syntax highlighting is a form of secondary notation, since the highlights are not part of the <b>text</b> meaning, but serve to reinforce it. Some editors also integrate syntax highlighting with other features, suchas spell checking or code folding, as aids to editing which are external to the language. Contents 1Practical benefits 2Support in <b>text</b> editors 3Syntax elements 3.1Examples 4History and limitations 5See also 6References Practical benefits Highlighting the effect of missing delimiter (after watch=false) in Javascript Syntax highlighting is one strategy to improve the readability and context of the <b>text</b>; especially for code that spans several pages. The reader can easily ignore large sections of comments or code, depending on what they are looking for. Syntax highlighting also helps programmers find errors in their program. For example, most editors highlight string literals in a different color. Consequently, spotting a missing delimiter is much easier because of the contrasting color of the <b>text</b>. Brace MATCHing is another important <b>feature</b> with many popular editors. This makes it simple to see if a brace has been left out or locate the MATCH of the brace the cursor is on by highlighting the pair in a different color. A study published in the conference PPIG evaluated the effects of syntax highlighting on the comprehension of short programs, finding that the presence of syntax highlighting significantly reduces the time taken for a programmer to internalise the semantics of a program.[2] Additionally, data gathered FROM an eye-tracker during the study suggested that syntax highlighting enables programmers to pay less attention to standard syntactic components such as keywords. Support in <b>text</b> editors gedit supports syntax highlighting Some <b>text</b> editors can also export the coloured markup in a format that is suitable for printing or for importing into word-processing and other kinds of <b>text</b>-formatting software; for instance as a HTML, colorized LaTeX, PostScript or RTF version of its syntax highlighting. There are several syntax highlighting libraries or "engines" that can be used in other applications, but are not complete programs in themselves, for example the Generic Syntax Highlighter (GeSHi) extension for PHP. For editors that support more than one language, the user can usually specify the language of the <b>text</b>, such as C, LaTeX, HTML, or the <b>text</b> editor can automatically recognize it based on the file extension or by scanning contents of the file. This automatic language detection presents potential problems. For example, a user may want to edit a document containing: more than one language (for example when editing an HTML file that contains embedded Javascript code), a language that is not recognized (for example when editing source code for an obscure or relatively new programming language), a language that differs FROM the file type (for example when editing source code in an extension-less file in an editor that uses file extensions to detect the language). In these cases, it is not clear what language to use, and a document may not be highlighted or be highlighted incorrectly. Syntax elements Most editors with syntax highlighting allow different colors and <b>text</b> styles to be given to dozens of different lexical sub-elements of syntax. These include keywords, comments, control-flow statements, variables, and other elements. Programmers often heavily customize their settings in an attempt to show as much useful information as possible without making the code difficult to read.

HTML Stripping and boundaries

If our index has sentence detection, we can configure highlighting to not create passages that cross between sentences:

SELECT HIGHLIGHT({},'content') AS h FROM highlight WHERE MATCH('html text')\G
*************************** 1. row ***************************
h:  ...  highlighting is a feature of <b>text</b> editors that are used for ... markup languages, such as <b>HTML</b>. The feature displays <b>text</b>, especially source code ... affect the meaning of the <b>text</b> itself; it is intended only ... 1 row in set (0.00 sec)

In this example, we see the passage ‘… markup languages, such as HTML. The feature displays text, especially source code …’ which crosses between sentences.

With “passage_boundary=sentence” this passage will be split into two:

SELECT HIGHLIGHT({passage_boundary='sentence'},'content') AS h FROM highlight WHERE MATCH('html text')\G
*************************** 1. row ***************************
h:  ...  highlighting is a feature of <b>text</b> editors that are used for ... , or markup languages, such as <b>HTML</b>. ... The feature displays <b>text</b>, especially source code, in different ... affect the meaning of the <b>text</b> itself; it is intended only ... 1 row in set (0.05 sec)

Let’s add a document with HTML content.

INSERT INTO highlight(title,content) values('html content','The ideas of syntax highlighting overlap significantly with those of <a title="Structure editor" href="/wiki/Structure_editor">syntax-directed editors</a> One of the first such class of editors for code was Wilfred Hansens 1969 code editor, Emily.<sup id="cite_ref-hansen_3-0" class="reference"><a href="#cite_note-hansen-3">[3]</a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4">[4]</a></sup> It provided advanced language-independent <a title="Autocomplete" href="/wiki/Autocomplete">code completion</a> facilities, and unlike modern editors with syntax highlighting, actually made it impossible to create syntactically incorrect programs.');

By default highlighting will process HTML content depending on the index settings. If HTML stripping is enabled in the index, then the HIGHLIGHT() result will also be HTML stripped.

SELECT HIGHLIGHT({},'content') AS h FROM highlight WHERE MATCH('code class')\G
*************************** 1. row ***************************
h:  ...  of the first such <b>class</b> of editors for code was Wilfred Hansens ... 1969 <b>code</b> editor, Emily.[3][4 ... ] It provided advanced language-independent <b>code</b> completion facilities, and unlike modern ...

If we want the highlight to include the HTML tags as well, we need to set “html_strip_mode=none”:

SELECT HIGHLIGHT({html_strip_mode='none'},'content') AS h FROM highlight WHERE MATCH('code class')\G
*************************** 1. row ***************************
h:  ... the first such <b>class</b> of editors for <b>code</b> was Wilfred ... 1969 <b>code</b> editor, Emily. <sup id="cite_ref-hansen_3-0" style="background: #EBE909; color: #000000;">class=" ... sup id="cite_ref-4" <b>class</b>="reference"><a title="Autocomplete" href="#cite_note- ... ="><b>code</b> completion facilities, and ... 1 row in set (0.05 sec)</a></sup>

Please note that “html_strip_mode=none” can highlight words that are part of HTML syntax, like ‘class’.
To protect the HTML entities, the retain mode can be used, but it requires no limit for the snippet (limit=0):

Please note that “html_strip_mode=none” can highlight words that are part of HTML syntax, like ‘class’.
To protect the HTML entities, the retain mode can be used, but it requires no limit for the snippet (limit=0):

This tutorial has explained how to do highlighting in Manticore Search using listed above functions

Interactive course

This tutorial is available in a form of an interactive course which features a command line allowing you to play with the above examples interactively.

Autocorrect in Google, Amazon and Pinterest and how to write your own one

Gregdevogo — Fri, 14 Feb 2020 14:49:41 +0000

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

Spell correction also known as:

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.

Autocorrect — corrects wrong typed query immediately
Autocomplete — another big feature many modern sites have which is often combined with the autocorrect functionality
Suggestions — 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)
Highlighting of mistakes — another nice feature is mistake highlighting. It can also be done both as you type and afterwards
“Did you mean” — 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:

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 instead”

As you type components:

After the query:

Let me demonstrate you with pictures how different popular sites use the aforementioned techniques.

Google 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.

Amazon uses eCommerce oriented search algorithm called A9. What differs it from Google’s algorithm is that it puts a strong emphasis on sales conversions.

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.

Pinterest also has its own algorithm based on internal domain/pins/pinners relevance.

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 data set the system is based on. The data set can be:

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 dictionary made up from your data 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)
Or can be based on an external dictionary 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:

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 context-aware, like if I search for “white ber” Google understands that I mean a bear:

But if I change it to “dark ber” it understands I mean beer:

The context may be not just a neighbour 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 previous search queries 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.
Another approach is to use your users’ previous search queries and/or your dictionary and/or documents to figure out some correction rules and use just them to correct new search queries. There’s even a patent about this 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 of different kinds to improve performance of finding candidates (Lucene’s way)
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 run --name manticore -d manticoresearch/manticore
1ac28e94b3ca728fb431ba79255f81eb31ec264b5d9d49f1d2db973e08a32b9f

And inside the container I’ll run mysql to connect to the Manticore Search server running there:

➜ ~ docker exec -it manticore mysql
Welcome to the MariaDB monitor. Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.5.21
Copyright © 2000, 2018, Oracle, MariaDB Corporation Ab and others.
Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

It ships with 2 test tables that we can use for a quick play with spell correction:

MySQL [(none)]> show tables;
+--------+-----------+
| Index  | Type      |
+--------+-----------+
| pq     | percolate |
| testrt | rt        |
+--------+-----------+
2 rows in set (0.00 sec)

Let’s check the schema of testrt:

MySQL [(none)]> describe testrt;
+---------+--------+------------+
| Field   | Type   | Properties |
+---------+--------+------------+
| id      | bigint |            |
| title   | field  | stored     |
| content | field  | stored     |
| gid     | uint   |            |
+---------+--------+------------+
4 rows in set (0.00 sec)

and insert few documents into it. Let it be movie titles:

MySQL [(none)]> insert into testrt(title) 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\'s List');
Query OK, 10 rows affected (0.00 sec)

We can now see all our documents in the index:

MySQL [(none)]> select * from testrt;
+---------------------+------+--------------------------+---------+
| 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         |         |
+---------------------+------+--------------------------+---------+
10 rows in set (0.00 sec)

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 “com”, “omb”, “mba”, “bat”. So why is that important?

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 few ways 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
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('comabt', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| combat  | 2        | 1    |
+---------+----------+------+
1 row in set (0.00 sec)

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', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| combat  | 0        | 1    |
| kombat  | 1        | 1    |
+---------+----------+------+
2 rows in set (0.00 sec)

If you enter 2 words CALL QSUGGEST only process your last one:

MySQL [(none)]> call qsuggest('mortal combat', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| combat  | 0        | 1    |
| kombat  | 1        | 1    |
+---------+----------+------+
2 rows in set (0.00 sec)

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('m', 'testrt');
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest('mo', 'testrt');
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest('mor', 'testrt');
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest('mort', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| mortal  | 2        | 1    |
+---------+----------+------+
1 row in set (0.01 sec)
MySQL [(none)]> call qsuggest('morta', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| mortal  | 1        | 1    |
+---------+----------+------+
1 row in set (0.00 sec)
MySQL [(none)]> call qsuggest('mortal', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| mortal  | 0        | 1    |
+---------+----------+------+
1 row in set (0.00 sec)
MySQL [(none)]> call qsuggest('mortal c', 'testrt');
Empty set (0.01 sec)
MySQL [(none)]> call qsuggest('mortal co', 'testrt');
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest('mortal com', 'testrt');
Empty set (0.00 sec)
MySQL [(none)]> call qsuggest('mortal comb', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| combat  | 2        | 1    |
| kombat  | 3        | 1    |
+---------+----------+------+
2 rows in set (0.00 sec)
MySQL [(none)]> call qsuggest('mortal comba', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| combat  | 1        | 1    |
| kombat  | 2        | 1    |
+---------+----------+------+
2 rows in set (0.00 sec)
MySQL [(none)]> call qsuggest('mortal combat', 'testrt');
+---------+----------+------+
| suggest | distance | docs |
+---------+----------+------+
| combat  | 0        | 1    |
| kombat  | 1        | 1    |
+---------+----------+------+
2 rows in set (0.00 sec)

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 neded functionality. By the way there’s an interactive course about it on their site