Indexes and the Metaphone, Soundex and NYSIIS Algorithms for Fuzzy Search

Phonetic algorithms

When using text mining algorithms, typos quite often arise in practice; one way of dealing with them is using trigrams. The drawback of this approach is that it works poorly with words shorter than 5-7 characters. An alternative way — is the use of phonetic algorithms, which assign the same codes to two words with similar pronunciation, allowing comparison and indexing of many such words based on their phonetic similarity.

Let's look at the best-known algorithms, such as Soundex, Daitch-Mokotoff Soundex, NYSIIS, Metaphone, Double Metaphone, Russian Metaphone, Caverphone.

The Soundex algorithm

Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for names with the same pronunciation to be encoded into the same representation, so that they can be matched despite minor differences in spelling.

Soundex — is an algorithm for encoding proper names. It was created in 1918–1922 in the USA by Robert Russell and Margaret King Odell, to make it easier to find similar-sounding surnames. In the middle of the 20th century Soundex was widely used in the USA when analyzing the results of the 1890–1920 population censuses. Below is an example of a card with data from the 1910 population census. Here you can see that the Soundex code for the surname Wilson looks like W425:

Two words with similar pronunciation correspond to the same soundex key. This property can be used, for example, when searching a database, when the pronunciation of a word is known but its spelling is not. This function returns a string of 4 characters, starting with a letter.

This implementation of the soundex function is described by Donald Knuth in the book «The Art Of Computer Programming, vol. 3: Sorting And Searching», Addison-Wesley (1973), pp. 391-392.

If you want to implement search and want to add a «Did you mean» option like Google's. To do this, in the ispell dictionary of word forms we add a field containing the metaphone() or soundex() key, and during search we compute the keys of the words being searched for, and if the words themselves are not in the dictionary, we compute the keys for the searched words and suggest something similar from the dictionary.

Examples:

In this example, two completely different words green and grin will give the same soundex key, because they are pronounced the same way.

soundex — Returns the soundex key for a string

After performing the operation the picture «looks like this»:

And this is the best thing I managed to find on this topic.
Maybe someone knows of any more complete solutions for a Russian implementation of this function?

One such algorithm is Soundex, which assigns the same code of the form D321 to words that sound similar in English. Soundex was developed by Robert Russell and Margaret King Odell and patented in 1918 and 1922. This algorithm became popular in the 1960s, after becoming the subject of several articles in the journals «Communications of the Association for Computing Machinery» and «Journal of the Association for Computing Machinery» and was published in Donald Knuth's book.

One of the first was the Soundex algorithm, invented back in the 1910s by Robert Russell. This algorithm (or more precisely, its American version) maps words to a numeric index of the form A126. Its operating principle is based on dividing consonant letters into groups with sequential numbers, from which the resulting value is then composed. Later a number of improvements were also proposed.



The first letter is kept, and subsequent letters are mapped to digits according to a table. Symbols not represented in the table (that is, all vowels and some consonants) are ignored. Adjacent symbols, or symbols separated by the letters H or W, belonging to the same group, are recorded as one. The result is truncated to 4 characters. Missing positions are filled with zeros. It is easy to notice that after all these procedures only about 7 thousand different variations of such a code remain, which entails a large number of completely dissimilar words having the same Soundex code. Thus, the result in most cases includes a large number of «false positive» values.



In the improved version, as can be seen, the letters are divided into a larger number of groups. Besides that, no particular attention is paid to the letters H and W — they are simply ignored. In addition, no operations are performed on the length of the result — the code does not have a fixed length and is not truncated.

Let's understand how the original version of the algorithm works:

1. Remember the first letter. Remove all ‘h’ and ‘w’, except for the first letter of the word;
2. Replace consonants with digits from 1 to 6, with letters that sound similar being assigned the same digit:

3. Any sequence of identical digits is reduced to a single such digit.
4. Remove all a, e, i, o, u, y, except for the first letter of the word.
5. Replace the first character with the letter remembered in step 1, making it uppercase.
6. The resulting string is truncated to the first four characters. If the length of the string is shorter than required, the missing characters are replaced with the digit 0.

