Fuzzy search in text and dictionary

Introduction

Fuzzy search algorithms (also known as similarity search or fuzzy string search ) are the basis of spell checking systems and full-fledged search engines like Google or Yandex. For example, such algorithms are used for functions like “Perhaps you meant ...” in the same search engines.

In this review article, I will consider the following concepts, methods, and algorithms:

• Levenshtein distance
• Distance Damerau-Levenshtein
• Bitap Algorithm with Modifications from Wu and Manber
• Sampling Expansion Algorithm
• N-gram method
• Signature Hashing
• BK trees

I will also conduct comparative testing of the quality and performance of the algorithms.

So...

Fuzzy search is an extremely useful feature of any search engine. At the same time, its effective implementation is much more complicated than the implementation of a simple search by exact match.

The problem of fuzzy search can be formulated as follows:
"For a given word, find in a text or dictionary of size n all words matching this word (or starting with this word) taking into account k possible differences."

For example, when querying “Machine”, taking into account two possible errors, find the words “Machine”, “Makhina”, “Raspberry”, “Kalina” and so on.

Fuzzy search algorithms are characterized by a metric - a function of the distance between two words, which makes it possible to assess the degree of similarity in a given context. Strict mathematical definitionthe metric includes the need to comply with the triangle inequality condition (X is the set of words, p is the metric):



Meanwhile, in most cases, a metric is a more general concept that does not require such a condition to be met, this concept can also be called distance .

Among the most well-known metrics are Hamming , Levenshtein and Damerau-Levenshtein distances . Moreover, the Hamming distance is a metric only on the set of words of the same length, which greatly limits the scope of its application.

However, in practice, the Hamming distance is practically useless, yielding to more natural metrics from a human point of view, which will be discussed below.

Levenshtein distance

The most commonly used metric is the Levenshtein distance, or editing distance, the calculation algorithms of which can be found at every step.
Nevertheless, it is worth making some comments regarding the most popular calculation algorithm - the Wagner-Fisher method .
The initial version of this algorithm has a time complexity of O (mn) and consumes O (mn) memory, where m and n are the lengths of the compared strings. The whole process can be represented by the following matrix:



If you look at the process of the algorithm, it is easy to notice that at each step only the last two rows of the matrix are used, therefore, memory consumption can be reduced to O (min (m, n)).



But this is not all - you can further optimize the algorithm if the task is to find no more than k differences. In this case, it is necessary to calculate in the matrix only a diagonal strip of width 2k + 1 (Ukkonen cut-off), which reduces the time complexity to O (k min (m, n)) .

Prefix distance

It is also necessary to calculate the distance between the pattern prefix and the string — that is, find the distance between the given prefix and the nearest string prefix. In this case, it is necessary to take the smallest of the distances from the sample prefix to all line prefixes. Obviously, the prefix distance cannot be considered a metric in the strict mathematical sense, which limits its application.

Often with a fuzzy search, it is important not so much the value of the distance itself, but the fact of whether it exceeds a certain value or not.

Distance Damerau-Levenshtein

This variation introduces another rule in determining the Levenshtein distance - the transposition (rearrangement) of two adjacent letters is also taken into account as one operation, along with insertions, deletions and replacements.
A couple of years ago, Frederic Damerau could guarantee that most typing errors are just transpositions. Therefore, this particular metric gives the best results in practice.



To calculate such a distance, it is enough to slightly modify the algorithm for finding the usual Levenshtein distance as follows: store not the last two, but the last three rows of the matrix, and also add the corresponding additional condition - if transposition is detected, its cost should also be taken into account when calculating the distance.

In addition to those discussed above, there are many other distances that are sometimes put into practice, such as the Jaro-Winkler metric , many of which are available in the SimMetrics and SecondString libraries .

Fuzzy Search Algorithms Without Indexing (Online)

These algorithms are designed to search in previously unknown text, and can be used, for example, in text editors, programs for viewing documents, or in web browsers to search on a page. They do not require pre-processing of text and can work with a continuous stream of data.

Linear search

Simple sequential application of a given metric (for example, the Levenshtein metric) to words from the input text. When using metric with restriction, this method allows you to achieve optimal speed. But, at the same time, the larger k , the more the operating time increases. The asymptotic time estimate is O (kn) .

Bitap (also known as Shift-Or or Baeza-Yates-Gonnet, and its modification from Wu-Manber)

