Анализ поисковых алгоритмов при решении задач идентификации объектов в слабоструктурированных базах данных

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

Ключевые слова 

База данных; расстояние Хемминга; сравнение строк; расстояние Левенштейна; метод расширенной выборки; сигнатурный алгоритм; метод N-gram; алгоритм последовательного перебора; деревья поиска; поиск данных.

The identification problems in semistructured databases are depicted in the article, results of comparative analyses are presented.

Keyword

database; Hamming distance; string matching; Levenstein distance;   method of advanced sample; signature algorithm;   N-gram method; exhaustive search algorithm;  searching tree; data search.

Проблемы идентификации объектов в базах данных

Эффективность управления современным бизнесом основана на возможности получения управленческим персоналом всесторонней информации по всем направлениям деятельности компании. При этом важно установление контроля над растущими потоками информации, ускорение процесса их обработки, обобщения и анализа. Необходимость постоянно обеспечивать всех участников процесса управления достоверной, целостной, непротиворечивой и актуальной информацией определяет ключевую задачу сегодняшнего дня в области повышения эффективности управления – внедрение современных информационных технологий в систему управления предприятием. Для многих компаний информация является основным активом. Потеря важной информации может привести к существенным финансовым потерям или под угрозой оказывается весь бизнес. Особенно сильно страдают печатные и электронные СМИ, библиотеки и архивы. Основную часть рабочих материалов таких организаций  составляет неструктурированная информация (бумажные документы, фотоматериалы, видео, аудиозаписи, электронные документы в различных форматах). Управлять информацией и обеспечивать её сохранность в указанном виде является крайне непростой задачей.

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

Управление дисковым пространством, увеличение емкости систем хранения и рост их производительности, миграция данных с устаревших хранилищ на новые – все эти, и многие другие задачи приходится постоянно решать компаниям, использующим системы хранения. Современный подход к операциям с данными позволяет изменить существующее положение вещей. Многие типы данных можно рассматривать не как набор чисел и символов, которыми оперируют вычислительные системы, а в виде объектов, с которыми оперирует пользователь: финансовые документы, почтовые сообщения, техническая документация, фотографии, видеоролики, звуковые записи, сканированные документы и т.д.

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

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

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

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

·                    Орфографические ошибки (опечатки) – ошибки, возникающие при вводе информации.

·                    Отсутствие данных – происходят по причине отсутствия у оператора соответст­вующих данных при вводе информации. Оператор может пропустить ввод неизвестных ему данных.

·                    Фиктивные значения – значения, введенные оператором, но не имеющие смысла. Наиболее часто  такая проблема встречается в полях, обязательных для заполнения, когда при отсутствии реальных данных оператор вынужден вводить бессмысленные данные. Например: номер социального страхования 999999999, или возраст клиента 99, или почтовый индекс 99999. Проблема усугубляется, если существует вероятность появления реальных данных, которые могут быть приняты за фиктивные.

·                    Логически неверные данные (в поле "Город" находится значение "Россия").

·                    Закодированные значения – сокращенная запись или кодировка реальных данных в одной ячейке таблицы.

2.                  Потери оплачиваемого времени сотрудников на непродуктивную деятельность. В том или ином виде данный вид потерь встречается в любой организации и может достигать, например, у менеджеров среднего звена более 50% рабочего времени, у менеджеров низовой категории до 80%.

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

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

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

Нечеткий поиск целесообразно применять при поиске слов с опечатками, а также в тех случаях, когда возникают сомнения в правильном написании – персональных данных (Ф.И.О.), наименования юридического лица (компании, организации), адресных данных, реквизитов документов и т.п. Алгоритмы, используемые при реализации нечеткого поиска, основаны на особой системе ассоциативного доступа к словам, содержащимся в текстовом индексе полнотекстового хранилища документов. В качестве единиц поиска используются цепочки составляющих слово букв. Для ускорения поиска предварительно создается специальный индекс, содержащий фрагменты слов со ссылками на слова, в которых эти фрагменты встретились. Алгоритм нечеткого поиска позволяет быстро отобрать все слова, фрагменты которых совпадают с фрагментами слова в запросе, лежащие в заданной окрестности допустимых искажений. Задавая размер этой окрестности (процент отличающихся фрагментов и допустимые смещения их позиций в слове), можно легко регулировать точность и полноту поиска – отбирать слова по степени близости к запросу. Скорость поиска пропорциональна логарифму от числа индексируемых слов и составляет менее одной секунды при индексе в несколько миллионов слов (такой полнотекстовый индекс соответствует нескольким гигабайтам полнотекстовых документов).

