Soundex

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Soundex — один из алгоритмов сравнения двух строк по их звучанию. Он устанавливает одинаковый индекс для строк, имеющих схожее звучание в английском языке.

Soundex был разработан Робертом Расселом (Robert C. Russel) и Маргарет Кинг Оделл (Margaret King Odell) и запатентован в 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));
}

См. также[править | править вики-текст]

Ссылки на попытки создания soundex для русского языка[править | править вики-текст]