WikiSort.ru - Театры

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.

Описание алгоритма

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

Пример исполнения

Ниже приведен пример реализации алгоритма на языке программирования 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");

См. также

• Metaphone

Примечания

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 11 января 2015 года.