Как избавиться от дубликатов в базе данных

Разработчик автоматизированных информационных систем (АИС) сталкивается с проблемой управления качеством данных. Строгого определения этому понятию нет, поэтому я воспользуюсь некоей «усредненной» трактовкой: это обеспечение такого состояния информации в хранилище, которое удовлетворяет требованиям пользователя по критериям достоверности, актуальности, логической полноты и непротиворечивости, отсутствия дублирующей информации.

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

В любой АИС можно выделить два основных типа дублирования информации:

В первом случае речь идет о различных кодах по отраслевым, муниципальным, федеральным и международным справочникам и классификаторам, идентификаторах сущностей, используемых в качестве ключевых атрибутов поиска (номера документов, счетов, телефонов, ПИН-коды и т. д.). Во втором случае мы имеем дело с разнообразными именами собственными, используемыми людьми для идентификации: фамилии, названия книг, фильмов, песен, фирм и т. д. Сюда же относятся адреса, содержащие названия улиц, номера строений и т. п., хранимые в одном атрибуте типа строкового поля «Адрес».

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

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

Для проверки дублирования слабоструктурированной информации нам помогут алгоритмы нечеткого поиска, позволяющие находить данные на основании неполного совпадения и оценки их релевантности — количественного критерия схожести. Следует учитывать, что данные алгоритмы не дают 100%-ной гарантии от ошибок, т. е. сохраняется вероятность того, что будут пропущены дублирующие данные или, наоборот, данные будут распознаны как дубликаты, не являясь таковыми. Поэтому для достижения наилучшего результата может быть необходимо участие человека.

Общий принцип применения алгоритмов для поиска дубликатов следующий:

Основными путями внесения и изменения информации в АИС являются:

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

Таким образом, задачу выявления и устранения дубликатов можно разбить на три этапа:

В качестве основы для реализации системы распознавания был выбран метод N-gram, который обеспечивает быстрый поиск на основе словаря грамов (подстрок) и может быть использован на всех этапах. На первом шаге все атрибуты поиска «склеиваются» в одну строку. Например, фамилия, имя и отчество будут обрабатываться как одна строка ФИО. Данный способ формирования строк для сравнения дает недостаточно точный, но быстрый результат при поиске.

На втором этапе результаты поиска этапа 1 уточняются, проходя дополнительную проверку путем вычисления релевантности и расстояний уже для отдельных атрибутов поиска с учетом различных весовых коэффициентов, подбираемых экспериментально. Например, если две строки с ФИО совпали с релевантностью 90%, но при сравнении фамилий получена релевантность 60%, то, несмотря на 100%-ное совпадение имен и отчеств, можно отвергнуть результат первого этапа как ошибочный.

Следует упомянуть о недостатке метода N-gram, который в некоторых случаях может оказаться сущест-венным: большой размер производного множества подстрок (N-grams) относительно количества исходных строк. Так, если N=3, то для каждой строки будет сформировано M = L — N + 1 словарных элементов, где L — длина строки, больше или равная N (при L Примеры

Для реализации подсистемы поиска дубликатов в одной из CRM-систем (CRM — Customer Relationship Management — управление отношениями с клиентами) была использована следующая схема (см. рисунок).

Схема базы данных в системе была выполнена в соответствии с принципом объектно-реляционного подхода, описанного нами ранее в серии статей «Проектирование ядра информационной системы» (см. «Мир ПК», №7, 8, 9/07).

Общий для всех классов предок Object отражается на одноименную таблицу. Связь с потомками (обобщение) и другие типы ассоциаций между классами унифицированы по ключу OID.

Служебные таблицы CompanyNGrams и PersonNGrams хранят соответственно подстроки-грамы объектов классов «Компания» и «Контактное лицо». Таблица ObjDuplicates благодаря унифицированной связи по OID хранит связи между потенциальными дубликатами обоих классов.

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

Разумеется, за универсальность нужно платить. Например, необходимо писать код проверки семантики классов объектов, добавляемых в таблицу дубликатов.

Рассмотренная в примере с фирмами и контактными лицами подсистема будет функционировать в следующем режиме. На первом этапе, при грубом сравнении без учета семантики следующие записи будут распознаны как дубликаты:

Однако и такие вот записи тоже попадут в число «подозрительных»:

Но на втором этапе при анализе с учетом семантики среди «подозрительных» записи из второго примера будут отбракованы вследствие низкой релевантности названий компаний и фамилий.