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» и «Journal of the Association for Computing Machinery» (CACM и JACM). Еще большую популярность этот алгоритм получил после того как был опубликован в книге Дональда Кнута. Искусство программирования, том 1. Основные алгоритмы.
Описание
- Первая буква сохраняется
- В остальной части слова:
- Гласные (aehiouwy) выбрасываем
- Каждую согласную заменяем на цифру от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры.
- b, f, p, v - на 1
- c, g, j, k, q, s, x, z - на 2
- d, t - на 3
- l - на 4
- m, n - на 5
- r - на 6
- Избавляемся от повторов: любая последовательность одинаковых цифр заменяется на одну такую цифру.
- Обрезаем до первых четырёх символов
Примеры:
- аmmonium -> ammnm -> a5555 -> a5
- implementation -> implmnttn -> i5455335 -> i54535 -> i545
Пример исполнения
Ниже приведен пример реализации алгоритма на языке программирования Perl.
sub soundex { # return soundex code
my($useword) = $_[0];
my($result) = "0000";
my($idx,$prev,$perhaps,$thechar);
$useword =~ tr/ //d; # rid spaces
$useword = lc($useword); # lower-case for consistency
if (length($useword) < 1) {
return($result);
}
$result = substr($useword,0,1); # first letter
$prev = "0";
$idx = 1;
while ($idx <= length($useword)) {
$perhaps = "0";
$thechar = substr($useword,$idx - 1,1);
if (index("bfpv", $thechar) >= 0) { $perhaps = "1"; }
if (index("cgjkqsxz",$thechar) >= 0) { $perhaps = "2"; }
if (index("dt", $thechar) >= 0) { $perhaps = "3"; }
if (index("l", $thechar) >= 0) { $perhaps = "4"; }
if (index("mn", $thechar) >= 0) { $perhaps = "5"; }
if (index("r", $thechar) >= 0) { $perhaps = "6"; }
if ($perhaps != $prev && $perhaps != "0"
&& $idx != 1) { # avoid dups and ignore first
$result .= $perhaps;
}
$prev = $perhaps;
$idx++;
} #endwhile
$result .= "0000"; # pad with zeros to ensure min length
$result = substr($result,0,4); # only return first four
return($result);
}