Soundex (Soundex)
Soundex — один из алгоритмов сравнения строк по их звучанию; устанавливает одинаковый индекс для строк, имеющих схожее звучание в английском языке.
Разработан Робертом Расселом (Robert C. Russel) и Маргарет Кинг Оделл (Margaret King Odell) и запатентован в 1918 и 1922 годах[1][2], является исторически первым фонетическим алгоритмом[англ.]. Стал популярным в 1960-х годах после того как ему были посвящены несколько статей в журналах «Communications of the ACM» и «Journal of the ACM»; ещё большую известность он обрёл после появления в «Искусстве программирования» Кнута[3]. С 1980-х годов используется как стандартная функция во многих СУБД.
Изначально ориентирован на фонетику американского варианта английского языка, посредством модификаций может быть применён и для других вариантов и языков, но в ряде случаев требуются существенные изменения (как, например, в алгоритме Дейча — Мокотоффа[англ.], поддерживающем имена собственные на идише и славянских языках). Впоследствии также появились альтернативы, ориентированные в большей степени на обычные слова английского языка, нежели на имена собственные (такие как Metaphone, Caverphone[англ.])
Шаги алгоритма
[править | править код]- Запоминается первая буква слова.
- Удаляются все вхождения 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 в словах дадут одну цифру 2, а не 22, так как разделены h).
- Tymczak → T522, а не T520 (буквы z и k заменяются на 22, так как разделены гласной).
Примечания
[править | править код]- ↑ U.S. Patent 1 261 167
- ↑ U.S. Patent 1 435 663
- ↑ Дональд Кнут. Часть 6. Поиск // Искусство программирования = The Art of Computer Programming. — 2012. — Т. 3. Сортировка и поиск. — С. 249.
 | В статье не хватает ссылок на источники (см. рекомендации по поиску). |