Soundex
Soundex — один из алгоритмов сравнения двух строк по их звучанию. Он устанавливает одинаковый индекс для строк, имеющих схожее звучание в английском языке.
Soundex был разработан Робертом Расселлом (Robert Russel) и Маргарет Обелл (Margaret Obell) и запатентован в 1918 и 1922 годах (U.S. Patent 1,261,167 и U.S. Patent 1,435,663). Этот алгоритм стал популярным в 1960-х годах, после того как стал темой нескольких статей в журналах «Communications of the Association for Computing Machinery» и «Journal of the Association for Computing Machinery» (CACM и JACM). Еще большую популярность этот алгоритм получил после того, как был опубликован в книге Дональда Кнута. Искусство программирования, том 1. Основные алгоритмы.
Описание алгоритма
- Первая буква сохраняется
- В остальной части слова:
- Буквы, обозначающие, как правило, гласные звуки: a, e, h, i, o, u, w и y — отбрасываются
- Оставшиеся буквы (согласные) заменяются на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:
- 1: b, f, p, v
- 2: c, g, j, k, q, s, x, z
- 3: d, t
- 4: l
- 5: m, n
- 6: r
- Любая последовательность одинаковых цифр сокращается до одной такой цифры.
- Итоговая строка обрезается до первых четырёх символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.
Примеры:
- аmmonium → ammnm → a5555 → a5 → a500
- implementation → implmnttn → i51455335 → i514535 → i514
Пример исполнения
Ниже приведен пример реализации алгоритма на языке программирования Perl.
sub soundex
{
my $word = lc (shift // $_);
$word =~ tr/\t //d;
my $fl = substr $word, 0, 1;
$word = substr $word, 1;
$word =~ tr/bfpvcgjkqsxzdtlmnraehiouwy/111122222222334556/ds;
$word = "$fl$word";
return substr($word, 0, 4)."0" x (4 - length($word));
}