Thus, for the word Morphs the algorithm will generate the code M612. It is easy to notice that after all these procedures fewer than 10 thousand different variations of such a code remain, which entails a large number of completely dissimilar words having the same Soundex code. Thus, the result in most cases includes a large number of false positives.

To reduce false positives, an improved version of the Soundex algorithm was created, which, unlike the original, uses the following character encoding table:

Thus the number of codes increases to almost 19 thousand. Moreover, the restriction on code length is lifted (the code is not padded with the digit 0, and characters after the 4th are not removed).

Using the improved Soundex algorithm, the word Morphs will be encoded as M913.

Soundex works well with the English language; the remaining question is whether it can be used for the Russian language. It turns out it can. To do this, before computing the code with either the original or the improved algorithm, one needs to transliterate the source word from Russian.

Task 1. Given a list of surnames and their corresponding Soundex codes in scrambled order. Some characters are missing:

S312, T␣6␣, ␣5␣3, C42␣, T520, L␣42, A536, C155, ␣623, S356, ␣252, ␣152, ␣330, A251, A400, L2␣0

Task 2. Describe step by step how the Soundex code is generated.

Task 3. Match the surnames to the Soundex codes and fill in the missing characters.

Task 4. Build the Soundex codes for the following surnames: Ferguson, Fitzgerald, Hamnett, Keefe, Maxwell, Razey, Shaw, Upfield.

Hint — Each code consists of a letter and three digits. The letter repeats the first letter of the surname, and the digits encode the consonants that appear further on in the surname.

Solution

All Soundex codes consist of a Latin letter and three digits. It's not hard to guess why the code for the surname Wilson begins with W: because that is the first letter of that surname.

Once it became clear that the first letter is preserved, the task breaks down into six small tasks with scrambled correspondences:

Chapman, Colquhoun
C42␣, C155

Stanmore, Stubbs
S312, S356

Buckingham, Evans, Fairwright, Kingscott, Whytehead
␣5␣3, ␣623, ␣252, ␣152, ␣330

Recall that Soundex — is an algorithm designed to find similar-sounding words. Presumably, the digits must encode some characteristic sounds. One can hypothesize that they correspond to the consonant letters that occur in the surname. However, there are only six digits — which means that the same digit encodes entire groups of consonants.

These groups are as follows:

The classification of letters in Soundex more or less corresponds to the classification of sounds by how they are pronounced: group 1 contains consonants pronounced with the participation of the lips; group 2 — consonants pronounced with the back of the tongue, and sibilants; group 3 — front-lingual stops (d and t); group 5 — nasals. Based on this, we can also distribute into groups the letters we did not see in the given data (they are given in the table in parentheses). The letter f falls into group 1 with the labial consonants (where v already is, f being its voiceless-voiced pair), while x and z — fall into group 2 (x consists of k and s, which are in group 2, and z — is the voiced pair of s). The letters h and w did not make it into this table: they are ignored when generating the Soundex code. The same applies to the letter y, which in English is considered a vowel.

It can be noted that combinations of consonants from the same group correspond to only one digit in the code. For example, from the codes given in the data, the surname Kingscott can only correspond to ␣5␣3, in which 5 stands for n, 3 — for t, and the middle digit must stand for g, s and c (obviously, this will be the digit 2).

Zeros in the code correspond to cases where there were not enough consonants to fill three positions. For example, one can establish that Allaway — is A400, where the two l's correspond to 4, and a, w, a and y do not take part in the encoding.

Answers to the task

1. Summarizing all these observations, one can construct an encoding algorithm. It is important to pay attention to the order of operations, so that it allows obtaining all the codes without errors.

2. Leave the first letter unchanged.

4. Replace all consonants with digits (letters whose most common readings are similar are grouped together):

5. Reduce two or more identical digits in a row to one.

6. Keep only the first three digits, or add zeros on the right, so that the length of the code is one letter and three digits.

Answer to task 2 (restored characters are underlined).

Answer to task 3.

Ferguson: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwell: M240, Razey: R200, Shaw: S000, Upfield: U143.

Afterword