The Bitap algorithm and its various modifications are most often used for fuzzy searches without indexing. Its variation is used, for example, in the agrep unix utility , which performs functions similar to the standard grep , but with support for errors in the search query and even providing limited opportunities for applying regular expressions.

For the first time, the idea of ​​this algorithm was proposed by citizens of Ricardo Baeza-Yates and Gaston Gonnet , having published an article in 1992.
The original version of the algorithm deals only with character substitutions, and, in fact, calculates the Hamming distance . But a little later Sun Wu andUdi Manber предложили модификацию этого алгоритма для вычисления расстояния Левенштейна, т.е. привнесли поддержку вставок и удалений, и разработали на его основе первую версию утилиты agrep.

Операция Bitshift

         

Вставки

Удаления

Замены

Результирующее значение


Где k — количество ошибок, j — индекс символа, s_x — маска символа (в маске единичные биты располагаются на позициях, соответствующих позициям данного символа в запросе).
Совпадение или несовпадение запросу определяется самым последним битом результирующего вектора R.

The high speed of this algorithm is ensured by bitwise parallelism of calculations - in one operation, it is possible to carry out calculations on 32 or more bits at a time.
Moreover, the trivial implementation supports searching for words no longer than 32. This restriction is determined by the width of the standard int type (on 32-bit architectures). Types of large dimensions can be used, but this can slow down the operation of the algorithm to some extent.

Despite the fact that the asymptotic running time of this algorithm O (kn) coincides with that of the linear method, it is much faster with long queries and the number of errors k is more than 2.

Testing

Testing was carried out on the text of 3.2 million words, the average word length is 10.

Exact search

Search time: 3562 ms

Search using the Levenshtein metric

Search time at k = 2 : 5728 ms
Search time at k = 5 : 8385 ms

Search using the Bitap algorithm with Wu-Manber modifications

Search time for k = 2 : 5499 ms
Search time for k = 5 : 5928 ms

Obviously, a simple search using the metric, unlike the Bitap algorithm, strongly depends on the number of errors k .

Nevertheless, if it comes to searching large volumes of unchanged texts, the search time can be significantly reduced by pre-processing such text, also called indexing .

Fuzzy Search Algorithms with Indexing (Offline)

A feature of all fuzzy search algorithms with indexing is that the index is built using a dictionary compiled from the source text or a list of records in any database.

These algorithms use different approaches to solving the problem - some of them use reduction to exact search, others use the properties of the metric to build various spatial structures and so on.

First of all, at the first step, a dictionary containing words and their positions in the text is built on the source text. You can also count the frequencies of words and phrases to improve the quality of search results.

It is assumed that the index, like the dictionary, is entirely loaded into memory.

The performance characteristics of the dictionary:

• The source text is 8.2 gigabytes of materials from the Moshkov library ( lib.ru ), 680 million words;
• Dictionary size - 65 megabytes;
• Number of words - 3.2 million;
• The average word length is 9.5 characters;
• The root mean square word length (may be useful in evaluating some algorithms) is 10.0 characters;
• Alphabet - capital letters A to Z, without E (to simplify some operations). Words containing non-alphabetical characters are not included in the dictionary.

The dependence of the dictionary size on the volume of the text is not strictly linear - up to a certain volume a basic frame of words is formed, comprising from 15% at 500 thousand words to 5% at 5 million, and then the dependence approaches linear, slowly decreasing and reaching 0.5% by 680 million words. Subsequent conservation of growth is ensured for the most part due to rare words.

Sampling Expansion Algorithm

This algorithm is often used in spell-checking systems (i.e., in spell-checkers), where the dictionary size is small, or where the speed is not the main criterion.
It is based on reducing the fuzzy search problem to the exact search problem.

A lot of “erroneous” words are built from the initial query, for each of which an exact search in the dictionary is then performed.



Its working time strongly depends on the number of k errors and the size of the alphabet A, and in the case of using binary search in the dictionary it is:


For example, for k = 1 and a word of length 7 (for example, “Crocodile”) in the Russian alphabet, a lot of erroneous words will be the size 450, that is, it will be necessary to make 450 queries to the dictionary, which is quite acceptable.
But already atk = 2 the size of such a set will be more than 115 thousand options, which corresponds to a complete search of a small dictionary, or 1/27 in our case, and, therefore, the operating time will be quite large. At the same time, one should not forget that for each of these words it is necessary to conduct a search for an exact match in the dictionary.

Features:

The algorithm can be easily modified to generate "erroneous" options according to arbitrary rules, and, moreover, does not require any preliminary processing of the dictionary, and, accordingly, additional memory.

