Алгоритм вычисления кода Caverphone

1. Преобразовать имя или фамилию в нижний регистр (алгоритм чувствителен к регистру).

2. Удалить буквы e на конце.

.   Преобразовать начало слова по следующей таблице (актуально для местных новозеландских имен и фамилий). При этом цифра 2 означает временную метку для согласной буквы, которая впоследствии будет удалена.

.   Провести замены символов по следующей таблице:

 

Таблица 2.2 - Замена символов в алгоритме Caverphone

cq

ci

ce

cy

tch

c

v

dg

tio

tia

d

ph

b

sh

2q

si

se

sy

2ch

k

f

2g

sio

sia

t

fh

p

s2

 

5. Заменить все гласные в начале слова на A, в остальных случаях на 3. Таким образом, цифра 3 служит временной меткой для гласной буквы, которая будет использоваться в последующих преобразованиях, а затем будет удалена. После, необходимо провести замены по следующим таблицам (условные обозначения: s+ - несколько идущих подряд символов, ^h - символ в начале строки, w$ - символ на конце строки):

. Удалить все цифры 2. Если на конце слова осталась цифра 3, то заменить её на A. Затем удалить все цифры 3.

. Обрезать слово до 10 символов, либо же дополнить до 10 символов единицами.

Пример работы данного алгоритма→ Габрелян, Габриэлян, Габриэльян, Капарулин, Капралин, Капрелян.→ Мейзерович, Мисарович, Мисюревич.→ Балалаев, Балалиев, Балалуев, Билалиев, Билалов, Билялов, Болелов, Палилов, Полилов, Полуляхов.сопоставляет одному и тому же коду около 4-5 фамилий.

Выводы

фонетический транскрипция алгоритм код

Большая часть этих алгоритмов реализована на множестве языков, в том числе на C, C++, Java, C# и PHP. Некоторые из них, например Soundex и Metaphone, интегрированы или реализованы в виде плагинов для многих популярных СУБД, а также используются в составе полноценных поисковых движков, например, Apache Lucene <http://lucene.apache.org/>. Область их применения довольно специфична, ведь значительного повышения удобства для пользователей можно добиться лишь при поиске фамилий, но тем не менее грамотное их использование - это плюс для поисковых систем.

Фонетические алгоритмы для русского языка

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

 

Фонетик получает на вход исходную строку и на основе правил, учитывающих произношение букв и слогов в русском языке, вырабатывает на выходе новую строку, называемую ключом для исходной строки. Ключ имеет переменную длину; из одной строки можно получить только один ключ.

Алгоритм включает следующие шаги.

. Преобразование строки в верхний регистр (это позволяет уменьшить алфавит в 2 раза и отсечь ошибки, связанные со случайными заглавными буквами в середине слова.)

. Удаление непроизносимых букв, а также знаков препинания.

. Замена сходных по начертанию латинских букв (A, B, C, E, H, O, P, T X, Y) на русские аналогичного начертания (А, В, С, Е, Н, О, Р, Т, Х, У).

. Выработка ключа с использованием имени и отчества либо только инициалов в зависимости от выбранной настройки и полноты исходных данных.

. Замена гласных букв на те, которые слышатся на их месте в безударном слоге. Буквы О, Ы, А, Я заменяются на А; Ю, У на У; Е, Е, Э, И на И. Несмотря на то, что в русском языке произношение буквы часто не соответствует написанию, сокращать слова до одних согласных нельзя, поскольку существует ряд парных глухих и звонких. С точки зрения грамматики русского языка такой подход не является абсолютно верным, но на практике показывает хорошие результаты.

. Оглушение согласных в соответствии с правилами русского языка. В слабой позиции по звонкости-глухости в области согласных происходит оглушение, при котором все звонкие согласные (кроме сонорных) на конце слова произносятся как парные им глухие, а также два конечных звонких переходят в соответствующие глухие. Алгоритм не оглушает согласные до сонорных звуков.

. Замена последовательностей букв, которые не встречаются в русском языке, на необходимые из словаря слогов.

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

