Thursday, March 24, 2011

Fuzzy string search


Fuzzy search algorithms (also known as similarity search algorithms) are a basis of spell-checkers and full-fledged search engines like Google or Yandex. For example, these algorithms are used to provide the "Did you mean ..." function.

In this article I'll discuss the following concepts, methods and algorithms:
  • Levenshtein distance
  • Damerau-Levenshtein distance
  • Bitap algorithm with modifications by Wu and Manber
  • Spell-checker method
  • N-gram method
  • Signature hashing method
  • BK-trees
I'll also perform a comparative test of the quality and efficiency of algorithms.


Fuzzy search is a very useful feature of any search engine. However, its effective implementation is much more complicated than implementing a simple search for an exact match.

The problem of fuzzy string searching can be formulated as follows:
"Find in the text or dictionary of size n all the words that match the given word (or start with the given word), taking into account k possible differences (errors)."

For example, if you're requested for "machine" with two possible errors, find the words "marine", "lachine", "martine", and so on.

Fuzzy search algorithms are characterized by metric - a function of distance between two words, which provides a measure of their similarity. A strict mathematical definition of metric includes a requirement to meet triangle inequality (X - a set of words, p - metric):

Triangle inequality

Meanwhile, in most cases a metric is understood as a more general concept that does not meet the condition above, this concept can also be called distance.

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

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

Levenshtein distance

The Levenshtein distance, also known as "edit distance", is the most commonly used metric, the algorithms of its computation can be found at every turn.
Nevertheless, it is necessary to make some comments about the most popular algorithm of calculation - Wagner-Fischer method.
The original version of this algorithm has time complexity of O(mn) and consume O(mn) memory, where m and n are the lengths of the compared strings. The whole process can be represented by the following matrix:

Levenshtein distance matrix

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

Levenshtein algorithm's work process

But that's not all - the algorithm can be optimized further, if no more than k differences should be found. In this case it is necessary to calculate only the diagonal band of width 2k+1 in matrix (Ukkonen cut-off), which reduces the time complexity to O (k min (m, n)).

Prefix distance
Usually it is necessary to calculate the distance between the prefix pattern and a string - ie, to find the distance between the specified prefix and nearest string prefix. In this case, you must take the smallest of the distances from the prefix pattern to all the prefixes of the string. Obviously, the prefix length can not be considered as a metric in the strict mathematical sense, what limits its application.

Often, the specific value of a distance is not as important as fact that it exceeds a certain value.

Damerau-Levenshtein distance

This variation contributes to the definition of the Levenshtein distance one more rule - transposition of two adjacent letters are also counted as one operation, along with insertions, deletions, and substitutions.
A couple of years ago, Frederick Damerau would ensure that most typing errors - transpositions. Therefore, this metric gives the best results in practice.

Damerau-Levenshtein algorithm's work process

To calculate this distance, it suffices to slightly modify the regular Levenshtein algorithm as follows: hold not two, but the last three rows, and add an appropriate additional condition - in the case of transposition take into account its cost.

In addition to the above, there are many others sometimes used in practice distances, such as Jaro–Winkler metric, many of which are available in SimMetrics and SecondString libraries.

Fuzzy search algorithms without indexing (Online)

These algorithms are designed to search against previously unknown text, and can be used, for example, in a text editor, document viewers or web browsers to search the page. They do not require text pre-processing and can operate with a continuous stream of data.

Linear search

A simple one-by-one metric computation (eg, Levenshtein metric) for words of the input text. When you use metric limitation, this method allows to achieve optimum speed.
But at the same time, than more k, than more time grows. Asymptotic time complexity - O (kn).

