GetInfo.Ru – Компьютерная библиотека
Последние поступления
Как выбрать систему управления базы данных
Базы данных03/09/14
Этапы загрузки UNIX (в схеме)
Unix27/03/12
Gatewall Antispam: тотальный контроль электронной почты
Спам21/04/11
Мастер-класс: создаем Интернет-магазин (Часть 1)
Обзоры ПО20/04/11
CorelDRAW Graphics Suite X5: Что нового?
Обзоры ПО20/07/10
Добавить статью
Самые читаемые материалы
Мягкие вычисления(45769)
Эволюционные вычисления(31878)
Сортировка и поиск: Рецептурный справочник(30744)
Алгоритмы архивации данных(25059)
Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет(19452)
Всего статей: 793Всего авторов: 364Подразделов: 47Добавлено за сутки: 0
Статьи  СТАТЬИ Форум  ФОРУМ Рейтинг  РЕЙТИНГ Поиск  ПОИСК Контакты  КОНТАКТЫ
» Главная » Алгоритмы » Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет

Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет


Андрей Зайцев
hammer@netclub.ru

Страницы: [ 1 ] [ 2 ] [ 3 ]

Постановка задачи

В ставших уже классическими работах Д. Кнута, Н. Вирта, У. Ахо и других авторов приводится ряд алгоритмов, позволяющих проводить эффективный поиск в текстовых документах. Наиболее известны из них алгоритмы Бойера-Мура (Boyer-Moore) и Кнута-Морриса-Пратта (Knuth-Morris-Pratt). При сравнительно малых затратах на предварительную обработку текста, эти алгоритмы обеспечивают достаточно высокую скорость поиска. Однако их применение при работе в Сети чрезвычайно осложняется необходимостью просматривать в поисках образца множество текстов, число которых может достигать сотен миллионов. При этом затраты времени возрастают линейно с ростом количества обрабатываемых документов.

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

В данной статье рассматривается разработанная автором методика построения поисковых индексов, применяемая для поддержки полнотекстового поиска в массиве документов, обрабатываемых системой КИС ЖКХ РФ.

Используемая методика

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

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

  • обработка отдельного документа и подготовка набора структур, его описывающих;

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

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

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

  • получение целочисленных идентификаторов запрошенных образцов для поиска;

  • получение кодированного множества документов по найденным идентификаторам;

  • извлечение набора идентификаторов документов из данного кодированного множества;

  • просмотр информации, описывающей найденные документы, выделение и сортировка подмножества документов согласно заданным пользователем ограничениям;

  • выдача списка документов по результатам предыдущего шага.

Обзор индексных структур

Общий словарь. Представляет собою бинарное дерево, ставящее в соответствие строковому представлению образца для поиска (лексемы) его уникальный идентификатор. В реализации применяется B-дерево 2-го порядка, позволяющее сократить расходы на балансировку при обновлении словаря. При этом гарантируется, что время поиска образца будет пропорционально log N, где N - объем (мощность) словаря.

Множество масок документов. Таблица, задающая для каждого идентификатора лексемы битовую маску, кодирующую информацию о множестве документов, в которых эта лексема встречается. Эти маски представляют собой последовательности целых чисел (слов), каждое из которых рассматривается в качестве битового массива. Таким образом, множество документов, содержащих некую лексему хранится в виде характеристической функции, так, что каждый ее ненулевой бит указывает на присутствие соответствующего документа во множестве. Схематично данная связь показана на рисунке 1.

Рисунок 1

Для ряда лексем с неравномерной функцией распределения хранимые таким образом маски окажутся слишком разреженными, то есть большое количество слов их составляющих будут содержать только нулевые биты. Знание об этом используется для дополнительной экономии памяти. Для этого хранимые маски дополнительно упаковываются по следующему алгоритму: каждое ненулевое слово исходной маски сохраняется и соответствующий ему бит дескриптора выставляется в 1. Каждое нулевое слово удаляется, а соответствующий ему бит выставляется в 0. Данное преобразование проиллюстрировано рисунком 2. Следует отметить тот факт, что эффективность подобного сжатия обратно пропорциональна длине слова.

Рисунок 2

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

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

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

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

Рисунок 3

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

Тип лексемы. В зависимости от категории, к которой принадлежит документ, лексема может являться обычной либо характеристической. Кроме того, она может иметь особое значение для данного документа. Особость лексемы определяется исходя из ряда соображений, например при оценке мета-описания документа.

Общее описание документа. Кроме информации о наборе лексем для каждого документа хранится также его общее описание, в которое входят: название документа, его автор, дата создания, тип документа и иная информация, определяемая в контексте приложения.

Список соответствия идентификаторов документов их содержимому. Исходные документы хранятся на диске в некотором виде (MS Word, HTML, XML, Plain TEXT, RTF, etc) и могут быть представлены пользователю для просмотра и закачивания на диск согласно списку идентификаторов, полученному на предыдущем шаге.

Применение

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

Для иллюстрации сказанного ниже публикуется ряд соображений, использованных автором при построении поискового модуля системы КИС ЖКХ РФ. Приводимая в приложениях информация не претендует на полноту и однозначность, однако дает возможность читателю представить некоторые особенности реализации методики.

 
13.01.2003
Версия для печати Версия для печати Запомнить ссылку Запомнить ссылку
Ваша оценка:  1   2   3   4   5     

 О проектеПерепечаткаАвторамПартнерыО нас пишут
Наверх
©2003—2007. GETINFO.RU. ВСЕ ПРАВА ЗАЩИЩЕНЫ.