УДК 519.683.5

Эффективная индексация текстовых документов с использованием CLB-деревьев
Effective Indexing of Text Documents using CLB-Trees

А. Б. Веретенников
A. B. Veretennikov

Уральский государственный университет им. А. М. Горького
Ural State University

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

Full text search, CLB-Tree, search engines, inverted files.
The problems of search in the large text arrays are considered and solved using the new data structure proposed earlier by author, CLB-Tree. Theoretical estimations of efficiency and results of computer experiments are given.

Введение

На сегодняшний день задачи обработки больших объемов текстов весьма актуальны, поскольку объем информации в сети Internet уже исчисляется терабайтами. Требуется создавать новые эффективные структуры данных для поиска в большом объеме электронных текстов. 
Для решения задач поиска слов или фраз используются инвертированные файлы [1]. Однако инвертированные файлы имеют один существенный недостаток — их сложно обновлять.  В [2, 3] была описана новая структура данных — CLB-дерево, предназначенная для поиска в большом объеме электронных документов, написанных на естественном языке.
Для добавления данных в уже созданный инвертированный файл, как правило, требуется практически перезаписать весь индекс. В отличие от этого, в CLB-дерево можно легко и быстро добавлять новые данные, в чем и заключается его основное достоинство. При этом по скорости поиска CLB-дерево не уступает инвертированным файлам и их аналогам.
В [2, 3] была описана начальная структура CLB-дерева, имевшая ряд недостатков. В данной статье описаны новые алгоритмы, устраняющие недостатки первоначальной структуры и позволившие значительно повысить скорость создания индексов. Приведены теоретические оценки производительности и результаты экспериментов.
Автор использует морфологический анализатор [4]. Для каждой словоформы, известной анализатору, возвращается одна или несколько базовых форм. Словоформы, хранящиеся в словаре анализатора, составляют более 90% всех словоформ в типичных документах.
Под известными словоформами будем понимать словоформы, входящие в словарь анализатора, остальные назовем неизвестными. Будем считать, что неизвестная словоформа является своей базовой формой. Таким образом, каждой словоформе сопоставляется набор ее базовых форм.

Первоначальная структура CLB-дерева

В [2, 3] была описана начальная структура CLB-дерева.  Для каждой базовой формы слова создается цепочка кластеров, состоящая из блоков фиксированного размера K, каждый из которых хранит в тебе ссылку на следующий блок цепочки. Каждая базовая форма каждой словоформы текста сохранялась в B-дереве [5] вместе с указателем на первый кластер цепочки. В цепочке кластеров для данной базовой формы слова сохраняется информация обо всех вхождения данной базовой формы в текстах.
В качестве примера информации о вхождении можно рассмотреть номер файла и позицию соответствующей словоформы в файле. Позицией в документе для словоформы может быть в данном случае отступ от начала файла в байтах или порядковый номер словоформы в файле.
Для базовой формы известного слова в оперативной памяти хранится последний кластер соответствующей цепочки, добавление информации об этой базовой форме слова производится в этот кластер. Когда кластер заполняется, он записывается на диск.
Подобная структура обладает недостаточной производительностью, проблемы и их решение описываются далее в данной работе.

Структура CLB-дерева