The problem for whose solution the Soundex algorithm was used (and at times continues to be used today) is generally called fuzzy search (approximate string matching, fuzzy string searching).

The ability to understand that two linguistic expressions are equivalent — is an important part of mastering human language. This ability can manifest at different levels. For example, at the level of semantics (word meanings) and syntax (relations between words in a phrase and sentence), a native speaker of Russian easily understands that the phrases Стометровую дистанцию он проплыл кролем за 45 секунд (He swam the hundred-meter distance freestyle in 45 seconds), На сто метров кролем у него ушло 45 секунд (The hundred meters freestyle took him 45 seconds) and Стометровку он проплыл кролем за ¾ минуты (He swam the hundred meters freestyle in ¾ of a minute) (Apresyan 1995: I, 12) mean the same thing. In just the same way, at the level of letters we easily understand that Муравьёва and Муравьева — (Muravyova) are one and the same surname, and Наталия and Наталья (Natalia) — are one and the same name (although in situations where one wants to nitpick, we might pretend to say something like «Well, but it says here Наталья Муравьева, and in your passport it's Наталия Муравьёва»). But automating this ability, which is so basic for us — understanding the equivalence of words and expressions that do not match exactly — is a very difficult task.

Such mismatches occur regularly in practice. Soundex was originally conceived precisely for matching proper names, since at the beginning of the 20th century the variability in the spelling of proper names was much higher than it is now — but even now it hasn't been fully reduced to zero. For instance, the book (Lisbach, Meyer 2013: 15) gives an example of two versions of recording information about the same person — for instance, taken down by ear at a call center and transcribed from documents with a split into fields:

An important advantage of Soundex, which largely secured its popularity, — is its ease of implementation: in particular, this algorithm doesn't need a dictionary. Soundex is mentioned in Donald Knuth's classic textbook «The Art of Computer Programming» (Knuth 1998: 395–396). However, in the first edition (Knuth 1973: 391–392) the author had not yet accounted for all the subtleties and proposed simultaneously discarding vowels, h and w; then, for example, Chapman would not give Chapman → Capman → Ca15a5 → C155, but rather Chapman → Cpmn → C155 → C15 → C150.

Soundex has been implemented in dozens of programming languages. For example, MySQL, a database management system, has a built-in SOUNDEX function. And in Python 3 you can write the whole content of this problem in a few lines (code author — Ivan Derzhanski):

The drawbacks of Soundex are plain to see. Sometimes this algorithm is unable to detect similarity between very close surnames: for example, Levinson gets the code L152, while Lewinson — gets the code L525. Furthermore, Soundex works poorly in situations where pronunciation diverges significantly from spelling, which happens quite often in English. For example, the Scottish surname Colquhoun, given in the problem statement, is pronounced roughly like Кэхун (Kehoon), and its Soundex code C425 reflects the unpronounced l (4) and q (2). Another variant of this surname — Colhoun (recall Captain Cassius Calhoun from Mayne Reid's «The Headless Horseman») — has a different code: it comes out as C450. However, in this spelling the л (l) is usually pronounced (Колхун, Kolhoon), so different codes in this case — are not really such a bad thing.

To solve the fuzzy search problem, more advanced algorithms are also often used. These can be either phonetic algorithms similar to Soundex (for example, Metaphone), or entirely different approaches — for example, ones related to edit distance, a problem which has already been published on our site.

The problem was used at the XIII International Linguistics Olympiad in 2015 in Blagoevgrad (Bulgaria).

The NYSIIS algorithm

Developed in 1970 as part of the «New York State Identification and Intelligence System», this algorithm gives somewhat better results relative to the original Soundex, using more complex rules for converting the source word into the resulting code. This algorithm is designed to work specifically with American surnames.

The algorithm for computing the NYSIIS code

1. Convert the beginning of the word according to the following rules:
   MAC → MCC
   KN → N
   K → C
   PH, PF → FF
   SCH → SSS
2. Convert the end of the word according to the following rules:
   EE → Y
   IE → Y
   DT, RT, RD, NT, ND → D
3. Then all letters, except the first, are converted according to the following rules:
   EV → AF
   A, E, I, O, U → A
   Q → G
   Z → S
   M → N
   KN → N
   K → C
   SCH → SSS
   PH → FF
   After vowels: remove H, convert W → A
4. Remove S at the end
5. Convert AY at the end → Y
6. Remove A at the end
7. Truncate to 6 characters (optional step).

Examples

CASPARAVAS → Каспаравичус, Касперович, Каспирович (Kasparavichus, Kasperovich, Kaspirovich).
CATNACAV → Катников, Цитников, Цотников (Katnikov, Tsitnikov, Tsotnikov).
LANSANC → Ленченко, Леонченко, Линченко, Лунченко, Лямзенко (Lenchenko, Leonchenko, Linchenko, Lunchenko, Lyamzenko).
PRADSC → Приходский, Проходский, Прудский, Прудских, Прудской (Prikhodsky, Prokhodsky, Prudsky, Prudskikh, Prudskoy).
STADNACAV → Стадников (Stadnikov).

NYSIIS converts a little over two surnames on average to the same code.

The Daitch-Mokotoff Soundex algorithm

This algorithm was developed in 1985 by two genealogists — Gary Mokotoff and Randy Daitch, striving to achieve better results than the original Soundex when working with Eastern European (including Russian) surnames.
This algorithm has little in common with the original Soundex, except that the result still remains a sequence of digits; however, now the first letter is also encoded.

It has significantly more complex conversion rules — now not only single characters but also sequences of several characters take part in forming the resulting code. In addition, a result of the form 023689 provides about 600 thousand different code variations, which, combined with the more complex rules, reduces the number of «extra», i.e. «false positive», words in the resulting set.

The conversions are carried out according to the following table (the order of conversions corresponds to the order of the letter combinations in the table):

«Alternative» variants of letter combinations (used to generate several alternative codes from the source word):
CH → TCH
CK → TSK
C → TZ
J → DZH

The encoding principle is the same as in soundex, but with additions:

1. Words are encoded with 6 digits, where each digit represents one of the sounds from the left column of the table.
2. When there are few letters in the word, the code is padded with zeros up to 6 characters. If there are too many letters — it is truncated to 6 characters. In the word GOLDEN only four sounds are encoded [G-L-D-N] and the result is 583600.
3. The letters A, E, I, O, U, J, and Y are always replaced by a digit when they are first in the word, as, for example, in the name Alpert 087930. In other cases these letters are skipped and not replaced by anything, except when two such letters in a row form a pair and another vowel immediately follows the pair. For example, in the name Breuer 'eu' is encoded as 791900, but not in the name Freud.
4. The letter H is replaced by a digit if it is first, as in Haber 579000, or if it is immediately followed by a vowel, as in Manheim 665600; in other cases it is skipped.
5. When neighboring letters form a longer sequence represented in the table, the longest matching variant must be encoded. Mintz is encoded as MIN-TZ 664000, not as MIN-T-Z.
6. When neighboring letters form two identical codes in a row, they are recorded as one, for example, TOPF becomes TO-PF 370000, not TO-P-F 377000. An exception to this rule is the combinations MN and NM, which are always encoded separately and cannot be merged, as in Kleinman 586660, not 586600.
7. The sequences CH, CK, C, J, and RS can sound differently in some languages — for these, two variants are proposed (in the table the Russian variant is highlighted in red).

The table is designed for languages based on the Latin alphabet, so in order to encode Russian profanity, one needs to use the magic of transliteration.

Examples

f('Майкл Джордан') == f('Michael Jordan') == 658000 493600
f('Арнольд Шварцнеггер') == f('Arnold Schwarzenegger') == 096830 479465
f('Орнольд Шворцнегир') == f('Arnold Schwarzenegger') == 096830 479465

095747 → Архипцев, Архипцов, Архипычев, Арцыбасов, Арцыбашев, Арчибасов (Arkhiptsev, Arkhiptsov, Arkhipychev, Artsybasov, Artsybashev, Archibasov)
095757 → Архипков, Архипцев, Архипцов, Архипычев (Arkhipkov, Arkhiptsev, Arkhiptsov, Arkhipychev)
584360 → Галстян, Галустян, Гильштейн, Глистин, Глуздань, Голштейн, Гольдштеин, Гольдштейн, Калустьян, Хлистун, Хлыстун, Хлюстин (Galstyan, Galustyan, Gilshtein, Glistin, Gluzdan, Golshtein, Goldshtein, Goldshtein, Kalustyan, Khlistun, Khlystun, Khlyustin).

On average this algorithm converts 5 surnames to the same code.

Later Alexander Beider and Stephen Morse developed the Beider-Morse Name Matching Algorithm, aimed at reducing the number of «false positive» values relative to Daitch-Mokotoff Soundex when working with Jewish (Ashkenazi) surnames.

The Metaphone algorithm

Somewhat better characteristics are shown by the Metaphone algorithm (1990), which differs from the earlier algorithms in its approach to the encoding process: it converts the source word taking into account the rules of the English language, using noticeably more complex rules, and in doing so much less information is lost, since letters are not split into groups. The resulting code is a set of characters from the set 0BFHJKLMNPRSTWXY; at the beginning of a word there may also be vowels from the set AEIOU.

Algorithm for computing the Metaphone code

1. Remove all repeated adjacent letters, except for the letter C.
2. Convert the beginning of the word according to the following rules:
   KN → N
   GN → N
   PN → N
   AE → E
   WR → R
3. Remove the letter B at the end if it follows M.
4. Replace C according to the following rules
   To X: CIA → XIA, SCH → SKH, CH → XH
   To S: CI → SI, CE → SE, CY → SY
   To K: C → K
5. Replace D according to the following rules
   To J: DGE → JGE, DGY → JGY, DGI → JGY
   To T: D → T
6. Replace GH → H, if this letter combination is not at the end and not before a vowel.
7. Replace GN → N and GNED → NED, if these letter combinations are at the end.
8. Replace G according to the following rules
   To J: GI → JI, GE → JE, GY → JY
   to K: G → K
9. Remove all H that follow vowels but are not before vowels.
10. Perform the following conversions according to the rules:
    CK → K
    PH → F
    Q → K
    V → F
    Z → S
11. Replace S with X:
    SH → XH
    SIO → XIO
    SIA → XIA
12. Replace T according to the following rules
    To X: TIA → XIA, TIO → XIO
    To 0: TH → 0
    Remove: TCH → CH
13. At the beginning of a word convert WH → W. If there is no vowel after W, remove W.
14. If X is at the beginning of a word, convert X → S, otherwise X → KS
15. Remove all Y that are not before vowels.
16. Remove all vowels except the initial one.

Examples

AKXN → Агашин, Акаченок, Акишин, Аксионенко, Аксионов, Акчунаев, Акшанов, Акшенцев, Акшинский, Акшинцев, Акшонов.
FSLX → Василишин, Васильчак, Васильченко, Васильчик, Васильчиков, Васильченко, Васильчук, Василющенко.
SRFM → Серафимов, Серафимский, Серафимчук, Церейфман.

The same Metaphone code value on average corresponds to 6 surnames.

The Double Metaphone Algorithm

Double Metaphone (2000) differs somewhat from the other phonetic algorithms, generating from the source word not one but two codes (both up to 4 characters long) — one reflects the primary pronunciation variant of the word, the other an alternative version. It has a large number of different rules that take into account, among other things, the different origins of words, paying attention to Eastern European, Italian, Chinese words and so on. The transformation rules are quite numerous; I will not publish them, but those interested can read about them in an article in Dr Dobbs magazine.

Examples

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

Double Metaphone maps, on average, 8-9 surnames to the same code.

Russian Metaphone

In 2002, in issue 8 of the magazine «Programmist» («Programmer»), an article by Pyotr Kankovski was published, describing his adaptation of the English version of the Metaphone algorithm to the harsh Siberian frosts, bears, and balalaikas. This algorithm converts source words in accordance with the rules and norms of the Russian language, taking into account the phonetic sound of unstressed vowels and possible «mergers» of consonants in pronunciation. It shows very good results in practice, despite being based on fairly simple rules. All letters are split into groups by sound — vowels and consonants (vowels and consonants respectively in English terminology), voiceless and voiced. Voiced consonants are converted into their corresponding voiceless pairs, sequences of letters that «merge» in pronunciation are combined, and some other manipulations are performed. Below I give a slightly refined version which, unlike Pyotr Kankovski's original, introduces rules related to the phonetic equivalence of Ц and ТС or ДС, and does not compress endings — saving bytes is not our task.

Algorithm for computing the Russian Metaphone code

1. For all vowel letters, perform the following operations.
   ЙО, ИО, ЙЕ, ИЕ → И
   О, Ы, Я → А
   Е, Ё, Э → И
   Ю → У
2. For all consonant letters followed by any consonant other than Л, М, Н or Р, or for consonants at the end of a word, perform devoicing:
   Б → П
   З → С
   Д → Т
   В → Ф
   Г → К
3. Merge ТС and ДС into Ц:
   ТС → Ц

As a result, the algorithm copes very well with its task — the resulting set indeed contains phonetically similar words. At the same time, there remain quite few extraneous words, largely because vowels are not ignored but converted and used in the resulting code. However, there are some words which, despite their phonetic similarity, do not fall into the resulting set because of the algorithm's overly «strict» rules.

In the case of Адольф Швардсенеггер, the result of running the Russian Metaphone algorithm will be:



Thus, in this case the algorithm reflects the real phonetic similarity of these two surnames.

Examples

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

This algorithm maps, on average, 1-2 surnames to the same code.

Metaphone 3

In October 2009, a professional version was released, developed by the same author, Lawrence Philips. It is a commercial product sold as source code. Metaphone 3 further improves the phonetic encoding of English-language words, non-English words familiar to Americans, as well as names and surnames commonly found in the United States. This, in particular, significantly improves the encoding of proper names. The author claims that overall it improves the accuracy of all words from about 89% in Double Metaphone to 98%. Developers can now also set switches in the code to make the algorithm encode Metaphone keys 1) taking into account non-initial vowels as well, and 2) encode voiced and voiceless consonants differently. This allows the result set to be focused more precisely if the developer finds that the search results include too many words that are not sufficiently similar to the search query. Metaphone 3 is sold as source code in C++, Java, C#, PHP, Perl and PL/SQL, with Ruby and Python wrappers that call the Java jar, as well as Metaphone 3 for Spanish and German pronunciation, available as Java and C# source code. The latest version of the Metaphone 3 algorithm is v2.5.4, released in March 2015. The Java source code of Metaphone3 for the earlier version 2.1.3, which lacked a large number of encoding fixes made in the current version 2.5.4, was included as part of the OpenRefine project and is available for public viewing.

