Soundex
Soundex — один из алгоритмов сравнения двух строк по их звучанию. Он устанавливает одинаковый индекс для строк, имеющих схожее звучание в английском языке.
Soundex был разработан Робертом Расселом (Robert C. Russel) и Маргарет Кинг Оделл (Margaret King Odell) и запатентован в 1918 и 1922 годах[1][2]. Этот алгоритм стал популярным в 1960-х годах, после того как стал темой нескольких статей в журналах «Communications of the Association for Computing Machinery» и «Journal of the Association for Computing Machinery» (CACM и JACM). Еще большую популярность этот алгоритм получил после того, как был опубликован в книге Дональда Кнута. Часть 6. Поиск // Искусство программирования = The Art of Computer Programming. — 2012. — Т. 3. Сортировка и поиск. — С. 249.
Описание алгоритма
- Запоминаем первую букву. Удаляем все 'h' и 'w', за исключением первой буквы слова.
- Согласные заменяем на цифры от 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
- Любая последовательность одинаковых цифр сокращается до одной такой цифры.
- Удаляем все a, e, i, o, u, y, за исключением первой буквы слова.
- Заменяем первый символ буквой, запомненной на шаге 1, делая её заглавной.
- Итоговая строка обрезается до первых четырех символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.
Примеры:
- аmmonium → а55o5iu5 → а5o5iu5 → a555 → A555
- implementation → i514e5e53a3io5 → i51455335 → i514 → I514
- "Robert" и "Rupert" → "R163", "Rubin" → "R150"
- "Ashcraft" и "Ashcroft" → "A261", а не "A226" (буквы 's' и 'c' в словах дадут 1 цифру '2', а не 22, т.к. разделены 'h').
- "Tymczak" → "T522", а не "T520" (буквы 'z' и 'k' заменяются на 22, т.к. разделены гласной).
- "Pfister" → "P236", а не "P123" (Pfister → 11i23e6 → 1i23e6 → 1236 → P236).
Пример исполнения
Ниже приведен пример реализации алгоритма на языке программирования Perl.
sub soundex {
my $word = uc shift;
$word =~ tr/\t //d;
my $fl = substr $word, 0, 1;
$word = substr $word, 1;
$word =~ tr/HW//d;
$word = $fl . $word;
$word =~ tr/BFPVCGJKQSXZDTLMNR/111122222222334556/s;
$word = substr $word, 1;
$word =~ tr/AEIOUY//d;
$word = $fl . $word;
return substr $word . "000", 0, 4;
}
Примеры использования:
soundex('ammonium');
soundex('implementation');
soundex("Robert");
soundex("Rupert");
soundex("Rubin");
soundex("Ashcraft");
soundex("Ashcroft");
soundex("Tymczak");
soundex("Pfister");
См. также
Примечания
В статье не хватает ссылок на источники (см. рекомендации по поиску). |