ООО ЭкоЮнит
FAQПоискПользователиГруппыФайлыВходРегистрацияГлавная
Версия для печати
 
АвторСообщение
Sergey Пол:Муж.


Местный босс - администратор


Зарегистрирован: 06.01.2005
Показать/Спрятать

В статье описан алгоритм Metaphone, адаптированный к суровым сибирским пельменям, самогонке морозам и образу мышления медведей в шапках-ушанках с балалайками.

 !  Sergey @ Чт 13 Май, 2010 14:41:
Статья с сайта Петра Каньковского kankowski.narod.ru/ .
К сожалению, сайт прекратил своё существование, но некоторые материалы не утеряли актуальности. Статья выложена с максимальным приближением к авторской вёрстке без каких либо правок.
Несколько лет назад эти материалы пригодились мне для разработки подсистемы нечёткого поиска в базе данных 1С Предприятия, фрагмент которой находится в теме Функция Русский MetaPhone, Soundex, расстояние Левенштейна и другие для 1С:Предприятия любой платформы и конфигурации . В силу особенностей платформы поиск происходил не слишком быстро, но результат выдавал. Я решил сохранить статью для сообщества. Если автор объявится и выразит своё несогласие, она будет удалена.


-------------------------------
Статья была опубликована 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), но в целом преобразования соответствуют русской фонетике и графике:


  1. Гласные. Разница между Вагнером и Вегнером явно не меньше, чем между Вайгелем и Вайгультом, а англоязычные алгоритмы её не учитывают. Лучше не убирать гласные, а превращать их в те, что слышатся на их месте в безударном слоге: О в А, Е в И и т. п. Так и делает MetaPhoneRu, преобразуя Зицер и Зицир в Зицир (здесь и далее верны первые написания фамилий). Сложность здесь в том, что в многосложном слове невозможно без словаря определить ударение, и ударные гласные тоже будут преобразованы: Козлов в Казлав. Но разные распространенные фамилии не будут преобразованы в одну, и этот недостаток можно проигнорировать. Вот ряд, согласно которому MetaPhoneRu объединяет похожие гласные:
    Код:
    Исходные символы | Конечный символ
    О, Ы, А, Я       |  А
    Ю, У             |  У
    Е, Ё, Э, И       |  И

    Таблица 1.


    Казалось бы, примитивная схема, но она верно распознаёт довольно сложные похожие фамилии Бауэр и Бауер (оба написания верные), создавая для них ключ Бауир.


  2. Оглушение согласных в слабой позиции («сомнительный» согласный). Например, лаг и лак звучат одинаково и имеют один ключ ЛАК. Звонкие согласные превращаются в глухие перед другими согласными и в конце слова. Эти преобразования перечислены в таблице 2.
    Код:
    Исходные символы   |     Конечный символ
    П, Б               |     П
    С, З               |     С
    Т, Д               |     Т
    Ф, В               |     Ф
    К, Г               |     К
    

    Таблица 2.


    Алгоритм: в первую позицию строки записывается пробел, и далее строка, начиная со второго символа, сканируется на наличие согласной в текущем и предыдущем символе. Найденный звонкий согласный заменяется соответствующим глухим. До основного цикла мы проверяем последний символ строки и также оглушаем его при необходимости. Пример: Гудз и Гутс переходят в Гутс, Гефт и Гевт — в Гефт, Бовт и Бофт — в Бофт.

    Особенность: алгоритм не оглушает согласные до сонорных звуков (м, н, л): ключи для фамилий Готлиб и Годлиб будут отличаться. Обычно согласные до сонорных слышны чётко: зло, блага, обнимать (ср. здесь, обточить). Если это нужно, вы можете исправить строку поиска cns3$, заставив функцию производить и это преобразование.


  3. Исключение повторяющихся символов. Здесь всё просто — Бопп может по ошибке быть написан с одной П, а Метревели многие напишут как Метревелли (по аналогии с Растрелли). Для этих фамилий будут созданы одинаковые ключи с одной повторяющейся буквой, и они будут найдены вне зависимости от написания.

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


  4. Сжатие окончаний. Типичные концовки фамилий заменяются спецсимволами и цифрами, например, Раневская превратится в РАН%. Это экономит место на хранении, ликвидирует ненужные преобразования окончаний, сокращая время работы алгоритма. Пример: вместо того, чтобы менять окончание –ова на –ава в фамилиях Огольцова и Агальцова (здесь верны оба написания), MetaPhoneRu преобразует только основу и создаёт для обеих фамилий ключ АГАЛЦ9.

    Схожие окончания преобразуются в один спецсимвол, например, Грицюк и Грицук, как и Грецук, дадут ГРИЦ0. Если вы используете алгоритм не для фамилий, уберите этот шаг или замените типичные окончания. Все сокращаемые окончания см. в таблице 3.


    Код:
    Исходные окончания          |     Конечный символ
    –УК, –ЮК                    |     0
    –ИНА                        |     1
    –ИК, –ЕК                    |     2
    –НКО                        |     3
    –ОВ, –ЕВ, [–ИЕВ, –ЕЕВ]      |     4
    –ЫХ, –ИХ                    |     5
    –АЯ                         |     6
    –ИЙ, –ЫЙ                    |     7
    –ИН                         |     8
    –ОВА, –ЕВА, [–ИЕВА, –ЕЕВА]  |     9
    –ОВСКИЙ                     |     @
    –ЕВСКИЙ                     |     #
    –ОВСКАЯ                     |     $
    –ЕВСКАЯ                     |     %
    

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


  5. Исключение Ъ, Ь и дефиса между частями двойной фамилии. Твёрдый знак редко встречается в фамилиях, а мягкий ставят по ошибке на конце фамилии вроде Гусарьф или не ставят в Оганьян. Дефис иногда также может быть поставлен неверно. Проще всего убрать эти знаки вообще, и они будут игнорироваться при сравнении ключей.

