soundEx algorithm

Немного о фонетических алгоритмах

Фонетические алгоритмы — алгоритмы, которые сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства. Существует достаточно много фонетических алгоритмов, например: NYSIIS, Metaphone, Double Metaphone, Caverphone и т.д. В данном отчёте я напишу об одном из фонетических алгоритмов, который называется soundEx.
soundEx — алгоритм, который был разработан Робертом Расселом и Маргарет Кинг Оделл в 10-х годах прошлого века. В основном, этот алгоритм стал известен после того, как был опубликован в книге Дональда Кнута «Искусство программирования».

soundEx

Пример:

Код Слово
a500 ammonium
i514 implementation

Данным алгоритмом предусмотрено сопоставление индекса вида LNNN(Q123) слову. Этот код получают следуя следующему алгоритму:

  • Первая буква сохраняется
  • Все гласные звуки + буквы h, w отбрасываются
  • Оставшиеся буквы заменяются цифрами в диапазоне от 1 до 6 по следующим правилам:
    B, P, F, V 1
    C, S, K, G, J, Q, X, Z 2
    D, T 3
    L 4
    M, N 5
    R 6
  • Последовательность из одинаковых цифр заменяется одной такой цифрой
  • Полученная строка обрезается до первых 4-х символов. Если в строке меньше 4х, то в конец добавляются нули.

Пример:

javalanguage → jvlngg → j214522 → j21452 → j214

Реализация:

Реализация soundEx приводится по выше описанному алгоритму.
Для тестирования создадим HashMap, в котором по ключу-индексу soundEx будем создавать список слов, подходящих под этот ключ.

Ссылка на Ideone

Пример:

In: Dedlovskiy Dedlovskih Nasimov Nagimov Zazimov Azazimov Marchenko Merchenko Dedlovich Nagiev Houston Watson
Out:
N521: Nagiev
D341: Dedlovskiy Dedlovskih Dedlovich
A251: Azazimov
M562: Marchenko Merchenko
W325: Watson
Z251: Zazimov
H235: Houston
N525: Nasimov Nagimov