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

№1-1,

технические науки

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

Похожие материалы

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

Решить проблему дублирования персональных данных средствами СУБД не представляется возможным. Все известные методы идентификации объектов в базах данных оперируют точным равенством сравниваемых полей и бессильны при наличии ошибок и пропусков данных [2].

Для разработки и реализации алгоритмов поиска дублирующихся субъектов предлагается:

  1. полагать, что необязательно проверять все реквизиты из анкеты клиента, достаточно сравнить некоторые наиболее важные, обязательные для заполнения реквизиты, и на основании совпадения только этих реквизитов практически гарантированно можно сделать вывод о том, что субъекты повторяют друг друга;
  2. считать, что дублирующимися субъектами являются субъекты, у которых «набор» проверяемых реквизитов совпадает полностью (точно) либо степень совпадения неполная, но допустима.

Степень совпадения позволит учесть, что возможны различия (ошибки) в одном и том же реквизите для разных субъектов, например, если оператор при вводе информации о субъекте допустил ошибку.

Разрабатываемые алгоритмы нечеткого сопоставления записей могут применяться в различных системах, где организованы хранение и обработка персональных данных субъектов, для исключения дублирования. Мотивом для разработки послужила необходимость модернизации процедуры проверки справочника субъектов АБС «RS-Bank/Pervasive».

Ключевой частью разрабатываемых алгоритмов будут являться алгоритмы нечёткого сопоставления строк (анализа строк). Термин анализ строк [1] здесь будем использовать для описания класса задач, связанных с вычислением расстояния между двумя строками (метрики). Существуют несколько метрик, основные – это расстояние Хемминга и расстояние Левенштейна. Расстояние Хемминга (Hamming) между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Если допускается сравнение строк разной длины, то минимальная общая цена преобразования будет равна одной из метрик, предложенных Левенштейном (Levenstein).

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

Одним из наиболее распространенных орфографических алгоритмов нечёткого сопоставления строк является метод динамического программирования Вагнера-Фишера. Затраты времени и памяти оцениваются как O(mn), однако, этот метод прост в реализации и эффективен для строк небольшой длины.

Вычислив расстояние Левенштейна, можно найти процент совпадения строк по следующей формуле:

Процент совпадения строк

гдеpercent_of_simil - процент совпадения; max_len - длина наибольшей строки; d - расстояние Левенштейна.

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

Для реализации процедуры проверки субъектов на дублирование будем объединять реквизиты субъектов в группы. Поскольку может быть задано несколько групп реквизитов, то проверку выполняем по реквизитам каждой из групп.

Данный подход позволяет достаточно эффективно отыскивать потенциальных дублёров и поддерживать справочник субъектов в актуальном состоянии. Однако в связи с тем, что размеры сравниваемых реквизитов невелики (в среднем 5-15 символов), временные затраты на анализ строк также получаются достаточно малыми, и здесь на первое место выходит стоимость дисковых операций. На поиск и считывание необходимых сведений о субъекте расходуется времени гораздо больше, чем непосредственно на сравнение. По результатам тестирования для больших справочников субъектов (50000–150000 записей) процедура проверки нуждается в оптимизации, так как время проверки в таких случаях получается неприемлемо большим.

Список литературы

  1. Райордан, Р. Основы реляционных баз данных: Пер. с англ./ Р Райордан. – М.: Издательско-торговый дом «Русская Редакция», 2001. – 384 с.: ил.
  2. Graham, S. String Search [Электронный ресурс] / Stephen A. Graham. – UK. School of Electronic Engineering Science University College of North Wales, 1992. – Режим доступа: http://read.at/infoscope/string_search/Stephen-92/index.html