Каждой базовой форме слова соответствует некоторая цепочка блоков, которые назовем кластерами. В этой цепочке содержится описание всех вхождений данной базовой формы во всех документах. Каждый кластер имеет фиксированный размер K. Каждая цепочка кластеров описывается небольшой структурой-указателем.
CLB-дерево состоит из следующих компонентов:
1.	Таблица указателей для базовых форм известных словоформ.
2.	Словарь неизвестных словоформ – B-дерево, хранящее неизвестные словоформы и указатели для них.
3.	Файл с цепочками кластеров.
Указатели для базовых форм известных словоформ хранятся в таблице – массиве, находящейся в оперативной памяти. Базовые формы неизвестных словоформ и указатели для них хранятся в B-дереве, оно расположено во внешней памяти и разбито на страницы фиксированного размера H.
Кластеры объединяются в блоки кластеров. Кластеры в блоке располагаются последовательно. Максимальная длина блока BLOCK_L является числом степени 2. Последний кластер в блоке хранит в себе указатель на первый кластер следующего блока, если текущий блок не последний. Все блоки, кроме последнего, имеют длину BLOCK_L.
Для многих базовых форм слов объем информации, который следует хранить в цепочке, мал  (меньше половины K).  Для этого случая существует отдельный список кластеров. Каждый из таких кластеров делится на определенное количество равных частей, и для конкретной базовой формы слова используется только одна из этих частей. В этом случае мы считаем, что цепочка кластера состоит из соответствующей части указанного кластера. Остальные части могут использоваться другими базовыми формами слов, для которых также имеется малый объем информации.
Поиск словоформы и извлечение информации о ней:
1.	Создается пустой список указателей
2.	Если словоформа известна, то морфологический анализатор выдает список номеров ее базовых форм. Каждый номер соответствует ячейке таблицы для базовых форм известных словоформ. Из этой ячейки, если она не пуста, извлекается указатель и добавляется в список указателей.
3.	Если это неизвестная словоформа, то она ищется в B-дереве и, если она там есть, возвращается ее указатель и добавляется в список указателей.
4.	Для каждого указателя из списка определяется цепочка кластеров, и считываются все данные из нее. 
Это позволяет реализовать различные алгоритмы поиска. По сути, с точки зрения поиска CLB-дерево предлагает те же возможности, которые есть у инвертированных файлов.
При добавлении информации о слове в индекс запись производится в последний кластер цепочки. Для быстродействия в значительной мере используется анализ морфологии. Различных базовых форм гораздо меньше, чем самих словоформ. Мы можем держать в памяти по одному кластеру для каждой цепочки, соответствующей базовой форме известного слова. Для повышения быстродействия используется алгоритм вставки пакета словоформ в B-дерево, подробно описанный в [2].

Рис 1. Структура CLB дерева.

Создание индекса

Описанная в [2] структура позволяет использовать только кластеры небольшого размера (в [2] — 512 байт), т. к. нужно хранить в оперативной памяти столько кластеров, сколько базовых форм известных слов. Малый размер кластера приводит к большому числу дисковых операций. Увеличение размера кластера требует большого объема оперативной памяти.
Выход в том, чтобы разделить все базовые формы слов на группы, и записывать группы по отдельности. Определяем число K_GROUPS – количество групп, исходя из размера доступной оперативной памяти. Пусть K_FORMS – количество базовых форм известных слов (на данный момент около 200000), тогда:
1.	число кластеров в кэше GROUP_SIZE = объем кэша / K.
2.	K_GROUPS = K_FORMS / GROUP_SIZE, с округлением в большую сторону.
Будем использовать кэш и для неизвестных словоформ. Задаем число U_GROUPS – число групп для неизвестных словоформ. Номер группы здесь определим с помощью хеш-функции HASH, которая, например, суммирует все коды символов словоформы и делит сумму на U_GROUPS.
Всего групп GROUPS = K_GROUPS + U_GROUPS. Введем GROUPS временных файлов. Первые K_GROUPS файлов для известных словоформ, остальные для неизвестных словоформ, нумерация идет от нуля.
При чтении текстов информация о словах в текстах сохраняется во временных файлах. Информация для каждой группы базовых форм слов сохраняется в своем временном файле. После завершения чтения каждая группа обрабатывается и сохраняется в индексе отдельно, с использованием своего кэша.

Алгоритм создания индекса
Чтение файлов. Для каждой прочитанной словоформы WORD:
1.	Если это известная словоформа, анализатор возвращает список номеров базовых форм словоформы.
a.	Для каждого номера N
b.	M = N / GROUP_SIZE
c.	В M-й временный файл записывается номер N, и информация о вхождении словоформы.
2.	Если это неизвестная словоформа
a.	M = HASH(WORD)
b.	В (M + K_GROUPS)-й временный файл записывается словоформа и информация о ее вхождении.
После чтения файлов производится запись в индекс в два этапа.  Используются две процедуры.
Процедура InsertRecord применяется при первом добавлении данной базовой формы слова в индекс, создается новая цепочка кластеров. 
Процедура AppendRecord применяется, когда данная базовая форма уже добавлялась в индекс, для нее уже существует цепочка кластеров.

