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 Machinery» и «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 -> 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;
  return substr "$fl$word", 0, 4; 
}

См. также

• Metaphone

Ссылки на попытки создания soundex для русского языка

• http://community.livejournal.com/ru_php/1062493.html

* http://kankowski.narod.ru/dev/metaphoneru.htm HTTP 404 (Дата обращения: 29 мая 2010) (архивная версия)