Проблемы

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

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

  • дублирование атрибутов, имеющих жестко заданную структуру (формат) содержания;
  • дублирование атрибутов, не имеющих жестко заданной структуры (формата) содержания, т. е. слабоструктурированных.

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

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

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

Решения

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

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

  1. Производится вычисление некоторого показателя соответствия («похожести») двух символьных строк, например дистанции (расстояния) или релевантности.
  2. Данный показатель приводится к относительной шкале соответствия в интервале от 0 до 1 (0 — полное несовпадение, 1 — полное совпадение). В дальнейшем эта шкала легко может быть приведена к процентному виду, удобному для восприятия человеком.
  3. Экспериментальным путем для тестового массива данных определяется нижний порог автоматической обработки (Па), за которым количество ошибок распознавания дубликатов становится неприемлемым. Определяется также нижний порог ручной обработки (Пр), за которым поиск выдает практически одни ошибки.
  4. Па может быть использован для дальнейшей уточняющей обработки дубликатов в автоматическом режиме, оставляя найденные элементы со значениями соответ-ствия ниже Па, но выше Пр для обработки человеком.

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

  • непосредственный ввод пользователями;
  • импорт данных из внешних источников.

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

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

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

Возможные реализации

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

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

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

Например, если у вас имеется база данных на 50 тыс. абонентов, средняя длина ФИО включает 50 символов, то мощность множества подстрок будет составлять примерно 50 000 * (50 — 3) = 2 350 000 элементов. При этом количество уникальных элементов, т. е. элементов словаря, которое напрямую зависит от длины подстроки N, будет существенно ниже (экспериментально была получена разница примерно на два порядка), и, следовательно, вам будет затруднительно организовать быстрый поиск по такому множеству, используя стандартные средства реляционной СУБД в виде индексов. Избирательность (selectivity) такого индекса будет мала, что может привести к отказу от его использования оптимизатором запросов. Решением данной проблемы при большом количестве данных для словаря является увеличение длины N. 

В качестве нестрогого доказательства применимости данного решения можно рассмотреть функцию максимального количества элементов словаря (уникальных элементов множества) в зависимости от размеров подстрок и алфавита. Эта функция будет давать верхнее значение в предположении, что символы алфавита размещены по N равномерным распределением по строкам. Чем меньше равномерность, тем меньше будет количество уникальных элементов. На практике равномерность при небольших N далека от идеальной, но она увеличивается с ростом N, и в предельном случае, когда N равно длине строки, при отсутствии точных дублей строк мы получаем полностью равномерное распределение. Пусть N — длина подстроки, m — количество символов в алфавите, включая пробел и знаки препинания. Тогда количество возможных размещений с повторениями из m символов алфавита по N вычисляется в соответствии с известной формулой комбинаторики и равно mN. Это значение и будет самой верхней и грубой оценкой (пренебрегаем еще и тем, что далеко не все размещения встречаются и допустимы в языке словаря) количества уникальных элементов словаря. Таким образом, при увеличении N количество уникальных элементов растет, как степенная функция.

Рассмотрим более подробно пример реализации системы распознавания дубликатов для списка фирм с использованием СУБД MS SQL 2000. Пусть фирма характеризуется следующим набором атрибутов:

Для распознавания дубликатов на первом этапе мы будем использовать строку, составленную из всех перечисленных атрибутов, общая длина которой может достигать 260 символов. Предположим, что в базе данных имеется 20 000 записей со средней длиной строки 150 символов. При таких параметрах выбираем длину подстроки N = 4. Таблицы для хранения списка фирм и словаря будут выглядеть так, как описано в листинге 1.

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

Для первоначального заполнения таблицы множе-ства подстрок CompanyNGrams можно воспользоваться приведенной выше функцией разбиения на грамы следующим образом:

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

Релевантность (R) двух строк S1 и S2 при длине грама (подстроки) N вычисляется по следующей формуле:

R = [NGramMatch (S1, S2) + NGramMatch (S2, S1)] / [NGramCount (S1) + NGramCount (S2)]

NGramCount (S) = [len (S) — N + 1],

где len (S) — длина строки S;

NGramMatch (S1, S2) — сумма совпадений всех подстрок из S1 в строке S2.

Тогда для поиска похожих строк можно использовать следующую функцию, состоящую всего из одного оператора SELECT:

Примеры

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

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

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

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

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

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

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

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

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

Полезные ресурсы

  1. Веб-сайт по алгоритмам нечеткого поиска: http://ru.searchipedia.org/catalog/  
  2. Часто задаваемые вопросы по «мягким» вычислениям: http://faqs.org.ru/progr/common/mild_faq.htm