Алгоритм записи в индекс. Первый этап. Запись в индекс информации об известных словоформах.
1.	Для каждого i от 0 до K_GROUPS–1 выполняем шаги 2 – 3.
2.	Для каждого номера формы N из i-го временного файла выполняем 3.
3.	Если N-я ячейка таблицы пуста, то вызов InsertRecord, ее результат записываем в ячейку таблицы, иначе вызов AppendRecord с указателем из ячейки и запись нового значения в ячейку.

Алгоритм записи в индекс. Второй этап. Запись в индекс информации об неизвестных словоформах.
1.	Для каждого i от K_GROUPS до GROUPS–1 выполняем шаги 2 — 4.
2.	Пока все слова из i-го временного файла не прочитаны, выполняем шаги 3 — 4.
3.	Чтение MAX_APPEND слов (или всех слов, если их меньше) и формирование пакета из слов. Число MAX_APPEND  выбирается как можно больше, алгоритм вставки пакета слов в B-дерево описан в [2].
4.	Вставка пакета в B-дерево, в процессе вставки для каждого слова один из двух вариантов: 
a.	если слова нет в B-дереве, то вызов InsertRecord, вставка слова вместе с указателем в B-дерево.
b.	если слово есть в B-дереве, то вызов AppendRecord, обновление указателя в B-дереве.
Вторая проблема, которая усугубляется при увеличении размера кластера: в [2] для каждой базовой формы слова используется по крайней мере один кластер. Это приводит к пустотам в файле с кластерами.
Будем использовать некоторые кластеры для хранения в них информации о нескольких базовых формах. Выберем число PARTS, являющееся степенью 2 и введем массив списков PART_LST из log2PARTS элементов (нумерация от 0). Каждый список хранит в себе номера кластеров. Список с номером i хранит в себе кластеры, разбитые на 2i+1 частей (номер 0 соответствует двум частям, log2PARTS-1 соответствует PARTS  частям). Каждая часть соответствует некоторой отдельной базовой форме слова. В конце кластера выделяем область, назовем ее таблицей частей, для хранения информации о том, какие части кластера заполнены. Размер этой области PARTS/8 байт, с округлением в большую сторону (чтобы хранить PARTS бит). Остальная область кластера делится на равные части. В таких кластерах не хранятся какие-либо указатели на следующие кластеры.
Поскольку запись информации о словах происходит по группам, нужно, чтобы для каждой группы массив PART_LST был свой. Перед шагом 2 в двух вышеописанных алгоритмов необходимо сменить текущий массив PART_LST на тот массив, который соответствует текущей группе слов.
Вводятся списки свободных кластеров FREE, количество этих списков max(log2(BLOCK_L),1), нумерация от 0. Нулевой список хранит номера единичных свободных кластеров, i-й список хранит номера первого кластера для групп длины 2i подряд расположенных кластеров.

Структура указателя на цепочку кластеров (далее указатель):

FIRST	Номер первого кластера	
LAST	Номер последнего кластера	
NUM	Номер кластера в блоке	
LASTDATA	Размер данных в последнем кластере	
PART	Номер части	
PARTCOUNT	Количество частей в текущем кластере	

Поле NUM – номер кластера в блоке, считается с 1. Если NUM равно 0, то информация о слове храниться в кластере, разделенном на части.

Процедура AllocCluster():
Процедура выдает номер свободного кластера.
Если FREE[0] пуст то добавление кластера в конец файла и N = номер добавленного кластера, иначе получение номера N из списка FREE[0] и удаление его из этого списка. Возвращаем N в качестве результата.

