Размещено на http://www.allbest.ru/

34

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУ ВПО «Северо-Кавказский государственный технический университет»

Факультет информационных технологий и телекоммуникаций

«Допустить к защите»

Заведующий кафедрой ЗИ

А.Ф. Чипига

КУРСОВАЯ РАБОТА

НА ТЕМУ: Исследование фонетических алгоритмов

Специальность 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Группа БАС-081

Проектировал

А.П. Погорелова

Руководитель работы

Р.А. Воронкин

Ставрополь 2011

Содержание

Введение

1. Фонетический поиск

1.1 Понятие фонетической транскрипции и фонетического поиска

1.2 Выводы

2. Общие сведения о фонетических алгоритмах

2.1 Алгоритм Soundex

2.2 Алгоритм NYSIIS

2.3 Алгоритм Daitch-Mokotoff Soundex

2.4 Алгоритм Metaphone

2.5 Алгоритм Caverphone

2.6 Выводы

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

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

3.2 Реализация алгоритма Metaphone для русского языка

3.3 Выводы

Заключение

Список использованных источников

Приложение

Введение

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

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

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

Специфика обработки имен физических лиц более полно учтена в известных алгоритмах сравнения двух строк по их звучанию - Soundex и MetaPhone.

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

1. Фонетический поиск

1.1 Понятие фонетической транскрипции и фонетического поиска

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

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

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

Как правило, звуковые оболочки слов и их форм различны, если исключить омонимы. Слова, имеющие одинаковый звуковой состав, могут различаться местом ударения (муку - муку, муки - муки) или порядком следования одинаковых звуков (кот - ток). Слова могут содержать и такие наименьшие, далее не членимые единицы речевого звучания, которые самостоятельно разграничивают звуковые оболочки слов и их форм, например: бак, бок, бук; в данных словах звуки [а], [о], [у] различают звуковые оболочки этих слов и выступают как фонемы. Слова бачок и бочок различаются на письме, но произносятся одинаково [б?чок]: звуковые оболочки этих слов не различаются, потому что звуки [а] и [о] в приведенных словах оказываются в первом предударном слоге и лишаются той различительной роли, какую они выполняют в словах бак - бок. Следовательно, фонема служит для различения звуковой оболочки слов и их форм. Фонемы дифференцируют не значение слов и форм, а лишь их звуковые оболочки, указывают на различия в значении, но не раскрывают их характера.

Различное качество звуков [а] и [о] в словах бак - бок и бачок - бочок объясняется различным местом, которое эти звуки занимают в словах по отношению к словесному ударению. Кроме того, при произнесении слов возможно влияние одного звука на качество другого, и вследствие этого качественный характер звука оказывается обусловленным позицией звука - положением после другого звука или перед ним, между другими звуками. В частности, для качества гласных звуков оказывается важным положение по отношению к ударному слогу, а для согласных - положение в конце слова. Так, в словах рог - рога [рок] - [р?га] согласный звук [г] (на конце слова) оглушается и произносится как [к], а гласный звук [о] (в первом предударном слоге) звучит как а [л]. Следовательно, качество звуков [о] и [г] в данных словах оказывается в той или иной степени зависимым от позиции этих звуков в слове.

Понятие фонемы предполагает разграничение самостоятельных и зависимых признаков звуков речи. Самостоятельные и зависимые признаки звуков соотносятся неодинаково у разных звуков и в различных фонетических условиях. Так, например, звук [з] в словах создал и раздел характеризуется двумя самостоятельными признаками: способом образования (щелевой звук) и местом образования (зубной звук). Кроме самостоятельных признаков, звук [з] в слове создал [создъл] имеет один зависимый признак - звонкость (перед звонким [д]), а в слове раздел [р?здел] - два зависимых признака, обусловленных позицией звука: звонкость (перед звонким [д]) и мягкость (перед мягким зубным [д]). Отсюда следует, что в одних фонетических условиях у звуков преобладают признаки самостоятельные, а в других - зависимые.