С помощью нечеткого поиска возможно решение следующих прикладных задач:

1.                Полная идентификация субъекта или объекта при наличии искажений информации в базе данных или в поисковых запросах.

2.                Устранение дубликатов записей при поступлении в БД из множественных источников со слабоструктурированной информацией.

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

Обзор алгоритмов поиска

1.     Расстояние между строками

Пусть a, b - некоторые строки – последовательности символов алфавита S длин m и n, и соответственно, задан набор операций, преобразующих данные строки:

-                  вставка символа;

-                  удаление символа;

-                  замена одного символа на другой.

Каждой операции присвоена стоимость. Существует последовательность операций, результатом применения которой к строке абудет являться строка b. Такая последовательность не является единственной. Стоимость последовательности определяется как суммарная стоимость входящих в нее операций. Тогда последовательность операций минимальной стоимости определяет метрику на множестве строк.

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

Еще одна метрика равна минимальной цене преобразования при условии, что разрешено использовать только операции удаления и вставки. Это эквивалентно присваиванию замене цены 2, а удалению и вставке цены 1, потому что операцию замены можно сымитировать парой удаление-вставка. Описанная метрика называется расстоянием редактирования.

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

2.                 Метод расширения выборки.

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

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

Метод отлично работает со словарями натурального языка, размер которых относительно не велик. Для русского языка такой словарь на сегодняшний день составляет порядка 40 000 слов [9], что на несколько порядков меньше, например списка клиентов среднего российского банка.

3.                 Сигнатурные алгоритмы

Основой сигнатурных алгоритмов является буквенное сэмплирование. В случае хеширования по сигнатуре сэмпл преобразуется в сигнатурный вектор, который можно рассматривать, как запись числа в двоичном представлении. Таким образом, хеш-функция H(a) однозначно определяет преобразование F(w) строки в целое число. Функция F(w) является хеш-функцией и может быть использована для процедуры индексации словаря. К примеру, выберем несколько слов и запишем их сигнатуру простейшей хеш-функцией (табл. 1). Удаление или добавление одной буквы слова приведет к изменению не более одного бита сигнатуры. При этом может не измениться ни один бит сигнатуры, в том случае, если удаленная буква встречается в слове более одного раза (для представленной в примере хэш-функции). Если заменить один символ, то изменится не более двух битов сигнатуры. При изменении двух бит сигнатуры, один бит обнуляется, а другой становится равным единице.

Таблица 1. Запись сигнатуры слов хеш-функцией

Из [2] следует, что для выборки всех слов, отличающихся от искомого на одну операцию редактирования, требуется прочесть не более: 1 + m + m2/4 списков, где m размер сигнатуры. Общее число списков равно 2m . Если m достаточно велико, то количество списков, проверяемых в процессе поиска, будет значительно меньше общего числа списков хеш-таблицы. Метод хеширования по сигнатуре обладает следующими достоинствами:

·  Позволяет осуществлять с высокой скоростью поиск на точное равенство и поиск, допускающий одну-две «ошибки» в задании поискового запроса.

·  При правильном выборе параметров объем индекса не более чем на 10-20% превышает размер файла, содержащего список терминов словаря.

·  Отличается простотой реализации.

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

4.     Метод N-gram

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

Рассматривают две основных задачи, которые нужно решить, используя алгоритм N-грамм:

1) Способ разбиения на граммы. Например, для последовательности символов "good morning" 3-грамм (иногда именуемые "триграмм") являются буквенные сочетания: "goo", "ood", "od ", "d m", " mo", "mor" и так далее. Аналогичным способом можно построить биграмы, 4-грамы и т.д. Следовательно, перед разбиением необходимо определить порядок грамм наиболее выгодный для применения на конкретной выборке, а также следует ли учитывать начало и конец слова. От этого будет зависеть скорость, точность и объем хранения грамм. Некоторые строки полезно предварительной очистить от пробелов. Пунктуация также обычно удаляется препроцессором.

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

Необходимо также отметить основной недостаток метода N-грамм – относительно большой объем дискового пространства, необходимый для хранения грам. Однако данный недостаток компенсируется точностью поиска, что отмечено в работах [3,4,5,6,7].

5.                 Алгоритмы последовательного перебора.

Простейшее решение задачи перебора состоит в последовательном сравнении, начиная с t(1) и p(1), символов слов T и P до тех пор, пока не будет обнаружено равенство или неравенство сравниваемых символов. В последнем случае следует вернуться к началу сравнения и, сдвинувшись на один символ по тексту (теперь это будет t(2)), и повторить процедуру.

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

