В статье описан пример собственной реализации алгоритма формирования ключа MetaPhone для кириллических фамилий средствами языка PL/SQL.
Ключевые слова база данных; фонетический алгоритм; Metaphone; Soundex; генерация ключа; ключ Metaphone; сравнение строк; поиск данных; индексирование слов; фонетическая классификация звуков.
Author described own Metaphone algorithm realization for Cyrillic families by PL/SQL tools.
Keyword database, Metaphone, Soundex, key generation, Metaphone key, string matching, phonetic algorithm, data search, word index; phonetic classification.
Ввод и обработка имен и фамилий представляют проблему для разработчиков баз данных. Длины фамилий (имен) могут быть различны, они не уникальны, их написание может быть необычным. Например, английские имена имеют множество этнических корней, поэтому некоторые из них произносятся одинаково, но пишутся по-разному, и наоборот.
Данная ситуация знакома всем, кто получает большое количество писем по электронной почте. Помимо фонетических ошибок, часто встречаются и ошибки в написании. В результате по одному адресу отправляется несколько копий документа.
Для решения указанных проблем были разработаны фонетические алгоритмы, определявшие схожие фамилии и имена.
В настоящее время получили широкое распространение фонетические алгоритмы Soundex и Metaphone, предназначенные для индексирования слов по их звучанию с учётом основных правил произношения, принятых в английском языке. При наличии функции преобразования, генерирующей общий хэш для похожих строк (ключ), процесс сравнения сводится к хэш-преобразованию эталонов и рабочих строк и их последующего строгого сравнения. Строки, которые имеют одинаковый хэш, считаются похожими. Алгоритмы достаточно просты в реализации, если не учитывать затраты на подбор подходящей функции преобразования.
Оригинальный алгоритм Soundex
Первый алгоритм Soundex был запатентован М. О'Делл и Р. С. Расселом в 1918 г. Он основан на фонетической классификации звуков по способу их произнесения.
Алгоритм очень прост и не требует ни возвратов, ни нескольких прохождений одного слова.
Сам алгоритм описан ниже.
1. Все буквы в слове сделать заглавными. На каждом этапе при необходимости дополняйте слово справа пробелами.
2. Запомнить первую букву слова.
3. Удалить все вхождения после первой позиции букв: А, Е, Н, I, О, U, W, Y.
4. Выполнить преобразование букв в цифры следующим способом:
1 = B, F, P, V
2 = C, G, J, K, Q, S, X, Z
3 = D, T
4 = L
5 = M, N
6 = R
5. Удалить все последовательные пары двойных цифр из строки, полученной на четвертом этапе.
6. Дополнить полученную на пятом этапе строку нулями справа и верните первые четыре символа.
В соответствии с альтернативной версией алгоритма, буквы на третьем этапе превращаются в девятки и сохраняются. Этап 5 может быть разделен на два подэтапа: 5.1 удаляет дубликаты, а 5.2 удаляет все девятки и закрывает пробелы. В результате в строке результата могут появиться пары повторяющихся цифр. Данная версия более детализирована и лучше обрабатывает большие выборки фамилий.
Усовершенствованный алгоритм Soundex
Усовершенствованный алгоритм Soundex также обрабатывает исходную фамилию и возвращает код из четырех символов. Если оригинальный алгоритм включал только 26000 (26 * 10* 10* 10) групп кода, то модернизированный алгоритм содержит 456976 (26 * 26 * 26 * 26) данных групп. Большая степень детализации кода позволяет разделять фонетически близкие имена на меньшие группы, чем оригинальный алгоритм.
Алгоритм Metaphone
Данный алгоритм был разработан Лоренсом Филипсом в 1990 году в качестве альтернативы алгоритму Soundex, обладающему рядом недостатков. Алгоритм Metaphone более точен, чем Soundex, потому что использует больший набор правил английского произношения. В отличие от алгоритма Soundex, который генерирует ключи с фиксированной длиной, алгоритм Metaphone после преобразования формирует ключи переменной длины. Из схожих по звучанию слов получаются одинаковые ключи.
Алгоритм Метафон (Metaphone) фонетически кодирует слова путем уменьшения их до 16 согласных звуков: B, X, S, K, J, T, F, H, L, M, N, P, R, 0, W, Y. Ноль представляет звук "th"; X представляет "sh".
Процедура:
1. Удалить вторую из двойных букв, за исключением C.
- Если слово начинается с KN, GN, PN, AE, WR, удалить первую букву.
- Удалить B в конце слова после M.
- C → X в CIA или CH; C → S в CI, CE или CY; C → K в противном случае.
- D → J в DGE, DGY или DGI; D → T в противном случае.
- Удалить G в GH и если не в конце или перед гласным в GN или GNED; G → J перед I или E или Y если не двойная GG; G → K в противном случае.
- Удалить H после гласной и если следующая буква не гласная.
- Удалить K после C.
- P → F в PH.
- Q → K.
- S → X в SH или SIO или SIA.
- T → X в TIA или TIO; T → 0 в TH; T удаляется в TCH.
- V → F.
- Если слово начинается с WH, удалить H; удалить W если следующая буква не гласная.
- Если слово начинается с X, тогда X → S; X → KS в противном случае.
- Удалить Y если следующая буква не гласная.
- Z → S.
- Если гласные находятся в начале слова, они не удаляются.
19. Во всех остальных случаях буквы не меняются.
Примеры
1. ALEXANDRE → ALEKSANTRE → ALKSNTR
2. ALEKSANDER → ALEKSANTER → ALKSNTR
Алгоритм фонетической похожести (Metaphone).
Задавшись целью разработать подобный алгоритм для русского языка, для начала рассмотрим тестовую базу данных, сформированную, например, на основе клиентской базы крупной кредитной организации выпишем из нее «сомнительные» фамилии.
На первых же записях были обнаружены фамилии: Ааб, Абаза, Абоймова, Ахмадова и Африкантов, которые на слух вряд ли можно сразу напечатать верно. Дальше следуют не менее интересные фамилии – после Вегнера, Вагнера, Вайгеля, Вайгульта, Вайлера, Вайлерта, Ваймана, Вайнера, Вайсборда и Вайшутеца встретились:Седъюров, Кинъябулатова, Объедугин, Подъем, Подъема, Подъемов, Явъяковская, Гъртанова, Покинь-Череда и Матьешайтис. Среди не слишком благозвучных фамилий Аръяхова, Пукась, Дрынь, Дубс, Нищий, Нахрынова и Нафикова попался великолепный, на взгляд автора, Объедько. Собственно фамилия Карахтанов коверкалась сотней разных способов при заполнении анкет, медицинских карт, пропусков и прочих документов и может пополнить этот список. Так же можно выделить группу условно-ошибочных: Неъмонов, Маъбудов, Маъдиев, Маъруфов, Маъсумшоев, то есть те фамилии, о которых без дополнительной проверки не представляется возможным сказать, существуют они или это опечатка.
Итак, вначале мы теоретически рассмотрим разные преобразования букв фамилий. С помощью программы перевести фамилии в традиционную фонетическую запись весьма сложно, так как ударение в тексте не обозначается, и некоторые буквосочетания произносятся по-разному в разных диалектах и людьми разных поколений. Но и не в этом наша задача, а в том, чтобы на практике находить один ключ для похожих фамилий. Поэтому ключ RuMetaPhone отличается от фонетической записи (Майя Серебрянникова: и МАЙАСИРИБРАНИК9), но в целом преобразования соответствуют русской фонетике и графике:
1. Гласные. Разница между Вагнером и Вегнером явно не меньше, чем между Вайгелем и Вайгультом, а англоязычные алгоритмы её не учитывают. Лучше не убирать гласные, а превращать их в те, что слышатся на их месте в безударном слоге: О в А, Е в И и т.п. Так и делает RuMetaPhone, преобразуя Зицер и Зицир в Зицир (здесь и далее верны первые написания фамилий). Сложность здесь в том, что в многосложном слове невозможно без словаря определить ударение, и ударные гласные тоже будут преобразованы: Козлов в Казлав. Но разные распространенные фамилии не будут преобразованы в одну, и этот недостаток можно проигнорировать. Вот ряд, согласно которому RuMetaPhone объединяет похожие гласные:
Таблица 1 Сопоставление гласных.
|
Исходные символы |
Конечный символ |
|
О, Ы, А, Я |
А |
|
Ю, У |
У |
|
Е, Ё, Э, И |
И |
Казалось бы, примитивная схема, но она верно распознаёт довольно сложные похожие фамилии Бауэр и Бауер (оба написания верные), создавая для них ключ Бауир.
2. Оглушение согласных в слабой позиции («сомнительный» согласный). Например, лаг и лак звучат одинаково и имеют один ключ ЛАК. Звонкие согласные превращаются в глухие перед другими согласными и в конце слова.
Алгоритм: в первую позицию строки записывается пробел, и далее строка, начиная со второго символа, сканируется на наличие согласной в текущем и предыдущем символе. Найденный звонкий согласный заменяется соответствующим глухим. До основного цикла мы проверяем последний символ строки и также оглушаем его при необходимости. Пример: Гудз и Гутс переходят в Гутс, Гефт и Гевт — в Гефт, Бовт и Бофт — в Бофт.
Особенность: алгоритм не оглушает согласные до сонорных звуков (м, н, л): ключи для фамилий Готлиб и Годлиб будут отличаться. Обычно согласные до сонорных слышны чётко: зло, блага, обнимать (для сравнения здесь, обточить). Если это нужно, вы можете исправить строку поиска cns3$, заставив функцию производить и это преобразование.
3. Исключение повторяющихся символов. Здесь всё просто — Бопп может по ошибке быть написан с одной П, а Метревели многие напишут как Метревелли (по аналогии с Растрелли). Для этих фамилий будут созданы одинаковые ключи с одной повторяющейся буквой, и они будут найдены вне зависимости от написания.
Заметим, что, выполняя оглушение до исключения повторов, можно без лишних усилий генерировать тот же ключ для Шмидт и Шмит и подобных фамилий, так как Шмидт будет сначала преобразована в Шмитт, затем будет удалён повторяющийся Т, и получится Шмит.
4. Сжатие окончаний. Типичные концовки фамилий заменяются спецсимволами и цифрами, например, Раневская превратится в РАН%. Это экономит место на хранение, ликвидирует ненужные преобразования окончаний, сокращая время работы алгоритма. Пример: вместо того, чтобы менять окончание –ова на –ава в фамилиях Огольцова и Агальцова (здесь верны оба написания), RuMetaPhone преобразует только основу и создаёт для обеих фамилий ключ АГАЛЦ9.
Схожие окончания преобразуются в один спецсимвол, например, Грицюк и Грицук, как и Грецук, дадут ГРИЦ0.
5. Исключение Ъ, Ь и дефиса между частями двойной фамилии. Твёрдый знак редко встречается в фамилиях, а мягкий ставят по ошибке на конце фамилии вроде Гусарьф или не ставят в Оганьян. Дефис иногда также может быть поставлен неверно. Проще всего убрать эти знаки вообще, и они будут игнорироваться при сравнении ключей.
А вот и пример работы с этой функцией:
|
Результат:
|
Функция MetaPhone
IF exists (SELECT * from dbo.sysobjects where id = object_id(N'[dbo].[MetaPhoneRu]') and xtype in (N'FN', N'IF', N'TF'))
drop function [dbo].[MetaPhoneRu]
GO
CREATE FUNCTION dbo.MetaPhoneRu (@W varchar(4000))
RETURNS varchar(4000)
AS
BEGIN
DECLARE @alf varchar(4000), @cns1 varchar(4000), @cns2 varchar(4000), @cns3 varchar(4000), @ch varchar(4000), @ct varchar(4000)
SET @cns1 = 'БЗДВГ'
SET @cns2 = 'ПСТФК'
SET @cns3 = 'ПСТКБВГДЖЗФХЦЧШЩ'
SET @ch = 'ОЮЕЭЯЁЫ'
SET @ct = 'АУИИАИА'
-- @alf - алфавит кроме исключаемых букв,
-- @cns1 и @cns2 - звонкие и глухие согласные,
-- @cns3 - согласные, перед которыми звонкие оглушаются,
-- @ch, @ct - образец и замена гласных
DECLARE @S varchar(4000), @V varchar(4000), @i int, @B int, @c char(1), @old_c char(1)
-- @S, @V - промежуточные строки, @i-счётчик цикла,
-- @B - позиция найденного элемента, @c - текущий символ
SET @W = UPPER(@W)
SET @S = ''
SET @V = ''
SET @i = 1
WHILE @i <= LEN(@W)
BEGIN
SET @c = SUBSTRING(@W, @i, 1)
IF CHARINDEX(@c, @alf)>0 SET @S = @S + @c
SET @i=@i+1
END
IF LEN(@S) = 0 RETURN ''
-- Заменяем окончания
IF LEN(@S)>6
SET @S = LEFT(@S, LEN(@S) - 6) +
CASE RIGHT(@S, 6)
WHEN 'ОВСКИЙ' THEN '@'
WHEN 'ЕВСКИЙ' THEN '#'
WHEN 'ОВСКАЯ' THEN '$'
WHEN 'ЕВСКАЯ' THEN '%'
ELSE RIGHT(@S, 6)
END
IF LEN(@S)>4
SET @S = LEFT(@S, LEN(@S) - 4) +
CASE RIGHT(@S, 4)
WHEN 'ИЕВА' THEN '9'
WHEN 'ЕЕВА' THEN '9'
ELSE RIGHT(@S, 4)
END
IF LEN(@S)>3
SET @S = LEFT(@S, LEN(@S) - 3) +
CASE RIGHT(@S, 3)
WHEN 'ОВА' THEN '9'
WHEN 'ЕВА' THEN '9'
WHEN 'ИНА' THEN '1'
WHEN 'ИЕВ' THEN '4'
WHEN 'ЕЕВ' THEN '4'
WHEN 'НКО' THEN '3'
ELSE RIGHT(@S, 3)
END
IF LEN(@S)>2
SET @S = LEFT(@S, LEN(@S) - 2) +
CASE RIGHT(@S, 2)
WHEN 'ОВ' THEN '4'
WHEN 'ЕВ' THEN '4'
WHEN 'АЯ' THEN '6'
WHEN 'ИЙ' THEN '7'
WHEN 'ЫЙ' THEN '7'
WHEN 'ЫХ' THEN '5'
WHEN 'ИХ' THEN '5'
WHEN 'ИН' THEN '8'
WHEN 'ИК' THEN '2'
WHEN 'ЕК' THEN '2'
WHEN 'УК' THEN '0'
WHEN 'ЮК' THEN '0'
ELSE RIGHT(@S, 2)
END
-- Оглушаем последний символ, если он - звонкий согласный:
SET @B = CHARINDEX(RIGHT(@S, 1), @cns1)
IF @B > 0
SET @S=LEFT(@S, LEN(@S)-1) +SUBSTRING(@cns2, @B, 1)
SET @old_c = ' '
SET @i = 1
WHILE @i <= LEN(@S)
BEGIN
SET @c = SUBSTRING(@S, @i, 1)
SET @B = CHARINDEX(@c, @ch)
IF @B > 0
BEGIN
IF @old_c = 'Й' OR @old_c = 'И'
BEGIN
IF @c = 'О' OR @c = 'Е'
BEGIN
SET @old_c = 'И'
SET @S = LEFT(@S, LEN(@S)-1) + @old_c
END
ELSE
IF @c <> @old_c SET @V = @V + SUBSTRING(@ct, @B, 1)
END
ELSE
BEGIN
IF @c <> @old_c SET @V = @V + SUBSTRING(@ct, @B, 1)
END
END
ELSE
BEGIN
IF @c <> @old_c
AND CHARINDEX(@c, @cns3)>0
BEGIN
SET @B = CHARINDEX(@old_c, @cns1)
IF @B>0
BEGIN
SET @old_c = SUBSTRING(@cns2, @B, 1)
SET @V = LEFT(@V, LEN(@V)-1) + @old_c
END
END
IF @c <> @old_c SET @V = @V + @c
END
SET @old_c = @c
SET @i = @i + 1
END
RETURN (@V)
END
GO
Заключение.
В настоящее время высококачественные фонетические алгоритмы для русского языка только проходят стадию внедрения и адаптации под требования корпоративных стандартов.
Предложенный вариант программной реализации алгоритма MetaPhone позволяет организовать поиск в базе данных схожих по звучанию слов, в частности, довольно быстро и правильно обрабатывать большинство русских фамилий (оптимизирован непосредственно для русских фамилий). Применение данной реализации позволит существенно облегчить решение бизнес-задач, связанных с обработкой персональных данных клиентов, а также максимально исключить влияние искажений информации, связанных с ошибками операторского ввода.
Литература
1. Буч Г., Максимчук Р.А., Энгл М.У., Янг Б. Дж., Коналлен Д., Хьюстон К.А. Объектно-ориентированный анализ и проектирование с примерами приложений. – М.: Вильямс, 2008, – 720 с.
2. Виейра Р. Программирование баз данных Microsoft SQL Server 2008. Базовый курс. – Киев.: Диалектика, 2009, – 816 с.
3. Вирт Н. Алгоритмы и структуры данных. – М.: ДМК Пресс, 2010, - 272 с.
4. Гагарина Л. Г., Колдаев В. Д. Алгоритмы и структуры данных. – М.:Инфра-М, 2009, - 304 с
5. Гасанов Э.Э., Кудрявцев В.Б. Теория хранения и поиска информации. М.:Физматлит, 2002, - 156 с.