Учет самостоятельных и зависимых признаков уточняет понятие фонемы. Независимые качества образуют самостоятельные фонемы, которые употребляются в одной и той же (тождественной) позиции и различают звуковые оболочки слов. Зависимые качества звука исключают возможность употребления звука в тождественной позиции и лишают звук различительной роли и потому образуют не самостоятельные фонемы, а лишь разновидности одной и той же фонемы. Следовательно, фонемой называется кратчайшая звуковая единица, независимая по своему качеству и потому служащая для различения звуковых оболочек слов и их форм. Качество гласных звуков [а], [о], [у] в словах бак, бок, бук фонетически не обусловлено, не зависит от позиции, а употребление этих звуков тождественно (между одинаковыми согласными, под ударением). Поэтому выделенные звуки обладают различительной функцией и, следовательно, являются фонемами.

В словах мать, мята, мять [ма*т', м'*ать, м'aт'] ударный звук [а] различается по качеству, так как употребляется не в тождественной, а в различных позициях (перед мягким, после мягкого, между мягкими согласными). Поэтому звук [а] в словах мать, мята, мять не имеет непосредственно различительной функции и образует не самостоятельные фонемы, а лишь разновидности одной и той же фонемы <а>. Фонетический алгоритм является алгоритмом для индексации из слов их произношение.

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

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

Среди наиболее известных фонетические алгоритмы: саундэкс, который был разработан для кодирования фамилий для использования в переписях, Саундэкс Дэйча-Мокотоффа, который является уточнением саундэкс.

Разработан, чтобы лучше соответствовать фамилии славянских и германских происхождения. Метафон и Двойной Метафон, который подходит для использования с большинством английских слов, а не только для названий объектов. Алгоритмы Метафон являются основой для многих популярных проверок правописания. Нью-Йорк государственной идентификации и информационной системы (NYSIIS), который отображает аналогичные фонемы той же буквой.

1.2 Выводы

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

Мы привыкли видеть слова в графической форме, в виде последовательности букв. Это представление кажется нам наиболее естественным, так как мы постоянно с ним сталкиваемся. И поэтому неудивителен первый порыв разработчиков использовать это представление в своих программах обработки текстов. Такое решение вполне оправдано, например, в программах проверки орфографии. Но если мы хотим моделировать словоизменительные и словообразовательные процессы, то наиболее удобным будет фонематическое представление языковой информации, в виде последовательности фонем. Дело в том, что живой язык подчиняется фонетическим законам более, нежели законам орфографическим, и учёт этого факта значительно упрощает алгоритмы морфологического или словообразовательного анализа и синтеза, избавляя их от необходимости учёта орфографических особенностей.

2. Общие сведения о фонетических алгоритмах

2.1 Алгоритм Soundex

Одним из первых был алгоритм Soundex, изобретенный еще в 10-x годах прошлого века Робертом Расселом. Этот алгоритм (а точнее, его американская версия) сопоставляет словам численный индекс вида A126. Принцип его работы основан на разбиении согласных букв на группы с порядковыми номерами, из которых затем и составляется результирующее значение. Позднее также был предложен ряд улучшений.

Первая буква сохраняется, последующие буквы сопоставляются цифрам по таблице. Символы, не представленные в таблице (а это все гласные и некоторые согласные), игнорируются. Смежные символы, или символы, разделенные буквами H или W, входящие в одну и ту же группу, записываются как один. Результат обрезается до 4 символов. Недостающие позиции заполняются нулями. Несложно заметить, что после всех этих процедур остается всего лишь 7 тысяч различных вариаций такого кода, что влечет за собой множество совершенно ничем не похожих друг на друга слов, имеющих одинаковый Soundex-код. Таким образом, результат в большинстве случаев включает в себя большое количество «ложноположительных» значений.

