Исследование фонетических алгоритмов

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

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

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

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

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

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

А.Ф. Чипига

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

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

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

Группа БАС-081

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

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

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

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

Ставрополь 2011

Содержание

Введение

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

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

.2 Выводы

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

.1 Алгоритм Soundex

.2 Алгоритм NYSIIS

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

.4 Алгоритм Metaphone

.5 Алгоритм Caverphone

.6 Выводы

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

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

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

.3 Выводы

Заключение

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

Приложение

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оригинальный Soundex:→ Дедловский, Дедловских, Дидилев, Дителев, Дудалев, Дудолев, Дутлов, Дыдалев, Дятлов, Дятлович.→ Нагимов, Нагмбетов, Назимов, Насимов, Нассонов, Нежнов, Незнаев, Несмеев, Нижневский, Никонов, Никонович, Нисенблат, Нисенбаум, Ниссенбаум, Ногинов, Ножнов.

Улучшенный Soundex:→ Насимов, Нассонов, Никонов.→ Нисенбаум, Ниссенбаум.→ Нагимов, Нагонов, Неганов, Ногинов.→ Нагмбетов.→ Назимов, Нежнов, Ножнов

В среднем, на одно значение кода 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→ SSS

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

EE → Y

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

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

EV → AF, E, I, O, U → A→ G→ S→ N→ N→ C→ SSS

PH → FF

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

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

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

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

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

Приведем примеры работы данного алгоритма→ Каспаравичус, Касперович, Каспирович.→ Катников, Цитников, Цотников.→ Ленченко, Леонченко, Линченко, Лунченко, Лямзенко.→ Приходский, Проходский, Прудский, Прудских, Прудской.→ Стадников.преобразует к одному и тому же коду немногим более двух фамилий.

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

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

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

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

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

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

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

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

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

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

К одному и тому же коду этот алгоритм преобразует в среднем 5 фамилий. Впоследствии Александр Бейдер и Стивен Морзе разработали Beider-Morse Name Matching Algorithm <#"524156.files/image002.gif">

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

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

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

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

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

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

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

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

3.3 Выводы

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

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

Заключение

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

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

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

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

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

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

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

. Цыганов Н.Л. Обзор алгоритмов нечёткого сопоставления записей применительно к задаче исключения дублирования персональных данных [Электронный ресурс]/ Н.Л. Цыганов, М.В. Марковский. - Московский инженерно-физический институт, 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*VOWELS="AEIOU",

*FRONTV="EIY",

*VARSON="CSPTG",

*DOUBLE=".";*excpPAIR="AGKPW", *nextLTR ="ENNNR";*chrptr, *chrptr1;phonetic(name,metaph,metalen)

char *name, *metaph;metalen;