Common misconceptions

There are some misconceptions about the Metaphone algorithms that should be cleared up. The following statements are true:

1. All of them are designed to handle ordinary «dictionary» words, not just names, and
2. Metaphone algorithms do not create phonetic representations of input words and names; rather, the result is an intentionally approximate phonetic representation according to this standard:

• words beginning with a vowel sound will have the letter «A», representing any vowel, as the first character of the encoding (in Double Metaphone and Metaphone 3 — the original Metaphone simply keeps the actual vowel),
• vowels after the initial vowel sound will not be taken into account or encoded, and
• pairs of voiced/unvoiced consonants will be mapped to the same encoding. (Examples of voiced/voiceless consonant pairs are D/T, B/P, Z/S, G/K, etc.).

This approximate encoding is needed to account for how native English speakers alter their pronunciation, and for spelling mistakes or other ways in which they change the words and names they are trying to write. Vowels, as is well known, are highly variable. The British often complain that Americans pronounce «T» the same way as «D». Also consider that all native English speakers often pronounce 'Z' where 'S' is written, almost always when a noun ending in a voiced consonant or liquid is pluralized, for example «seasons», «rays», «examples», etc. Not encoding vowels after the initial vowel sound helps group together words in which the vowel and consonant may be transposed due to misspelling or an alternative pronunciation

