Исследование фонетических алгоритмов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
.)
. Удаление непроизносимых букв, а также знаков препинания.
. Замена сходных по начертанию латинских букв (A, B, C, E, H, O, P, T X, Y) на русские аналогичного начертания (А, В, С, Е, Н, О, Р, Т, Х, У).
. Выработка ключа с использованием имени и отчества либо только инициалов в зависимости от выбранной настройки и полноты исходных данных.
. Замена гласных букв на те, которые слышатся на их месте в безударном слоге. Буквы О, Ы, А, Я заменяются на А; Ю, У на У; Е, Е, Э, И на И. Несмотря на то, что в русском языке произношение буквы часто не соответствует написанию, сокращать слова до одних согласных нельзя, поскольку существует ряд парных глухих и звонких. С точки зрения грамматики русского языка такой подход не является абсолютно верным, но на практике показывает хорошие результаты.
. Оглушение согласных в соответствии с правилами русского языка. В слабой позиции по звонкости-глухости в области согласных происходит оглушение, при котором все звонкие согласные (кроме сонорных) на конце слова произносятся как парные им глухие, а также два конечных звонких переходят в соответствующие глухие. Алгоритм не оглушает согласные до сонорных звуков.
. Замена последовательностей букв, которые не встречаются в русском языке, на необходимые из словаря слогов.
. Удаление парных согласных. Частой ошибкой является некорректное написание парных согласных. Для этих ситуаций создаются одинаковые ключи с одной повторяющейся буквой, которые будут найдены независимо от написания.
. Замена типовых для русского языка окончаний фамилий на специальные символы. Эта команда сокращает время обработки и экономит место для хранения ключей. Данное преобразование имеет смысл только для фамилий.
Пункты 1, 2, 5, 6, 8, 9 с некоторыми изменениями заимствованы из реализации алгоритма MetaPhone [4]. Для повышения качества сравнения алгоритм дополнен следующими этапами.
. В большинстве случаев в информационной системе вместе с фамилией присутствуют имя и отчество, тогда имеет смысл привязать их к ключу. Имя и отчество обрабатываются отдельно от фамилии согласно пп. 1-6 алгоритма и дополняют ключ, полученный на основе фамилии. Если в одной системе в данных присутствуют лишь инициалы, то у обеих строк данные для обработки сокращаются до фамилии и первых букв имени и отчества, преобразованных к верхнему регистру.
. В связи с тем, что персональные данные нередко получают из источника данных невысокого качества, о чем свидетельствует наличие инициалов вместо полноценных имени и отчества, имеет смысл заменять в ключе символы инициалов на сходные по написанию. Если рассмотреть графическое начертание букв, то И имеет сходство с Н, следовательно, в инициалах они могут быть заменены друг на друга. Остальные буквы остаются без изменений.
. Итоговый ключ формируется конкатенацией ключа, полученного из фамилии, и результатов обработки имени и отчества или инициалов.
В таблице 3.1 приведен пример списка, подаваемого на вход алгоритма, и соответствующих выходных значений.
Таблица 3.1 - Работа алгоритма фонетик
Исходное словоКлючГодеева А.В.ГАД9АВГодиева И.А.ГАД9ИАИванюков П.В.ИВАНУК4ПВИванников С.А.ИВАНИК4САКовалева С.А.КАВАЛИВА САКовалева О.А.КАВАЛИВА ОАГолушков О.В.ГАЛУШК4ОВКолушков С.П.КАЛУШК4СПКуликов А.А.КУЛИК4АА
Таким образом, получается список ключей, на основе которого можно строить таблицу соответствия идентификационных данных лиц из разных БД.
Для проверки релевантности алгоритма Фонетик из автоматизированной банковской системы было выгружено 25907 записей о физических лицах. Этот массив данных был получен слиянием нескольких БД и содержал некоторое количество дублирующих записей о физических лицах, которые не были обнаружены средствами СУБД во время слияния. Весь массив данных обработан экспертами, которые выявили в нем 661 дублирующую запись.
Анализ сформированного массива данных о физических лицах проведен алгоритмами Фонетик, прямого сравнения, Soundex и алгоритмом, рассчитывающим дистанцию Левенштейна. Алгоритмы запускались на данной выборке по очереди, по принципу сравнения каждой записи с каждой.
В алгоритме, вычисляющем дистанцию Левенштейна, записи считались различными, если дистанция редактирования превышала единицу. Перед применением алгоритма Soundex, разработанного для английского языка, записи подвергались транслитерации.
В качестве нулевой гипотезы H0 полагалось, что сравниваемые записи соответствуют одному физическому лицу. Типы ошибок в работе алгоритмов определялись по таблице 3.2, в которой символом H1 обозначена гипотеза, противоположная H0.
Таблица 3.2 - Типы ошибок
Результат работы алгоритмаВерная гипотеза для входных данныхH0H1H0H0 верно принятаH0 неверно принята (ошибка второго рода)H1H0 неверно отвергнута (ошибка первого рода)H0 верно отвергнута
По итогам работы всех алгоритмов была заполнена результирующая таблица с количеством ошибок для каждого алгоритма.
По общему количеству ошибок сравнения наихудшие результаты показал алгоритм, вычисляющий дистанцию Левенштейна. Второе место по общему количеству ошибок после алгоритма Фонетик занимает алгоритм прямого сравнения. Однако в данном случае значимость ошибок первого и второго рода различна. Наиболее критичными являются ошибки первого рода, поскольку сходные объекты, классифицированные как различные, не попадут в итоговую выборку, то есть будут потеряны. Наличие ошибки второго рода не столь критично, так как на практике все объекты, классифицированные ка?/p>