Построим первый, более простой для понимания, вариант процедуры на Visual Basic. Конечный вариант будет сложным и даже слегка запутанным, но работать он будет быстрее.


Код:
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 

«Плюсы» этой реализации:


  1. Небольшой и довольно быстрый алгоритм правильно обрабатывает большинство слов, хорошо оптимизирован именно под фамилии.

«Минусы»:


  1. Программа считает разными фамилии Аввакумов и Авакумов, так как преобразует Аввакумова в Афвакумова. Нужно проверять повторы не только после замены согласных, но и до этой замены.
  2. Можно сделать программу быстрее и проще, объединив основной цикл и цикл для устранения повторов и введя переменную для предыдущего символа.
  3. Желательно добавить проверку сочетаний ЙО, ЙЕ, превращая их в Ё и Е (учитывая принятый в MetaPhoneRu код для гласных, в И). Например, фамилии Емец, Пиотух и Иозеп могут восприниматься на слух как Йемец, Петух и Ёзеп.

Все эти недостатки были учтены в следующем варианте алгоритма:


Код:
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

«Плюсы»:


  1. Вложенные Case хотя и не улучшают читаемости кода, но работают быстрее (не проверяются ненужные условия).
  2. MetaPhoneRu2 делает дополнительные проверки для буквосочетаний ИО, ЙО, ЙЕ и ИЕ.

«Минусы»:


  1. Несмотря на эти проверки, фамилии Ивлиев и Ивлев считаются разными, так как –ЕВ преобразуется в цифру при сжатии фамилии, а И остаётся. Для этого случая в анализ окончаний была добавлена строка Case "ИЕВ", "ЕЕВ", сжимающая окончание до той же цифры, что и Case "ЕВ". Аналогично с фамилиями на –ева, –иева.
  2. Чтобы не допускать повторов в строке, приходится проверять в нескольких случаях одно и то же условие If c <> old_c Then, что удлиняет и запутывает программу, хотя и не влияет на производительность.

Замечания:


  1. Фрагменты кода, проверяющие повторы до и после замены согласных, обозначены Аввакумов и Шмидт.
  2. Сложное условие (old_c = "Й" Or old_c = "И") And (c = "О" Or c = "Е") не использовано намерено: в VB оно подсчитывается полностью, что занимает много времени. По времени выгоднее создать повторяющиеся вложенные условия, хотя они и займут больше места.
  3. Исключение из строки отсутствующих в alf$ символов не было перенесено в основной цикл, так как тогда невозможно было бы различить те спецсимволы, которые изначально были в строке и те, которые добавило сжатие окончаний. Можно сократить процедуру, если отсекать спецсимволы ещё при вводе (сделать «фильтр» в событии KeyPress для TextBox) и отдельно исключать затем мягкий и твёрдый знак, дефис.

Вы можете скачать базу данных MetaPhoneRu.mdb (58 Kb в zip-архиве), которая поясняет использование MetaPhoneRu на практике. Нажмите кнопку Найти и согласитесь с предложенной фамилией Агольцова. Появится запись на фамилию Агальцова. Нажмите Найти Далее — будет выделена Огольцова. В файле MetaPhone.bas собраны все варианты реализации алгоритма, включая дополнительный третий вариант с подробными комментариями.

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



