Фонетические алгоритмы: Soundex

При использовании алгоритмов текстового майнинга достаточно часто на практике возникают опечатки, один из способов борьбы с ними это использование триграмм. Недостаток этого подхода в том, что он плохо работает со словами короче 5-7 символов. Альтернативный способ - это применение фонетических алгоритмов, которые сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства.  

Одним из таких алгоритмов является Soundex, который устанавливает одинаковый код вида D321 для слов, имеющих схожее звучание в английском языке.  Soundex был разработан Робертом Расселом и Маргарет Кинг Оделл и запатентован в 1918 и 1922 годах. Этот алгоритм стал популярным в 1960-х годах, после того как стал темой нескольких статей в журналах «Communications of the Association for Computing Machinery» и «Journal of the Association for Computing Machinery» и был опубликован в книге Дональда Кнута. 

Давайте разберемся как работает оригинальная версия алгоритма: 

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. 

Таким образом для слова Morphs алгоритм сгенерирует код M612. Несложно заметить, что после всех этих процедур остается меньше 10 тысяч различных вариаций такого кода, что влечет за собой множество совершенно ничем не похожих друг на друга слов, имеющих одинаковый Soundex-код. Таким образом, результат в большинстве случаев включает в себя большое количество ложных срабатываний.  

Для уменьшения ложных срабатываний был создан улучшенный алгоритм Soundex, который в отличие от оригинального использует следующую таблицу кодирования символов: 

  • b, p -> 1 
  • f, v -> 2 
  • c, k, s -> 3 
  • g, j->4 
  • q, x, z -> 5 
  • d, t -> 6 
  • l -> 7, 
  • m, n -> 8 
  • r-> 9 

Таким образом число кодов увеличивается почти до 19 тысяч. Более того снимается ограничение на длину кода (код не дополняется символами 0 и не удаляются все символы после 4-ого). 

С применение улучшенного алгоритма Soundex слово Morphs будет закодировано в M913. 

Soundex хорошо работает с английским языком, остается вопрос можно ли его использовать для русского языка. Оказывается можно. Для этого перед вычислением кода оригинальным или улучшенным алгоритмом нужно выполнить транслитерацию исходного слова на русском языке.

Пример реализации оригинального алгоритма на perl-e:

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 text mining алгоритмы анализ текстов фонетика


 


 
архив

подписка