E-mail:
Пароль:
Забыли пароль?

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

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

XI международная конференция «Информатика: проблемы, методология, технологии – 2011»

Мухин Александр

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

Рассмотрим задачу поиска документов, содержащих заданное слово либо набор слов. Не будем формально определять значение тер-мина «слово», важно лишь то, что оно состоит из заранее определённо-го набора символов (букв). Для представления слова в шаблоне поиска разрешается использовать метасимволы. Символ, соответствующий любой, в том числе пустой, строке в пределах одного слова обозначим «*» (звёздочка). Для любого одиночного символа используется знак вопроса «?». Поисковое выражение может содержать несколько таких шаблонов слов, объединённых посредством логических операций И/ИЛИ/НЕ и операции группировки (скобки). Текстовая информация в документе может быть представлена в различных формах и зачастую хранится в виде, не обеспечивающем быстрый доступ к данным, по-этому извлечение текста, выделение слова и сравнение с шаблоном может оказаться очень долгим. Очевидным решением является использование специального индекса для ускорения поиска.

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

В качестве ключа битового индекса выступает пара «буква»:«позиция буквы в слове», при этом специальный символ «$» соответствует концу слова. Каждому ключу сопоставляется битовый вектор слов, в котором единичный бит означает, что соответствующее слово содержит данную букву на указанной позиции. Например, слову «МИР» соответствуют 4 единичных бита в битовых векторах ключей «М:1», «И:2», «Р:3» и «$:4», в остальных же на этом месте стоит 0 (Рис. 1).

Рис 1. Представление слова МИР с помощью битового индекса

Рассмотрим выражение «МИР AND (*УД OR МА?*)». На Рис. 1 видно, что шаблону «МИР» соответствует единственное слово, получаемое пересечением четырёх БВ: «М:1», «И:2», «Р:3» и «$:4». Напомним, что под пересечением понимается побитовая логическая операция AND. По построению результирующий вектор может содержать не более одного ненулевого бита. Пересечение всего двух БВ «М:1» и «А:2» позволяет вычислить шаблон «МА*». Для получения «МА?*» результат необходимо пересечь с инвертированным БВ «$:3». В данном случае результат может содержать более одного бита, например, шаблону соответствуют слова «МАЙ» и «МАРТ». Поиск слов по шаблону с неопределённым началом оказывается более трудной задачей. Для шаблона «*УД» требуется вычислить («У:1» AND «Д:2» AND «$:3») OR («У:2» AND «Д:3» AND «$:4») OR … Количество операций определяется максимальной длиной N слова в словаре, так как произведение «Д:(n-1)» AND «$:n» образует пустой БВ для всех n больших N.

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

Рис 2. Получение БВ документов, содержащих слово МИР

На заключительном этапе над полученными БВ документов выполняются указанные в поисковом выражении логические операции.

В качестве другого примера рассмотрим применение битовых индексов для обработки числовых данных. В простейшем случае ключом битового индекса для числового массива может служить номер бита в двоичном представлении числа [1]. Пусть имеется массив целых неотрицательных чисел. Тогда ключу N соответствует БВ, у которого бит k совпадает с битом с номером N в двоичном представлении k-го элемента массива. Таким образом, для представления чисел в диапазоне от 0 до (232 - 1) требуется 32 БВ. В англоязычной литературе такой индекс называется bitsliced (BSI).

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

1. A ← 1 (полный БВ), v ← 0
2. A'←A AND B[i]. Если A'=0, то v ← 2v, иначе v ← 2v+1, A←A'

Здесь v – искомый максимум, A – битовый вектор, на послед-нем шаге содержит номера элементов массива со значением v. B[i] – БВ, соответствующий разряду i двоичного представления числа. На первом шаге выполняется инициализация значений. Второй шаг выполняется многократно для i от n до 1, где n – количество БВ. На каждой итерации находится пересечение БВ, полученного на предыдущем шаге, с представлением очередного битового разряда числа. Если пересечение содержит лишь нулевые биты, то очередной бит результата равен нулю. В противном случае бит результата полагаем равным 1, и сохраняем БВ соответствующих элементов массива для использования на следующих итерациях. Помимо описанного алгоритма существуют [2] алгоритмы поиска нескольких наибольших значений.

BSI также может использоваться для расчёта других агрегатных функций. Рассмотрим алгоритм вычисления суммы подмножества элементов массива, содержащего целые 32-битные числа со знаком. Пусть целевое подмножество задано БВ X. Отрицательные числа представлены в дополнительном коде. Тогда битовые векторы B[1]…B[31] содержат разряды числа с младшего по старший соответственно, а B[32] содержит знаковый разряд. Ниже приводится сам алгоритм.

1. S ← – |X AND B[32]| * 232
2. S ← S + |X AND B[n]| * 2n для n от 1 до 31

Символом |Y| обозначается число единичных битов в БВ Y. На каждом шаге алгоритма определяется число единичных битов в пере-сечении БВ X и очередного битового разряда. Полученные величины складываются с определённым весом, причём, знаковый разряд имеет отрицательный вес. Как и в предыдущем примере, существует возможность получения приблизительного результата, если осуществлять суммирование, начиная с более значимых разрядов.

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

Литература:

1. O'Neil, P., Quass, D. Improved Query Performance with Variant Indexes // SIGMOD 1997 – Tucson, USA, ACM Press, 1997
 
2. Rinfret D., O'Neil P., O'Neil E. Bit-sliced index arithmetic // Pro-ceedings of the 2001 ACM SIGMOD international conference on Management of data – ACM New York, 2001 – P. 47-57.

Возврат к списку

ѕрокрутить вверх