Скачать Metaphoneru.zip (58.65 KB). Добавлен/обновлён Чт 13 Май, 2010 15:21. Скачано 537 раз(а).

ВверхНа форуме нет Профиль Сайт Имя в Skype
Sergey Пол:Муж.


Местный босс - администратор


Зарегистрирован: 06.01.2005
Показать/Спрятать

Для интересующихся темой дополнительные ссылки, на мой взгляд наиболее интересные:
Почему функция SOUNDEX не работает с русскими словами?
Фонетический поиск
Фонетические алгоритмы
Soundex по-русски

_________________
Профессионал - это тот же дилетант, только знающий где ошибется. Генератор db_update.php для phpBB2 с некоторыми удобствами.
Как ставить моды. Что такое [SQL] и с чем его едят | Как правильно задавать вопросы и получать адекватные ответы | Правила форума
Бесплатная техподдержка только на форуме! Не надо стучаться в аську, скайп, слать емайлы, пытаться писать в приват. Спасибо за понимание. Please do not PM, ICQ, Skype or email me for support help - you won't get any reply. If you have a question or issue, post it in the appropriate forum/topic. Thanks!
ВверхНа форуме нет Профиль Сайт Имя в Skype
Показать сообщения:   

Общий рейтинг темы «Как ваша фамилия», или Русский MetaPhone (Russian Metaphone description)
Средний рейтинг: 4.71 :: Мин. рейтинг: 3 :: Макс. рейтинг: 5 :: Количество оценок: 7
Выберите вашу оценку: 1   2   3   4   5  


Похожие темы
Тема Автор Форум Ответов Посл. сообщение
Нет новых сообщений Как в мета description вставить первое сообщение темы?
How to add meta description tag from the first post of a topic?
и сократить его до 130 символов. Вот пробовал так, выводит сообщение, но если встречается какой-либо код, то все отображается выше шапки форума: Код meta name=description content=!-- IF SCRIPT_NAME == viewtopic --!--
zapatronen Поддержка и моды для phpBB3 21 Вт 05 Янв, 2016 22:21 Посмотреть последнее сообщение
Марат_00
Нет новых сообщений Поиск по разделу
Поиск в разделе форума
Как сделать поиск по одному разделу, то есть, выбираем к примеру форум Прочие вопросы, и сверху справа окошко для поиска именно в этом форуме ?
Ренегат Поддержка и моды для phpBB2 2 Вс 11 Дек, 2016 22:02 Посмотреть последнее сообщение
Ренегат
Нет новых сообщений [RC] Advanced Similar Topics - Похожие темы (AJAX-мод)
автоматический поиск похожих по смыслу тем при создании новой темы или живой поиск
Наименование модификации: Advanced Similar (Related) Topics (compatible with phpBB SEO) Описание: Мод осуществляет поиск тем, схожих по смыслу, при создании новой темы после ввода названия и выводит таблицу результатов
Sergey Поддержка и моды для phpBB3 298 Пн 18 Янв, 2016 11:21 Посмотреть последнее сообщение
DeathMan
Нет новых сообщений Мод Search Similar Topics Before Posting - Похожие темы при создании новой (AJAX-мод)
автоматический поиск похожих по смыслу тем при создании новой темы или живой поиск
Описание мода: Мод осуществляет поиск тем, схожих по смыслу, при создании новой темы после ввода названия и выводит таблицу результатов поиска под полем названия темы. Версия мода: 1.0.4 Сложность установки: Легко Время
Sergey Поддержка и моды для phpBB2 17 Вт 12 Окт, 2010 19:43 Посмотреть последнее сообщение
Sergey
Нет новых сообщений Перевод на русский язык User Notes - Блокнот
Если не ошибаюсь, на этом форуме стоит этот User Notes (Блокнот). Если да, не поделитесь ли переводом?
Joe_Dou Поддержка и моды для phpBB2 2 Пн 23 Окт, 2006 13:10 Посмотреть последнее сообщение
Joe_Dou






Часовой пояс: UTC + 3 часа
Просматривают тему:
Зарегистрированные пользователи: Нет

Перейти:   
Версия для печати
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете вкладывать файлы
Вы можете скачивать файлы
/a
Имя:

Пароль:

Запомнить
  Яндекс.Метрика
CrackerTracker © 2004 - 2017 CBACK.de