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[англ.])

Шаги алгоритма

[править | править код]
  1. Запоминается первая буква слова.
  2. Удаляются все вхождения h и w (за исключением первой буквы слова).
  3. Согласные заменяются на цифры от 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
  4. Любая последовательность одинаковых цифр сокращается до одной такой цифры.
  5. Удаляются все a, e, i, o, u, y (за исключением первой буквы слова).
  6. Заменяется первый символ буквой, запомненной на шаге 1, делая её заглавной.
  7. Итоговая строка обрезается до первых четырёх символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 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, так как разделены гласной).

Примечания

[править | править код]
  1. U.S. Patent 1 261 167
  2. U.S. Patent 1 435 663
  3. Дональд Кнут. Часть 6. Поиск // Искусство программирования = The Art of Computer Programming. — 2012. — Т. 3. Сортировка и поиск. — С. 249.