{ii, jj, silent, hard, Lng, lastChr;curLtr, prevLtr, nextLtr, nextLtr2, nextLtr3;vowelAfter, vowelBefore, frontvAfter;wname[60];*ename=wname;= 0;(ii=0; name[ii] != '\0'; ii++) {(isalpha(name[ii])) {[jj] = toupper(name[ii]);++;

}

}[jj] = '\0';(strlen(ename) == 0) return;((chrptr=strchr(excpPAIR,ename[0])) != NULLCHAR)

{= nextLTR + (chrptr-excpPAIR);(*chrptr1 == ename[1]) strcpy(ename,&ename[1]);

}(ename[0] == 'X') ename[0] = 'S'; if (strncmp(ename,"WH",2) == 0) strcpy(&ename[1], &ename[2]);= strlen(ename);= Lng -1;(ename[lastChr] == 'S') {[lastChr] = '\0';= strlen(ename);= Lng -1;

}

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

curLtr = ename[ii];= FALSE; prevLtr = ' ';(ii > 0) {= ename[ii-1];(strchr(VOWELS,prevLtr) != NULLCHAR) vowelBefore = TRUE;

}(ii == 0 && (strchr(VOWELS,curLtr) != NULLCHAR)) {(metaph,&curLtr,1);;

}= FALSE; frontvAfter = FALSE; nextLtr = ' ';(ii < lastChr) {= ename[ii+1];(strchr(VOWELS,nextLtr) != NULLCHAR) vowelAfter = TRUE;(strchr(FRONTV,nextLtr) != NULLCHAR) frontvAfter =TRUE;(curLtr == nextLtr && (strchr(DOUBLE,nextLtr) == NULLCHAR)) continue;= ' ';(ii < (lastChr-1)) nextLtr2 = ename[ii+2];= ' ';(ii < (lastChr-2)) nextLtr3 = ename[ii+3];(curLtr) {'B': silent = FALSE;(ii == lastChr && prevLtr == 'M') silent = TRUE;(! silent) strncat(metaph,&curLtr,1);;'C': if (! (ii > 1 && prevLtr == 'S' && frontvAfter))(ii > 0 && nextLtr == 'I' && nextLtr2 == 'A')(metaph,"X",1);(frontvAfter)(metaph,"S",1);(ii > 1 && prevLtr == 'S' && nextLtr == 'H')(metaph,"K",1);(nextLtr == 'H')(ii == 0 && (strchr(VOWELS,nextLtr2) == NULLCHAR))(metaph,"K",1);(metaph,"X",1);(prevLtr == 'C')(metaph,"C",1);(metaph,"K",1);;'D': if (nextLtr == 'G' && (strchr(FRONTV,nextLtr2) != NULLCHAR))(metaph,"J",1);(metaph,"T",1);;'G': silent=FALSE;

/* SILENT -gh- except for -gh and no vowel after h */((ii < (lastChr-1) && nextLtr == 'H')

&& (strchr(VOWELS,nextLtr2) == NULLCHAR))=TRUE;((ii == (lastChr-3))

&& nextLtr == 'N' && nextLtr2 == 'E' && nextLtr3 == 'D')=TRUE;((ii == (lastChr-1)) && nextLtr == 'N') silent=TRUE;(prevLtr == 'D' && frontvAfter) silent=TRUE;(prevLtr == 'G')=TRUE;=FALSE;(!silent)(frontvAfter && (! hard))(metaph,"J",1);(metaph,"K",1);;'H': silent = FALSE;(strchr(VARSON,prevLtr) != NULLCHAR) silent = TRUE;(vowelBefore && !vowelAfter) silent = TRUE;(!silent) strncat(metaph,&curLtr,1);;'F':'J':'L':'M':'N':'R': strncat(metaph,&curLtr,1);;'K': if (prevLtr != 'C') strncat(metaph,&curLtr,1);;'P': if (nextLtr == 'H')(metaph,"F",1);(metaph,"P",1);;'Q': strncat(metaph,"K",1);;'S': if (ii > 1 && nextLtr == 'I'

&& (nextLtr2 == 'O' || nextLtr2 == 'A'))(metaph,"X",1);(nextLtr == 'H')(metaph,"X",1);(metaph,"S",1);;'T': if (ii > 1 && nextLtr == 'I'

&& (nextLtr2 == 'O' || nextLtr2 == 'A'))(metaph,"X",1);(nextLtr == 'H')(ii > 0 || (strchr(VOWELS,nextLtr2) != NULLCHAR))(metaph,"0",1);(metaph,"T",1);(! (ii < (lastChr-2) && nextLtr == 'C' && nextLtr2 == 'H'))(metaph,"T",1);;'V': strncat(metaph,"F",1);;'W':'Y': if (ii < lastChr && vowelAfter) strncat(metaph,&curLtr,1);;'X': strncat(metaph,"KS",2);;'Z': strncat(metaph,"S",1);;;

}metaphone(argc)argc;

{name[128];metaph[50];(argc != 1) {(stderr, "metaphone: argc != 1\n");("");(1);

}(name, sizeof(name));[0] = '\0';(name,metaph,20);(metaph);(1);

}