Рисунок 2.1 - Структура алгоритма Soundex

В улучшенной версии, как можно заметить, буквы разбиты на большее количество групп. Помимо этого, никакого особого внимания буквам H и W не уделяется, они просто игнорируются. Кроме того, никаких операций с длиной результата не производится - код не имеет фиксированной длины и не обрезается.

Приведем примеры работы данного алгоритма.

Оригинальный Soundex:

D341 > Дедловский, Дедловских, Дидилев, Дителев, Дудалев, Дудолев, Дутлов, Дыдалев, Дятлов, Дятлович.

N251 > Нагимов, Нагмбетов, Назимов, Насимов, Нассонов, Нежнов, Незнаев, Несмеев, Нижневский, Никонов, Никонович, Нисенблат, Нисенбаум, Ниссенбаум, Ногинов, Ножнов.

Улучшенный Soundex:

N8030802 > Насимов, Нассонов, Никонов.

N80308108 > Нисенбаум, Ниссенбаум.

N8040802 > Нагимов, Нагонов, Неганов, Ногинов.

N804810602 > Нагмбетов.

N8050802 > Назимов, Нежнов, Ножнов

В среднем, на одно значение кода Soundex приходится 21 фамилия. В случае же улучшенной версии Soundex, к одному и тому же коду преобразуются всего 2-3 фамилии.

2.2 Алгоритм NYSIIS

Разработанный в 1970 году как часть системы «New York State Identification and Intelligence System», этот алгоритм дает несколько лучшие результаты относительно оригинального Soundex, используя более сложные правила преобразования исходного слова в результирующий код. Этот алгоритм разработан для работы именно с американскими фамилиями.

Приведем алгоритм вычисления кода NYSIIS.

1. Преобразовать начало слова по следующим правилам:

MAC > MCC

KN > N

K > C

PH, PF > FF

SCH > SSS

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

EE > Y

IE > YDT, RT, RD, NT, ND > D

3. Затем все буквы, кроме первой, преобразуются по следующим правилам:

EV > AF

A, E, I, O, U > A

Q > G

Z > S

M > N

KN > N

K > C

SCH > SSS

PH > FF

4. После гласных: удалить H, преобразовать W > A

5. Удалить S на конце

6. Преобразуем AY на конце > Y

7. Удалить A на конце

8. Обрезать до 6 символов (необязательный шаг).

Приведем примеры работы данного алгоритма

CASPARAVAS > Каспаравичус, Касперович, Каспирович.

CATNACAV > Катников, Цитников, Цотников.

LANSANC > Ленченко, Леонченко, Линченко, Лунченко, Лямзенко.

PRADSC > Приходский, Проходский, Прудский, Прудских, Прудской.

STADNACAV > Стадников.

NYSIIS преобразует к одному и тому же коду немногим более двух фамилий.

2.3 Алгоритм Daitch-Mokotoff Soundex

Этот алгоритм в 1985 году разработали два генеалога - Гарри Мокотофф и Рэнди Дэйч, стремясь достичь лучших, относительно оригинального Soundex, результатов при работе с восточно-европейскими (в том числе русскими) фамилиями.

Этот алгоритм имеет мало общего с оригинальным Soundex, разве что результатом всё так же остается последовательность цифр, однако теперь первая буква также кодируется.

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

Преобразования осуществляются по следующей таблице (порядок преобразований соответствует порядку буквосочетаний в таблице):

Таблица 2.1 - Преобразования алгоритма Daitch-Mokotoff Soundex