The Caverphone Algorithm

The Caverphone algorithm was developed in 2002 as part of a New Zealand project for matching data in old and new electoral rolls, which is why it is most oriented toward local pronunciation, although for Russian surnames too it gives quite acceptable results.

Algorithm for computing the Caverphone code

1. Convert the given name or surname to lowercase (the algorithm is case-sensitive).
2. Remove the letter e at the end.
3. Convert the beginning of the word according to the following table (relevant for local New Zealand given names and surnames). Here, the digit 2 denotes a temporary marker for a consonant letter that will be removed later.

   cough	rough	tough	enough	gn	mb
   cou2f	rou2f	tou2f	enou2f	2n	m2

4. Perform character substitutions according to the following table:

   cq

   ci

   ce

   cy

   tch

   c

   q

   x

   v

   dg

   tio

   tia

   d

   ph

   b

   sh

   z

   2q

   si

   se

   sy

   2ch

   k

   k

   k

   f

   2g

   sio

   sia

   t

   fh

   p

   s2

   s

5. Replace all vowels at the beginning of a word with A, and in all other cases — with 3. Thus, the digit 3 serves as a temporary marker for a vowel letter that will be used in subsequent conversions and later removed. After that, substitutions must be performed according to the following tables (notation: s+ — several identical characters in a row, ^h — character at the beginning of the line, w$ — character at the end of the line):

   j

   ^y3

   ^y

   y

   3gh3

   gh

   g

   s+

   t+

   p+

   k+

   f+

   m+

   y

   Y3

   A

   3

   3kh3

   22

   k

   S

   T

   P

   K

   F

   M

   n+

   w3

   wh3

   w$

   w

   ^h

   h

   r3

   r$

   r

   l3

   l$

   l

   N

   W3

   Wh3

   3

   2

   A

   2

   R3

   3

   2

   L3

   3

   2

