Содержание к диссертации
Введение
1. Обзор. методы хранения и управления данными. методы неточного сопоставления строк. методы принятия решений 12
1.1. Методы хранения и управления данными 12
1.1.1. Базы данных 12
1.1.2. Хранилища данных 14
1Л.З. Очистка данных 18
1.2. Методы неточного сопоставления строк 23
1.2.1. Расстояние редактирования 25
1.2.2. Нахождение наибольшей общей подпоследовательности 28
1.2.3. Метод п-грамм 31
1.2.4. Trie-деревья 33
1.2.5. Хеширование 33
1.3. Методы принятия решений 35
1.3.1. Таблицы принятия решений 36
1.3.2. Деревья принятия решений 37
1.3.3. Фреймовые модели 39
1.3.4. Нейросетевые методы 42
1.3.5. Теория нечетких множеств 46
1.3.6. Генетические алгоритмы 49
1.3.7. Структурные методы анализа 51
1.4. Выводы 52
2. Разработка математических моделей и методов идентификации объектов нечисловой природы на примере юридических лиц 54
2.1. Алгоритмы сравнения реквизитов объектов 54
2.1.1. Символьные поля 54
2.1.2. Сложные символьные поля 56
2.1.2.1. Наименование объекта 56
2.1.2.2. Почтовый адрес 58
2.1.3. Числовые поля 64
2.2. Алгоритмы сравнения объектов 65
2.2.1. Таблицы принятия решений 65
2.2.2. Деревья принятия решений 67
2.2.3. Структурный метод принятия решений 70
2.3. Выводы 73
3. Применение алгоритмов идентификации юридических лиц в задаче построения хранилища данных 75
3.1. Выбор класса задач 75
3.2. Построение хранилища данных Управления Федеральной службы налоговой полиции по Саратовской области 76
3.2.1. Особенности предметной области. Выбор СУБД 77
3.2.2. Входной поток и Метапоток хранилища данных 78
3.2.3. Восходящий поток 81
3.2.4. Выходной поток 83
3.2.5. Выбор реквизитов для принятия решения 86
3.2.6. Построение дерева принятия решений 89
3.2.7. Структурный метод принятия решений 90
3.3. Выводы 92
4. Реализация, эксперименты, внедрение 93
4.1. Оценки эффективности алгоритма.
Сравнение с традиционными методами 93
4.2. Описание программной реализации алгоритма идентификации объектов нечисловой природы 96
4.3. Технические характеристики 100
4.4. Выводы 101
Заключение 102
Литература
- Методы неточного сопоставления строк
- Сложные символьные поля
- Особенности предметной области. Выбор СУБД
- Описание программной реализации алгоритма идентификации объектов нечисловой природы
Введение к работе
Хранилище данных - это предметно-ориентированный, интегрированный, привязанный ко времени и неизменяемый набор данных, предназначенный для поддержки принятия решений. Впервые концепция информационных систем с хранилищем данных была предложена специалистами фирмы IBM [43]. Чрезвычайная сложность и, как следствие, высокая стоимость таких систем до середины 90-х годов XX века препятствовали их коммерческому внедрению. Основной вклад в становление технологии создания хранилищ данных внесли Барри Девлин, Уильям Инмон и Ральф Кимбал. В России разработкой и внедрением хранилищ данных занимается ряд компаний, таких как Intersoft Lab, Data Integration Software, РДТЕХ, Tomik, Трисофт, РЕЛЭКС и Аналитические технологии.
Наполнение хранилищ, как правило, осуществляется информацией из нескольких оперативных источников данных [18]. Наибольшую популярность приобрели базы данных. К сожалению, не все организации могут позволить себе разработку или впоследствии поддержку качественных систем хранения и обработки информации. Человеческий фактор и частичное отсутствие контроля данных на вводе либо неадекватная модель проверки информации приводят к появлению искажений в данных. Опечатки и пропуски присутствуют практически во всех реквизитах сохраненных объектов, в том числе и в идентификационных наборах. Основной причиной появления искажений является человеческий фактор на этапе ввода информации в базы данных. Особо остро проблема «загрязненных» данных препятствует созданию хранилища, когда отсутствует возможность повлиять на структуру и качество имеющейся информации. Такая ситуация типична, например, в правоохранительных органах, по роду деятельности которых необходима информация из многих разнообразных источников.
Управление федеральной службы налоговой полиции Российской Федерации по Саратовской области (УФСНП РФ по Саратовской области) регулярно получало БД от сторонних организаций. Для эффективного использования имеющейся информации необходимо было разработать хранилище данных с удобной системой поиска и представления информации. При построении хранилища данных, остро встала проблема наличия опечаток и пропусков данных в имеющихся БД [71, 73, 74, 75, 76, 78]. Разработка методов идентификации юридических лиц при построении информационного хранилища является предметом данной диссертационной работы.
Построение информационных хранилищ, то есть интегрирование имеющихся баз данных с учетом возможных искажений, является трудной задачей. По статистике, при создании хранилищ, этап подготовки и загрузки информации занимает от 60 до 80% рабочего времени. Наиболее трудный этап формирования хранилища - очистка данных. При этом наиболее технологически сложная подзадача - идентификация объектов, имеющих опечатки, пропуски и другие искажения.
Механизмы идентификации объектов в продуктах коммерческих фирм реализованы с использованием различного математического аппарата. Как правило, разработчики раскрывают алгоритмы, которые реализованы в программных продуктах. Однако по некоторым публикациям можно получить представление об используемых методах. Например, ООО «Аналитические технологии» в многомерном хранилище данных Deductor Warehouse использует нейронные сети. Компания РЕЛЭКС в основу идентификации в объектно-ориентированном хранилище данных «НЕВОД» использовала элементы нечеткой логики. В большинстве программного обеспечения алгоритмы идентификации используют аппарат обучения с учителем и различные справочники, которые формируются в процессе обучения. Такой подход имеет несколько недостатков. Во-первых, значительно различающиеся источники информации требуют персонального дополнительного обучения сети либо изменения
функций принадлежности, что является весьма сложной и самостоятельной задачей. Во-вторых, идентификация, основанная на опорных справочниках, предъявляет высокие требования к их содержимому и влечет ложные выводы при наличии ошибок. Третьим недостатком является высокая трудоемкость при заполнении справочников и адаптации системы.
В БД задачи идентификации традиционно решаются следующими путями:
выделяют один или несколько реквизитов, так называемые идентифицирующие наборы (ИН), однозначно определяющих запись в базе данных;
вводят в состав реквизитов поле, имеющее априори уникальные значения, называемые первичным ключом;
в некоторых программных комплексах используются комбинации ИН, которые последовательно проверяются до нахождения соответствия значений в совокупности реквизитов.
Все вышеперечисленные методы оперируют точным равенством сравниваемых полей и бессильны при наличии ошибок, пропусков в данных или при несоответствии состава ИН, что приводит к следующим недостаткам:
невозможности построения целостного хранилища данных,
низкой достоверности информации в полученном хранилище, что проявляется в ложном слиянии информации от разных объектов, или присутствии нескольких записей, относящихся к одному и тому же объекту.
Решение поставленной задачи основывается, исходя из следующих соображений:
Объекты реального мира обладают многими описывающими реквизитами, из которых можно выбрать несколько ИН. Наличие ошибок и пропусков в данных априори не позволяет точно идентифицировать все объекты, основываясь на одном реквизите, или на точном равенстве нескольких реквизитов.
Эксперт конкретной предметной области, принимая во внимание особенности этой предметной области, может точно идентифицировать объекты, имеющие опечатки и пропуски в значениях реквизитов.
Разработанный в данной диссертационной работе подход позволяет исключить влияние искаженных данных на идентификацию объектов. В связи с автоматизацией идентификации объектов исключается «человеческий фактор», что существенно повышает достоверность и сокращает время заполнения хранилища данных.
Приведем некоторые задачи, корректное решение которых практически невозможно без разработанных в данной диссертационной работе методов идентификации:
построение хранилища данных из нескольких БД;
аналитический поиск некоторых ситуаций по двум и более БД;
устранение дублирования объектов в рамках одной БД;
нахождение ошибочных/противоречивых объектов в БД;
разработка информационно-поисковой системы.
Целью диссертационной работы является разработка математических моделей и методов очистки данных и идентификации объектов нечисловой природы в хранилищах данных.
Для достижения указанной цели в работе решены задачи:
выбор и обоснование метода неточного сравнения строк;
разработан классификатор строковых реквизитов с получением как числовых, так и эвристических результатов сравнения;
построена математическая модель реквизита, имеющего сложную внутреннюю семантическую структуру;
выбор и обоснование методов принятия решения об идентификации объектов по совокупности результатов сравнений реквизитов;
проверка метода идентификации на задаче интеграции различных баз данных в единое информационное пространство.
Научная новизна:
-получены результаты анализа эффективности основных методов нечислового сопоставления реквизитов объектов, что позволило предложить эври-
стический подход для комплексного решения задачи идентификации объектов нечисловой природы в хранилищах данных;
-создан классификатор строковых данных, синтезирующий результат близости реквизитов, устойчивый к искажениям, как в символьной, так и в числовой форме, отличающийся прозрачной схемой построения и не требующий эталонных наборов информации;
-разработана математическая модель реквизита, имеющего сложную, жестко не заданную семантическую структуру, которая основана на фреймах, что позволило повысить точность сравнения подобных реквизитов;
-создан метод идентификации, основанный на совокупности символьных результатов работы классификаторов по сравнению реквизитов, моделях представления знаниях экспертов о предметной области и возможных ситуациях в форме деревьев принятия решений;
-разработана геометрическая модель различий объектов, используемая для идентификации объектов нечисловой природы, и набор соответствующих ей адаптивных алгоритмов для автоматического выбора состава и порядка сравнения наиболее информативных реквизитов.
Практическую значимость имеют:
универсальный программный комплекс, для СУБД ORACLE, предназначенный для проведения идентификации нечисловых объектов, таких как; юридические и физические лица, документы;
хранилище данных, содержащее информацию из нескольких баз данных контролирующих органов Саратовской области, полученный с применением разработанных математических моделей и методов идентификации объектов;
процедура корректной выборки информации по юридическим лицам, присутствующим в двух различных БД по дополнительно наложенным условиям.
На защиту выносятся:
Классификаторы нечисловых реквизитов, в том числе имеющих сложную семантическую структуру на основе математической модели, генерирующие символьный либо числовой результат сравнения.
Метод проверки идентичности двух объектов на основе деревьев принятия решений и совокупности полученных результатов классификаторами по отобранным для идентификации реквизитам.
Математическая модель и метод идентификации нечисловых объектов, инвариантный по отношению к наличию пропусков и опечаток в данных с автоматической адаптацией набора реквизитов для сравнения.
1. Методика внедрения разработанного математического обеспечения при создании хранилища данных на примере Управления Федеральной службы налоговой полиции Российской Федерации по Саратовской области.
Внедрение
Разработанный метод идентификации был успешно применен в Управлении Федеральной службы налоговой полиции Российской Федерации по Саратовской области при решении задачи построения интегрированного банка данных по информации из нескольких БД государственных контрольных органов Саратовской области. Получен акт внедрения разработанных методов.
Апробация работы
Основные теоретические положения и практические результаты работы обсуждались и докладывались на: V молодежной научно-технической конференции «Наукоемкие технологии и интеллектуальные системы 2003» (Москва, 2003), Всероссийской научно-практической конференции «Технологии Интернет - на службу обществу» (Саратов, 2003), XVI Международной научной конференции «Математические методы в технике и технологиях» (Ростов-на-Дону, 2003), Всероссийской научной конференции «Сложные системы. Анализ, моделирование, управление» (Саратов, 2004).
Публикации. Основные положения диссертации отражены в 8 публикациях, в том числе в 1 статье в журнале «Системная интеграция» рекомендованном ВАК. Без соавторов опубликовано 2 работы.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Изложена на 136 страницах, содержит 18 рисунков, 8 таблиц, список используемых источников включает 147 наименований.
Первая глава посвящена обзору методов хранения данных, методов сопоставления строк и методов принятия решения, необходимых для построения алгоритма идентификации.
Вторая глава посвящена разработке методов идентификации юридических лиц. Рассмотрены основные, наиболее часто встречающиеся и необходимые для процесса идентификации ЮЛ реквизиты. Особое внимание уделено алгоритмам, разработанным для обработки сложно структурированных реквизитов, таких как наименование предприятия, почтовый адрес. Предлагается подход к обработке числовых данных.
Третья глава описывает применение разработанного метода идентификации ЮЛ при построении хранилища данных в УФСНП РФ по Саратовской области. Изложены особенности предметной области. Проведен выбор реквизитов используемых для принятия решения об идентичности объектов. Приведен алгоритм идентификации ЮЛ.
В четвертой главе описана реализация метода, проведено сравнение полученного алгоритма с традиционными, используемыми для решения подобных задач.
Заключение содержит основные выводы и рекомендации, являющиеся результатом проведенных исследований.
Методы неточного сопоставления строк
Анализ реально-сложившейся ситуации в БД показывает, что значения одного из реквизитов в идентичных записях разных БД могут иметь различные значения [71, 73, 75, 76]. Например, наименование предприятия «Саратов скиеАвиаЛинии» может иметь значение: «Саравиалинии», «Саравиа», «Авиа линии - Саратов», «Аэрофлот», «Маравиалинии» - ошибка в 1 знаке, «Саравиалниии» - транспозиция соседних символов и тому подобное. Интуитивно понятно, что все эти названия относятся к одному и тому же юридическому лицу, однако с точки зрения строк - они абсолютно разные. Анализируя БД одного из медицинских учреждений г. Саратова были обнаружены записи, относящиеся к одному пациенту, но значения поля ФИО которого со временем претерпевали изменения: Ахмедов Байрам Юсуф-Оглы Ахмедов Байрам Юсуф Оглы Ахмедов Байрам Юсуф оглы Ахмедов БеЙрам Юсуфович
Из приведенных примеров видно, что могут встречаться правильные значения, опечатки, синонимы, сокращения, устаревшие значения, а также ложные сведения. Причины появления несоответствий в данных схематично приведены на рисунках 1.2 и 1.3.
Принимая во внимание тот факт, что практически вся информация, содержащаяся в БД введена оператором в ЭВМ вручную, путем нажатия на клавиши клавиатуры в определенном порядке, числовые поля необходимо рассматривать как строковые. Например, «125» и «15». Если эти два номера рассматривать как числа, разница между ними очень большая, а если с точки зрения строк - во втором числе отсутствует всего один символ. Таким образом, большинство случаев относится к обработке строковых данных.
Существует множество методов анализа [24,25, 26,27,28,29,31,32,53] и неточного сопоставления строк [95, 109, 114, 130, 139, 144], Наиболее популярным из методов неточного сопоставления строк являются методы вычисления расстояния редактирования [8]. В общем, под расстоянием редактирования понимается метрика, численно вычисляющая стоимость преобразования одной строки в другую. Различают несколько операций, каждая из которых может иметь собственную стоимость: вставка символа, удаление, замена и транспозиция соседних символов.
Расстояние Хемминга [99] между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Расстояние Хемминга эквивалентно минимальной цене преобразования первой строки во вторую в случае, когда разрешена только операция замены с единичным весом.
В случае строк разной длины, первоначально производится выравнивание строк путем добавления пустых символов е. Если придать операциям вставке, удалению и замене равный вес, минимальная общая цена преобразования будет метрикой Левенштейна [110].
Расширив метрику Левенштейна операцией транспозиции соседних символов, также имеющую цену равную единице, получаем метрику, которая оптимально подходит для сравнения пар слов, введенных оператором ЭВМ.
Определение 1.1. Алфавитом А - {А, щ, аъ ... сс }, \А\ = 2, Х 1 будем называть любое конечное множество символов, содержащее пробельный символ А.
Определение 1.2. Словом или строкой w в алфавите А длины п, будем называть последовательность символов алфавита .
Введение пустого символа е позволяет рассматривать слова постоянной длины, так как к слову меньшей длины всегда можно добавить справа нужное количество пустых символов.
Определение 1.3. Выравниванием строк и = щ и2 -ит и v = vj v2 ...v„ длины 1 будем называть пару строк ми v длины 1 max(m, п), где слова и я v получаются из исходных слов и и v в результате добавления пустых символов е таким образом, чтобы в обоих словах и и v не было пустых символов в одинаковых позициях. Пример: и = поле, v = полог. Тогда: и = полее, v полог.
Пусть для любой пары символов а, Р из А и {е} определена положительная стоимость б(а - ft) 0 замены а на р. Введение пустого символа позволяет заменить операции удаления и добавления операциями замены. В частности, замена а— е соответствует удалению а, а е—»р - вставке р.
Сложные символьные поля
При идентификации юридических лиц, товаров, книг и практически любых других объектов, одним из ключевых реквизитов является наименование обрабатываемого объекта. Опишем подробнее предлагаемый метод для обработки данного вида реквизитов на примере неточного сравнения наименований юридических лиц в Российской Федерации.
При регистрации предприятия ему присваивается два имени. Полное и короткое. Например: «Общество открытого типа Орфей» и «ООО Орфей». В общем случае в названии организации присутствует организационно-правовая форма (ОПФ) и непосредственно наименование. Так как не существует жестко заданных правил занесения информации в БД, большинство БД содержат неточную информацию в реквизитах объектов. ОПФ может присутствовать как в сокращенном, так и в полном виде. ОПФ является необходимым составляющим наименования, но вследствие того, что идентификация ЮЛ по одному лишь наименованию невозможна, организационно-правовой формой можно пренебречь. Список слов, которые исключаются из рассмотрения называются стоп-словами, и их состав различен для каждого из реквизитов.
Алгоритм субъективного сравнения символьных полей, не имеющих сложной внутренней структуры можно представить в виде кортежа U, V, S, A, Y, 2 . Где: U ={и,-,/ = 1,и _ множество слов входящих в состав первого реквизита. У - \vj} J Ь т - множество слов входящих в состав второго реквизита. Ъ = \sк і - h _ множество слов входящих в состав множества стоп-слов для данного реквизита. А - оператор вычисляющий субъективное равенство реквизитов. У - пороговое значение расстояния редактирования, при котором строки (слова) считаются похожими, соответственно, если Y = О, похожими будут признаны только посимвольно равные строки. Z - пороговое значение суммы равных и похожих слов, входящих в сравниваемые строки, при котором они будут признаны похожими. Вычленим стоп-слова из рассмотрения
Количество похожих слов будет равно Р = 11Щ О- где (2.5) 7=liv=l E(u v J = q "у. 1, если О edist(u ,v w) Y, О, иначе, где под edist(u ,v w) подразумевается расстояние редактирования с учетом транспозиции соседних символов с единичным весом (см. п. 1.1.1). Результат субъективного сравнения реквизитов вычисляется по следующей формуле: - ,если r Z, "я",еслиг + p Z, A(U,VtS) = { (2.7) "#",еслиг + р г, "_! ,еслии = 0илиМ = 0. Параметры У, Z задаются оператором или экспертами предметной области на основе анализа представленных данных, или методом подбора. Параметр Z можно рассчитывать автоматически, по формуле: Z = mm (q,w) (2.8)
Однако, практические эксперименты не показали улучшения точности сравнения полей, при автоматическом вычислении значения Z. Лучше вручную подбирать значение, путем проведения ряда экспериментов.
Относительно структуры данных, хорошим примером является почтовый адрес [72, 77]. Чаще всего адрес пишется в виде стоки, типа «г. Саратов, ул. Политехническая, 37». Составляющие адреса априори могут присутствовать в произвольном порядке, что является сложной задачей для автоматической обработки такой информации.
Для того, что бы произвести сравнение двух строк содержащих адресную информацию, сначала необходимо расчленить каждый адрес на состав ляющие, а затем сравнивать между собой только имеющие одинаковую смысловую нагрузку, например, название города с названием города, название улицы с названием улицы. На этом этапе появляется задача распознавания слов входящих в строку к тем или иным реквизитам адреса, например, к названию улицы.
Сделать достаточно хороший синтаксический анализ адресной строки достаточно сложно из-за наличия тесной связи между синтаксисом и семантикой, а также из-за присутствия в текстах русского языка большого количества синтаксически омонимичных конструкций, которые не допускают однозначной интерпретации без привлечения знаний о семантической сочетаемости слов.
На основе анализа различной адресной информации были выделены следующие адресные составляющие (см. рис. 2.1). Такая сложность формы возникла из-за административно - территориального деления России, в состав краев входят автономные области и т.п. Из-за многогранности проблемы ЧФ встречаются случаи, которые не очень хорошо ложатся на предложенную форму, например, операторы добавляют номера телефонов, контактные лица, любые комментарии в свободной форме в конец адресной строки. По большому счету указанная выше форма - это разумный компромисс между сложностью и качеством [50].
Особенности предметной области. Выбор СУБД
Как уже было сказано выше, все имеющиеся БД имели разную структуру и были реализованы на базе различных СУБД: ORACLE, MS SQL Server, MS Access, Paradox, FoxPro 2.6 for DOS, или информация приходила в формате XML, либо в виде текстовых файлов. Для того, что бы иметь возможность использовать полученную информацию интегрировано, в рамках одного окна, то есть с помощью какого то одного ПО, необходимо привести данные к «общему знаменателю», импортировать информацию в хранилище данных и далее работать только с ним. На этом этапе встал выбор СУБД для хранения и обработки информации, а так же ПО для организации доступа к данным с рабочих мест.
В 1996 году были сформулированы требования к СУБД для хранилища данных, опубликованные Red Brick System Inc [124]: - высокая производительность загрузки данных; - возможность обработки данных во время загрузки; - наличие средств управления качеством данных; - высокая производительность запросов; - широкая масштабируемость по размеру БД; - масштабируемость по количеству пользователей; - возможность организации сети хранилищ данных; - наличие средств администрирования хранилища; - поддержка интегрированного многомерного анализа; - расширенный набор функциональных средств запросов. На балансе ФСНП имело СУБД Oracle и ИСУБД CronosPIus. Выбор СУБД сделан в пользу Oracle, которая соответствует наибольшему числу тре бований и обладает самым широким набором языков программирования и средств разработки: PL/SQL, Java, внешние динамические библиотеки (ЛИ).
К сожалению, в ФСНП не было закуплено ни одного программного продукта, реализующего все этапы построения и заполнения хранилища данных. Поэтому пришлось воспользоваться различными программными продуктами, для реализации отдельных операций с хранилищем. Некоторые из них, а именно, методы идентификации объектов и метод построения отсылочных таблиц, были разработаны автором данной диссертационной работы самостоятельно.
Моментальные снимки одной и той же БД, полученные в разные месяцы, зачастую имели не только разные данные, что само по себе естественно, но и измененные метаданные. Поэтому было принято решение каждый временной «срез» данных хранить отдельно. Физически это реализуется в виде отдельной схемы данных в БД, в имени которой были закодированы имя БД и дата создания среза, например GKS_200305. В принципе, при необходимости, можно производить анализ изменения данных внутри одной и той же БД со временем, искать исчезнувшие объекты из БД, которые на заданном промежутке времени должны присутствовать обязательно. Например, сведения о полученных лицензиях или о состоявшихся сделках, или качественный и количественный состав товарных накладных.
Из-за большого количества разнородных источников данных, создавать универсальное ПО, для импорта и интеграции данных нецелесообразно. Поэтому к каждому конкретному случаю необходим индивидуальный подход. Для каждой БД создается новая схема, и стандартными методами импортируются в нее данные. В некоторых случаях данные необходимо предварительно конвертировать в тот формат, который проще импортировать в Oracle.
Хранилище данных представляет собой в БД Oracle схему под названием IDB, которая представляет собой ряд таблиц, содержавших в себе реквизиты всех известных объектов и отсылочную информацию в другие схемы данных. В общем случае структура ИБД выглядит следующим образом:
-Таблица, содержащая основные реквизиты объектов, в данном случае таблица FIRM (см. таб. 3.1).
-Другие вспомогательные таблицы, предназначенные для хранения дополнительных атрибутов объектов, например видов деятельности, расчетных счетов в банках, номеров телефонов и так далее. Автор не видит смысла в описании данных таблиц, так как это напрямую не связано с алгоритмами идентификации объектов и интеграции баз данных.
-Для каждой интегрируемой БД создается своя отсылочная таблица (см. таб. 3.2). Создавать для каждой БД свою отсылочную таблицу удобно, так как
Описание программной реализации алгоритма идентификации объектов нечисловой природы
Получаемые из сторонних организаций БД имели кардинально отличающиеся друг от друга структуры. Зачастую копии одной и той же БД, полученные в разное время, имели различия в составе таблиц и полей. В связи с этим, написание универсального клиентского ПО, для импорта и интеграции БД в единое информационное пространство представляет трудно реализуемую задачу, эффективность использования которого не дает значительных преимуществ. Поэтому решено было создать пакет процедур и функций, который реализовывал бы все задуманные алгоритмы и был прост в использовании. Априори известно, что если данные хранятся в СУБД, то и обрабатывать их лучше и быстрее средствами самой СУБД.
СУБД Oracle предлагает разработчикам два встроенных языка программирования PL/SQL и Java, а так же возможность вызова внешних процедур и функций из внешних динамических библиотек. На начало работ по написанию диссертационной работы автор имел опыт программирования на языке PL/SQL и достаточное количество написанных на этом языке пакетов, процедур и функций. Выбор был сделан в пользу языка PL/SQL.
На языке PL/SQL был создан пакет IDB (см. прил. 2), который включает в себя набор процедур и функций для нечеткого сравнения строк, проверки корректности контрольной суммы в ИНН, а так же некоторые средства для отслеживания текущего состояния процесса интеграции. Все функции описаны в спецификации пакета IDB. Для ускорения процесса идентификации, некоторые особо требовательные к процессорному времени процедуры и функции взяты из динамической библиотеки fuzzyapi.dll, реализованной Бойцовым Леонидом на языке C++ и доступной для скачивания из интернета по адресу http://itman.narod.ru/source/fuzzyapi.zip и свободного использования. Использование внешних функций, написанных на языке C++ дало десятикратное увеличение скорости идентификации ЮЛ, по сравнению с аналогичными функциями, написанными на языке PL/SQL. Каждый язык программирования имеет свои особенности и области применения. Необходимо выбирать языки программирования в соответствии с поставленной задачей и необходимыми скоростными характеристиками.
В прил. 1 содержится пример использования пакета IDB для интеграции БД по учету налогоплательщиков в Интегрированный банк данных. Дерево принятия решений реализуется в виде программного кода именно на этом этапе. В комментариях, для более наглядного чтения, указаны номера правил из дерева принятия решений. Нумерация правил произведена слева на право по листьям дерева принятия решений (см. рис.3.4). Часть структуры интегрируемой БД приведена в прил. 3. Описание всей БД занимает несколько десятков листов, поэтому она здесь не представлены в полном объема. В приложении описаны лишь те таблицы, которые непосредственно использовались для идентификации и несколько таблиц, расшифровывающие значения закодированных полей.
Как было отмечено ранее, каждая БД имеет свою, неповторимую окраску качества присутствующих данных. Различные подходы к заполнению реквизитов. Функция LikeStringExt, входящая в состав пакета IDB, реализует субъективный анализ строк, то есть их сравнение. Аргументами данной функции являются собственно две сравниваемые строки, параметры strljn и str2_in, и еще два настроечных параметра max_ed и min_col_slov о которых необходимо упомянуть отдельно.
В целом алгоритм работы функции следующий. Строки разбиваются на слова по пробелам, или знакам препинания. Затем из двух наборов полученных слов удаляются так называемые СТОП - СЛОВА. Эти слова носят вспомогательных характер и смысловой нагрузки, для процесса идентификации объектов, не несут. Для некоторых специфических БД, можно создать персональные таблицы СТОП - СЛОВ, и таким образом отсечь некоторые часто встречающиеся ошибки или лишнюю информацию.
Далее происходит попарное сравнение слов из двух полученных массивов. При этом считается количество равных и количество похожих слов. Слово первого набора, которому найдено похожее или равное во втором наборе, вместе со словом из второго набора исключается из дальнейшего рассмотрения. Вычленение одинаковых и похожих слов из рассмотрения дает ускорение процесса идентификации, что при больших объемах данных имеет критическое значение. Заголовок функции LikeStringExt получающей субъективный результат сравнения двух строк приведен ниже по тексту. Опишем используемые параметры этой функции.