. Замена типовых для русского языка окончаний фамилий на специальные символы. Эта команда сокращает время обработки и экономит место для хранения ключей. Данное преобразование имеет смысл только для фамилий.

Пункты 1, 2, 5, 6, 8, 9 с некоторыми изменениями заимствованы из реализации алгоритма MetaPhone [4]. Для повышения качества сравнения алгоритм дополнен следующими этапами.

. В большинстве случаев в информационной системе вместе с фамилией присутствуют имя и отчество, тогда имеет смысл привязать их к ключу. Имя и отчество обрабатываются отдельно от фамилии согласно пп. 1-6 алгоритма и дополняют ключ, полученный на основе фамилии. Если в одной системе в данных присутствуют лишь инициалы, то у обеих строк данные для обработки сокращаются до фамилии и первых букв имени и отчества, преобразованных к верхнему регистру.

. В связи с тем, что персональные данные нередко получают из источника данных невысокого качества, о чем свидетельствует наличие инициалов вместо полноценных имени и отчества, имеет смысл заменять в ключе символы инициалов на сходные по написанию. Если рассмотреть графическое начертание букв, то И имеет сходство с Н, следовательно, в инициалах они могут быть заменены друг на друга. Остальные буквы остаются без изменений.

. Итоговый ключ формируется конкатенацией ключа, полученного из фамилии, и результатов обработки имени и отчества или инициалов.

В таблице 3.1 приведен пример списка, подаваемого на вход алгоритма, и соответствующих выходных значений.

 

Таблица 3.1 - Работа алгоритма фонетик

Исходное слово	Ключ
Годеева А.В.	ГАД9АВ
Годиева И.А.	ГАД9ИА
Иванюков П.В.	ИВАНУК4ПВ
Иванников С.А.	ИВАНИК4СА
Ковалева С.А.	КАВАЛИВА СА
Ковалева О.А.	КАВАЛИВА ОА
Голушков О.В.	ГАЛУШК4ОВ
Колушков С.П.	КАЛУШК4СП
Куликов А.А.	КУЛИК4АА

 

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

Для проверки релевантности алгоритма Фонетик из автоматизированной банковской системы было выгружено 25907 записей о физических лицах. Этот массив данных был получен слиянием нескольких БД и содержал некоторое количество дублирующих записей о физических лицах, которые не были обнаружены средствами СУБД во время слияния. Весь массив данных обработан экспертами, которые выявили в нем 661 дублирующую запись.

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

В алгоритме, вычисляющем дистанцию Левенштейна, записи считались различными, если дистанция редактирования превышала единицу. Перед применением алгоритма Soundex, разработанного для английского языка, записи подвергались транслитерации.

В качестве нулевой гипотезы H0 полагалось, что сравниваемые записи соответствуют одному физическому лицу. Типы ошибок в работе алгоритмов определялись по таблице 3.2, в которой символом H1 обозначена гипотеза, противоположная H0.

 

Таблица 3.2 - Типы ошибок

Результат работы алгоритма	Верная гипотеза для входных данных
	H0	H1
H0	H0 верно принята	H0 неверно принята (ошибка второго рода)
H1	H0 неверно отвергнута (ошибка первого рода)	H0 верно отвергнута

 

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

По общему количеству ошибок сравнения наихудшие результаты показал алгоритм, вычисляющий дистанцию Левенштейна. Второе место по общему количеству ошибок после алгоритма Фонетик занимает алгоритм прямого сравнения. Однако в данном случае значимость ошибок первого и второго рода различна. Наиболее критичными являются ошибки первого рода, поскольку сходные объекты, классифицированные как различные, не попадут в итоговую выборку, то есть будут потеряны. Наличие ошибки второго рода не столь критично, так как на практике все объекты, классифицированные как сходные, будут представлены для последующей обработки в ручном режиме, а значит, будут проконтролированы.

По количеству ошибок первого рода алгоритм Фонетик на порядок эффективнее алгоритмов, вычисляющих дистанцию Левенштейна, и алгоритма Soundex. Алгоритм прямого сравнения оказался наименее эффективным по количеству ошибок 1-го рода.

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