Bitap (also known as Shift-Or or Baeza-Yates-Gonnet, and it's modifications by Wu and Manber)

Bitap algorithm and its various modifications are most often used for fuzzy search without indexing. Its variation is used, for example, in unix-utility agrep, which one functions like the standard grep, but it supports errors in the search query, and even provides a limited ability to use regular expressions.

For the first time the idea of this algorithm is proposed by Ricardo Baeza-Yates and Gaston Gonnet, the relevant article published in 1992.
The original version of the algorithm deals only with letter substitutions, and, in fact, computes the Hamming distance. But later Sun Wu and Udi Manber suggested a modification of this algorithm for computing the Levenshtein distance, ie brought support insertions and deletions, and developed the first version of agrep utility.

Bitshift operation

         Bitshift operation

Result value
Result value

Where k - error count, j - letter index, sx - letter mask (in mask one bits are placed at positions corresponding to the positions of this letter in the query).
Query match or mismatch is determined by the last bit of the result vector R.

High speed of this algorithm is ensured by the bit parallelism - calculations can be performed on 32 or more bits in a single operation.
In this case, a trivial implementation supports the search for the words shorten than 32 symbols. This restriction is caused by the width of a standard type int (32-bit architectures). We can use wider types, but it's usage may slow down the algorithm's work.

Despite the fact that the asymptotic time of this algorithm O (kn) equals linear method's time, it is much faster when the query is long and number of errors k more than 2.


Testing was performed on the text of 3.2 million words, average word length - 10.

Exact search
Search time: 3562 ms

Linear search using Levenshtein metric
Search time with k = 2: 5728 ms
Search time with k = 5: 8385 ms

Bitap with Wu-Manber modifications search
Search time with k = 2: 5499 ms
Search time with k = 5: 5928 ms

It is obvious that a simple iteration using the metric, in contrast to the Bitap algorithm, highly depends on the number of errors k.

At the same time, if we should search in constant large text, the search time can be greatly reduced by making text preprocessing (indexing).

Fuzzy search algorithms with indexing (Offline)

Feature of all fuzzy search algorithms with indexing is that the index is based on the dictionary compiled by the original text or list of records in a database.

These algorithms use different approaches to solve problem - some of them use reduction to exact search, while others use properties of metrics to construct various spatial structures and so on.

At the first step, we construct a dictionary using the original text, which would contain words and their position in text. Also, it is possible to calculate the frequency of words and phrases to improve search results.

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

Dictionary specifications:
  • Source text — 8.2 Gb Moshkow's library (, 680 millions of words;
  • Dictionary size — 65 Mb;
  • Word count - 3.2 million;
  • Average word length — 9.5 letters;
  • Average word square length — 10.0 letters;
  • Russian alphabet (32 letters). Words that contain characters not in the alphabet, are not included in the dictionary.
Dependence of the dictionary size from the text size is not strictly linear - to a certain volume base word set is formed, between 15% on 500 thousand words and 5% on 5 million words, and then approaches a linear dependence, slowly decreasing and reaching 0.5% at 680 million words. Subsequent growth is ensured due to rare words.

Growth of dictionary size

Spell-checker method

As the name implies, this algorithm is often used in spelling correction systems (ie, spell-checker systems), when the size of the dictionary is small, or else when speed is not the main criterion.
It is based on reducing the problem of fuzzy search to the problem of exact search.

A set of "mistaken" words is built from original query. Then every word from this set is searched in the dictionary for exact match.

Spell-checker method

Its time complexity is strongly dependent on the number of errors k and the alphabet size |A|, and for a binary search over the dictionary is:

For example, in case of error count k = 1 and word length of 7 in the English alphabet set of misspelled words will have about 370 words, so we need to make 370 queries in the dictionary, which is quite acceptable.
But even at k = 2 the size of this set will be more than 75,000 words, which corresponds to a complete iteration over a small dictionary and, therefore, time is sufficiently large. In this case, we should not forget also that for each of such words are necessary to search for an exact match in the dictionary.

The algorithm can be easily modified to generate "mistaken" words using arbitrary rules and, moreover, does not require any dictionary preprocessing or additional memory.

Possible improvements:
We can generate not a whole set of "mistaken" words, but only those that are most likely to occur in real situations, like words with common spelling mistakes or typos.

N-gram method

This method was invented long ago, and is the most widely used because its implementation is relatively simple and it provides a reasonably good performance. This algorithm is based on the principle:

"If the word A matches with the word B considering several errors, then they will most likely have at least one common substring of length N".

These substrings of length N are named "N-grams".
At indexing step, the word is partitioned into N-grams, and then the word is added to lists that correspond each of these N-grams. At search step, the query is also partitioned into N-grams, and for each of them corresponding lists are scanned using the metric.

N-gram method

The most frequently used in practice are trigrams - substrings of length 3. Choosing a larger value of N leads to a limitation on the minimum length of words at which error detection is still possible.

N-gram algorithm doesn't find all possible spelling errors. Take, for instance, the word VOTKA (which must be corrected to VODKA, of course), and divide it into trigrams: VOTKA > VOT OTK TKA - we can see that all of these trigrams contain an error T. Thus, the word "VODKA" will not be found because it does not contain any of the trigrams, and will not get into their lists. The shorter the word and more errors in it, the higher chance that it won't contains in corresponding to query N-grams lists and will not appear in the result set.

Meanwhile, N-gram method leaves ample scope for using custom metrics with arbitrary properties and complexity, but there remains a need for brute force of about 15% of the dictionary.

We can separate N-gram hash tables by position of N-gram in the word (first modification M1). As the length of a word and the query can't differ by more than k, and the position of N-grams in the word can't differ by more than k. Thus, we should check only table that corresponds to the N-gram position in the word, and k tables to the left and to the right, total 2k+1 neighboring tables.

First modification of N-gram method

We can even slightly reduce the size of iterating set by separating tables by word length, and, similarly, scanning only the neighboring 2k+1 tables (second modification M2).

Signature hashing

This algorithm is described in L. M. Boytsov's article "Signature hashing". It is based on a fairly obvious representation of the "structure" of the word as a bit word, used as a hash (signature) in the hash table.

When indexing, such hashes are calculated for each word and this word is added in the corresponding table row. Then, during the search the hash is computed for a query and set of adjacent hashes that differ from the query's hash with no more than k bits is generated. For each of these hashes we iterate over corresponding list of words using the metric.

The hash computing process - for each bit of the hash a group of characters from the alphabet is matched. Bit 1 at position i in the hash means that there is a symbol of i-th group of the alphabet in the word. Order of the letters in the word is absolutely does not matter.

Signature hashing

Single character deletion either does not change the hash value (if the word still have characters from the same group of the alphabet), or bit of corresponding group will be changed to 0. When you insert a similar manner or a bit of get up at 1 or no changes will be. Single character substitution a bit more complicated - the hash can either remain unchanged or will change in 1 or 2 bits. In case of transpositions there are no changes in the hash because the order of symbols at the hash construction does not matter as noted earlier. Thus, to fully cover the k errors we need to change at least 2k bits in the hash.

List of hashes with one error

Average time complexity with k "incomplete" (insertions, deletions and transpositions, as well as a part of substitutions) errors:
Signature hashing time complexity

The fact that the replacement of one character can change two bits at a time, the algorithm that works with, for example, changing of 2 bits in hash, in reality won't return the full set of results because of lack of significant (depending on the ratio of the hash size to the alphabet size) amount of the words with two substitutions (and the wider the hash, the more frequently two bits will be changed at the same and the more incomplete set will be returned). In addition, this algorithm does not allow for prefix search.


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

Triangle inequality

This property allows metrics to form the metric spaces of arbitrary dimension. These metric spaces are not necessarily Euclidean, for example, the Levenshtein and Damerau-Levenshtein metrics form a non-Euclidean space. Based on these properties, we can construct a data structure for searching in a metric space, which is Barkhard-Keller tree.


We can use the ability of some metrics to calculate the limited distance, setting an upper limit to the sum of the maximum distance to the node descendants and the resulting distance, which will speed up the process a bit:

BK-trees metric limitations


Testing was performed 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.

Time comparison

Testing was performed using Damerau-Levenshtein distance with error count k = 2. Index size is specified including dictionary size (65 Mb).

Spell-checker method
Index size: 65 Mb
Search time: 320 ms / 330 ms
Result recall: 100%

N-gram (original)
Index size: 170 Mb
Index creation time: 32 s
Search time: 71 ms / 110 ms
Result recall: 65%

N-gram (first modification)
Index size: 170 Mb
Index creation time: 32 s
Search time: 39 ms / 46 ms
Result recall: 63%

N-gram (second modification)
Index size: 170 Mb
Index creation time: 32 s
Search time: 37 ms / 45 ms
Result recall: 62%

Signature hashing
Index size: 85 Mb
Index creation time: 0.6 s
Search time: 55 ms
Result recall: 56.5%

Index size: 150 Mb
Index creation time: 120 s
Search time: 540 ms
Result recall: 63%


Most of fuzzy search algorithms with indexing are not truly sublinear (i.e., having an asymptotic time of O (log n) or below), and their performance usually depends on N. Nevertheless, multiple enhancements and improvements make it possible to achieve sufficiently small operational time, even with very large dictionaries.

There is also another set of various and inefficient methods, based on adaptations of techniques and methods from other subject areas to the current. Among these methods is the prefix tree (Trie) adaptation to fuzzy search problems, which I left neglected due to its low efficiency. But there are also algorithms based on the original approaches, for example, the Maass-Novak algorithm, it has sublinear asymptotic time, but it is highly inefficient because of the huge constants hidden behind asymptotic time estimation, which leads to a huge index.

The use of fuzzy search algorithms in real search engines is closely related to the phonetic algorithms, lexical stemming algorithms, which extract base part from different forms of the same word (for example, that functionality provided by Snowball), statistic-based ranking or the use of some complex sophisticated metrics.

This link takes you to my Java implementation of the following stuff:
  • Levenshtein Distance (with cutoff and prefix version);
  • Damerau-Levenshtein Distance (with cutoff and prefix version);
  • Bitap (Shift-Or with Wu-Manber modifications);
  • Spell-checker Method;
  • N-Gram Method (with some modifications);
  • Signature Hashing Method;
  • Burkhard-Keller (BK) Trees.
I tried to make this code easy to understand, but effective enough for practical application. So enjoy.

It is worth noting that in the process of researching this subject I've made some own work, which allows to reduce the search time significantly due to a moderate increase in the index size and some restrictions on freedom of used metrics. But that's another cool story.


  1. Java source codes for this article.
  2. Levenshtein distance.
  3. Damerau-Levenshtein distance.–Levenshtein_distance
  4. Shift-Or description with Wu-Manber modifications, in Deutsch.
  5. N-gram method.
  6. Signature hashing.
  7. Signature hashing in Russian.
  8. Information retrieval and fuzzy string searching.
  9. Shift-Or and some other algorithms implementation.
  10. Fast Text Searching with Agrep (Wu & Manber).
  11. Damn Cool Algorithms - Levenshtein automata, BK-tree, and some others.
  12. BK-tree Java implementation.
  13. Maass-Novak algorithm.
  14. SimMetrics metric library.
  15. SecondString metric library.

Wednesday, March 23, 2011

Phonetic algorithms


A phonetic algorithm matches two different words with similar pronunciation to the same code, which allows phonetic similarity based word set comparison and indexing.

Often it is quite difficult to find atypical name (or surname) in the database, for example:
— Hey, John, look for Adolf Schwarzenegger.
— Adolf Shwardseneger? There is no such person!
In this case, the use of phonetic algorithms (especially in combination with fuzzy matching algorithms) can significantly simplify the problem.

These algorithms are very useful for searching in lists of people in databases, as well as for using in a spell checker. They are often used in combination with the algorithms of fuzzy search, providing users with a handy search by name and surname in databases, lists of people and so on.

In this article I will discuss the most well-known algorithms, such as Soundex, Daitch-Mokotoff Soundex, NYSIIS, Metaphone, Double Metaphone, Caverphone.


One of the first algorithms was Soundex invented in the 1910s by Robert Russell. This algorithm (its American version) matches words to the numerical index like A126. Its working principle is based on the partition of consonants in groups with ordinal numbers, which are then compiled to the resulting value. Later several improvements was suggested.


The first letter is stored, subsequent letters are matched to digits by the table above. Letters that are not listed in the table (all the vowels and some consonants) are ignored. Adjacent letters, or letters from the same group separated by H or W are written as one letter. The result is truncated to 4 characters. Missing positions contain zeros. It is easy to see that after all these procedures there is only 7000 different values of that code, which results in a set of unliked words with the same Soundex code. Thus, in most cases the result involves a large number of "false positive" values.


As you can see in the refined soundex the letters are divided into more groups. In addition, there are no special cases with H and W, they are simply ignored. Also length of the result is not truncated, so the code does not have a fixed length.

Original Soundex:
F234 → Fusedale.
G535 → Genthner, Gentner, Gianettini, Gunton.
G640 → Garlee, Garley, Garwell, Garwill, Gerrell, Gerrill, Giral, Gorelli, Gorioli, Gourlay, Gourley, Gourlie, Graal, Grahl, Grayley, Grealey, Greally, Grealy, Grioli, Groll, Grolle, Guerola, Gurley.
H326 → Hadcroft, Hadgraft, Hatchard, Hatcher, Hatzar, Hedger, Hitscher, Hodcroft, Hutchcraft.
P630 → Parade, Pardew, Pardey, Pardi, Pardie, Pardoe, Pardue, Pardy, Parradye, Parratt, Parrett, Parrot, Parrott, Pearde, Peart, Peaurt, Peert, Perdue, Peret, Perett, Perot, Perott, Perotti, Perrat, Perrett, Perritt, Perrot, Perrott, Pert, Perutto, Pirdue, Pirdy, Pirot, Pirouet, Pirt, Porrett, Porritt, Port, Porte, Portt, Prate, Prati, Pratt, Pratte, Pratty, Preddy, Preedy, Preto, Pretti, Pretty, Prewett, Priddey, Priddie, Priddy, Pride, Pridie, Pritty, Prott, Proud, Prout, Pryde, Prydie, Purdey, Purdie, Purdy.

Refined Soundex:
B1905 → Braz, Broz
C30908 → Caren, Caron, Carren, Charon, Corain, Coram, Corran, Corrin, Corwin, Curran, Curreen, Currin, Currom, Currum, Curwen
H093 → Hairs, Hark, Hars, Hayers, Heers, Hiers
L7081096 → Lambard, Lambart, Lambert, Lambird, Lampaert, Lampard, Lampart, Lamperd, Lampert, Lamport, Limbert, Lombard
N807608 → Nolton, Noulton

One Soundex code value is matched for 21 surnames. In the case of an refined version of Soundex, 2-3 names match to the same code.


Developed in 1970 as part of the "New York State Identification and Intelligence System", this algorithm gives better results relatively to the original Soundex using more sophisticated rules for transforming the original word to the result code. This algorithm is designed to work specifically with American names.

NYSIIS computation algorithm
  1. Transform the beginning of the word using the following rules:
    MAC → MCC
    KN → N
    K → C
    PH, PF → FF
    SCH → SSS
  2. Transform the ending of the word using the following rules:
    EE → Y
    IE → Y
    DT, RT, RD, NT, ND → D
  3. Transform all letters except first using the rules below:
    EV → AF
    A, E, I, O, U → A
    Q → G
    Z → S
    M → N
    KN → N
    K → C
    SCH → SSS
    PH → FF
    After a vowel: remove H and transform W → A
  4. Remove S at the end
  5. Transform AY at the end → Y
  6. Remove A at the end
  7. Truncate word to 6 letters (optional).
DAGAL → Diggell, Dougal, Doughill, Dougill, Dowgill, Dugall, Dugall.
GLAND → Glinde.
PLANRAG → Plumridge.
SANAC → Chinnick, Chinnock, Chinnock, Chomicki, Chomicz, Schimek, Shimuk, Simak, Simek, Simic, Sinnock, Sinnocke, Sunnex, Sunnucks, Sunock.
WABARLY → Webberley, Wibberley.

NYSIIS matches to the same code a bit more than two surnames.

Daitch-Mokotoff Soundex

This algorithm was developed by two genealogist, Gary Mokotoff and Randy Daitch in 1985. They tried to achieve the best results with Eastern European (including Russian, Jewish) surnames.
This algorithm has little in common with the original Soundex, except that the result is still a sequence of digits. But now the first letter is also encoded as a digit.

It has a much more complicated conversion rules. Calculation of resulting code is also involves not only single characters, but the groups of characters. In addition, the result of the form 023689 provides about 600 000 different values of that code. This feature coupled together with complex rules reduces the number of "false positive" words in the result set.

Transformations are performed using the table below. The order of conversions is the order of letter combinations in the table.
Letter combinationAt the startAfter a vowelOther
AI, AJ, AY, EI, EY, EJ, OI, OJ, OY, UI, UJ, UY01
A, UE, E, I, O, U, Y0
DT, D, TH, T333
CHS, KS, X55454
S, Z444
CH, CK, C, G, KH, K, Q555
MN, NM6666
M, N666
FB, B, PH, PF, F, P, V, W777
"Alternative" variants of letter combinations (used for multiple alternative codes generation):
C → TZ

147740Iozefovich, Jacobovitch, Jacobovitz, Jacobowicz, Jacobowits, Jacobowitz, Josefovic, Josefowicz, Josifovic, Josifovitz, Josipovic, Josipovitz, Josofovitz, Jozefowicz, Yezafovich.
147750Iozefovich, Josefovic, Josifovic, Josipovic, Yezafovich.
345750 → Dashkovich, Djakovic, Djekovic, Djokovic.
783940Baldrick, Fielders, Walters, Weldrick, Wolters.
783950Baldrick, Weldrake, Weldrick, Welldrake.
964660Runchman, Runcieman, Runciman.
965660Runchman, Runcieman, Runciman.
596490Grancher, Greenacre.
596590 → Gehringer, Grainger, Grancher, Granger, Grangier, Greenacre, Grunguer.

This algorithm transforms about 5 surnames to the same code.

Subsequently Alexander Beider and Stephen Morse developed Beider-Morse Name Matching Algorithm, aimed to reducing the number of "false positive" values in Daitch-Mokotoff Soundex results with Jewish (Ashkenazic) surnames.


Metaphone (1990) algorithm has somewhat better efficiency. It has different approach to the encoding process: it transforms the original word using English pronunciation rules, so the conversion rules are much more complicated. The algorithm loses much less information, since the letters are not divided into groups. The final code is a set of characters 0BFHJKLMNPRSTWXY, but in the beginning of a word can also appear vowels from the set AEIOU.

Metaphone code computation algorithm
  1. Remove all repeating neighboring letters except letter C.
  2. The beginning of the word should be transformed using the following rules:
    KN → N
    GN → N
    PN → N
    AE → E
    WR → R
  3. Remove B letter at the end, if it is after M letter.
  4. Replace C using the rules below:
    With Х: CIA → XIA, SCH → SKH, CH → XH
    With S: CI → SI, CE → SE, CY → SY
    With K: C → K
  5. Replace D using the following rules:
    With J: DGE → JGE, DGY → JGY, DGI → JGY
    With T: D → T
  6. Replace GH → H, except it is at the end or before a vowel.
  7. Replace GN → N and GNED → NED, if they are at the end.
  8. Replace G using the following rules
    With J: GI → JI, GE → JE, GY → JY
    With K: G → K
  9. Remove all H after a vowel but not before a vowel.
  10. Perform following transformations using the rules below:
    CK → K
    PH → F
    Q → K
    V → F
    Z → S
  11. Replace S with X:
    SH → XH
    SIO → XIO
    SIA → XIA
  12. Replace T using the following rules
    With X: TIA → XIA, TIO → XIO
    With 0: TH → 0
    Remove: TCH → CH
  13. Transform WH → W at the beginning. Remove W if there is no vowel after it.
  14. If X is at the beginning, then replace X → S, else replace X → KS
  15. Remove all Y which are not before a vowel.
  16. Remove all vowels except vowel at the start of the word.
FXPL → Fishpool, Fishpoole.
JLTL → Gellately, Gelletly.
LWRS → Lowers, Lowerson.
MLBR → Mallabar, Melbert, Melbourn, Melbourne, Melburg, Melbury, Milberry, Milborn, Milbourn, Milbourne, Milburn, Milburne, Millberg, Mulberry, Mulbery, Mulbry.
SP → Saipy, Sapey, Sapp, Sappy, Sepey, Seppey, Sopp, Zoppie, Zoppo, Zupa, Zupo, Zuppa.

Same code is matched to 6 surnames in the average.

Double Metaphone

Double Metaphone (2000) differs a bit from other phonetic algorithms by generating from the original word two code values (both up to 4 characters) - one reflects the basic version of word pronunciation, another - an alternative version. It has large number of different rules that take into account origin of words, focusing on Eastern European, Italian, Chinese and another words. Transformation rules are sufficiently numerous, so everyone can read about this algorithm in the Dr Dobbs article.

APLF → Abelevitz, Abelov, Abelovitz, Abilowitz, Appleford.
APLT → Abelwhite, Abilowitz, Ablett, Ablewhite, Ablitt, Ablott, Appleton, Applewhaite, Applewhite, Epelett, Epilet, Eplate, Eplett, Euplate, Ipplett.
LPS → Labbez, Labes, Libbis, Llopis, Lopes, Lopez.
MKTSMackiewicz, Mccuthais, Mecozzi.
MTF → Mateev, Mathew, Mattevi, Mattheeuw, Matthew, Middiff.
M0 → Maith, Mathe, Mathew, Mathey, Mathie, Mathieu, Mathou, Mathy, Matthai, Mattheeuw, Matthew, Matthiae, Meth, Moth, Mouth.
SLFT → Salvador, Salvadore, Salvadori, Salvati, Salvatore, Slaughter.

Double Metaphone matches 8 or 9 surnames on the average to the same code.


Caverphone algorithm was developed in 2002 as part of one of New Zealand project to match the data in the old and new electoral lists, therefore it is most focused on a New Zealand pronunciation, but for foreign surnames ut gives quite acceptable results.

Caverphone code computation algorithm
  1. Convert the first or last name to lowercase (the algorithm is case sensitive).
  2. Remove letters e at the end.
  3. Transform the beginning of the word using the table below (This is relevant only for New Zealand names). In this case digit 2 means temporary placeholder for a consonant letter, which will subsequently be removed.
  4. Replace the letters using the table below:
  5. Replace all vowel at the word beginning with A, in other cases replace them with 3. So the digit 3 is a temporary placeholder for a vowel letter, that will be used in subsequent transformations and then will be removed. At the next step, it is necessary to replace using the following tables (the legend: s+ - group of consecutive letters, ^h - letter at the start, w$ - letter at the end):
  6. Remove all digits 2. If there is a digit 3 at the end 3, replace it with A. After that remove all digits 3.
  7. Truncate the word to 10 letters or fill it to 10 letters with digit 1.
ANRKSN1111 → Henrichsen, Henricsson, Henriksson, Hinrichsen.
ASKKA11111 → Izchaki.
MKLFTA1111 → Maclaverty, Mccleverty, Mcclifferty, Mclafferty, Mclaverty.
SLKMP11111 → Slocomb, Slocombe, Slocumb.
WTLM111111 → Whitlam.

Caverphone matches about 4-5 surnames to the same code.


Most of these algorithms are implemented in a variety of languages, including C, C + +, Java, C # and PHP. Some of them, like Soundex and Metaphone, integrated or implemented as plug-ins for many popular databases, as well as used in the full-fledged search engines (for example, Apache Lucene). Their application is specific enough, because they are mostly suitable for surnames.


  1. Java source code for this article. Fuzzy-search-tools project on Google Code
  2. Soundex, Refined Soundex, Metaphone, Double Metaphone and Caverphone Java implementations.
    Apache Commons Codec
  3. NYSIIS Java implementation. Egothor project
  4. Daitch-Mokotoff Soundex Java implementation.
  5. Soundex description.
  6. Daitch-Mokotoff Soundex description.
  7. NYSIIS description.
  8. Metaphone description.
  9. Double Metaphone description.
  10. Russian Metaphone description.
  11. Caverphone description.
  12. Soundex online demo.
  13. NYSIIS online demo.
  14. Daitch-Mokotoff Soundex online demo.
  15. Metaphone online demo.

Wednesday, March 9, 2011

Нечёткий поиск в тексте и словаре


Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:
  • Расстояние Левенштейна
  • Расстояние Дамерау-Левенштейна
  • Алгоритм Bitap с модификациями от Wu и Manber
  • Алгоритм расширения выборки
  • Метод N-грамм
  • Хеширование по сигнатуре
  • BK-деревья
А также проведу сравнительное тестирование качества и производительности алгоритмов.


Нечеткий поиск является крайне полезной функцией любой поисковой системы. Вместе с тем, его эффективная реализация намного сложнее, чем реализация простого поиска по точному совпадению.

Задачу нечеткого поиска можно сформулировать так:
«По заданному слову найти в тексте или словаре размера n все слова, совпадающие с этим словом (или начинающиеся с этого слова) с учетом k возможных различий».

Например, при запросе «Машина» с учетом двух возможных ошибок, найти слова «Машинка», «Махина», «Малина», «Калина» и так далее.

Алгоритмы нечеткого поиска характеризуются метрикой — функцией расстояния между двумя словами, позволяющей оценить степень их сходства в данном контексте. Строгое математическое определение метрики включает в себя необходимость соответствия условию неравенства треугольника (X — множество слов, p — метрика):

Неравенство треугольника

Между тем, в большинстве случаев под метрикой подразумевается более общее понятие, не требующее выполнения такого условия, это понятие можно также назвать расстоянием.

В числе наиболее известных метрик — расстояния Хемминга, Левенштейна и Дамерау-Левенштейна. При этом расстояние Хемминга является метрикой только на множестве слов одинаковой длины, что сильно ограничивает область его применения.

Впрочем, на практике расстояние Хемминга оказывается практически бесполезным, уступая более естественным с точки зрения человека метрикам, о которых и пойдет речь ниже.

Расстояние Левенштейна

Наиболее часто применяемой метрикой является расстояние Левенштейна, или расстояние редактирования, алгоритмы вычисления которого можно найти на каждом шагу.
Тем не менее, стоит сделать несколько замечаний относительно наиболее популярного алгоритма расчета - метода Вагнера-Фишера.
Исходный вариант этого алгоритма имеет временную сложность O(mn) и потребляет O(mn) памяти, где m и n — длины сравниваемых строк. Весь процесс можно представить следующей матрицей:

Матрица расстояний Левенштейна

Если посмотреть на процесс работы алгоритма, несложно заметить, что на каждом шаге используются только две последние строки матрицы, следовательно, потребление памяти можно уменьшить до O(min(m, n)).

Процесс работы алгоритма Левенштейна

Но это еще не всё - можно дальше оптимизировать алгоритм, если стоит задача нахождения не более k различий. В этом случае нужно вычислять в матрице лишь диагональную полосу шириной 2k+1 (отсечение Укконена), что сводит временную сложность к O(k min(m, n)).

Префиксное расстояние
Также бывает необходимо вычислять расстояние между префиксом-образцом и строкой — т. е. найти расстояние между заданным префиксом и ближайшим префиксом строки. В этом случае необходимо взять наименьшее из расстояний от префикса-образца до всех префиксов строки. Очевидно, что префиксное расстояние не может считаться метрикой в строгом математическом смысле, что ограничивает его применение.

Зачастую при нечетком поиске важно не столько само значение расстояния, сколько факт того, превышает оно или нет определенную величину.

Расстояние Дамерау-Левенштейна

Эта вариация вносит в определение расстояния Левенштейна еще одно правило - транспозиция (перестановка) двух соседних букв также учитывается как одна операция, наряду со вставками, удалениями и заменами.
Еще пару лет назад Фредерик Дамерау мог бы гарантировать, что большинство ошибок при наборе текста - как раз и есть транспозиции. Поэтому именно данная метрика дает наилучшие результаты на практике.

Процесс работы алгоритма Дамерау-Левенштейна

Чтобы вычислять такое расстояние, достаточно немного модифицировать алгоритм нахождения обычного расстояния Левенштейна следующим образом: хранить не две, а три последних строки матрицы, а также добавить соответствующее дополнительное условие — в случае обнаружения транспозиции при расчете расстояния также учитывать и её стоимость.

Кроме рассмотренных выше, существует еще множество других, иногда применяющихся на практике расстояний, таких как метрика Джаро-Винклера, многие из которых доступны в библиотеках SimMetrics и SecondString.

Алгоритмы нечеткого поиска без индексации (Онлайн)

Эти алгоритмы предназначены для поиска по заранее неизвестному тексту, и могут быть использованы, например, в текстовых редакторах, программах для просмотра документов или в веб-браузерах для поиска по странице. Они не требуют предварительной обработки текста и могут работать с непрерывным потоком данных.

Линейный поиск

Простое последовательное применение заданной метрики (например, метрики Левенштейна) к словам из входного текста. При использовании метрики с ограничением, этот метод позволяет добиться оптимальной скорости работы. Но, при этом, чем больше k, тем сильнее возрастает время работы. Асимптотическая оценка времени — O(kn).

Bitap (также известный как Shift-Or или Baeza-Yates-Gonnet, и его модификация от Wu-Manber)

Алгоритм Bitap и различные его модификации наиболее часто используются для нечеткого поиска без индексации. Его вариация используется, например, в unix-утилите agrep, выполняющей функции аналогично стандартному grep, но с поддержкой ошибок в поисковом запросе и даже предоставляя ограниченные возможности для применения регулярных выражений.

Впервые идею этого алгоритма предложили граждане Ricardo Baeza-Yates и Gaston Gonnet, опубликовав соответствующую статью в 1992 году.
Оригинальная версия алгоритма имеет дело только с заменами символов, и, фактически, вычисляет расстояние Хемминга. Но немного позже Sun Wu и Udi Manber предложили модификацию этого алгоритма для вычисления расстояния Левенштейна, т.е. привнесли поддержку вставок и удалений, и разработали на его основе первую версию утилиты agrep.

Операция Bitshift

         Операция Bitshift

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

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

Высокая скорость работы этого алгоритма обеспечивается за счет битового параллелизма вычислений - за одну операцию возможно провести вычисления над 32 и более битами одновременно.
При этом тривиальная реализация поддерживает поиск слов длиной не более 32. Это ограничение обуславливается шириной стандартного типа int (на 32-битных архитектурах). Можно использовать и типы больших размерностей, но это может в некоторой степени замедлить работу алгоритма.

Не смотря на то, что асимптотическое время работы этого алгоритма O(kn) совпадает с таковым у линейного метода, он значительно быстрее при длинных запросах и количестве ошибок k более 2.


Тестирование осуществлялось на тексте 3.2 млн слов, средняя длина слова - 10.

Точный поиск
Время поиска: 3562 мс

Поиск с использованием метрики Левенштейна
Время поиска при k=2: 5728 мс
Время поиска при k=5: 8385 мс

Поиск с использованием алгоритма Bitap с модификациями Wu-Manber
Время поиска при k=2: 5499 мс
Время поиска при k=5: 5928 мс

Очевидно, что простой перебор с использованием метрики, в отличие от алгоритма Bitap, сильно зависит от количества ошибок k.

Тем не менее, если речь заходит о поиске в неизменных текстах большого объема, то время поиска можно значительно сократить, произведя предварительную обработку такого текста, также называемую индексацией.

Алгоритмы нечеткого поиска с индексацией (Оффлайн)

Особенностью всех алгоритмов нечеткого поиска с индексацией является то, что индекс строится по словарю, составленному по исходному тексту или списку записей в какой-либо базе данных.

Эти алгоритмы используют различные подходы к решению проблемы - одни из них используют сведение к точному поиску, другие используют свойства метрики для построения различных пространственных структур и так далее.

Прежде всего, на первом шаге по исходному тексту строится словарь, содержащий слова и их позиции в тексте. Также, можно подсчитывать частоты слов и словосочетаний для улучшения качества результатов поиска.

Предполагается, что индекс, как и словарь, целиком загружен в память.

Тактико-технические характеристики словаря:
  • Исходный текст — 8.2 гигабайта материалов библиотеки Мошкова (, 680 млн слов;
  • Размер словаря — 65 мегабайт;
  • Количество слов — 3.2 млн;
  • Средняя длина слова — 9.5 символов;
  • Средняя квадратичная длина слова (может быть полезна при оценке некоторых алгоритмов) — 10.0 символов;
  • Алфавит — заглавные буквы А-Я, без Ё (для упрощения некоторых операций). Слова, содержащие символы не из алфавита, не включены в словарь.
Зависимость размера словаря от объема текста не является строго линейной — до некоторого объема формируется базовый каркас слов, составляющий от 15% на 500 тысячах слов до 5% на 5 миллионах, и затем зависимость приближается к линейной, медленно убывая и доходя до 0.5% на 680 млн слов. Последующее сохранение роста обеспечивается в большинстве своем за счет редких слов.

Рост размера словаря

Алгоритм расширения выборки

Этот алгоритм часто применяется в системах проверки орфографии (т.е. в spell-checker'ах), там, где размер словаря невелик, либо же где скорость работы не является основным критерием.
Он основан на сведении задачи о нечетком поиске к задаче о точном поиске.

Из исходного запроса строится множество "ошибочных" слов, для каждого из которых затем производится точный поиск в словаре.

Расширение выборки

Время его работы сильно зависит от числа k ошибок и от размера алфавита A, и в случае использования бинарного поиска по словарю составляет:

Например, при k = 1 и слова длины 7 (например, "Крокодил") в русском алфавите множество ошибочных слов будет размером около 450, то есть будет необходимо сделать 450 запросов к словарю, что вполне приемлемо.
Но уже при k = 2 размер такого множества будет составлять более 115 тысяч вариантов, что соответствует полному перебору небольшого словаря, либо же 1 / 27 в нашем случае, и, следовательно, время работы будет достаточно велико. При этом не нужно забывать еще и о том, что для каждого из таких слов необходимо провести поиск на точное совпадение в словаре.

Алгоритм может быть легко модифицирован для генерации «ошибочных» вариантов по произвольным правилам, и, к тому же, не требует никакой предварительной обработки словаря, и, соответственно, дополнительной памяти.

Возможные улучшения:
Можно генерировать не всё множество «ошибочных» слов, а только те из них, которые наиболее вероятно могут встретиться в реальной ситуации, например, слова с учетом распространенных орфографических ошибок или ошибок набора.

Метод N-грамм

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

Метод N-грамм

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

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

Между тем, метод N-грамм оставляет полный простор для использования собственных метрик с произвольными свойствами и сложностью, но за это приходится платить - при его использовании остается необходимость в последовательном переборе около 15% словаря, что достаточно много для словарей большого объема.

Возможные улучшения:
Можно разбивать хеш-таблицы N-грамм по длине слов и по позиции N-граммы в слове (модификация 1). Как длина искомого слова и запроса не могут отличаться более чем на k, так и позиции N-граммы в слове могут различаться не более чем на k. Таким образом, необходимо будет проверить лишь таблицу, соответствующую позиции этой N-граммы в слове, а также k таблиц слева и k таблиц справа, т.е. всего 2k+1 соседних таблиц.

Модификация 1 метода N-грамм

Можно еще немного уменьшить размер необходимого для просмотра множества, разбив таблицы по длине слова, и аналогичным образом просматривая только соседние 2k+1 таблицы (модификация 2).

Хеширование по сигнатуре

Этот алгоритм описан в статье Бойцова Л.М. "Хеширование по сигнатуре". Он базируется на достаточно очевидном представлении «структуры» слова в виде битовых разрядов, используемой в качестве хеша (сигнатуры) в хеш-таблице.

При индексации такие хеши вычисляются для каждого из слов, и в таблицу заносится соответствие списка словарных слов этому хешу. Затем, во время поиска, для запроса вычисляется хеш и перебираются все соседние хеши, отличающиеся от исходного не более чем в k битах. Для каждого из таких хешей производится перебор списка соответствующих ему слов.

Процесс вычисления хеша - каждому биту хеша сопоставляется группа символов из алфавита. Бит 1 на позиции i в хеше означает, что в исходном слове присутствует символ из i-ой группы алфавита. Порядок букв в слове абсолютно никакого значения не имеет.

Хеширование по сигнатуре

Удаление одного символа либо не изменит значения хеша (если в слове еще остались символы из той же группы алфавита), либо же соответствующий этой группе бит изменится в 0. При вставке, аналогичным образом либо один бит встанет в 1, либо никаких изменений не будет. При замене символов всё немного сложнее - хеш может либо вовсе остаться неизменным, либо же изменится в 1 или 2 позициях. При перестановках никаких изменений и вовсе не происходит, потому что порядок символов при построении хеша, как и было замечено ранее, не учитывается. Таким образом, для полного покрытия k ошибок нужно изменять не менее 2k бит в хеше.

Список хешей с ошибками

Время работы, в среднем, при k "неполных" (вставки, удаления и транспозиции, а также малая часть замен) ошибках:
Асимптотическое время работы хеширования по сигнатуре

Из того, что при замене одного символа могут изменятся сразу два бита, алгоритм, реализующий, например, искажения не более 2 битов одновременно в действительности не будет выдавать полного объема результатов из-за отсутствия значительной (зависит от отношения размера хеша к алфавиту) части слов с двумя заменами (и чем больше размер хеша, тем чаще замена символа будет приводить к искажению сразу двух бит, и тем менее полным будет результат). К тому же, этот алгоритм не позволяет проводить префиксный поиск.


Деревья Burkhard-Keller являются метрическими деревьями, алгоритмы построения таких деревьев основаны на свойстве метрики отвечать неравенству треугольника:

Неравенство треугольника

Это свойство позволяет метрикам образовывать метрические пространства произвольной размерности. Такие метрические пространства не обязательно являются евклидовыми, так, например, метрики Левенштейна и Дамерау-Левенштейна образуют неевклидовы пространства. На основании этих свойств можно построить структуру данных, осуществляющую поиск в таком метрическом пространстве, которой и являются деревья Баркхарда-Келлера.


Можно использовать возможность некоторых метрик вычислять расстояние с ограничением, устанавливая верхний предел, равный сумме максимального расстояния к потомкам вершины и результирующего расстояния, что позволит немного ускорить процесс:

Ограничение метрики в алгоритме BK-деревьев


Тестирование осуществлялось на ноутбуке с Intel Core Duo T2500 (2GHz/667MHz FSB/2MB), 2Gb ОЗУ, ОС — Ubuntu 10.10 Desktop i686, JRE — OpenJDK 6 Update 20.

Сравнение времени работы

Тестирование осуществлялось с использованием расстояния Дамерау-Левенштейна и количеством ошибок k = 2. Размер индекса указан вместе со словарем (65 Мб).

Расширение выборки
Размер индекса: 65 Мб
Время поиска: 320 мс / 330 мс
Полнота результатов: 100%

N-грамм (оригинальный)
Размер индекса: 170 Мб
Время создания индекса: 32 с
Время поиска: 71 мс / 110 мс
Полнота результатов: 65%

N-грамм (модификация 1)
Размер индекса: 170 Мб
Время создания индекса: 32 с
Время поиска: 39 мс / 46 мс
Полнота результатов: 63%

N-грамм (модификация 2)
Размер индекса: 170 Мб
Время создания индекса: 32 с
Время поиска: 37 мс / 45 мс
Полнота результатов: 62%

Хеширование по сигнатуре
Размер индекса: 85 Мб
Время создания индекса: 0.6 с
Время поиска: 55 мс
Полнота результатов: 56.5%

Размер индекса: 150 Мб
Время создания индекса: 120 с
Время поиска: 540 мс
Полнота результатов: 63%


Большинство алгоритмов нечеткого поиска с индексацией не являются истинно сублинейными (т.е. имеющими асимптотическое время работы O(log n) или ниже), и их скорость работы обычно напрямую зависит от N. Тем не менее, множественные улучшения и доработки позволяют добиться достаточного малого времени работы даже при весьма больших объемах словарей.

Существует также еще множество разнообразных и неэффективных методов, основанных, помимо всего прочего, на адаптации различных, уже где-либо применяемых техник и приемов к данной предметной области. В числе таких методов - адаптация префиксных деревьев (Trie) к задачам нечеткого поиска, которую я оставил без внимания в виду её малой эффективности. Но есть и алгоритмы, основанные на оригинальных подходах, например, алгоритм Маасса-Новака, который хоть и имеет сублинейное асимптотическое время работы, но является крайне неэффективным из-за огромных констант, скрывающихся за такой временной оценкой, которые проявляются в виде огромного размера индекса.

Практическое использование алгоритмов нечеткого поиска в реальных поисковых системах тесно связано с фонетическими алгоритмами, алгоритмами лексического стемминга - выделения базовой части у различных словоформ одного и того же слова (например, такую функциональность предоставляют Snowball и Яндекс mystem), а также с ранжированием на основе статистической информации, либо же с использованием сложных изощренных метрик.

По ссылке можно найти мои реализации на Java:
  • Расстояние Левенштейна (с отсечением и префиксным вариантом);
  • Расстояние Дамерау-Левенштейна (с отсечением и префиксным вариантом);
  • Алгоритм Bitap (Shift-OR / Shift-AND с модификациями Wu-Manber);
  • Алгоритм расширения выборки;
  • Метод N-грамм (оригинальный и с модификациями);
  • Метод хеширования по сигнатуре;
  • BK-деревья.
Я хотел сделать код удобным для понимания, и вместе с тем достаточно эффективным для практического применения. Выжимать же последние соки из JVM в мои задачи не входило. Enjoy.

Стоит заметить, что в процессе изучения этой темы у меня появились кое-какие собственные наработки, позволяющие на порядок сократить время поиска за счет умеренного увеличения размера индекса и некоторого ограничения в свободе выбора метрик. Но это уже совсем другая история.


  1. Исходные коды к статье на Java.
  2. Расстояние Левенштейна.Расстояние_Левенштейна
  3. Расстояние Дамерау-Левенштейна.–Levenshtein_distance
  4. Хорошее описание Shift-Or c модификациями Wu-Manber, правда, на немецком.
  5. Метод N-грамм.
  6. Хеширование по сигнатуре.
  7. Сайт Леонида Моисеевича Бойцова, целиком посвященный нечеткому поиску.
  8. Реализация Shift-Or и некоторых других алгоритмов.
  9. Fast Text Searching with Agrep (Wu & Manber).
  10. Damn Cool Algorithms - автомат Левенштейна, BK-деревья, и еще кое-какие алгоритмы.
  11. BK-деревья на Java.
  12. Алгоритм Маасса-Новака.
  13. Библиотека метрик SimMetrics.
  14. Библиотека метрик SecondString.

English version: Fuzzy string search
На Хабрахабре: Нечёткий поиск в тексте и словаре

Friday, March 4, 2011

Фонетические алгоритмы

Фонетические алгоритмы сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства.

Часто довольно трудно найти в базе нетипичную фамилию, например:
— Леха, поищи в нашей базе Адольфа Швардсенеггера,
Шворцинегира? Нет такого!
В этом случае использование фонетических алгоритмов (особенно в сочетании с алгоритмами нечеткого сопоставления) может значительно упростить задачу.

Такие алгоритмы очень удобно использовать при поиске в базах по спискам людей, в программах проверки орфографии. Зачастую они используются совместно с алгоритмами нечеткого поиска (которые, несомненно, заслуживают отдельной статьи), предоставляя пользователям удобный поиск по именам и фамилиям в различных базах данных, списках сотрудников и так далее.

В этой статье я рассмотрю наиболее известные алгоритмы, такие как Soundex, Daitch-Mokotoff Soundex, NYSIIS, Metaphone, Double Metaphone, русский Metaphone, Caverphone.


Одним из первых был алгоритм Soundex, изобретенный еще в 10-x годах прошлого века Робертом Расселом. Этот алгоритм (а точнее, его американская версия) сопоставляет словам численный индекс вида A126. Принцип его работы основан на разбиении согласных букв на группы с порядковыми номерами, из которых затем и составляется результирующее значение. Позднее также был предложен ряд улучшений.


Первая буква сохраняется, последующие буквы сопоставляются цифрам по таблице. Символы, не представленные в таблице (а это все гласные и некоторые согласные), игнорируются. Смежные символы, или символы, разделенные буквами H или W, входящие в одну и ту же группу, записываются как один. Результат обрезается до 4 символов. Недостающие позиции заполняются нулями. Несложно заметить, что после всех этих процедур остается всего лишь 7 тысяч различных вариаций такого кода, что влечет за собой множество совершенно ничем не похожих друг на друга слов, имеющих одинаковый Soundex-код. Таким образом, результат в большинстве случаев включает в себя большое количество "ложноположительных" значений.


В улучшенной версии, как можно заметить, буквы разбиты на большее количество групп. Помимо этого, никакого особого внимания буквам H и W не уделяется, они просто игнорируются. Кроме того, никаких операций с длиной результата не производится - код не имеет фиксированной длины и не обрезается.

Оригинальный Soundex:
D341 → Дедловский, Дедловских, Дидилев, Дителев, Дудалев, Дудолев, Дутлов, Дыдалев, Дятлов, Дятлович.
N251 → Нагимов, Нагмбетов, Назимов, Насимов, Нассонов, Нежнов, Незнаев, Несмеев, Нижневский, Никонов, Никонович, Нисенблат, Нисенбаум, Ниссенбаум, Ногинов, Ножнов.

Улучшенный Soundex:
N8030802 → Насимов, Нассонов, Никонов.
N80308108 → Нисенбаум, Ниссенбаум.
N8040802 → Нагимов, Нагонов, Неганов, Ногинов.
N804810602 → Нагмбетов.
N8050802 → Назимов, Нежнов, Ножнов.

В среднем, на одно значение кода Soundex приходится 21 фамилия. В случае же улучшенной версии Soundex, к одному и тому же коду преобразуются всего 2-3 фамилии.


Разработанный в 1970 году как часть системы "New York State Identification and Intelligence System", этот алгоритм дает несколько лучшие результаты относительно оригинального Soundex, используя более сложные правила преобразования исходного слова в результирующий код. Этот алгоритм разработан для работы именно с американскими фамилиями.

Алгоритм вычисления кода NYSIIS
  1. Преобразовать начало слова по следующим правилам:
    MAC → MCC
    KN → N
    K → C
    PH, PF → FF
    SCH → SSS
  2. Преобразовать конец слова по следующим правилам:
    EE → Y
    IE → Y
    DT, RT, RD, NT, ND → D
  3. Затем все буквы, кроме первой, преобразуются по следующим правилам:
    EV → AF
    A, E, I, O, U → A
    Q → G
    Z → S
    M → N
    KN → N
    K → C
    SCH → SSS
    PH → FF
    После гласных: удалить H, преобразовать W → A
  4. Удалить S на конце
  5. Преобразуем AY на конце → Y
  6. Удалить A на конце
  7. Обрезать до 6 символов (необязательный шаг).
CASPARAVAS → Каспаравичус, Касперович, Каспирович.
CATNACAV → Катников, Цитников, Цотников.
LANSANC → Ленченко, Леонченко, Линченко, Лунченко, Лямзенко.
PRADSC → Приходский, Проходский, Прудский, Прудских, Прудской.
STADNACAV → Стадников.

NYSIIS преобразует к одному и тому же коду немногим более двух фамилий.

Daitch-Mokotoff Soundex

Этот алгоритм в 1985 году разработали два генеалога - Гарри Мокотофф и Рэнди Дэйч, стремясь достичь лучших, относительно оригинального Soundex, результатов при работе со восточно-европейскими (в том числе русскими) фамилиями.
Этот алгоритм имеет мало общего с оригинальным Soundex, разве что результатом всё так же остается последовательность цифр, однако теперь первая буква также кодируется.

Он имеет значительно более сложные правила конверсии - теперь в формировании результирующего кода участвуют не только одиночные символы, но и последовательности из нескольких символов. Кроме того, результат вида 023689 обеспечивает около 600 тысяч различных вариаций кода, что вкупе с усложненными правилами уменьшает количество "лишних", т.е. "ложноположительных" слов в результирующем множестве.

Преобразования осуществляются по следующей таблице (порядок преобразований соответствует порядку буквосочетаний в таблице):
Исходные буквосочетанияВ началеЗа гласнойОстальное
AI, AJ, AY, EI, EY, EJ, OI, OJ, OY, UI, UJ, UY01
A, UE, E, I, O, U, Y0
DT, D, TH, T333
CHS, KS, X55454
S, Z444
CH, CK, C, G, KH, K, Q555
MN, NM6666
M, N666
FB, B, PH, PF, F, P, V, W777
"Альтернативные" варианты буквосочетаний (используются для генерации нескольких альтернативных кодов из исходного слова):
C → TZ

095747Архипцев, Архипцов, Архипычев, Арцыбасов, Арцыбашев, Арчибасов
095757 → Архипков, Архипцев, Архипцов, Архипычев
584360 → Галстян, Галустян, Гильштейн, Глистин, Глуздань, Голштейн, Гольдштеин, Гольдштейн, Калустьян, Хлистун, Хлыстун, Хлюстин.

К одному и тому же коду этот алгоритм преобразует в среднем 5 фамилий.

Впоследствии Александр Бейдер и Стивен Морзе разработали Beider-Morse Name Matching Algorithm, нацеленный на уменьшение количества "ложноположительных" значений относительно Daitch-Mokotoff Soundex при работе с еврейскими (ашкенази) фамилиями.


Несколько лучшими характеристиками обладает алгоритм Metaphone (1990 год), отличающийся от предыдущих алгоритмов несколько иным подходом к процессу кодирования: он преобразует исходное слово с учетом правил английского языка, используя заметно более сложные правила, и при этом теряется значительно меньше информации, так как буквы не разбиваются на группы. Итоговый код представляет собой набор символов из множества 0BFHJKLMNPRSTWXY, в начале слова также могут быть гласные из множества AEIOU.

Алгоритм вычисления кода Metaphone
  1. Удаляем все повторяющиеся соседние буквы, за исключением буквы C.
  2. Начало слова преобразовать по следующим правилам:
    KN → N
    GN → N
    PN → N
    AE → E
    WR → R
  3. Удаляем на конце букву B, если она идет после M.
  4. Заменяем C по следующим правилам
    На Х: CIA → XIA, SCH → SKH, CH → XH
    На S: CI → SI, CE → SE, CY → SY
    На K: C → K
  5. Заменяем D по следующим правилам
    На J: DGE → JGE, DGY → JGY, DGI → JGY
    На T: D → T
  6. Заменяем GH → H, если это буквосочетание стоит не в конце и не перед гласной.
  7. Заменяем GN → N и GNED → NED, если эти буквосочетания стоят в конце.
  8. Заменяем G по следующим правилам
    На J: GI → JI, GE → JE, GY → JY
    на K: G → K
  9. Удаляем все H, идущие после гласных, но не перед гласными.
  10. Выполняем последующие преобразования по правилам:
    CK → K
    PH → F
    Q → K
    V → F
    Z → S
  11. Заменяем S на X:
    SH → XH
    SIO → XIO
    SIA → XIA
  12. Заменяем T по следующим правилам
    На X: TIA → XIA, TIO → XIO
    На 0: TH → 0
    Удаляем: TCH → CH
  13. В начале слова преобразовать WH → W. Если после W нет гласной, то удалить W.
  14. Если X в начале слова, то преобразовать X → S, иначе X → KS
  15. Удалить все Y, которые не находятся перед гласными.
  16. Удалить все гласные, кроме начальной.
AKXN → Агашин, Акаченок, Акишин, Аксионенко, Аксионов, Акчунаев, Акшанов, Акшенцев, Акшинский, Акшинцев, Акшонов.
FSLX → Василишин, Васильчак, Васильченко, Васильчик, Васильчиков, Васильченко, Васильчук, Василющенко.
SRFM → Серафимов, Серафимский, Серафимчук, Церейфман.

Одно и то же значение кода Metaphone имеют в среднем 6 фамилий.

Double Metaphone

Double Metaphone (2000 год) несколько отличается от других фонетических алгоритмов, генерируя из исходного слова не один, а два кода (оба длиной до 4 символов) - один отражает основной вариант произношения слова, другой же - альтернативную версию. Он имеет большое количество различных правил, учитывающих, помимо всего прочего, различное происхождение слов, уделяя внимание восточно-европейским, итальянским, китайским словам и так далее. Правила преобразований достаточно многочисленны, я не буду их публиковать, а желающие смогут прочитать о них в статье журнала Dr Dobbs.

KKRF → Гагаров, Кагаров, Качаровский, Качеровский, Качуривский, Качуров, Качуровский, Кичеров, Кокарев, Кокоуров, Кокоуров, Кочаров, Кочуров, Кукарев, Цакиров, Цокуров, Цугров.
KXRFГишаров, Гочаров, Качеров, Качеровский, Кашаревский, Кочаров, Кочерев, Кочеряев, Кочураев, Кошарев, Кошеров.
PNFS → Бановский, Бахновский, Биневский, Бинявский, Буйновский, Буяновский, Паневский, Пановский, Пановских, Пеньевский, Пиневский, Пиуновский, Пихновский.

Double Metaphone сопоставляет в среднем 8-9 фамилий одному и тому же коду.

Русский Metaphone

В 2002 году в 8-ом выпуске журнала "Программист" была опубликована статья Петра Каньковски, рассказывающая о его адаптации английской версии алгоритма Metaphone к суровым сибирским морозам, медведям и балалайкам. Этот алгоритм преобразует исходные слова в соответствии с правилами и нормами русского языка, учитывая фонетическое звучание безударных гласных и возможные "слияния" согласных при произношении. Он показывает очень хорошие результаты на практике, несмотря на то, что основывается на довольно простых правилах. Все буквы разбиты на группы по звучанию - гласные и согласные (vowels и consonants соответственно в английской терминологии), глухие и звонкие. Звонкие согласные преобразуются в соответствующие им парные глухие, объединяются "сливающиеся" при произношении последовательности букв, и проводятся некоторые другие манипуляции. Ниже я приведу немного доработанный вариант, который, в отличие от оригинала Петра Каньковски, привносит правила, связанные с фонетической эквивалентностью Ц и ТС или ДС, и не сжимает окончания - байты экономить - это не наша задача.

Алгоритм вычисления кода русского Metaphone
  1. Для всех гласных букв проделать следующие операции.
    ЙО, ИО, ЙЕ, ИЕ → И
    О, Ы, Я → А
    Е, Ё, Э → И
    Ю → У
  2. Для всех согласных букв, за которыми следует любая согласная, кроме Л, М, Н или Р, либо же для согласных на конце слова, провести оглушение:
    Б → П
    З → С
    Д → Т
    В → Ф
    Г → К
  3. Склеиваем ТС и ДС в Ц:
    ТС → Ц
В итоге, алгоритм очень хорошо справляется со своей задачей - в результирующем наборе содержатся действительно фонетически схожие слова. И при этом остается довольно мало лишних слов, в основном благодаря тому, что гласные не игнорируются, а преобразуются и используются в итоговом коде. Однако же, есть некоторые слова, которые, не смотря на свою фонетическую схожесть, не попадают в результирующий набор из-за слишком "строгих" правил алгоритма.

В случае Адольфа Швардсенеггера результатом работы алгоритма русского Metaphone будет:


Таким образом, алгоритм в данном случае отражает реальное фонетическое сходство этих двух фамилий.

ВИТАФСКИЙ → Витавский, Витовский.
ВИТИНБИРК → Витенберг, Виттенберг.
НАСАНАФ → Насанов, Насонов, Нассонов, Носонов.
ПИРМАКАФ → Пермаков, Пермяков, Перьмяков.

Этот алгоритм преобразует к одному и тому же коду в среднем 1-2 фамилии.


Алгоритм Caverphone был разработан в 2002 году в рамках одного из новозеландских проектов для сопоставления данных в старых и новых электоральных списках, потому он наиболее ориентирован на местное произношение, хотя и для русских фамилий он дает вполне приемлемые результаты.

Алгоритм вычисления кода Caverphone
  1. Преобразовать имя или фамилию в нижний регистр (алгоритм чувствителен к регистру).
  2. Удалить буквы e на конце.
  3. Преобразовать начало слова по следующей таблице (актуально для местных новозеландских имен и фамилий). При этом цифра 2 означает временную метку для согласной буквы, которая впоследствии будет удалена.
  4. Провести замены символов по следующей таблице:
  5. Заменить все гласные в начале слова на A, в остальных случаях - на 3. Таким образом, цифра 3 служит временной меткой для гласной буквы, которая будет использоваться в последующих преобразованиях, а затем будет удалена. После, необходимо провести замены по следующим таблицам (условные обозначения: s+ - несколько идущих подряд символов, ^h - символ в начале строки, w$ - символ на конце строки):
  6. Удалить все цифры 2. Если на конце слова осталась цифра 3, то заменить её на A. Затем удалить все цифры 3.
  7. Обрезать слово до 10 символов, либо же дополнить до 10 символов единицами.
KPRLN11111 → Габрелян, Габриэлян, Габриэльян, Капарулин, Капралин, Капрелян.
MSRFK11111 → Мейзерович, Мисарович, Мисюревич.
PLLF111111 → Балалаев, Балалиев, Балалуев, Билалиев, Билалов, Билялов, Болелов, Палилов, Полилов, Полуляхов.

Caverphone сопоставляет одному и тому же коду около 4-5 фамилий.


Большая часть этих алгоритмов реализована на множестве языков, в том числе на C, C++, Java, C# и PHP. Некоторые из них, например Soundex и Metaphone, интегрированы или реализованы в виде плагинов для многих популярных СУБД, а также используются в составе полноценных поисковых движков, например, Apache Lucene. Область их применения довольно специфична, ведь значительного повышения удобства для пользователей можно добиться лишь при поиске фамилий, но тем не менее грамотное их использование - это плюс для поисковых систем.


  1. Код на Java к статье. Яндекс.Диск
  2. Реализации Soundex, Refined Soundex, Metaphone, Double Metaphone, Caverphone на Java.
    Apache Commons Codec
  3. Реализация NYSIIS на Java. Проект Egothor
  4. Реализация Daitch-Mokotoff Soundex на Java.
  5. Описание Soundex.
  6. Описание Daitch-Mokotoff Soundex.
  7. Описание NYSIIS.
  8. Описание Metaphone.
  9. Описание Double Metaphone.
  10. Описание русского Metaphone.
  11. Описание Caverphone.
  12. Онлайн-демо Soundex.
  13. Онлайн-демо NYSIIS.
  14. Онлайн-демо Daitch-Mokotoff Soundex.
  15. Онлайн-демо Metaphone.

English version: Phonetic algorithms
На Хабрахабре: Фонетические алгоритмы