Исходные буквосочетания	В начале	За гласной	Остальное
AI, AJ, AY, EI, EY, EJ, OI, OJ, OY, UI, UJ, UY	0	1
AU	0	7
1	2	3	4
1	2	3	4
IA, IE, IO, IU	1
EU	1	1
A, UE, E, I, O, U, Y	0
J	1	1	1
SCHTSCH, SCHTSH, SCHTCH, SHTCH, SHCH, SHTSH, STCH, STSCH, STRZ, STRS, STSH, SZCZ, SZCS	2	4	4
SHT, SCHT, SCHD, ST, SZT, SHD, SZD, SD	2	43	43
CSZ, CZS, CS, CZ, DRZ, DRS, DSH, DS, DZH, DZS, DZ, TRZ, TRS, TRCH, TSH, TTSZ, TTZ, TZS, TSZ, SZ, TTCH, TCH, TTSCH, ZSCH, ZHSH, SCH, SH, TTS, TC, TS, TZ, ZH, ZS	4	4	4
SC	2	4	4
DT, D, TH, T	3	3	3
CHS, KS, X	5	54	54
S, Z	4	4	4
CH, CK, C, G, KH, K, Q	5	5	5
MN, NM		66	66
M, N	6	6	6
FB, B, PH, PF, F, P, V, W	7	7	7
H	5	5
L	8	8	8
R	9	9	9

«Альтернативные» варианты буквосочетаний (используются для генерации нескольких альтернативных кодов из исходного слова):

CH > TCH

CK > TSK

C > TZ

J > DZH

Приведем примеры работы данного алгоритма.

095747 > Архипцев, Архипцов, Архипычев, Арцыбасов, Арцыбашев, Арчибасов

095757 > Архипков, Архипцев, Архипцов, Архипычев

584360 > Галстян, Галустян, Гильштейн, Глистин, Глуздань, Голштейн, Гольдштеин, Гольдштейн, Калустьян, Хлистун, Хлыстун, Хлюстин.

К одному и тому же коду этот алгоритм преобразует в среднем 5 фамилий. Впоследствии Александр Бейдер и Стивен Морзе разработали Beider-Morse Name Matching Algorithm, нацеленный на уменьшение количества «ложноположительных» значений относительно Daitch-Mokotoff Soundex при работе с еврейскими (ашкенази) фамилиями.

2.4 Алгоритм Metaphone

Несколько лучшими характеристиками обладает алгоритм Metaphone (1990 год), отличающийся от предыдущих алгоритмов несколько иным подходом к процессу кодирования: он преобразует исходное слово с учетом правил английского языка, используя заметно более сложные правила, и при этом теряется значительно меньше информации, так как буквы не разбиваются на группы. Итоговый код представляет собой набор символов из множества 0BFHJKLMNPRSTWXY, в начале слова также могут быть гласные из множества AEIOU.

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

1. Удаляем все повторяющиеся соседние буквы, за исключением буквы C.

2. Начало слова преобразовать по следующим правилам:

KN > N

GN > N

PN > N

AE > E

WR > R

3. Удаляем на конце букву B, если она идет после M.

4. Заменяем C по следующим правилам

На Х: CIA > XIA, SCH > SKH, CH > XH

На S: CI > SI, CE > SE, CY > SY

На K: C > K

5. Заменяем D по следующим правилам

На J: DGE > JGE, DGY > JGY, DGI > JGY

На T: D > T

6. Заменяем GH > H, если это буквосочетание стоит не в конце и не перед гласной.

7. Заменяем GN > N и GNED > NED, если эти буквосочетания стоят в конце.

8. Заменяем G по следующим правилам

На J: GI > JI, GE > JE, GY > JY

На K: G > K

9. Удаляем все H, идущие после гласных, но не перед гласными.

10. Выполняем последующие преобразования по правилам:

CK > K

PH > F

Q > K

V > F

Z > S

11. Заменяем S на X:

SH > XH

SIO > XIO

SIA > XIA

12. Заменяем T по следующим правилам

На X: TIA > XIA, TIO > XIO

На 0: TH > 0

Удаляем: TCH > CH

13. В начале слова преобразовать WH > W. Если после W нет гласной, то удалить W.

14. Если X в начале слова, то преобразовать X > S, иначе X > KS

