Исследование фонетических алгоритмов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? сходные, будут представлены для последующей обработки в ручном режиме, а значит, будут проконтролированы.
По количеству ошибок первого рода алгоритм Фонетик на порядок эффективнее алгоритмов, вычисляющих дистанцию Левенштейна, и алгоритма Soundex. Алгоритм прямого сравнения оказался наименее эффективным по количеству ошибок 1-го рода.
Алгоритм Фонетик при сравнении строк, содержащих фамилию, имя и отчество физического лица, показывает высокую стабильность и эффективность в работе, отличается хорошей приспособленностью к нормам и правилам русского языка, высокой релевантностью, низкими показателями ошибок первого и второго рода. Использование технологии поиска сходных записей на основе данного алгоритма позволяет снизить избыточность БД, сократить долю ручного труда операторов, в реальном времени отслеживать историю обращений клиента, а также проводить интеллектуальную обработку, например резервирование или репликацию, и прочие операции с данными, требующие больших затрат времени. Фонетик хорошо подходит в качестве инструмента сопровождения автоматизированных банковских систем, систем денежных переводов, иных программных средств, требующих непосредственного взаимодействия оператора системы с физическими лицами, информация о которых вносится в систему.
.2 Реализация алгоритма Metaphone для русского языка
В 2002 году в 8-ом выпуске журнала Программист была опубликована статья Петра Каньковски , рассказывающая о его адаптации английской версии алгоритма Metaphone к суровым сибирским морозам, медведям и балалайкам. Этот алгоритм преобразует исходные слова в соответствии с правилами и нормами русского языка, учитывая фонетическое звучание безударных гласных и возможные слияния согласных при произношении. Он показывает очень хорошие результаты на практике, несмотря на то, что основывается на довольно простых правилах. Все буквы разбиты на группы по звучанию - гласные и согласные (vowels и consonants соответственно в английской терминологии), глухие и звонкие. Звонкие согласные преобразуются в соответствующие им парные глухие, объединяются сливающиеся при произношении последовательности букв, и проводятся некоторые другие манипуляции. Ниже я приведу немного доработанный вариант, который, в отличие от оригинала Петра Каньковски, привносит правила, связанные с фонетической эквивалентностью Ц и ТС или ДС, и не сжимает окончания - байты экономить - это не наша задача.
Алгоритм вычисления кода русского Metaphone
1. Для всех гласных букв проделать следующие операции.
ЙО, ИО, ЙЕ, ИЕ > И
О, Ы, Я > А
Е, Ё, Э > И
Ю > У
. Для всех согласных букв, за которыми следует любая согласная, кроме Л, М, Н или Р, либо же для согласных на конце слова, провести оглушение:
Б > П
З > С
Д > Т
В > Ф
Г > К
. Склеиваем ТС и ДС в Ц: ТС > Ц
В итоге, алгоритм очень хорошо справляется со своей задачей - в результирующем наборе содержатся действительно фонетически схожие слова. И при этом остается довольно мало лишних слов, в основном благодаря тому, что гласные не игнорируются, а преобразуются и используются в итоговом коде. Однако же, есть некоторые слова, которые, не смотря на свою фонетическую схожесть, не попадают в результирующий набор из-за слишком строгих правил алгоритма.
В случае Адольфа Швардсенеггера результатом работы алгоритма русского Metaphone будет:
Рисунок 3.1 - Реализация алгоритма Петра Каньковски
Таким образом, алгоритм в данном случае отражает реальное фонетическое сходство этих двух фамилий.
Пример работы данного алгоритма.
ВИТАФСКИЙ > Витавский, Витовский.
ВИТИНБИРК > Витенберг, Виттенберг.
НАСАНАФ > Насанов, Насонов, Нассонов, Носонов.
ПИРМАКАФ > Пермаков, Пермяков, Перьмяков.
Этот алгоритм преобразует к одному и тому же коду в среднем 1-2 фамилии.
3.3 Выводы
Изучив фонетические алгоритмы можно коротко охарактеризовать каждый из них.
Алгоритм Фонетик при сравнении строк, содержащих фамилию, имя и отчество физического лица, показывает высокую стабильность и эффективность в работе, отличается хорошей приспособленностью к нормам и правилам русского языка, низкими показателями ошибок. Использование технологии поиска сходных записей на основе данного алгоритма позволяет снизить избыточность БД, сократить долю ручного труда операторов, в реальном времени отслеживать историю обращений клиента, а также проводить интеллектуальную обработку, например резервирование или репликацию, и прочие операции с данными, требующие больших затрат времени.позволяет вам искать похожие по звучанию слова, в частности, фамилии. Он упростит работу кассиров в банке, почтовых служб и облегчит вам решение любых других бизнес-задач, связанных с обработкой личных данных клиентов.
Заключение
Методы и алгоритмы анализа строк находят практическое применение во многих областях науки и информационных технологий: глобальные поисковые системы, сжатие данных, криптография, распознавание речи, компьютерное зрение, генетика и молекулярная биология. Одной из актуальных сфер применения таких алгоритмов являются также задачи сопровождения БД, входящих в состав различных информационных систем (ИС). Типичными и часто обсуждаемыми на форумах программистов являются задачи сопоставления и идентификации объектов, сведения о которых хранятся в разных БД. В частности, к под