Способ решения задачи исключения дублирования персональных данных в информационных системах

Размещено на http://www.allbest.ru/

Способ решения задачи исключения дублирования персональных данных в информационных системах

Вахрушев Иван Николаевич, аспирант

Ржеуцкая Светлана Юрьевна, кандидат наук, доцент

Вологодский государственный университет

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

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

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

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

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

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

Здесь вводим понятие «процент совпадения» реквизитов субъектов. Процент совпадения - это процент, которые задается пользователем и определяет, какая точность требуется при сравнении одного реквизита у разных субъектов для того, чтобы полагать эти реквизиты совпадающими (а клиентов, соответственно, дублирующими друг друга). Степень совпадения позволит учесть, что возможны различия (ошибки) в одном и том же реквизите для разных субъектов, например, если оператор при вводе информации о субъекте допустил ошибку.

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

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

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

С точки зрения приложений определение расстояния между словами или текстовыми полями по Левенштейну обладает следующими недостатками:

при перестановке местами слов или частей слов получаются сравнительно большие расстояния;

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

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

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

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

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

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

Для реализации процедуры проверки субъектов на дублирование будем объединять реквизиты субъектов в группы. При этом в одной группе может быть несколько категорий реквизитов: обязательные (О), условные (У) и информационные (И). Информационные реквизиты не проверяются и необходимы для формирования протокола выполнения процедуры. Условные реквизиты являются дополнительными и проверяются только в том случае, если обязательные реквизиты не заданы или совпали не полностью. Например, задана группа реквизитов (табл. 1).

Таблица 1. Параметры проверки субъектов на дублирование

Группа может использоваться для проверки при вводе и редактировании субъектов - юридических лиц. Сначала проверяем по «ИНН+КПП» (проверяем вместе, причем по строгому совпадению на 100%), если вдруг они не совпадают (или не заданы), то проверяем по «ОГРН» и «Названию». При этом возможны следующие ситуации.

Если совпадают (1+2); значит, субъекты - дубли, при этом 3 и 4 даже не сравниваем (совпали все О-реквизиты, У-реквизиты не влияют на результат, их не проверяем, чтобы не тратить время).

Совпадает (1); (2) задан, но не совпадает; тогда проверяем (3) и (4), если совпадают оба, субъекты - дубли, иначе (3 и 4 не совпадают), значит, субъекты - не дубли (совпали не все О-реквизиты, поэтому проверяем все У-реквизиты, и если все У-реквизиты совпадают, то субъекты будут дублями).

Если (1) не совпадает, то (2) не проверяется, а пара (1+2) считается несовпавшим реквизитом, далее - проверяем (3) и (4); если они оба совпадают, то субъект считается дублем.

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

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

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

Солодков, А. Идентификация сложных объектов нечисловой природы в СУБД с наличием ошибок и пропусков данных [Электронный ресурс] / А.Ю. Солодков. - Саратовский государственный технический университет, 2003. Режим доступа: http://iu4.bmstu.ru

Райордан, Р. Основы реляционных баз данных: Пер. с англ./ Р Райордан. - М.: Издательско-торговый дом «Русская Редакция», 2001. - 384 с.: ил.

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

Размещено на Allbest.ru