Процедура InsertRecord(Указатель PTR, добавляемые данные Data):
Процедура создает цепочку кластеров и помещает в нее некоторую информацию о найденной форме слова. Процедура заполняет передаваемый ей указатель на создаваемую цепочку кластеров. В скобках после названия процедуры описаны ее аргументы.
1.	NEWSIZE = <Размер Data>
2.	Если NEWSIZE больше чем размер частей у кластеров, имеющих 2 части (что маловероятно), то переход на шаг 2.1, иначе на шаг 3
2.1.	N = AllocCluster()
2.2.	Запись Data в кластер N, PTR.FIRST = N, PTR.LAST = N, PTR.NUM=1,  переход на шаг 13.
3.	Определяем, на сколько частей должен делиться кластер, чтобы размер одной части был больше или равен NEWSIZE, в переменную PARTCOUNT помещаем количество частей.
4.	INDEX = (log2 PARTCOUNT) –1
5.	Если PART_LST[INDEX] пуст, переход на шаг 5.1 иначе на шаг 6
5.1.	N = AllocCluster()
5.2.	Добавление N в PART_LST[INDEX] и запись в таблицу частей этого кластера нулевых значений для всех частей. Переход на шаг 6.
6.	Получение номера P кластера из PART_LST[INDEX].
7.	PTR.FIRST = P, PTR.NUM = 0
8.	Определение номера PART свободной части по таблице частей кластера P.
9.	PTR.PART = PART, PTR.PARTCOUNT = PARTCOUNT
10.	Запись значения 1 в таблицу частей кластера P для части PART.
11.	Если все части P заполнены, удаляем P из списка PART_LST[INDEX].
12.	Запись Data в кластер P по смещению PART×<размер части>.
13.	PTR.LASTDATA = NEWSIZE.

Процедура AppendRecord(Указатель PTR, добавляемые данные Data):
Процедура добавляет в существующую цепочку кластеров информацию о найденной форме слова.
NEWSIZE = PTR.LASTDATA + <Размер Data>
Если PTR.NUM = 0, значит, информация сейчас храниться в кластере, разбитом на части, выполняем процедуру 1, иначе выполняем процедуру 2, обе процедуры имеют те же параметры что и AppendRecord.

Процедура 1
Данная процедура соответствует добавлению информации в кластер, если на данный момент кластер разделен на части.
1.	Определяем INDEX = (log2PTR.PARTCOUNT)-1
2.	Если NEWSIZE  меньше или равен чем <размер части>, то переход на шаг 2.1, иначе на шаг 3:
2.1.	Добавление Data в кластер PTR.FIRST по смещению PTR.PART×<размер части>+PTR.LASTDATA, переход на шаг 12.
3.	Читаем информацию о слове, хранящуюся в кластере в промежуточный буфер BUFFER
4.	Устанавливаем значение 0 в таблице частей кластера PTR.FIRST освобождая часть.
5.	Если раньше все части кластера были заполнены, то есть сейчас свободна одна часть, добавляем PTR.FIRST  в PART_LST[INDEX].
6.	Если все части кластера свободны, удаляем его из PART_LST[INDEX] и помещаем его в FREE[0].
7.	Если NEWSIZE больше чем размер частей у кластеров, имеющих 2 части, то переход на шаг 8, иначе на шаг 7.1
7.1.	Определяем, на сколько частей должен делиться кластер, чтобы размер одной части был больше или равен NEWSIZE, в переменную PARTCOUNT помещаем количество частей.
7.2.	INDEX = (log2 PARTCOUNT) –1
7.3.	Если список PART_LST[INDEX] не пуст, то переход на шаг 7.4 иначе на шаг 7.3.1
7.3.1.	N = AllocCluster()
7.3.2.	Добавление N в PART_LST[INDEX] и запись в таблицу частей этого кластера нулевых значений для всех частей.
7.3.3.	Переход на шаг 7.4.
7.4.	Получение номера кластера P из PART_LST[INDEX].
7.5.	Определение номера PART свободной части по таблице частей кластера P.
7.6.	Запись значения 1 в таблицу частей кластера P для части PART.
7.7.	Если все части P заполнены, удаляем P из PART_LST[INDEX].
7.8.	PTR.PART=PART, PTR.PARTCOUNT=PARTCOUNT, PTR.FIRST=P.
7.9.	Запись данных из буфера BUFFER в кластер P.
7.10.	Добавление Data в кластер P.
7.11.	Переход на шаг 12.
8.	N = AllocCluster().
9.	Запись данных из буфера BUFFER в кластер N.
10.	Добавление Data в кластер N.
11.	PTR.FIRST = N, PTR.LAST = N, PTR.NUM = 1.
12.	PTR.LASTDATA = NEWSIZE.