Possible improvements:

You can not generate all the many “erroneous” words, but only those that are most likely to occur in a real situation, for example, words taking into account common spelling or typing errors.

N-gram method

This method was invented for a long time, and is the most widely used, since its implementation is extremely simple, and it provides good enough performance. The algorithm is based on the principle:
“If the word A matches the word B, taking into account several errors, then with a high degree of probability they will have at least one common substring of length N”.
These substrings of length N are called N-grams.
During indexing, a word is split into such N-grams, and then this word is listed for each of these N-grams. During the search, the query is also divided into N-grams, and for each of them, a sequential search of the list of words containing such a substring is performed.



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

Особенности:

Алгоритм N-грамм находит не все возможные слова с ошибками. Если взять, например, слово ВОТКА, и разложить его на триграммы: ВОТКА → ВОТ ОТК ТКА — то можно заметить, что они все содержат ошибку Т. Таким образом, слово «ВОДКА» найдено не будет, так как оно не содержит ни одной из этих триграмм, и не попадет в соответствующие им списки. Таким образом, чем меньше длина слова и чем больше в нем ошибок, тем выше шанс того, что оно не попадет в соответствующие N-граммам запроса списки, и не будет присутствовать в результате.

Meanwhile, the N-gram method leaves full scope for using your own metrics with arbitrary properties and complexity, but you have to pay for it - when you use it, you still need to sequentially search around 15% of the dictionary, which is quite a lot for large dictionaries.

Possible improvements:

You can divide the hash tables of N-grams by the length of words and by the position of the N-gram in the word (modification 1). Just as the length of the searched word and query cannot differ by more than k , so the position of the N-gram in the word can differ by no more than k. Thus, it will be necessary to check only the table corresponding to the position of this N-gram in the word, as well as k tables on the left and k tables on the right, i.e. only 2k + 1 neighboring tables.



You can reduce the size of the set necessary for viewing a little more by breaking the tables by the word length and similarly looking only at the adjacent 2k + 1 tables (modification 2).

Signature Hashing

This algorithm is described in the article by L. Boytsov "Hashing by signature." It is based on a fairly obvious representation of the word “structure” in the form of bit bits, used as a hash (signature) in a hash table.

When indexing, such hashes are calculated for each of the words, and the correspondence of the list of dictionary words to this hash is entered in the table. Then, during the search, the hash is computed for the request and all neighboring hashes that differ from the original one in no more than k bits are sorted. For each of these hashes, the list of words corresponding to it is enumerated.

Hash calculation process - each bit of the hash is associated with a group of characters from the alphabet. Bit 1 at position i in the hash means that the character from the i-th is present in the original wordalphabet groups. The order of letters in a word has absolutely no meaning.



Deleting one character will either not change the hash value (if there are still characters from the same alphabet group in the word), or the bit corresponding to this group will change to 0. When inserted, in the same way, either one bit will go to 1 or there will be no changes. When replacing characters, everything is a little more complicated - the hash can either remain unchanged at all, or it can change in 1 or 2 positions. When rearranging, no changes take place at all, because the order of characters in the construction of the hash, as was noted earlier, is not taken into account. Thus, to completely cover k errors, at least 2k bits in the hash must be changed .



Operating time, on average, with k "incomplete" (insertion, deletion and transposition, as well as a small part of the replacements) errors:

Features:

Due to the fact that when replacing one character two bits can change at once, an algorithm that implements, for example, distortions of no more than 2 bits at a time, in reality will not produce the full amount of results due to the absence of a significant (depends on the ratio of the hash size to the alphabet) part of the words with two replacements (and the larger the hash size, the more often the replacement of a character will lead to distortion of two bits at once, and the less complete the result). In addition, this algorithm does not allow prefix searches.

BK trees

Trees Burkhard-Keller are metric trees, algorithms for constructing such trees are based on the properties of metrics to answer the triangle inequality:



This feature allows metrics to form metric spaces of any dimension. Such metric spaces are not necessarily Euclidean , for example, the Levenshtein and Damerau-Levenshtein metrics form non - Euclidean spaces. Based on these properties, you can build a data structure that searches in such a metric space, which are the Barkhard-Keller trees.

Improvements:

You can use the ability of some metrics to calculate a constrained distance by setting an upper limit equal to the sum of the maximum distance to the descendants of the vertex and the resulting distance, which will speed up the process a little:

Testing

