Software & Systems

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

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

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

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

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

Для последующих шагов существует ряд алгоритмов, таких как алгоритм Вагнера–Фишера [1] или алгоритм Смита–Ватермана [2], позволяющих количественно оценить близость строк между собой, используя в качестве меры близости дистанции редактирования. К подобным мерам относится расстояние Левенштейна, то есть минимальное количество элементарных операций вставки, удаления и замены одного символа, необходимых для превращения одной строки в другую, или расстояние Хэмминга, используемое для сравнения строк одинаковой размерности.

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

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

В основе алгоритма Фонетик, реализованного в данной работе в среде Delphi 7, лежит вариант алгоритма MetaPhone, предложенный в [4].

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

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

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

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

Таблица 1

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

Для проверки релевантности алгоритма Фонетик из автоматизированной банковской системы было выгружено 25907 записей о физических лицах. Этот массив данных был получен слиянием нескольких БД и содержал некоторое количество дублирующих записей о физических лицах, которые не были обнаружены средствами СУБД во время слияния. Весь массив данных обработан экспертами, которые выявили в нем 661 дублирующую запись.

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

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

Таблица 2

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

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

Таблица 3

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

По количеству ошибок первого рода алгоритм Фонетик на порядок эффективнее алгоритмов, вычисляющих дистанцию Левенштейна, и алгоритма Soundex. Алгоритм прямого сравнения оказался наименее эффективным по количеству ошибок 1-го рода.

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

Литература

1. Wagner R.A., Fischer M.J. The string-to-string correction problem / Journal of the ACM, 1974. Vol. 21, № 1, pp. 168–173.

2. Smith T.F., Waterman M.S. Identification of common molecular subsequences / Journal of Molecular Biology, 1981. Vol. 147, pp. 195–197.

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

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

5. Гешвинде Э., Шениг Г. Разработка Web-приложений на PHP и PostgreSQL. Руководство разработчика и администратора. СПб: ДиаСофтЮП, 2003. 608 с.