Процедура 2
Эта процедура обеспечивает добавление информации в цепочку кластеров, когда кластеры используются уже целиком для одной цепочки.
1.	K' – Размер данных в кластере. Если NUM = BLOCK_L то K' = K – <размер указателя на кластер>, иначе K' = K, т. к., если кластер является последним кластером в блоке, имеющим длину BLOCK_L, то в кластере сохраняем указатель на первый кластер следующего блока.
2.	Если NEWSIZE ≤ K' то добавление новой информации в текущий кластер PTR.LAST, устанавливаем PTR.LASTDATA = NEWSIZE, выход.
3.	NEWSIZE = NEWSIZE – K', LASTSIZE = <Размер добавляемых данных> – NEWSIZE. Запись первых LASTSIZE байт Data в кластер PTR.LAST.
4.	Если PTR.NUM = BLOCK_L, переходим на шаг 4.1 иначе на шаг 4.2.
4.1.	Добавляем в конец файла BLOCK_L кластеров, N устанавливаем на первый из них, далее эти кластеры будут зарезервированы для этой цепочки. PTR.LAST= N. PTR.NUM = 1. Переходим на шаг 6.
4.2.	Если PTR.NUM – является степенью 2, а также в цепочке меньше BLOCK_L кластеров, то переходим на шаг 4.2.1, иначе: N = PTR.LAST+1,  PTR.LAST = N и переходим на шаг 5.
4.2.1.	Если PTR.NUM не равен BLOCK_L / 2 то переходим на шаг 4.2.2, иначе на шаг 4.2.4.
4.2.2.	 i = log2 (PTR.NUM×2)
4.2.3.	Если в списке FREE[i] есть элемент, извлекаем его из списка и помещаем в N, иначе добавляем PTR.NUM×2 кластеров в конец файла и устанавливаем N на первый из добавленных кластеров, далее добавленные кластеры будут принадлежать текущей цепочке кластеров. Переходим на шаг 4.3.
4.2.4.	Добавляем в конец файла BLOCK_L кластеров, N устанавливаем на первый из них, далее эти кластеры будут зарезервированы для этой цепочки. Переходим на шаг 4.3.
4.3.	Читаем PTR.NUM кластеров в промежуточный буфер TEMP, начиная с кластера PTR.FIRST.
4.4.	PTR.FIRST = N
4.5.	Запись буфера TEMP в PTR.NUM кластеров, начиная с кластера PTR.FIRST.
4.6.	PTR.LAST = N + PTR.NUM.
5.	PTR.NUM = PTR.NUM+1.
6.	PTR.LASTDATA = NEWSIZE.
7.	Добавление оставшихся NEWSIZE байт Data в кластер PTR.LAST.

Теоретическое обоснование производительности

Пусть d – доля известных слов в текстах, R – текущее количество слов в CLB-дереве. Вследствие описанной организации CLB-дерева справедливы следующие утверждения.