15. Удалить все Y, которые не находятся перед гласными.

16. Удалить все гласные, кроме начальной.

Приведем примеры работы алгоритма Metaphone

AKXN > Агашин, Акаченок, Акишин, Аксионенко, Аксионов, Акчунаев, Акшанов, Акшенцев, Акшинский, Акшинцев, Акшонов.

FSLX > Василишин, Васильчак, Васильченко, Васильчик, Васильчиков, Васильченко, Васильчук, Василющенко.

SRFM > Серафимов, Серафимский, Серафимчук, Церейфман.

Одно и то же значение кода Metaphone имеют в среднем 6 фамилий.

Double Metaphone (2000 год) несколько отличается от других фонетических алгоритмов, генерируя из исходного слова не один, а два кода (оба длиной до 4 символов) - один отражает основной вариант произношения слова, другой же - альтернативную версию. Он имеет большое количество различных правил, учитывающих, помимо всего прочего, различное происхождение слов, уделяя внимание восточно-европейским, итальянским, китайским словам и так далее. Правила преобразований достаточно многочисленны. (Приложение).

Примеры работы этого алгоритма

JXRF > Гишаров.

KKRF > Гагаров, Кагаров, Качаровский, Качеровский, Качуривский, Качуров, Качуровский, Кичеров, Кокарев, Кокоуров, Кокоуров, Кочаров, Кочуров, Кукарев, Цакиров, Цокуров, Цугров.

KXRF > Гишаров, Гочаров, Качеров, Качеровский, Кашаревский, Кочаров, Кочерев, Кочеряев, Кочураев, Кошарев, Кошеров.

PNFS > Бановский, Бахновский, Биневский, Бинявский, Буйновский, Буяновский, Паневский, Пановский, Пановских, Пеньевский, Пиневский, Пиуновский, Пихновский.

Double Metaphone сопоставляет в среднем 8-9 фамилий одному и тому же коду.

2.5 Алгоритм Caverphone

Алгоритм фонетического сравнения Каверфон (Caverphone) был создан в рамках Кавершамского проекте в университете Отаго в Новой Зеландии в 2002 году. Алгоритм позволяет акценты присутствующие в изучаемой зоне (южная часть города Дунедин, Новой Зеландия).

Новая версия Каверфон 2.0 была предложена для более общего фонетического сравнения.

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

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

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

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

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

Таблица 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$ - символ на конце строки):

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

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

Пример работы данного алгоритма

KPRLN11111 > Габрелян, Габриэлян, Габриэльян, Капарулин, Капралин, Капрелян.

MSRFK11111 > Мейзерович, Мисарович, Мисюревич.

PLLF111111 > Балалаев, Балалиев, Балалуев, Билалиев, Билалов, Билялов, Болелов, Палилов, Полилов, Полуляхов.

Caverphone сопоставляет одному и тому же коду около 4-5 фамилий.

2.6 Выводы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В таблице 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-го рода.

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

3.2 Реализация алгоритма Metaphone для русского языка

В 2002 году в 8-ом выпуске журнала «Программист» была опубликована статья Петра Каньковски, рассказывающая о его адаптации английской версии алгоритма Metaphone к суровым сибирским морозам, медведям и балалайкам. Этот алгоритм преобразует исходные слова в соответствии с правилами и нормами русского языка, учитывая фонетическое звучание безударных гласных и возможные «слияния» согласных при произношении. Он показывает очень хорошие результаты на практике, несмотря на то, что основывается на довольно простых правилах. Все буквы разбиты на группы по звучанию - гласные и согласные (vowels и consonants соответственно в английской терминологии), глухие и звонкие. Звонкие согласные преобразуются в соответствующие им парные глухие, объединяются «сливающиеся» при произношении последовательности букв, и проводятся некоторые другие манипуляции. Ниже я приведу немного доработанный вариант, который, в отличие от оригинала Петра Каньковски, привносит правила, связанные с фонетической эквивалентностью Ц и ТС или ДС, и не сжимает окончания - байты экономить - это не наша задача.

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