Данный алгоритм требует выполнения не менее n-m+1 сравнений и работает достаточно медленно. Вместе с тем он относительно прост для реализации и позволяет проводить поиск с использованием шаблона любой длины.

Точный поиск по алгоритму Бойера-Мура. Известно несколько модификаций исходного алгоритма. Наиболее известны два из них: алгоритм Бойера-Мура (Boyer-Moore) и алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt). На практике при решении задач точного поиска в большинстве случаев алгоритм Бойера-Мура работает быстрее.

Точный поиск по алгоритму СДВИГ-И (SHIFT-AND).Алгоритм СДВИГ-И показал хорошую скорость поиска и достаточно просто программируется. Кроме того, данный алгоритм обладает уникальной особенностью: он может быть легко модифицирован для задач нечеткого (приблизительного) поиска.

6.                 Деревья поиска.

Trie-деревья представляют собой структуру, поиск в которой основан на представлении термина последовательностью символов. В отличие от обычных сбалансированных деревьев, в trie-дереве все строки, имеющие общее начало, располагаются в одном поддереве. Каждое ребро помечено некоторой строкой. Терминальным вершинам ("листьям") соответствуют слова списка. Корнем дерева является вершина, которой соответствует "пустое" слово длины ноль. Из нее выходит столько дуг, сколько символов встречается на первой позиции в терминах словаря (самое большее - число символов в алфавите). Вершины второго уровня соответствуют символам второй позиции, и так далее. Каждая конечная вершина - термин, символы которого записаны в единственном пути из корневой вершины в эту конечную.

В случае неудачи поиск возвращает термин словаря, совпадающий с искомым образцом в наибольшем числе начальных символов. Обычно Trie -деревья используются для поиска по подстроке, но их можно использовать, и весьма эффективно, для поиска по сходству.

Достоинства

·   эффективно хранят локализованные в пространстве группы объектов

·   если дерево сбалансировано, то обеспечивает быстрый поиск в худшем случае

·   вставка/удаление одной точки не требует существенной перестройки дерева (динамический индекс)

Недостатки

·                    чувствительно к порядку добавляемых данных

·                    данные в листьях могут перекрываться

·                    подходит для точного поиска, при приблизительном поиске возвращает слишком большой набор

Заключение.

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

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

Из наиболее эффективных алгоритмов следует отметить алгоритмы n-грамм, trie-деревьев, а также сигнатурные алгоритмы, которые обеспечивают хорошее соотношение между размером индекса и скоростью поиска. Оценки результатов тестирования алгоритмов по критериям эффективности, скорости и занимаемого дискового пространства представлены в таблице 2. Требования к алгоритмам расположены в порядке убывания их значимости: эффективность – скорость – размер дискового пространства. В столбце Итог кратко резюмированы возможности применения алгоритма к задачам идентификации объектов в слабоструктурированной БД

Таблица 2. Сравнение алгоритмов

Литература

1.                Бойцов Л.М. Классификация и экспериментальное исследование современных алгоритмов нечеткого словарного поиска // Труды 6-ой Всероссийской научной конференции “Электронные библиотеки: перспективные методы и технологии, электронные коллекции” - RCDL2004, Пущино, Россия, 2004.

2.                Бойцов Л.М. Использование хеширования по сигнатуре для поиска по сходству // Прикладная математика и информатика, ВМиК МГУ, № 8, 2001, с. 135-154.

3.                Buckley, J. Solving fuzzy equations in economics and finance // Fuzzy Sets & Systems, 1992, # 48.

4.                Chávez E., Navarro G. Proceedings of the 5th Latin American Symposium on Theoretical Informatics. A Metric Index for Approximate String Matching, pages 181-195, 2002.

5.                Masek U., Peterson M. S. A faster algorithm for computing string-edit distances. In Journal of Computer and System Sciences, volume 20(1), 1980, p. 785-807.

6.                Myers E.W. A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming, In Journal of the ACM (JACM), volume 46(3), 1998, p. 395 – 415.

7.                Ukkonen E. Approximate String Matching with q- Grams and maximal matches. In Theoretical Computer Science, volume 92(1), 1992, p. 191-211.

8.                Wu S., Manber U. Fast Text Searching with Errors. In Communications of the ACM, volume 35 pages 83-91, 1992.

9.                Материалы сайта:  http://www.lingvotech.com/skolkoslov