Теорема 1.  Вставка N слов в CLB-дерево потребует O(d∙N/K + (1-d)∙N∙(1+ logH((1-d)∙(R+N)))) обращений к внешней памяти.
Доказательство теоремы следует из описанного выше алгоритма индексирования. Первое слагаемое определяется вставкой известных слов, второе – неизвестных слов. Значение logH((1-d)∙(R+N)) – это высота B-дерева. Вставка каждого неизвестного слова требует O(1) обращений к внешней памяти для записи в цепочку кластеров и O(logH((1-d)∙(R+N))) для записи в B-дерево. Эта теорема показывает, что в CLB-дерево можно легко добавлять новые данные.

Теорема 2.  Поиск набора слов из N-элементов в CLB-дереве потребует
O(N∙(logH((1-d)∙R) + occ/K)) обращений к внешней памяти (здесь occ – количество вхождений данных слов в текстах).
Здесь O(N∙logH((1-d)∙R)) – столько обращений к внешней памяти требуется для чтения информации из B-дерева для неизвестных слов, которые могут быть среди искомых слов. Это слагаемое мало и на практике его можно не учитывать. Основное время занимает O(occ/K) обращений к внешней памяти, для чтения информации обо всех вхождениях словоформы в текстах.
Следовательно, поиск с помощью CLB-дерева имеет такую же эффективность, как и с помощью инвертированных файлов.

Для данных теорем автор имеет доказательства, но их подробное изложение выходит за рамки данной статьи.

Результаты экспериментов

Автором был проведен эксперимент создания CLB-дерева.
Эксперимент проводился на компьютере: процессор Intel Сore 2 Duo  2,66 ГГц, оперативная память 2 Гб, Microsoft Windows 2008.
Использовались два CLB-дерева, одно для известных слов, другое для неизвестных слов. Для первого были взяты параметры: H = 4 Кб, K = 128 Кб, размер кэша 512 Мб, для второго: H = 4 Кб, K = 16 Кб, размер кэша 512 Мб.
Для сравнения производительности эксперименты проводились также с инвертированными файлами.
1. Эксперимент создания индекса. Общий размер документов: 86 Гб, известных слов 90%. Все файлы представляли собой обычный текст.
CLB-дерево: время 4 часа, 2 минуты, из этого время чтения файлов (и записи временных файлов для различных групп слов) составляет 2 часа 30 минут, запись индекса 1 час 32 минуты, объем индекса 56 Гб.
Инвертированный файл: время 20 часов, объем индекса 108 Гб.
2. Добавление небольшого файла в созданный в результате предыдущего эксперимента индекс. Размер файла 700 Кб.
CLB-дерево: время 8 минут, 28 секунд.
Инвертированный файл: время 2 часа, 48 минут.
3. Добавление большого объема данных в созданный в результате предыдущего эксперимента индекс. Добавлялось 20 Гб документов (20 Гб текста).
CLB-дерево: время 1 час 59 минут.
Инвертированный файл: время 8 часов, 24 минуты.
Эксперименты показывают значительное превосходство по скорости добавления данных, особенно небольшого размера, в CLB-дерево по сравнению с инвертированными файлами.
Были проведены эксперименты поиска различных слов и словосочетаний. Скорости поиска с помощью CLB-дерева и инвертированного файла примерно одинаковы.

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

1.	Prywes N. S., Gray H. J. The organization of a Multilist-type associative memory. IEEE Trans. on Communication and Electronics, 1963, 68, 488-492.
2.	Веретенников А. Б., Лукач Ю. С. Еще один способ индексации больших массивов текстов. Известия Уральского государственного университета. Серия "Компьютерные науки", 2006, № 43. c. 103-122.
3.	Веретенников А. Б., Лукач Ю. С. CLB-деревья: новый способ индексации больших массивов текстов. Международная алгебраическая конференция: К 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина. Тез. докл. Екатеринбург. Изд-во Урал. ун-та, 2005, с. 173-175.
4.	Лукач Ю. С. Быстрый морфологический анализ флективных языков. Международная алгебраическая конференция: К 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина. Тез. докл. Екатеринбург. Изд-во Урал. ун-та, 2005, с. 182-183.
5.	Bayer R., McCreight E. Organization and maintenance of large ordered indexes. Acta Informatica, 1972, 1, 3, 173-189.