1. Для всех гласных букв проделать следующие операции.

ЙО, ИО, ЙЕ, ИЕ > И

О, Ы, Я > А

Е, Ё, Э > И

Ю > У

2. Для всех согласных букв, за которыми следует любая согласная, кроме Л, М, Н или Р, либо же для согласных на конце слова, провести оглушение:

Б > П

З > С

Д > Т

В > Ф

Г > К

3. Склеиваем ТС и ДС в Ц: ТС > Ц

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

В случае Адольфа Швардсенеггера результатом работы алгоритма русского Metaphone будет:



Рисунок 3.1 - Реализация алгоритма Петра Каньковски

Таким образом, алгоритм в данном случае отражает реальное фонетическое сходство этих двух фамилий.

Пример работы данного алгоритма.

ВИТАФСКИЙ > Витавский, Витовский.

ВИТИНБИРК > Витенберг, Виттенберг.

НАСАНАФ > Насанов, Насонов, Нассонов, Носонов.

ПИРМАКАФ > Пермаков, Пермяков, Перьмяков.

Этот алгоритм преобразует к одному и тому же коду в среднем 1-2 фамилии.

3.3 Выводы

Изучив фонетические алгоритмы можно коротко охарактеризовать каждый из них.

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

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

Заключение

Методы и алгоритмы анализа строк находят практическое применение во многих областях науки и информационных технологий: глобальные поисковые системы, сжатие данных, криптография, распознавание речи, компьютерное зрение, генетика и молекулярная биология. Одной из актуальных сфер применения таких алгоритмов являются также задачи сопровождения БД, входящих в состав различных информационных систем (ИС). Типичными и часто обсуждаемыми на форумах программистов являются задачи сопоставления и идентификации объектов, сведения о которых хранятся в разных БД. В частности, к подобным задачам относят поиск, сопоставление и слияние персональных данных о физических лицах. Это могут быть, например, списки клиентов телефонных компаний, покупателей различных товаров и услуг, клиентов банка.

Следует отметить, что изначально ни один из алгоритмов изначально не разрабатывался для сравнения данных о физических лицах. Специфика обработки имен физических лиц более полно учтена в известных алгоритмах сравнения двух строк по их звучанию - Soundex и MetaPhone. Описание алгоритма Soundex дано в классическом учебнике по программированию [1], алгоритм MetaPhone адаптирован для русского языка в работе [2]. Эти алгоритмы основаны на построении некоторой хэш-функции, преобразующей исходные строки в хэш-код, одинаковый для схожих строк. Процесс сравнения двух строк сводится к вычислению хэш-кодов этих строк и их последующего строгого сравнения. Строки, имеющие одинаковый хэш-код, считаются похожими.

Об эффективности подобных алгоритмов говорит тот факт, что в некоторых языках программирования сравнение подобного рода организовано в качестве стандартной процедуры. Например, в MySQL и PHP функция Soundex является встроенной.

Список использованных источников

1. Дональд Э. Кнут. Искусство программирования. Т. 3. Сортировка и поиск. М.: Издат. дом «Вильямс», 2005.

2. Каньковски П. «Как ваша фамилия», или Русский MetaPhone // Программист. 2002. №8. С. 36-39.

3. Гешвинде Э., Шениг Г. Разработка Web-приложений на PHP и PostgreSQL.

4. Лиманов Н. И., Седов М. Н. Метод автоматизированного поиска персональных данных на основе нечеткого сравнения // Информационные технологии. 2009. №11. С.

5. Бойцов Л.М. Использование хеширования по сигнатуре для поиска по сходству // Прикладная математика и информатика. 2000. №7.

6. Федоркова Г.О. Применение метода нечеткого поиска в операции соединения реляционных таблиц баз данных. Электронный журнал «Исследовано в России, 2004.