6. Remove all digit 2's. If a digit 3 remains at the end of the word, replace it with A. Then remove all digit 3's.
7. Truncate the word to 10 characters, or pad it with ones up to 10 characters.

Examples

KPRLN11111 → Габрелян, Габриэлян, Габриэльян, Капарулин, Капралин, Капрелян.
MSRFK11111 → Мейзерович, Мисарович, Мисюревич.
PLLF111111 → Балалаев, Балалиев, Балалуев, Билалиев, Билалов, Билялов, Болелов, Палилов, Полилов, Полуляхов.

Caverphone maps around 4-5 surnames to the same code.

Conclusions

Most of these algorithms have been implemented in a variety of languages, including C, C++, Java, C# and PHP. Some of them, for example Soundex and Metaphone, are integrated or implemented as plugins for many popular DBMSs, and are also used as part of full-fledged search engines, such as Apache Lucene. Their scope of application is fairly specific, since a significant improvement in usability for users can be achieved only in surname search, but nevertheless their competent use is a plus for search systems.

References:

1. Yu. D. Apresyan. Selected Works. Vol. I. // Lexical Semantics. Moscow: Languages of Russian Culture, 1995.
2. Donald Knuth. The art of computer programming. Vol. 3: Sorting and searching // Reading (Mass.), 1973.
3. Donald Knuth. The art of computer programming. Vol. 3: Sorting and searching. 2 nd ed. // Reading (Mass.), 1998.
4. Bertrand Lisbach & Victoria Meyer. Linguistic identity matching // Wiesbaden: Springer, 2013.

5. Donald Knuth «The Art Of Computer Programming, vol. 3: Sorting And Searching», Addison-Wesley (1973), pp. 391-392.

See also

• levenshtein — Calculates the Levenshtein distance between two strings

• metaphone — Returns the metaphone key for a string

• similar_text — Calculates the degree of similarity between two strings

• soundex

• metaphone

• search engine

• ranking

• Caverphone

• Search index

• Vertical search

• Information retrieval

• Index ( database )

• Semantic web

• Site search

• Data analysis

• Data indexing and query processing
• [[b8939]]
• [[b6236]]

See also

• Typo Correction Algorithms With and Without Context
• Data analysis Data indexing and query processing.