Е. В. СИЗИКОВ

Московский авиационный институт (государственный технический университет)

ОРГАНИЗАЦИЯ ИНВЕРТИРОВАННЫХ СИГНАТУРНЫХ ФАЙЛОВ С ПОМОЩЬЮ АЛГОРИТМА

БИТОВЫХ СКАЧКОВ

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

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

Инвертированный файл состоит из словаря – упорядоченного набора уникальных слов индексируемого текстового массива и множества ссылок на сами документы. Таким образом, для каждого слова определяется список документов, в котором это слово может быть найдено. Кроме того, существуют специализированные методы сжатия инвертированных файлов позволяющие вести поиск почти без потерь в скорости: алгоритм Голомба, унарное кодирование, методы гамма-Елиаса, дельта-Елиаса и др. Ситуация заметно улучшается в случае использования методов сжатия, размер индекса относительно объема текстов уменьшается и обычно соответствует 10-20%. К достоинствам инвертированного файла традиционно относят высокую скорость обработки и простоту реализации, недостаток – конечный размер индекса. Однако для запросов включающих в себя большое число терминов, схема инвертированных файлов может оказаться недостаточно эффективной.

Альтернативно используются сигнатурные файлы. Сигнатура – битовый вектор длины, равной числу слов словаря, ставится в соответствие каждому документу. Каждый бит вектора означает наличие или отсутствие термина в документе. Таким образом, для нахождения документов содержащих искомое слово требуется просмотреть все сигнатуры и отметить те из них, для которых соответствующий бит, отличен от нуля. Как правило, сигнатуры хранятся в упакованном виде, при этом могут использоваться различные методы упаковки разреженных матриц, арифметическое кодирование или варианты метода Лемпела-Зива. Однако упаковка сигнатур, при уменьшении размера индекса (около 20-40% от объема индексируемых текстовых данных), только негативно сказывается на общей производительности.

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

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

За счет применяемого алгоритма упаковки сигнатур индексная структура имеет размер 3-5% от объема индексируемого текста, что в среднем меньше, чем в других известных методах. Кроме того, даже в случае сильного изменения состава словаря поисковых терминов, в отличие от метода сигнатурных файлов, обеспечивается необходимые возможности для оперативного добавления новых документов без переформирования индекса.

Список литературы

1.  Hugh E. Williams and J. Zobel, Compressing Integers for Fast File Access // Computer Journal. Volume 42. Issue 03. pp. 193-201.

2.  Zobel J., Moffat A., Ramamohanarao K. Inverted files versus signature files for text indexing // Collaborative Information Technology Research Institute, Departments of Computer Science, RMIT and The University of Melbourne, Australia. feb 1995, Technical report No TR-95-5.

3.  Tousidou E., Bozanis P., Manolopoulos Y. Signature–based structures for objects with set-valued attributes, 2000.

4.  Gonnet G. H., Baeza-Yates R. Text algorithms // Handbook of Algorithms and Data Structures in Pascal and C: 2nd edition. Addison-Wesley, Wokingham UK, 1997. Chapter 7.
pp. 251-88.

5.  Makinen V., Novarro G., Ukkonen E. Algorithms for Transposition Invariant String Matching (Extended Abstract), 2002.