Testing was carried out on a laptop with Intel Core Duo T2500 (2GHz / 667MHz FSB / 2MB), 2Gb RAM, OS - Ubuntu 10.10 Desktop i686, JRE - OpenJDK 6 Update 20.



Testing was carried out using the Damerau-Levenshtein distance and the number of errors k = 2 . The size of the index is indicated with the dictionary (65 MB).

Sample Extension

Index size: 65 MB
Search time: 320 ms / 330 ms
Completeness of results: 100%

N-gram (original)

Index size: 170 Mb
Index creation time: 32 s
Search time: 71 ms / 110 ms
Completeness of results: 65%

N-gram (modification 1)

Index size: 170 Mb
Index creation time: 32 s
Search time: 39 ms / 46 ms
Completeness of results: 63%

N-gram (modification 2)

Index size: 170 Mb
Index creation time: 32 s
Search time: 37 ms / 45 ms
Completeness of results: 62%

Signature Hashing

Index size: 85 Mb
Index creation time: 0.6 s
Search time: 55 ms
Completeness of results: 56.5%

BK trees

Index size: 150 Mb
Index creation time: 120 s
Search time: 540 ms
Completeness of results: 63%

Total

Most are not fuzzy search with indexing algorithms sublinear true (i.e., having an asymptotic time O (log n) or below), and their speed is typically directly dependent on N . Nevertheless, numerous improvements and improvements allow us to achieve a sufficiently short time even with very large volumes of dictionaries.

There are also many more diverse and ineffective methods based, among other things, on the adaptation of various techniques already used elsewhere in this subject area. Among these methods is the adaptation of prefix trees (Trie) to fuzzy search tasks.which I ignored in view of its low efficiency. But there are also algorithms based on original approaches, for example, the Maass-Novak algorithm , which, although it has a sublinear asymptotic run time, is extremely inefficient due to the huge constants hiding behind such a time estimate, which appear as a huge index size.

The practical use of fuzzy search algorithms in real search engines is closely related to phonetic algorithms , lexical stemming algorithms - highlighting the base part of different word forms of the same word (for example, Snowball and Yandex mystem provide such functionality), as well as ranking based on statistical information, or using sophisticated sophisticated metrics.

You can find my Java implementations at http://code.google.com/p/fuzzy-search-tools :

• Levenshtein distance (with clipping and prefix option);
• Damerau-Levenshtein distance (with clipping and prefix option);
• Bitap Algorithm (Shift-OR / Shift-AND with Wu-Manber modifications);
• Sampling expansion algorithm;
• N-gram method (original and with modifications);
• Signature hashing method;
• BK trees.

I wanted to make the code easy to understand, and yet effective enough for practical use. Squeezing the last juices from the JVM was not my task. Enjoy.

It is worth noting that in the process of studying this topic, I had some of my own developments that allow me to reduce the search time by an order of magnitude due to a moderate increase in the size of the index and some restriction on the freedom of choice of metrics. But this is a completely different story.

References:

1. Source codes for the article in Java. http://code.google.com/p/fuzzy-search-tools
2. Levenshtein distance. http://ru.wikipedia.org/wiki/Levenshtein_Distance
3. Distance Damerau-Levenshtein. http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance
4. Хорошее описание Shift-Or c модификациями Wu-Manber, правда, на немецком. http://de.wikipedia.org/wiki/Baeza-Yates-Gonnet-Algorithmus
5. Метод N-грамм. http://www.cs.helsinki.fi/u/ukkonen/TCS92.pdf
6. Хеширование по сигнатуре. http://itman.narod.ru/articles/rtf/confart.zip
7. Сайт Леонида Моисеевича Бойцова, целиком посвященный нечеткому поиску. http://itman.narod.ru/
8. Реализация Shift-Or и некоторых других алгоритмов. http://johannburkard.de/software/stringsearch/
9. Fast Text Searching with Agrep (Wu & Manber). http://www.at.php.net/utils/admin-tools/agrep/agrep.ps.1
10. Damn Cool Algorithms - Levenshtein's automaton, BK-trees, and some other algorithms. http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
11. BK trees in Java. http://code.google.com/p/java-bk-tree/
12. The Maass-Novak algorithm. http://yury.name/internet/09ia-seminar.ppt
13. SimMetrics Metrics Library. http://staffwww.dcs.shef.ac.uk/people/S.Chapman/simmetrics.html
14. SecondString Metrics Library. http://sourceforge.net/projects/secondstring/

Russian version: Fuzzy string search