7. Международный журнал Программные продукты и системы в выпуске журнала №1 за 2011 год.

8. Кнут Дональд. Искусство программирования, том 1: Пер. с англ. / Дональд Кнут. - М.: Вильямс, 2000. - 690 с.

9. Марков А.А. Теория алгоритмов / А.А. Марков, Н.М. Нагорный. - М.: Наука. Главная редакция физико-математической литературы, 1984. - 432 с.

10. Цыганов Н.Л. Обзор алгоритмов нечёткого сопоставления записей применительно к задаче исключения дублирования персональных данных [Электронный ресурс]/ Н.Л. Цыганов, М.В. Марковский. - Московский инженерно-физический институт, 2006. - Режим доступа: http://www.library.mephi.ru/data/scientific-sessions/2006/t15/1-1-25.doc

Приложение

Программа для АЛГОРИТМА METAPHONE

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#define TRUE (1)

#define FALSE (0)

#define NULLCHAR (char *) 0

char *VOWELS="AEIOU",

*FRONTV="EIY",

*VARSON="CSPTG",

*DOUBLE=".";

char *excpPAIR="AGKPW", *nextLTR ="ENNNR";

char *chrptr, *chrptr1;

void phonetic(name,metaph,metalen)

char *name, *metaph;

int metalen;

