ООО ЭкоЮнит
FAQSearchMemberlistUsergroupsFilesLog inRegisterГлавная
printer-friendly view
 
AuthorMessage
Sergey Gender:Male


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


Joined: 06 Jan 2005
Show/Hide

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

 !  Sergey @ Thu 13 May, 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 объединяет похожие гласные:
    Code:
    Исходные символы | Конечный символ
    О, Ы, А, Я       |  А
    Ю, У             |  У
    Е, Ё, Э, И       |  И

    Таблица 1.


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


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

    Таблица 2.


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

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


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

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


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

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


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

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


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

Построим первый, более простой для понимания, вариант процедуры на 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 

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


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

«Минусы»:


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

«Плюсы»:


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



Download Metaphoneru.zip (58.65 KB). Added/Updated Thu 13 May, 2010 15:21. Downloaded 617 Time(s).

Back to topOffline View user's profile Visit poster's website Skype Name
Sergey Gender:Male


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


Joined: 06 Jan 2005
Show/Hide

Для интересующихся темой дополнительные ссылки, на мой взгляд наиболее интересные:
Почему функция 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!
Back to topOffline View user's profile Visit poster's website Skype Name
Display posts from previous:   

Summary Rating For >> «Как ваша фамилия», или Русский MetaPhone (Russian Metaphone description)
Average Rating: 4.71 :: Min Rating: 3 :: Max Rating: 5 :: Number of Ratings: 7
Choose Rating: 1   2   3   4   5  


Similar Topics
Topic Author Forum Replies Last Post
No new posts Как в мета description вставить первое сообщение темы?
How to add meta description tag from the first post of a topic?
и сократить его до 130 символов. Вот пробовал так, выводит сообщение, но если встречается какой-либо код, то все отображается выше шапки форума: Code meta name=description content=!-- IF SCRIPT_NAME == viewtopic --!--
zapatronen Поддержка и моды для phpBB3 22 Fri 26 Jan, 2018 17:47 View latest post
Алексус
No new posts Поиск по разделу
Поиск в разделе форума
Как сделать поиск по одному разделу, то есть, выбираем к примеру форум Прочие вопросы, и сверху справа окошко для поиска именно в этом форуме ?
Ренегат Поддержка и моды для phpBB2 2 Sun 11 Dec, 2016 22:02 View latest post
Ренегат
No new posts [RC] Advanced Similar Topics - Похожие темы (AJAX-мод)
автоматический поиск похожих по смыслу тем при создании новой темы или живой поиск
Наименование модификации: Advanced Similar (Related) Topics (compatible with phpBB SEO) Описание: Мод осуществляет поиск тем, схожих по смыслу, при создании новой темы после ввода названия и выводит таблицу результатов
Sergey Поддержка и моды для phpBB3 298 Mon 18 Jan, 2016 11:21 View latest post
DeathMan
No new posts Мод Search Similar Topics Before Posting - Похожие темы при создании новой (AJAX-мод)
автоматический поиск похожих по смыслу тем при создании новой темы или живой поиск
Описание мода: Мод осуществляет поиск тем, схожих по смыслу, при создании новой темы после ввода названия и выводит таблицу результатов поиска под полем названия темы. Версия мода: 1.0.4 Сложность установки: Легко Время
Sergey Поддержка и моды для phpBB2 17 Tue 12 Oct, 2010 19:43 View latest post
Sergey
No new posts Перевод на русский язык User Notes - Блокнот
Если не ошибаюсь, на этом форуме стоит этот User Notes (Блокнот). Если да, не поделитесь ли переводом?
Joe_Dou Поддержка и моды для phpBB2 5 Fri 08 Sep, 2017 22:10 View latest post
vlad77






All times are UTC + 3 hours
Users browsing this topic:
Registered Users: None

Jump to:   
printer-friendly view
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
/a
Username:

Password:

Log me on automatically each visit
  Яндекс.Метрика
CrackerTracker © 2004 - 2019 CBACK.de