Sergey  
Местный босс - администраторJoined: 06 Jan 2005 Location: Оренбург Posts: 1165Last Visited: Yesterday at 14:46 Кредиты: 3714
Reputation: 48 Age: 41
Zodiac:  
| | ! | Sergey @ Thu 13 May, 2010 14:41: | Статья с сайта http://www.kankowski.naro.....d.ru/. К сожалению, сайт прекратил своё существование, но некоторые материалы не утеряли актуальности.
Эта статья выложена с максимальным приближением к авторской вёрстке без каких либо правок. Если автор объявится и выразит своё несогласие, статья будет удалена. |
-------------------------------
Статья была опубликована c незначительной литературной правкой в журнале "Программист" № 8 за 2002 г.
Я живу в сибирском городе Новокузнецке. Здесь много приезжих и потомков сосланных в Сибирь немцев, евреев и поляков, поэтому регистрация на собрании, выдача похвальных листов и оформление документов - всегда головная боль как для организаторов, так и для участников. После вручения наград обычно подходят с пол-десятка человек, чтобы исправить фамилию в грамоте или похвальном листе.
Вряд ли этому можно помочь, но вот облегчить поиск сложных фамилий в базе данных вполне можно. Для английского языка давно существует и активно используется алгоритмы Soundex и Metaphone , которые создают для фамилии ключ, причём похожим фамилиям или неверным написаниям одной фамилии будет соответствовать один ключ. Если кассир в банке наберёт вашу фамилию неверно, она всё равно получит доступ к вашей записи в базе данных, так как поиск ведётся по ключам. Например, ключ MetaPhone для Gustavson и Gustafson - KSTFS. Ключ SoundEx для тех же фамилий - G312.
Уже отсюда можно видеть, что MetaPhone убирает гласные, преобразует строку в верхний регистр и пишет одну букву F вместо двух одинаково читающихся F и V. Более простой алгоритм SoundEx записывает первую букву, затем номера групп последующих согласных (B, F, P, V - первая группа; C, G, J, K, Q, S, X, Z - вторая; D, T - третья; L - четвёртая; M, N - пятая и R - шестая). Из повторяющихся номеров остаётся только один; всего записывается не более четырёх номеров.
Задавшись целью разработать подобный алгоритм для русского языка, начал с того, что открыл старый телефонный справочник Новокузнецка и принялся выписывать из него «сомнительные» фамилии. На первых же страницах обнаружились Абаза, Абоймова, Ахмадова и Африкантов, которые на слух вряд ли можно сразу напечатать верно. Дальше — больше. После Вегнера, Вагнера, Вайгеля, Вайгульта, Вайлера, Вайлерта, Ваймана, Вайнера, Вайсборда и Вайшутеца меня смогли удивить только Коцко-Дундук, Покинь-Череда и Матьешайтис. Среди не слишком благозвучных фамилий Пукась, Телятник, Дрынь, Дубс, Нищий, Нахрынова и Нафикова попался великолепный, на мой взгляд, Диамант. Оказалось, в Новокузнецке живут Босс, Хан, Кот, Король, Колумб, три Буша и один Путин… В общем, вполне можно было сделать статью для юмористического журнала, но я всё-таки занялся MetaPhoneRu (такое название было выбрано для алгоритма).
Итак, вначале мы теоретически рассмотрим разные преобразования букв фамилий. С помощью программы перевести фамилии в традиционную фонетическую запись весьма сложно, так как ударение в тексте не обозначается, и некоторые буквосочетания произносятся по-разному в разных диалектах и людьми разных поколений. Но и не в этом наша задача, а в том, чтобы на практике находить один ключ для похожих фамилий. Поэтому ключ MetaPhoneRu отличается от фонетической записи (Майя Серебрянникова: [мájа сир’ґэбр’аЇникъва] и МАЙАСИРИБРАНИК9), но в целом преобразования соответствуют русской фонетике и графике:
- Гласные. Разница между Вагнером и Вегнером явно не меньше, чем между Вайгелем и Вайгультом, а англоязычные алгоритмы её не учитывают. Лучше не убирать гласные, а превращать их в те, что слышатся на их месте в безударном слоге: О в А, Е в И и т. п. Так и делает MetaPhoneRu, преобразуя Зицер и Зицир в Зицир (здесь и далее верны первые написания фамилий). Сложность здесь в том, что в многосложном слове невозможно без словаря определить ударение, и ударные гласные тоже будут преобразованы: Козлов в Казлав. Но разные распространенные фамилии не будут преобразованы в одну, и этот недостаток можно проигнорировать. Вот ряд, согласно которому MetaPhoneRu объединяет похожие гласные:
Code: Исходные символы | Конечный символ
О, Ы, А, Я | А
Ю, У | У
Е, Ё, Э, И | И
Таблица 1.
Казалось бы, примитивная схема, но она верно распознаёт довольно сложные похожие фамилии Бауэр и Бауер (оба написания верные), создавая для них ключ Бауир.
- Оглушение согласных в слабой позиции («сомнительный» согласный). Например, лаг и лак звучат одинаково и имеют один ключ ЛАК. Звонкие согласные превращаются в глухие перед другими согласными и в конце слова. Эти преобразования перечислены в таблице 2.
Code: Исходные символы | Конечный символ
П, Б | П
С, З | С
Т, Д | Т
Ф, В | Ф
К, Г | К
Таблица 2.
Алгоритм: в первую позицию строки записывается пробел, и далее строка, начиная со второго символа, сканируется на наличие согласной в текущем и предыдущем символе. Найденный звонкий согласный заменяется соответствующим глухим. До основного цикла мы проверяем последний символ строки и также оглушаем его при необходимости. Пример: Гудз и Гутс переходят в Гутс, Гефт и Гевт — в Гефт, Бовт и Бофт — в Бофт.
Особенность: алгоритм не оглушает согласные до сонорных звуков (м, н, л): ключи для фамилий Готлиб и Годлиб будут отличаться. Обычно согласные до сонорных слышны чётко: зло, блага, обнимать (ср. здесь, обточить). Если это нужно, вы можете исправить строку поиска cns3$, заставив функцию производить и это преобразование.
- Исключение повторяющихся символов. Здесь всё просто — Бопп может по ошибке быть написан с одной П, а Метревели многие напишут как Метревелли (по аналогии с Растрелли). Для этих фамилий будут созданы одинаковые ключи с одной повторяющейся буквой, и они будут найдены вне зависимости от написания.
Заметим, что, выполняя оглушение до исключения повторов, можно без лишних усилий генерировать тот же ключ для Шмидт и Шмит и подобных фамилий, так как Шмидт будет сначала преобразована в Шмитт, затем будет удалён повторяющийся Т, и получится Шмит.
- Сжатие окончаний. Типичные концовки фамилий заменяются спецсимволами и цифрами, например, Раневская превратится в РАН%. Это экономит место на хранении, ликвидирует ненужные преобразования окончаний, сокращая время работы алгоритма. Пример: вместо того, чтобы менять окончание –ова на –ава в фамилиях Огольцова и Агальцова (здесь верны оба написания), MetaPhoneRu преобразует только основу и создаёт для обеих фамилий ключ АГАЛЦ9.
Схожие окончания преобразуются в один спецсимвол, например, Грицюк и Грицук, как и Грецук, дадут ГРИЦ0. Если вы используйте алгоритм не для фамилий, уберите этот шаг или замените типичные окончания. Все сокращаемые окончания см. в таблице 3.
Code: Исходные окончания | Конечный символ
–УК, –ЮК | 0
–ИНА | 1
–ИК, –ЕК | 2
–НКО | 3
–ОВ, –ЕВ, [–ИЕВ, –ЕЕВ] | 4
–ЫХ, –ИХ | 5
–АЯ | 6
–ИЙ, –ЫЙ | 7
–ИН | 8
–ОВА, –ЕВА, [–ИЕВА, –ЕЕВА] | 9
–ОВСКИЙ | @
–ЕВСКИЙ | #
–ОВСКАЯ | $
–ЕВСКАЯ | %
Таблица 3. В квадратных скобках указаны окончания, которые заменяют второй и третий вариант алгоритма
- Исключение Ъ, Ь и дефиса между частями двойной фамилии. Твёрдый знак редко встречается в фамилиях, а мягкий ставят по ошибке на конце фамилии вроде Гусарьф или не ставят в Оганьян. Дефис иногда также может быть поставлен неверно. Проще всего убрать эти знаки вообще, и они будут игнорироваться при сравнении ключей.
Построим первый, более простой для понимания, вариант процедуры на Visual Basic. Конечный вариант будет сложным и даже слегка запутанным, но работать он будет быстрее.
Code: Function MetaPhoneRu1(ByVal W As String) As String
'Первоначальный вариант — простой, но не оптимальный.
Const alf$ = "ОЕАИУЭЮЯПСТРКЛМНБВГДЖЗЙФХЦЧШЩЫЁ", _
cns1$ = "БЗДВГ", _
cns2$ = "ПСТФК", _
cns3$ = "ПСТКБВГДЖЗФХЦЧШЩ", _
ch$ = "ОЮЕЭЯЁЫ", _
ct$ = "АУИИАИА"
'alf - алфавит кроме исключаемых букв, cns1 и cns2 - звонкие и глухие
'согласные, cns3 - согласные, перед которыми звонкие оглушаются,
'ch, ct - образец и замена гласных
Dim S$, V$, i&, B&, c$
'S, V - промежуточные строки, i - счётчик цикла, B - позиция
'найденного элемента, c$ - текущий символ
'Переводим в верхний регистр, оставляем только символы из alf
'приписываем пробел с начала, копируем в S:
W = UCase$(W): S = " "
For i = 1 To Len(W)
c = Mid$(W, i, 1)
If InStr(alf, c) Then S = S & c
Next i
If Len(S) = 1 Then Exit Function
'Заменяем окончания:
Select Case Right$(S, 6)
Case "ОВСКИЙ": S = Left$(S, Len(S) - 6) & "@"
Case "ЕВСКИЙ": S = Left$(S, Len(S) - 6) & "#"
Case "ОВСКАЯ": S = Left$(S, Len(S) - 6) & "$"
Case "ЕВСКАЯ": S = Left$(S, Len(S) - 6) & "%"
End Select
Select Case Right$(S, 3)
Case "ОВА", "ЕВА": S = Left$(S, Len(S) - 3) & "9"
Case "ИНА": S = Left$(S, Len(S) - 3) & "1"
Case "НКО": S = Left$(S, Len(S) - 3) & "3"
End Select
Select Case Right$(S, 2)
Case "ОВ", "ЕВ": S = Left$(S, Len(S) - 2) & "4"
Case "АЯ": S = Left$(S, Len(S) - 2) & "6"
Case "ИЙ", "ЫЙ": S = Left$(S, Len(S) - 2) & "7"
Case "ЫХ", "ИХ": S = Left$(S, Len(S) - 2) & "5"
Case "ИН": S = Left$(S, Len(S) - 2) & "8"
Case "ИК", "ЕК": S = Left$(S, Len(S) - 2) & "2"
Case "УК", "ЮК": S = Left$(S, Len(S) - 2) & "0"
End Select
'Оглушаем последний символ, если он - звонкий согласный:
B = InStr(cns1, Right$(S, 1))
If B Then Mid$(S, Len(S), 1) = Mid$(cns2, B, 1)
'Основной цикл:
For i = 2 To Len(S)
c = Mid$(S, i, 1)
B = InStr(ch, c)
If B Then Mid$(S, i, 1) = Mid$(ct, B, 1) 'Замена гласных
If InStr(cns3, c) Then 'Оглушение согласных
B = InStr(cns1, Mid$(S, i - 1, 1))
If B Then Mid$(S, i - 1, 1) = Mid$(cns2, B, 1)
End If
Next i
'Устраняем повторы, убираем первый пробел:
For i = 2 To Len(S)
c = Mid$(S, i, 1)
If c <> Mid$(S, i - 1, 1) Then V = V & c
Next i
MetaPhoneRu1 = V
End Function
«Плюсы» этой реализации:
- Небольшой и довольно быстрый алгоритм правильно обрабатывает большинство слов, хорошо оптимизирован именно под фамилии.
«Минусы»:
- Программа считает разными фамилии Аввакумов и Авакумов, так как преобразует Аввакумова в Афвакумова. Нужно проверять повторы не только после замены согласных, но и до этой замены.
- Можно сделать программу быстрее и проще, объединив основной цикл и цикл для устранения повторов и введя переменную для предыдущего символа.
- Желательно добавить проверку сочетаний ЙО, ЙЕ, превращая их в Ё и Е (учитывая принятый в MetaPhoneRu код для гласных, в И). Например, фамилии Емец, Пиотух и Иозеп могут восприниматься на слух как Йемец, Петух и Ёзеп.
Все эти недостатки были учтены в следующем варианте алгоритма:
Code: Function MetaPhoneRu2(ByVal W As String) As String
'Второй вариант — пожалуй, лучший.
'Заменяет ЙО, ЙЕ и др.; неплохо оптимизирован.
Const alf$ = "ОЕАИУЭЮЯПСТРКЛМНБВГДЖЗЙФХЦЧШЩЁЫ", _
cns1$ = "БЗДВГ", _
cns2$ = "ПСТФК", _
cns3$ = "ПСТКБВГДЖЗФХЦЧШЩ", _
ch$ = "ОЮЕЭЯЁЫ", _
ct$ = "АУИИАИА"
Dim S$, V$, i&, B&, c$, old_c$
'Переводим в верхний регистр, оставляем только
'символы из alf и копируем в S:
W = UCase$(W)
For i = 1 To Len(W)
c = Mid$(W, i, 1)
If InStr(alf, c) Then S = S & c
Next i
If Len(S) = 0 Then Exit Function
'Сжимаем окончания:
Select Case Right$(S, 6)
Case "ОВСКИЙ": S = Left$(S, Len(S) - 6) & "@"
Case "ЕВСКИЙ": S = Left$(S, Len(S) - 6) & "#"
Case "ОВСКАЯ": S = Left$(S, Len(S) - 6) & "$"
Case "ЕВСКАЯ": S = Left$(S, Len(S) - 6) & "%"
Case Else
If Right$(S, 4) = "ИЕВА" Or Right$(S, 4) = "ЕЕВА" Then
S = Left$(S, Len(S) - 4) & "9"
Else
Select Case Right$(S, 3)
Case "ОВА", "ЕВА": S = Left$(S, Len(S) - 3) & "9"
Case "ИНА": S = Left$(S, Len(S) - 3) & "1"
Case "ИЕВ", "ЕЕВ": S = Left$(S, Len(S) - 3) & "4"
Case "НКО": S = Left$(S, Len(S) - 3) & "3"
Case Else
Select Case Right$(S, 2)
Case "ОВ", "ЕВ": S = Left$(S, Len(S) - 2) & "4"
Case "АЯ": S = Left$(S, Len(S) - 2) & "6"
Case "ИЙ", "ЫЙ": S = Left$(S, Len(S) - 2) & "7"
Case "ЫХ", "ИХ": S = Left$(S, Len(S) - 2) & "5"
Case "ИН": S = Left$(S, Len(S) - 2) & "8"
Case "ИК", "ЕК": S = Left$(S, Len(S) - 2) & "2"
Case "УК", "ЮК": S = Left$(S, Len(S) - 2) & "0"
End Select
End Select
End If
End Select
'Оглушаем последний символ, если он - звонкий согласный:
B = InStr(cns1, Right$(S, 1))
If B Then Mid$(S, Len(S), 1) = Mid$(cns2, B, 1)
old_c = " "
'Основной цикл:
For i = 1 To Len(S)
c = Mid$(S, i, 1)
B = InStr(ch, c)
If B Then 'Если гласная
If old_c = "Й" Or old_c = "И" Then
If c = "О" Or c = "Е" Then 'Буквосочетания с гласной
old_c = "И": Mid$(V, Len(V), 1) = old_c
Else 'Если не буквосочетания с гласной, а просто гласная
If c <> old_c Then V = V & Mid$(ct, B, 1)
End If
Else 'Если не буквосочетания с гласной, а просто гласная
If c <> old_c Then V = V & Mid$(ct, B, 1)
End If
Else 'Если согласная
If c <> old_c Then 'для «Аввакумов»
If InStr(cns3, c) Then 'Оглушение согласных
B = InStr(cns1, old_c)
If B Then old_c = Mid$(cns2, B, 1): Mid$(V, Len(V), 1) = old_c
End If
If c <> old_c Then V = V & c 'для «Шмидт»
End If
End If
old_c = c
Next i
MetaPhoneRu2 = V
End Function
«Плюсы»:
- Вложенные Case хотя и не улучшают читаемости кода, но работают быстрее (не проверяются ненужные условия).
- MetaPhoneRu2 делает дополнительные проверки для буквосочетаний ИО, ЙО, ЙЕ и ИЕ.
«Минусы»:
- Несмотря на эти проверки, фамилии Ивлиев и Ивлев считаются разными, так как –ЕВ преобразуется в цифру при сжатии фамилии, а И остаётся. Для этого случая в анализ окончаний была добавлена строка Case "ИЕВ", "ЕЕВ", сжимающая окончание до той же цифры, что и Case "ЕВ". Аналогично с фамилиями на –ева, –иева.
- Чтобы не допускать повторов в строке, приходится проверять в нескольких случаях одно и то же условие If c <> old_c Then, что удлиняет и запутывает программу, хотя и не влияет на производительность.
Замечания:
- Фрагменты кода, проверяющие повторы до и после замены согласных, обозначены Аввакумов и Шмидт.
- Сложное условие (old_c = "Й" Or old_c = "И") And (c = "О" Or c = "Е") не использовано намерено: в VB оно подсчитывается полностью, что занимает много времени. По времени выгоднее создать повторяющиеся вложенные условия, хотя они и займут больше места.
- Исключение из строки отсутствующих в alf$ символов не было перенесено в основной цикл, так как тогда невозможно было бы различить те спецсимволы, которые изначально были в строке и те, которые добавило сжатие окончаний. Можно сократить процедуру, если отсекать спецсимволы ещё при вводе (сделать «фильтр» в событии KeyPress для TextBox) и отдельно исключать затем мягкий и твёрдый знак, дефис.
Вы можете скачать базу данных MetaPhoneRu.mdb (58 Kb в zip-архиве), которая поясняет использование MetaPhoneRu на практике. Нажмите кнопку Найти и согласитесь с предложенной фамилией Агольцова. Появится запись на фамилию Агальцова. Нажмите Найти Далее — будет выделена Огольцова. В файле MetaPhone.bas собраны все варианты реализации алгоритма, включая дополнительный третий вариант с подробными комментариями.
MetaPhoneRu позволяет вам искать похожие по звучанию слова, в частности, фамилии. Он упростит работу кассиров в банке, почтовых служб и облегчит вам решение любых других бизнес-задач, связанных с обработкой личных данных клиентов. |
Download Metaphoneru.zip (58.65 KB).
Added/Updated Thu 13 May, 2010 15:21.
Downloaded 148 Time(s).