{

int ii, jj, silent, hard, Lng, lastChr;

char curLtr, prevLtr, nextLtr, nextLtr2, nextLtr3;

int vowelAfter, vowelBefore, frontvAfter;

char wname[60];

char *ename=wname;

jj = 0;

for (ii=0; name[ii] != '\0'; ii++) {

if (isalpha(name[ii])) {

ename[jj] = toupper(name[ii]);

jj++;

}

}

ename[jj] = '\0';

if (strlen(ename) == 0) return;

if ((chrptr=strchr(excpPAIR,ename[0])) != NULLCHAR)

{

chrptr1 = nextLTR + (chrptr-excpPAIR);

if (*chrptr1 == ename[1]) strcpy(ename,&ename[1]);

}

if (ename[0] == 'X') ename[0] = 'S'; if (strncmp(ename,"WH",2) == 0) strcpy(&ename[1], &ename[2]);

Lng = strlen(ename);

lastChr = Lng -1;

if (ename[lastChr] == 'S') {

ename[lastChr] = '\0';

Lng = strlen(ename);

lastChr = Lng -1;

}

for (ii=0; ((strlen(metaph) < metalen) && (ii < Lng)); ii++) {

curLtr = ename[ii];

vowelBefore = FALSE; prevLtr = ' ';

if (ii > 0) {

prevLtr = ename[ii-1];

if (strchr(VOWELS,prevLtr) != NULLCHAR) vowelBefore = TRUE;

}

if (ii == 0 && (strchr(VOWELS,curLtr) != NULLCHAR)) {

strncat(metaph,&curLtr,1);

continue;

}

vowelAfter = FALSE; frontvAfter = FALSE; nextLtr = ' ';

if (ii < lastChr) {

nextLtr = ename[ii+1];

if (strchr(VOWELS,nextLtr) != NULLCHAR) vowelAfter = TRUE;

if (strchr(FRONTV,nextLtr) != NULLCHAR) frontvAfter =TRUE;

if (curLtr == nextLtr && (strchr(DOUBLE,nextLtr) == NULLCHAR)) continue;

nextLtr2 = ' ';

if (ii < (lastChr-1)) nextLtr2 = ename[ii+2];

nextLtr3 = ' ';

if (ii < (lastChr-2)) nextLtr3 = ename[ii+3];

switch (curLtr) {

case 'B': silent = FALSE;

if (ii == lastChr && prevLtr == 'M') silent = TRUE;

if (! silent) strncat(metaph,&curLtr,1);

break;

case 'C': if (! (ii > 1 && prevLtr == 'S' && frontvAfter))

if (ii > 0 && nextLtr == 'I' && nextLtr2 == 'A')

strncat(metaph,"X",1);

else

if (frontvAfter)

strncat(metaph,"S",1);

else

if (ii > 1 && prevLtr == 'S' && nextLtr == 'H')

strncat(metaph,"K",1);

else

if (nextLtr == 'H')

if (ii == 0 && (strchr(VOWELS,nextLtr2) == NULLCHAR))

strncat(metaph,"K",1);

else

strncat(metaph,"X",1);

else

if (prevLtr == 'C')

strncat(metaph,"C",1);

else

strncat(metaph,"K",1);

break;

case 'D': if (nextLtr == 'G' && (strchr(FRONTV,nextLtr2) != NULLCHAR))

strncat(metaph,"J",1);

else

strncat(metaph,"T",1);

break;

case 'G': silent=FALSE;

/* SILENT -gh- except for -gh and no vowel after h */

if ((ii < (lastChr-1) && nextLtr == 'H')

&& (strchr(VOWELS,nextLtr2) == NULLCHAR))

silent=TRUE;

if ((ii == (lastChr-3))

&& nextLtr == 'N' && nextLtr2 == 'E' && nextLtr3 == 'D')

silent=TRUE;

else

if ((ii == (lastChr-1)) && nextLtr == 'N') silent=TRUE;

if (prevLtr == 'D' && frontvAfter) silent=TRUE;

if (prevLtr == 'G')

hard=TRUE;

else

hard=FALSE;

if (!silent)

if (frontvAfter && (! hard))

strncat(metaph,"J",1);

else

strncat(metaph,"K",1);

break;

case 'H': silent = FALSE;

if (strchr(VARSON,prevLtr) != NULLCHAR) silent = TRUE;

if (vowelBefore && !vowelAfter) silent = TRUE;

if (!silent) strncat(metaph,&curLtr,1);

break;

case 'F':

case 'J':

case 'L':

case 'M':

case 'N':

case 'R': strncat(metaph,&curLtr,1);

break;

case 'K': if (prevLtr != 'C') strncat(metaph,&curLtr,1);

break;

case 'P': if (nextLtr == 'H')

strncat(metaph,"F",1);

else

strncat(metaph,"P",1);

break;

case 'Q': strncat(metaph,"K",1);

break;

case 'S': if (ii > 1 && nextLtr == 'I'

&& (nextLtr2 == 'O' || nextLtr2 == 'A'))

strncat(metaph,"X",1);

else

if (nextLtr == 'H')

strncat(metaph,"X",1);

else

strncat(metaph,"S",1);

break;

case 'T': if (ii > 1 && nextLtr == 'I'

&& (nextLtr2 == 'O' || nextLtr2 == 'A'))

strncat(metaph,"X",1);

else

if (nextLtr == 'H')

if (ii > 0 || (strchr(VOWELS,nextLtr2) != NULLCHAR))

strncat(metaph,"0",1);

else

strncat(metaph,"T",1);

else

if (! (ii < (lastChr-2) && nextLtr == 'C' && nextLtr2 == 'H'))

strncat(metaph,"T",1);

break;

case 'V': strncat(metaph,"F",1);

break;

case 'W':

case 'Y': if (ii < lastChr && vowelAfter) strncat(metaph,&curLtr,1);

break;

case 'X': strncat(metaph,"KS",2);

break;

case 'Z': strncat(metaph,"S",1);

break;

return;

}

int metaphone(argc)

int argc;

{

char name[128];

char metaph[50];

if (argc != 1) {

fprintf(stderr, "metaphone: argc != 1\n");

retquote("");

return(1);

}

popquote(name, sizeof(name));

metaph[0] = '\0';

phonetic(name,metaph,20);

retquote(metaph);

return(1);

}

Размещено на Allbest.ru